DSS

From CryptoDox, The Online Encyclopedia on Cryptography and Information Security

Digital Signature Standard (DSS) is the digital signature algorithm (DSA) developed by the U.S. National Security Agency (NSA) to generate a digital signature for the authentication of electronic documents. DSS was put forth by the National Institute of Standards and Technology (NIST) in 1994, and has become the United States government standard for authentication of electronic documents.

DSA is a pair of large numbers that are computed according to the specified algorithm within parameters that enable the authentication of the signatory, and as a consequence, the integrity of the data attached. Digital signatures are generated through DSA, as well as verified. Signatures are generated in conjunction with the use of a private key; verification takes place in reference to a corresponding public key. Each signatory has their own paired public (assumed to be known to the general public) and private (known only to the user) keys. Because a signature can only be generated by an authorized person using their private key, the corresponding public key can be used by anyone to verify the signature.

A data summary of the information (called a message digest) is created through the use of a hash function specified in FIPS 180). The data summary is used in conjuntion with the DSA algorithm to create the digital signature that is sent with the message. Signature verification involves the use of the same hash function.

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. [1] Dr. Claus P. Schnorr claims that his U.S. Patent 4,995,082 covers DSA; this claim is disputed [2] [3]

Contents 1 Key generation 2 Signing 3 Verifying 4 Correctness of the algorithm 5 See also 6 References 7 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-182-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 1 < 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
• The signature is (r,s)

Verifying

• 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.

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

Thus

Since g has order q we have

Finally, the correctness of DSA follows from

See also

• Elliptic Curve DSA

References

• DSS - Whatis.com Definition
• Digital Signature Algorithm at Wikipedia

External Links

• FIPS 186 - Digital Signature Standard