The DSA (Digital Signature Algorithm)

Introduction

DSA — the Digital Signature Algorithm — was published by the U.S. National Institute of Standards and Technology (NIST) in 1994 as part of the Digital Signature Standard (DSS). Unlike RSA, which handles both encryption and signatures with the same underlying math, DSA does one thing only: it produces and verifies digital signatures. It was designed specifically as a patent-free, royalty-free alternative at a time when RSA’s patent made licensing a real concern for the U.S. government and the public at large.

Table of Contents

• Why a Signature-Only Algorithm?
• Domain Parameters and Key Generation
• Signing a Message
• Verifying a Signature
• A Worked Example
• The Critical Importance of k
• DSA vs. RSA Signatures vs. ECDSA
• FAQ
• References

Why a Signature-Only Algorithm?

DSA’s math is built on the same discrete logarithm problem that underpins Diffie-Hellman and ElGamal — given g, p, and gᵏ mod p, it’s computationally infeasible to recover k. Where ElGamal generalizes this into a full public-key encryption scheme, DSA narrows the same underlying hardness assumption into a signature scheme specifically, producing shorter signatures than a naive ElGamal-style signature would, while still resting on well-understood, publicly analyzed mathematics.

Domain Parameters and Key Generation

DSA uses three shared, public domain parameters:

• p: a large prime modulus.
• q: a smaller prime that evenly divides p − 1, defining the size of the subgroup DSA actually operates in.
• g: a generator of the order-q subgroup of the integers mod p — computed as g = h^((p−1)/q) mod p for some h, chosen so that g ≠ 1.

Each user then generates a key pair:

• Private key x: a randomly chosen integer, 0 < x < q, kept secret.
• Public key y: computed as y = gˣ mod p.

Signing a Message

To sign a message m using private key x:

1. Choose a random, secret integer k, where 0 < k < q. This value must be unique and unpredictable for every single signature — reusing it, or generating it predictably, completely breaks DSA (see below).
2. Compute r = (gᵏ mod p) mod q.
3. Compute s = k⁻¹ · (H(m) + x·r) mod q, where H(m) is a cryptographic hash of the message (SHA-256 or similar in real implementations) and k⁻¹ is the modular inverse of k mod q.
4. If either r or s comes out to 0, discard k and start over with a new random value — a zero would leak information and produce an invalid signature.
5. The signature is the pair (r, s).

Verifying a Signature

Given a message m, signature (r, s), and the signer’s public key y, anyone can verify:

1. Reject immediately if r or s falls outside the valid range (0, q).
2. Compute w = s⁻¹ mod q.
3. Compute u1 = (H(m)·w) mod q and u2 = (r·w) mod q.
4. Compute v = ((gᵘ¹ · yᵘ²) mod p) mod q.
5. The signature is valid if and only if v = r.

Interactive Visualizer

The visualizer above runs this exact algorithm with small demonstration numbers — generate a key pair, sign a message, then verify it. Try editing even one character of the message before verifying: because the hash changes completely, the signature will correctly fail to verify, exactly as it should.

A Worked Example

Using small numbers purely for demonstration (real DSA uses p at least 2048 bits and q at least 224 bits):

• Domain parameters: p = 23, q = 11, g = 4
• Private key: x = 7 → Public key: y = gˣ mod p = 8
• Signing “HELLO” with a freshly chosen k: produces a signature (r, s) that verifies successfully against the public key
• Tampering with the message (even by one character) changes its hash completely, so the same signature no longer verifies — exactly the integrity guarantee a signature scheme is supposed to provide

The Critical Importance of k

DSA’s single most important operational rule is that k must be freshly random and never reused across two different signatures with the same private key. If an attacker ever observes two signatures, (r, s₁) and (r, s₂) — note the same r, meaning the same k was reused — from the same key, simple algebra recovers k directly, and from k, the private key x itself, completely.

This isn’t a theoretical concern. In 2010, security researchers demonstrated that Sony had reused the same k value across every ECDSA signature (DSA’s elliptic-curve cousin, sharing the identical mathematical vulnerability) used to sign PlayStation 3 software, allowing the private signing key to be extracted and effectively ending the PS3’s code-signing security model. It remains one of the most cited real-world cryptographic implementation failures, and it’s why modern implementations increasingly favor deterministic k generation (RFC 6979), which derives k securely from the message and private key rather than relying on a fresh random number generator call that could fail or be predictable.

DSA vs. RSA Signatures vs. ECDSA

• RSA signatures: use the same modular-exponentiation math as RSA encryption, just applied with the roles of public/private keys reversed. RSA signature verification is typically faster than DSA’s, while DSA signing is typically faster than RSA’s.
• DSA: signature-only, based on the discrete logarithm problem in a prime-order subgroup, historically valued for being unencumbered by RSA’s patent (which expired in 2000 anyway).
• ECDSA: DSA’s math ported onto elliptic curves (see the ECC guide), offering equivalent security to classic DSA with dramatically smaller keys and signatures — the modern default for new systems, used in TLS certificates, Bitcoin, and SSH, among others.

FAQ

Is DSA still secure?

The algorithm itself remains sound with adequately sized parameters (2048-bit p or larger), but it has been effectively superseded by ECDSA and EdDSA for new systems, which offer equivalent security with much smaller keys and better resistance to the kind of implementation mistakes that doomed the PS3’s signing key.

Why can’t DSA also encrypt messages, like RSA can?

DSA’s math was deliberately narrowed to only support the signature operations described above — it doesn’t define an encryption or decryption procedure at all. If you need discrete-log-based encryption, that’s what ElGamal or Diffie-Hellman key exchange (typically combined with a symmetric cipher) are for.

What happens if the same k is used twice?

The private key can be recovered directly through basic algebra, as happened publicly with Sony’s PS3 signing key in 2010. This is DSA’s single most important operational security requirement.

What’s the difference between DSA and ECDSA?

ECDSA applies the exact same signing and verification logic as DSA, but replaces the modular-exponentiation math in a prime field with point multiplication on an elliptic curve, achieving equivalent security with far smaller keys — a 256-bit ECDSA key roughly matches a 3072-bit DSA key’s security level.

Why does verification use the public key but not decrypt anything?

DSA verification doesn’t recover the original message at all (there’s nothing to “decrypt” — the message is sent alongside its signature, not inside it). It only mathematically confirms that whoever holds the private key corresponding to the given public key produced a value (r, s) consistent with that specific message’s hash.

References

1. NIST FIPS 186-5. “Digital Signature Standard (DSS).” Available at: https://csrc.nist.gov/pubs/fips/186-5/final

2. Wikipedia. “Digital Signature Algorithm.” Available at: https://en.wikipedia.org/wiki/Digital_Signature_Algorithm

3. Bushing, Marcan, Segher, and Sven. “Console Hacking 2010: PS3 Epic Fail.” 27th Chaos Communication Congress — the talk that publicly revealed Sony’s reused-k vulnerability.

4. Pornin, T. “RFC 6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA).” IETF, 2013.