|
|
| An Overview/ DSA |
The Digital Signature Algorithm (DSA) was published by the National Institute of Standards and Technology (NIST) in the Digital Signature Standard (DSS), which is a part of the U.S. government’s Capstone project. DSS was selected by NIST, in cooperation with the NSA, to be the digital authentication standard of the U.S. government. The standard was issued on May 19, 1994.
DSA is based on the discrete logarithm problem and derives from cryptosystems proposed by Schnorr and ElGamal. It is for authentication only.
In DSA, signature generation is faster than signature verification, whereas in RSA, signature verification is faster than signature generation (if the public and private exponents, respectively, are chosen for this property, which is the usual case). NIST claims that it is an advantage of DSA that signing is faster, but many people in cryptography think that it is better for verification to be the faster operation. Naccache et al. have developed some techniques to improve the efficiency of DSA, both for signing and verification.
DSA has been criticized by the computer industry since its announcement. Criticism has focused on a few main issues: it lacks key exchange capability; the underlying cryptosystem is too recent and has been subject to too little scrutiny for users to be confident of its strength; verification of signatures with DSA is too slow; the existence of a second authentication standard will cause hardship to computer hardware and software vendors, who have already standardized on RSA; and the process by which NIST chose DSA was too secretive and arbitrary, with too much influence wielded by NSA. Other criticisms were addressed by NIST by modifying the original proposal.
DSA is based on the difficulty of computing discrete logarithm and is based on schemes proposed by Schnorr and ElGamal. The algorithm is generally considered secure when the key size is large enough. DSS was originally proposed by NIST with a fixed 512-bit key size. After much criticism that this is not secure enough especially for long-term security, NIST revised DSS to allow key sizes up to 1024 bits.
The particular form of the discrete logarithm problem used in DSA is to compute discrete logarithms in certain subgroups in the finite field GF(p) for some prime p. The problem was first proposed for cryptographic use in 1989 by Schnorr. Even though no attacks have been reported on this form of the discrete logarithm problem, further analysis is necessary to fully understand the difficulty of the problem. Some researchers warned about the existence of “trapdoor” primes in DSA, which could enable a key to be easily broken. These trapdoor primes are relatively rare, however, and are easily avoided if proper key generation procedures are followed.
