Digital Signature Algorithm
The Digital Signature Algorithm (DSA ) is a standard by the U.S. government for Digital Signatures. He was recommended by the National Institute of Standards and Technology ( NIST) in August 1991 for use in their Digital Signature Standard ( DSS). The DSS contains the DSA (originally the only defined in the DSS algorithm) than other algorithms RSA signature and ECDSA. The DSS was first published in FIPS PUB 186 and last amended in FIPS PUB 186-3.
It was designed to bring the NSA as part of the attempt of the U.S. government, highly secure encryption under control. Component of this strategy was the export ban strong encryption algorithms whose disregard was prosecuted. The DSA is based on the discrete logarithm in finite fields. It is based on the ElGamal signature schemes and is related to the Schnorr signature. The transfer of the DSA on elliptic curves is as ECDSA (Elliptic Curve Digital Signature Algorithm ) and is standardized in ANSI X9.62.
Schnorr accused in the IEEE P1363 standardization of NIST, which developed from her signature process Digital Signature Algorithm infringing his patent. Prior to the development of the DSA negotiations failed with Schnorr to use his signature scheme. The company RSA, which holds an exclusive license to Schnorr signature scheme, could complicate a discrete logarithm method instead of their RSA system as standard with patent litigation, but shied probably an open confrontation with the U.S. government.
- Choose a prime number of length bit, with, with a multiple of 64.
- Choose another prime number of length 160 bit, which is a divisor of.
- Choose for the following applies: and.
- Compute. It follows from the theorem of Lagrange, then that is of order unity in the group.
- Pick a random applies:
Be published (public key), must remain secret because it is the secret key.
Is signed the message; refers to the SHA-1 hash of the message.
- Choose for each message to be signed with a random
- Compute, is to be elected a new
- Compute is so newly started Step 1
The signature of the message is now. It must not be delivered because otherwise and thus the secret signature key can be computed using the extended Euclidean algorithm. For the same reason, it is important that an attacker can not easily guess.
If the signature is composed of and as well as the message. The value is not delivered.
- Check if, and. This is not the case, the signature back as invalid.
- If so, then the signature is valid.