Cryptography Overview
60 RSA BSAFE Crypto-C Developer’s Guide
Digital Signature Algorithm (DSA)
The Digital Signature Algorithm (DSA) is part of the Digital Signature Standard
(DSS), published by the National Institute of Standards and Technology (NIST), a
division of the US Department of Commerce. It is the digital authentication standard
of the US government. The DSS specifies the Secure Hash Algorithm (SHA1) as the
message digest to use with DSA when generating a digital signature.
To generate a DSA key pair:
1. Find a prime, p, at least 512 bits long.
2. Find a second prime, q, exactly 160 bits long that satisfies the property q|(p–1). q is
called the subprime.
3. Generate a random value, h, the same length as p but less than p.
4. Compute g = h
(p-1)/q
mod p. g is called the base.
5. Generate another random value, x, 160 bits long. x is the private value.
6. Compute the public value: y ≡ g
x
mod p.
Note: The three values p, q, and g (the prime, subprime, and base, respectively) are
called the DSA parameters. The parameters are public and must be generated
before you can sign a message.
To sign a message using DSA:
1. Digest the message using SHA1. This yields a 20-byte (160-bit) digest.
2. Generate a random value, k, 160 bits long and less than q.
3. Find the following values:
k
inv
= k
–1
mod q
r = (g
k
mod p) mod q
xr = (x · r) mod q
s = [k
inv
· (digest + xr)] mod q
4. Output the signature (r,s).
To verify a message:
1. Digest the message using SHA1.
2. From the signature (r,s), compute:
s
inv
= s
–1
mod q
u
1
= (digest · s
inv
) mod q
u
2
= (r · s
inv
) mod q
