Digital Signature Algorithm

From Free net encyclopedia

Alternate meanings for the abbreviation DSA: See DSA (disambiguation)

The Digital Signature Algorithm (DSA) is a United States Federal Government standard for digital signatures. It was proposed by the National Institute of Standards and Technology (NIST) in August 1991 for use in their Digital Signature Standard (DSS), specified in FIPS 186 [1], adopted in 1993. A minor revision was issued in 1996 as FIPS 186-1 [2], and the standard was expanded further in 2000 as FIPS 186-2 [3].

DSA is covered by Template:US patent, filed July 26, 1991, and attributed to David W. Kravitz, a former NSA employee. This patent was given to "The United States of America as represented by the Secretary of Commerce, Washington, D.C." and the NIST has made this patent available world-wide royalty-free. [4] Dr. Claus P. Schnorr claims that his Template:US patent covers DSA; this claim is disputed [5] [6]

Contents 1 Key generation 2 Signing 3 Verifying 4 Correctness of the algorithm 5 See also 6 External links

Key generation

• Choose a 160-bit prime q.
• Choose an L-bit prime p, such that p=qz+1 for some integer z and such that 512 ≤ L ≤ 1024 and L is divisible by 64.
  Note: FIPS-186-2, change notice 1 specifies that L should only assume the value 1024, and the forthcoming FIPS 186-3 (described, e.g., in SP 800-57) uses SHA-224, SHA-256, SHA-384, and SHA-512 as a hash function, q of size 224, 256, 384, and 512 bits, with L equal to 2048, 3072, 7680, and 15360, respectively.
• Choose h, where 1 < h < p − 1 such that g = h^z mod p > 1.
• Choose x by some random method, where 0 < x < q.
• Calculate y = g^x mod p.
• Public key is (p, q, g, y). Private key is x.

Note that (p, q, g) can be shared between different users of the system, if desired.

Signing

• Generate a random per message value k where 0 < k < q (this is known as a nonce)
• Calculate r = (g^k mod p) mod q
• Calculate s = (k^-1(SHA-1(m) + x*r)) mod q, where SHA-1(m) is the SHA-1 hash function applied to the message m
• Recalculate the signature in the unlikely case that r=0 or s=0
• The signature is (r,s)

Verifying

• Reject the signature if either 0<r<q or 0<s<q is not satisfied.
• Calculate w = (s)^-1 mod q
• Calculate u1 = (SHA-1(m)*w) mod q
• Calculate u2 = (r*w) mod q
• Calculate v = ((g^u1*y^u2) mod p) mod q
• The signature is valid if v = r

DSA is similar to the ElGamal signature scheme.

Correctness of the algorithm

The signature scheme is correct in the sense that the verifier will always accept genuine signatures. This can be shown as follows:

From g = h^z mod p follows g^q ≡ h^qz ≡ h^p-1 ≡ 1 (mod p) by Fermat's little theorem. Since g>1 and q is prime it follows that g has order q.

The signer computes

<math>s=k^{-1}(\mbox{SHA-1}(m)+xr) \mod{q}.</math>

Thus

<math>

\begin{matrix} k & \equiv & \mbox{SHA-1}(m)s^{-1}+xrs^{-1}\\

 & \equiv & \mbox{SHA-1}(m)w + xrw \pmod{q}.\\

\end{matrix} </math>

Since g has order q we have

<math>

\begin{matrix} g^k & \equiv & g^{{\rm SHA-1}(m)w}g^{xrw}\\

   & \equiv & g^{{\rm SHA-1}(m)w}y^{rw}\\
   & \equiv & g^{u1}y^{u2} \pmod{p}.\\

\end{matrix} </math>

Finally, the correctness of DSA follows from

<math>r=(g^k \mod p) \mod q = (g^{u1}y^{u2} \mod p) \mod q = v.</math>

See also

• Elliptic Curve DSA

External links

• FIPS-186, the first version of the official DSA specification.
• FIPS-186, change notice No.1, the first change notice to the first version of the specification.
• FIPS-186-1, the first revision to the official DSA specification.
• FIPS-186-2, the second revision to the official DSA specification (including the first change notice to this revision).
• Recomendation for Key Management -- Part 1: general, NIST Special Publication 800-57, p. 62–63

Template:Public-key cryptographyde:Digital Signature Algorithm es:DSA fr:Digital Signature Algorithm pl:Digital Signature Algorithm