RSA Security 5.2.2 manual Digital Signature Algorithm DSA

Cryptography Overview

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)/qmod 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 ≡ gx 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:

kinv = k–1mod q

r= (gk mod p) mod q xr = (x · r) mod q

s= [kinv · (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:

sinv = s–1mod q

u1 = (digest · sinv) mod q u2 = (r · sinv) mod q

6 0 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