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

$ echo "GURbsl4CFPCG83RCZxsEpoRleXicXQhH1OC4Fk77b7EMj2g8aHUhD/L+sm
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 

$ 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                                    

$ 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                                       

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?

  • 4
    They're the same thing. – Polynomial Oct 24 '12 at 5:56

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.

  • 1
    The former RSALabs website has vanished. Wikipedia has a link to PKCS1 at emc.com/collateral/white-papers/… that works as of today, but now that EMC has been bought by Dell it may well disappear again. The IETF versions (RFC 2313, 2437, 3447, 8017) are more stable. – dave_thompson_085 Nov 1 '17 at 0:10

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.

  • 5
    Please do not use the expression "encrypted with the private key". It is just wrong and confusing, because "RSA encryption" does not work like that. – Thomas Pornin Oct 24 '12 at 11:20
  • Fair enough. Editing! :) – Polynomial Oct 24 '12 at 11:36

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.

  • 1
    Of course, the algorithm as presented above is very weak, because it lacks all the parts about padding (which are crucial for security). That's "textbook RSA", also known as "RSA as you should never use it". – Thomas Pornin Oct 24 '12 at 17:23
  • yup "plain RSA", we better use RSA with OAEP. – user827918 Oct 24 '12 at 17:36
  • 1
    Use RSA+OAEP for encryption; it is not specified for signature, which was the question asked. There is a similar but not identical scheme for signature, PSS, but it is (still!) rarely used, because signature type 1 padding did not suffer the actual attacks encryption type 2 did. And even then you left out the ASN.1 encode and decode @Thomas correctly described, which AFAICT don't really matter for security but are vital for interoperation. – dave_thompson_085 May 26 '14 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.