Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.
$ 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?

share|improve this question
3  
They're the same thing. –  Polynomial Oct 24 '12 at 5:56
add comment

3 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
3  
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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