RSA Security 5.2.2 manual Verifying a Signature, Math

Cryptography Overview

x1 , you will be using regular arithmetic. This is so different from arithmetic in F2m that, for example, x1 + x2 ≠ x1 + x2 . However, if you convert two field elements and perform operations on them that show they are equal after conversion, then they were equal before conversion.

5.Compute s = k–1(e+dr) mod n. Again, you must check that s is nonzero.

The signature for this message is the pair r and s. Notice that, as with DSA, the signature depends on both the message and the private key. This means no one can substitute a different message for the same signature.

Note: The previous equation is merely an outline. For cryptographic purposes, it is necessary to verify that certain numbers are nonzero, or that they satisfy other conditions. Crypto-C makes the appropriate verifications when it generates your key pair.

Verifying a Signature

When a message is received, the recipient can verify the signature using the received signature values and the signer’s public key, Q. Because the pair (r,s) that has been received may not actually be a valid signature pair, it is customary to call the received pair (r’,s’) instead.

To verify a signature:

1.First verify that r’ and s’ are between 1 and n-1. If they are not, the output is invalid.

2.Digest the received message using SHA1. This yields a 20-byte (160-bit) digest, e.

3.Compute c = (s’)-1. Remember, s’ is an integer mod n, so its inverse is also an integer mod n.

4.Compute u1 = ec mod n and u2 = r’c mod n.

5.Compute the elliptic curve point (x1,y1) = u1P +u2Q.

6.Convert x1 to an integer, x1 . See Step 5 on page 74 for details.

7.Compute v = x1 mod n

If v = r’, the signature is verified. If they are different, the signature is invalid.

The Math

The ECDSA algorithm depends in part on the fact that if r = r’ mod n, then rP = r’P. (See “The Point P and its Order” on page 69.)

7 4 R S A B S A F E C r y p t o - C D e v e l o p e r ’s G u i d e