โ† Wiki Index / Computation & Algorithms / Digital Signature Algorithm
๐Ÿ’ป Computation & Algorithms

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:

  1. 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.
  2. 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:

  1. The signer generates a secret ephemeral nonce k sampled uniformly at random from 0 < k < q.
  2. The signer computes the first signature component r:

r = (gk mod p) mod q

If r = 0, a fresh nonce k must be selected.

  1. The signer computes the message digest z = H(m), taking the N leftmost bits if the digest exceeds N bits.
  2. 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):

  1. The verifier confirms that 0 < r < q and 0 < s < q.
  2. The verifier computes the modular inverse w = sโˆ’1 mod q.
  3. The verifier evaluates two intermediate scalar weights:

u1 = z ยท w mod q u2 = r ยท w mod q

  1. 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 AlgorithmHard ProblemKey Size (128-bit Security)Signature SizeNonce Failure ImpactVerification Speed
Classical DSAFinite-Field DLP3,072-bit modulus512 bits (2 N)Instant private key lossModerate (two exponentiations)
ECDSAElliptic Curve DLP256-bit curve512 bits (2 q)Instant private key lossFast
Schnorr / Ed25519Discrete Logarithm256-bit curve512 bitsInstant private key lossExtremely fast (batchable)
ML-DSA (Dilithium)Module Learning With Errors~2,592 bytes~3,293 bytesNonce-free variant availableMatrix vector arithmetic

References

  1. National Institute of Standards and Technology. (1994). Digital Signature Standard (DSS). Federal Information Processing Standards Publication 186.
  2. Johnson, D., Menezes, A., & Vanstone, S. (2001). The Elliptic Curve Digital Signature Algorithm (ECDSA). International Journal of Information Security, 1(1), 36-63.
  3. Pornin, T. (2013). Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA). Internet Engineering Task Force RFC 6979.
  4. Kravitz, D. W. (1993). Digital signature algorithm. U.S. Patent No. 5,231,668.
๐Ÿงฌ Support Open Science
Explore interactive science games on LowKey Games or browse scientific apparel & accessories in the CRV Science Shop.
๐Ÿ’ก Spot an inaccuracy or have primary literature to expand this article?
Submit a citation or revision note using your shared CRV Science / LowKey Games profile ID.
Suggest Revision