Digital Signature Algorithm

From Wikipedia, the free encyclopedia

The Digital Signature Algorithm (DSA) is a United States Federal Government standard or FIPS 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 U.S. Patent 5,231,668 , 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 U.S. Patent 4,995,082 covers DSA; this claim is disputed.

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

[edit] Key generation

Choose a 160-bit prime q.
Choose an L-bit prime p, such that p=qz+1 for some integer z, 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.
Choose h, where 1 < h < p − 1 such that g = h^z mod p > 1. (Recall that z = (p-1) / q.)
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.

The forthcoming FIPS 186-3 (described, e.g., in SP 800-57) uses SHA-224/256/384/512 as the hash function, q of size 224, 256, 384, and 512 bits, and L equal to 2048, 3072, 7680, and 15360, respectively.

There exist efficient algorithms for computing the modular exponentiations h^z mod p and g^x mod p. Most numbers h satisfy the requirement, so the value 2 is commonly used.

[edit] Signing

Generate a random per message value k where 0 < k < q
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)

The extended Euclidean algorithm can be used to compute the modular inverse k^-1 mod q.

[edit] 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.

[edit] 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

$s=k^{-1}(\mbox{SHA-1}(m)+xr) \mod{q}.$

Thus

$\begin{matrix} k & \equiv & \mbox{SHA-1}(m)s^{-1}+xrs^{-1}\\ & \equiv & \mbox{SHA-1}(m)w + xrw \pmod{q}.\\ \end{matrix}$

Since g has order q we have

$\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}$

Finally, the correctness of DSA follows from

$r=(g^k \mod p) \mod q = (g^{u1}y^{u2} \mod p) \mod q = v.$

[edit] See also

Elliptic Curve DSA

[edit] 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

Public-key cryptography v • d • e
Algorithms: Cramer-Shoup \| DH \| DSA \| ECDH \| ECDSA \| EKE \| ElGamal \| GMR \| IES \| Lamport \| MQV \| NTRUEncrypt \| NTRUSign \| Paillier \| Rabin \| Rabin-Williams \| RSA \| Schnorr \| SPEKE \| SRP \| XTR
Theory: Discrete logarithm \| Elliptic curve cryptography \| RSA problem
Standardization: ANS X9F1 \| CRYPTREC \| IEEE P1363 \| NESSIE \| NSA Suite B Misc: Digital signature \| Fingerprint \| PKI \| Web of trust \| Key size
Cryptography v • d • e
History of cryptography \| Cryptanalysis \| Cryptography portal \| Topics in cryptography
Symmetric-key algorithm \| Block cipher \| Stream cipher \| Public-key cryptography \| Cryptographic hash function \| Message authentication code \| Random numbers