Digital Signature Algorithm
The Digital Signature Algorithm is a United States federal standard for digital signatures adopted in FIPS PUB 186 in 1994 that provides non-repudiation and authentication using discrete logarithm modular arithmetic.
Digital Signature Algorithm (DSA) is a standardized asymmetric cryptographic algorithm in computation and algorithms that provides message authentication, data integrity, and non-repudiation across digital communications. Conceived in 1991 by American cryptographer David W. Kravitz (formerly of the National Security Agency) and officially adopted by the United States National Institute of Standards and Technology (NIST) in 1994 as the Digital Signature Standard (DSS) under FIPS PUB 186, DSA introduced an unencumbered public-key signature standard as an alternative to the proprietary RSA cryptosystem.
Within computational complexity theory, DSA's security rests upon the computational intractability of the Discrete Logarithm Problem (DLP) within prime subgroups of the multiplicative group of integers modulo a prime. While the forward modular exponentiation can be calculated in logarithmic time via binary square-and-multiply, computing the secret discrete logarithm from the public key requires sub-exponential time via the index calculus algorithm and the general number field sieve.
Mathematical Architecture and Parameter Selection
The execution of DSA is governed by public domain parameters (p, q, g) shared among a community of users:
- Modulus and Divisor Selection:
- A prime modulus p is selected with a bit length L (originally 512 to 1,024 bits; modernized in FIPS 186-3 to 2,048 or 3,072 bits).
- A prime divisor q is selected with bit length N (such that N = 160 bits for L = 1,024, or N = 256 bits for L = 2,048) such that q divides p โ 1.
- Subgroup Generator Derivation:
- An integer h is chosen such that 1 < h < p โ 1 and g = h(pโ1)/q mod p satisfies g > 1. By construction, g generates a cyclic subgroup of order q modulo p.
Key Pair Generation
To participate in the system, an entity generates a key pair:
- Private Signing Key (x): An integer sampled uniformly at random from the open interval 0 < x < q.
- Public Verification Key (y): Computed by evaluating modular exponentiation in the subgroup:
y = gx mod p
Signature Generation and Verification Mechanics
Let m be the message to be signed, and let H be a standardized cryptographic hash function (such as SHA-256).
1. Signature Generation
To generate a digital signature on message m:
- The signer generates a secret ephemeral nonce k sampled uniformly at random from 0 < k < q.
- The signer computes the first signature component r:
r = (gk mod p) mod q
If r = 0, a fresh nonce k must be selected.
- The signer computes the message digest z = H(m), taking the N leftmost bits if the digest exceeds N bits.
- The signer computes the second signature component s using the modular multiplicative inverse of k modulo q:
s = kโ1 ยท (z + x ยท r) mod q
If s = 0, a fresh nonce k must be selected.
The signature is the pair of integers (r, s).
2. Signature Verification
Given the message m, the public verification key y, and the signature (r, s):
- The verifier confirms that 0 < r < q and 0 < s < q.
- The verifier computes the modular inverse w = sโ1 mod q.
- The verifier evaluates two intermediate scalar weights:
u1 = z ยท w mod q u2 = r ยท w mod q
- The verifier evaluates the double modular exponentiation in the prime group and reduces the result modulo q:
v = ((gu1 ยท yu2) mod p) mod q
The signature is valid if and only if v = r.
Mathematical Correctness Proof
The correctness follows algebraically because s โก kโ1 ยท (z + xr) (mod q). Multiplying by k ยท sโ1 yields:
k โก sโ1 ยท (z + xr) โก z ยท w + r ยท w ยท x โก u1 + u2 ยท x (mod q)
Because g has order q modulo p, raising g to exponents congruent modulo q preserves equivalence:
gk โก gu1 + u2ยทx โก gu1 ยท (gx)u2 โก gu1 ยท yu2 (mod p)
Reducing both sides modulo q yields r = (gk mod p) mod q = v.
Nonce Security and Catastrophic Failure Modes
The security of DSA depends critically on the uniform unpredictability and secrecy of the ephemeral nonce k. If an attacker discovers k, the private key x is recovered through elementary modular arithmetic:
x = (s ยท k โ z) ยท rโ1 mod q
The Repeated Nonce Catastrophe
If a signer uses the identical nonce k to sign two distinct messages m1 and m2 under the same private key, the first signature component r remains identical across both signatures (r1 = r2 = r). An eavesdropper intercepting both signatures computes:
s1 โ s2 = kโ1 ยท (z1 โ z2) mod q
The nonce k is instantly derived as:
k = (z1 โ z2) ยท (s1 โ s2)โ1 mod q
Once k is known, the private key x is compromised. This vulnerability caused the landmark 2010 security breach of the Sony PlayStation 3 gaming console, where firmware signing keys were recovered because a static nonce k had been hardcoded into the cryptographic implementation.
To permanently neutralize nonce-leakage vulnerabilities, RFC 6979 standardized deterministic DSA (and ECDSA), wherein k is derived deterministically from the private key and message digest using HMAC, guaranteeing uniform entropy while eliminating random number generator dependencies.
Transition to Elliptic-Curve DSA (ECDSA)
While classical finite-field DSA requires 2,048-bit to 3,072-bit moduli to match modern security baselines, Elliptic Curve DSA (ECDSA) maps the identical mathematical signing structure over the group of points on an elliptic curve over a finite field:
- The scalar multiplication [k]G replaces modular exponentiation gk mod p.
- Because the best known algorithms for the Elliptic Curve Discrete Logarithm Problem (ECDLP)โPollard's rho algorithmโrun in fully exponential time O(โq), ECDSA achieves 128-bit security using a 256-bit prime group order (such as curve secp256k1 or NIST P-256), yielding signatures that are four times smaller than classical DSA.
Comparison of Digital Signature Algorithms
| Signature Algorithm | Hard Problem | Key Size (128-bit Security) | Signature Size | Nonce Failure Impact | Verification Speed |
|---|---|---|---|---|---|
| Classical DSA | Finite-Field DLP | 3,072-bit modulus | 512 bits (2 N) | Instant private key loss | Moderate (two exponentiations) |
| ECDSA | Elliptic Curve DLP | 256-bit curve | 512 bits (2 q) | Instant private key loss | Fast |
| Schnorr / Ed25519 | Discrete Logarithm | 256-bit curve | 512 bits | Instant private key loss | Extremely fast (batchable) |
| ML-DSA (Dilithium) | Module Learning With Errors | ~2,592 bytes | ~3,293 bytes | Nonce-free variant available | Matrix vector arithmetic |
References
- National Institute of Standards and Technology. (1994). Digital Signature Standard (DSS). Federal Information Processing Standards Publication 186.
- Johnson, D., Menezes, A., & Vanstone, S. (2001). The Elliptic Curve Digital Signature Algorithm (ECDSA). International Journal of Information Security, 1(1), 36-63.
- Pornin, T. (2013). Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA). Internet Engineering Task Force RFC 6979.
- Kravitz, D. W. (1993). Digital signature algorithm. U.S. Patent No. 5,231,668.