Digital Signature Algorithm

The Digital Signature Algorithm (DSA) is a public-key cryptosystem and Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular exponentiation and the discrete logarithm problem. In a digital signature system, there is a keypair involved, consisting of a private and a public key. In this system a signing entity that declared their public key can generate a signature using their private key, and a verifier can assert the source if it verifies the signature correctly using the declared public key. DSA is a variant of the Schnorr and ElGamal signature schemes.

The National Institute of Standards and Technology (NIST) proposed DSA for use in their Digital Signature Standard (DSS) in 1991, and adopted it as FIPS 186 in 1994. Five revisions to the initial specification have been released. The last standard, however, removed NIST's approval for DSA signature generation.

U.S. patent 4,995,082 (also now expired) covered DSA; this claim is disputed.

In 1993, Dave Banisar managed to get confirmation, via a FOIA request, that the DSA algorithm wasn't been designed by the NIST, but by the NSA.

In February 2023, NIST released FIPS 186-5, which deprecates DSA for generating new signatures but allows it to be used to verify pre-existing signatures.

OpenSSH announced that DSA was going to be removed in 2025. The support was entirely dropped in version 10.0.

The DSA algorithm involves four operations: key generation (which creates the key pair), key distribution, signing and signature verification.

Key generation has two phases. The first phase is a choice of algorithm parameters which may be shared between different users of the system, while the second phase computes a single key pair for one user.

• Choose an approved cryptographic hash function H was always SHA-1, but the stronger SHA-2 hash functions are approved for use in the current DSS. If N bits of the hash output are used.
• Choose a key length N such that L and q.
• Choose an p−1 is a multiple of {2…p−2}.
• Compute h. Commonly q, {1…q−1}.
• Compute y is the public key.

  2. Key distribution

  edit

  The signer should publish the public key m is signed as follows:

  • Choose an integer r:=(gkmodp)modq. In the unlikely case that s:=(k−1(H(m)+xr))modq. In the unlikely case that (r,s)

    The calculation of r is the most computationally expensive part of the signing operation, but it may be computed before the message is known. Calculating the modular inverse (r,s) is a valid signature for a message 0<s<q.

  • Compute u2:=r⋅wmodq.
  • Compute g=h(p−1)/q mod p, it follows that q is prime, s=k−1(H(m)+xr)modq

    Thus

    q we have

    k are critical. It is so critical that violating any one of those three requirements can reveal the entire private key to an attacker. Using the same value twice (even while keeping x.

    This issue affects both DSA and Elliptic Curve Digital Signature Algorithm (ECDSA) – in December 2010, the group fail0verflow announced the recovery of the ECDSA private key used by Sony to sign software for the PlayStation 3 game console. The attack was made possible because Sony failed to generate a new random k is different for each k is chosen in order to subliminally leak information via signatures. For example, an offline private key could be leaked from a perfect offline device that only released innocent-looking signatures.

    Implementations

    edit

    Below is a non-exhaustive list of cryptographic libraries that provide support for DSA:

    • Botan
    • Bouncy Castle
    • cryptlib
    • Crypto++
    • libgcrypt
    • Nettle
    • OpenSSL
    • wolfCrypt
    • GnuTLS

    See also

    edit

    • Modular arithmetic
    • RSA (cryptosystem)
    • ECDSA

    References

    edit

    "FIPS PUB 186: Digital Signature Standard (DSS), 1994-05-19". qcsrc.nist.gov. Archived from the original on 2013-12-13.
    1. 1 2 3 4 5 "FIPS PUB 186-2: Digital Signature Standard (DSS), 2000-01-27" (PDF). csrc.nist.gov.
    2. ↑ "Digital Signature Standard (DSS)". U.S. Department of Commerce. 31 October 2019. Retrieved 21 July 2020.
    3. ↑ Dr. David W. Kravitz Archived January 9, 2013, at the Wayback Machine
    4. ↑ Werner Koch. "DSA and patents"
    5. ↑ "OpenSSH announces DSA-removal timeline [LWN.net]". lwn.net. Retrieved 11 January 2024.
    6. ↑ "NIST Special Publication 800-57" (PDF). csrc.nist.gov. Archived from the original (PDF) on 2014-06-06.
    7. ↑ Bendel, Mike (2010-12-29). "Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access". Exophase.com. Retrieved 2011-01-05.
    8. ↑ "Bouncy Castle Releases Java 1.81 and C# .NET 2.6.1". Bouncycastle. Retrieved 2025-12-15.
    9. ↑ "Cryptographic Functions (The Libgcrypt Reference Manual)". www.gnupg.org. Retrieved 2025-12-15.
    10. ↑ "wolfSSL User Manual | Chapter 10: wolfCrypt Usage Reference | Docs". wolfSSL (in Japanese). Retrieved 2025-12-15.
    11. ↑

    ---

    View original on Wikipedia | Back | FazBrowse Home