Cryptography Overview
74 RSA BSAFE Crypto-C Developer’s Guide
, you will be using regular arithmetic. This is so different from arithmetic in
F
2
m that, for example, . 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 u
1
= ec mod n and u
2
= r’c mod n.
5. Compute the elliptic curve point (x
1
,y
1
)=u
1
P +u
2
Q.
6. Convert x
1
to an integer,
. See Step 5 on page 74 for details.
7. Compute v = 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.)
x
1
x
1
x
2
+x
1
x
2
+≠
x
1
x
1
