rsa encrypted hash == rsa signature

Question

$ echo -n "1327943823" > test_ok.txt
$ openssl dgst -sha1 -binary -out test_ok.sha1 test_ok.txt

$ echo "GURbsl4CFPCG83RCZxsEpoRleXicXQhH1OC4Fk77b7EMj2g8aHUhD/L+sm
oGSVpuEwup1fmkZBADXwBel8UKsmxgTLRX+vlGgyTr1XPqqHFNjtL33fd5
7NuKBqaJjwSp7D5xVMeVdQtQQbsKuKx5AvOPPyZfdtdyoJw/all1tl4=" > test_ok.sig.64
$ base64 -D -i test_ok.sig.64 -o test_ok.sig

$ openssl rsautl -verify -inkey test.pub -pkcs -pubin -in test_ok.sig -out 
test_ok.sha1.calc

$ hexdump test_ok.sha1
0000000 08 a8 55 9c d4 43 f9 cb ec 9f 04 f4 f2 dc aa 1f
0000010 7f e9 e1 11                                    
0000014

$ hexdump test_ok.sha1.calc
0000000 30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 08
0000010 a8 55 9c d4 43 f9 cb ec 9f 04 f4 f2 dc aa 1f 7f
0000020 e9 e1 11                                       
0000023

test_ok.sha1.calc is an ASN.1 encoded object containing an sha1 hash matching that of test_ok.sha1.

That's all fine and great but...

$ openssl dgst -sha1 -verify test.pub -signature test_ok.sig test_ok.txt

That one matches too.

My question is... how often are the encrypted hash and the signature going to match?

Answer 1

RSA signatures work like that:

• To sign, the signer hashes the input messages, then puts the hash value into an ASN.1 structure (i.e. adds a fixed header to the hash value). The resulting sequence of bytes is then padded (padding details are in the RSA standard) so that the total length matches that of the RSA modulus (an element of the public key). The padded structure is then interpreted as a big integer, with big-endian convention, and the modular exponentiation of RSA is applied, with the private exponent. The result is the signature.

• To verify, the verifier applies the modular exponentiation of RSA with the public exponent, which undoes the last step of the signature generation. If this yields a properly padded ASN.1 structure, and the hash value contained within that structure matches that of the input message, then the verifier declares himself content with it.

We shall note that RSA is a signature algorithm with recovery: when verifying the signature, the verifier not only obtains a boolean result ("valid" or "not valid") but also recovers the hash of the input message itself.

Answer 2

An RSA signature is literally that - a hash of the data, "encrypted" with an RSA key. I say "encrypted" because it's not really being encrypted, but processed in a way that generates a signature. Either way, they should always match.

Answer 3

Here is the algorithm, have a look about this, source.

RSA key pair generation

INPUT: Security parameter l. OUTPUT: RSA public key (n, e) and private key d.

   1. Randomly select two primes p and q of the same bitlength l/2.
   2. Compute n = pq and φ = ( p − 1)(q − 1).
   3. Select an arbitrary integer e with 1 < e < φ and gcd(e, φ) = 1.
   4. Compute the integer d satisfying 1 < d < φ and ed ≡ 1 (mod φ).
   5. Return(n, e, d).

Basic RSA signature generation

INPUT: RSA public key (n, e), RSA private key d, message m. OUTPUT: Signature s.

   1. Compute h = H (m) where H is a hash function.
   2. Compute s = h^d mod n.
   3. Return(s).

Basic RSA signature verification

INPUT: RSA public key (n, e), message m, signature s. OUTPUT: Acceptance or rejection of the signature.

   1. Compute h = H (m).
   2. Compute h` = s^e mod n.
   3. If h = h` then return(“Accept the signature”);
       Else return(“Reject the signature”).

Basic RSA encryption

INPUT: RSA public key (n, e), plaintext m ∈ [0, n − 1]. OUTPUT: Ciphertext c.

   1. Compute c = m^e mod n.
   2. Return(c)

What happen is when signing first generate hash and sign it using private key. to verify this need public key. So this is not a encryption(which need a public key). If you encrypt hash it will be like this h^e mod n. So can this happen h^d mod n = h^e mod n? This can happen because everything happen in finite fields, but we can't guarantee that. Please consider that I am talking this in theoretical.