3.4.1 What are DSA and DSS?
The National Institute of Standards and Technology (NIST) (see Question 6.2.1) published the Digital Signature Algorithm (DSA) in the Digital Signature Standard (DSS), which is a part of the U.S. government's Capstone project (see Question 6.2.3). DSS was selected by NIST, in cooperation with the NSA (see Question 6.2.2), to be the digital authentication standard of the U.S. government. The standard was issued in May 1994.
DSA is based on the discrete logarithm problem (see Question 2.3.7) and is related to signature schemes that were proposed by Schnorr [Sch90] and ElGamal (see Question 3.6.8). While the RSA system can be used for both encryption and digital signatures (see Question 2.2.2) the DSA can only be used to provide digital signatures. For a detailed description of DSA, see [NIS94b] or [NIS92].
In DSA, signature generation is faster than signature verification, whereas with the RSA algorithm, signature verification is very much faster than signature generation (if the public and private exponents, respectively, are chosen for this property, which is the usual case). It might be claimed that it is advantageous for signing to be the faster operation, but since in many applications a piece of digital information is signed once, but verified often, it may well be more advantageous to have faster verification. The tradeoffs and issues involved have been explored by Wiener [Wie98]. There has been work by many authors including Naccache et al. [NMR94] on developing techniques to improve the efficiency of DSA, both for signing and verification.
Although several aspects of DSA have been criticized since its announcement, it is being incorporated into a number of systems and specifications. Initial criticism focused on a few main issues: it lacked the flexibility of the RSA cryptosystem; verification of signatures with DSA was too slow; the existence of a second authentication mechanism was likely to cause hardship to computer hardware and software vendors, who had already standardized on the RSA algorithm; and that the process by which NIST chose DSA was too secretive and arbitrary, with too much influence wielded by the NSA. Other criticisms more related to the security of the scheme were addressed by NIST by modifying the original proposal. A more detailed discussion of the various criticisms can be found in [NIS92], and a detailed response by NIST can be found in [SB93].