Encyclopedia > Digital Signature Algorithm

Article Content

Digital Signature Algorithm

The Digital Signature Algorithm (DSA) is a United States Federal Government standard for digital signatures. It was proposed by the National Insititute of Standards and Technology[?] (NIST) in August 1991 for use in their Digital Signature Standard (DSS).

Key Generation

• Choose an L-bit prime p, where 512 <= L <= 1024, and L is divisible by 64
• Choose a 160-bit prime q, such that p - 1 = qz, where z is any natural number
• Choose h, where 1 < h < p - 1 such that g = hz mod p > 1
• Choose x by some random method, where 0 < x < q
• Calculate y = gx 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

• Choose a random per message value s (called a nonce), where 1 < s < q
• Calculate s1 = (gs mod p) mod q
• Calculate s2 = (H(m) - s1*x)s-1 mod q, where H(m) is the SHA-1 hash function applied to the message m
• Signature is (s1,s2)

Verifying

• Calculate w = (s2)-1 (mod q)
• Calculate u1 = H(m)*w (mod q)
• Calculate u2 = s1*w (mod q)
• Calculate v = [gu1*yy2 mod p] mod q
• Signature valid if v = s1

DSA is similar to Elgamal discrete logarithm cryptosystem signatures. However, DSA can only be used for signatures, not for encryption, unlike Elgamal or RSA.

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia
 Search over one million articles, find something about almost anything!

Featured Article
 Pot ...     Contents Pot See: Gardening or Garden Cannabis Potentiometer Pol Pot This is a disambiguation page; that is, one that just points ...