DSA (Digital Signature Algorithm)
What you'll learn: How DSA generates keys, creates signatures, and verifies them using modular arithmetic and discrete logarithms.
What is DSA?
DSA is a U.S. federal standard (FIPS 186) for digital signatures, designed specifically for signing rather than encryption. Unlike RSA—which can do both—DSA focuses solely on creating and verifying digital signatures. It relies on the discrete logarithm problem for security, making it computationally infeasible to forge signatures without the private key.
Key Generation
DSA creates three key components:
- Domain parameters (p, q, g): shared public values where p is a large prime, q is a smaller prime divisor of p-1, and g is a generator
- Private key (x): a random integer between 1 and q-1
- Public key (y): computed as g^x mod p
Think of the private key as your unique stamp pattern, and the public key as the visible impression it leaves—anyone can see the impression, but only you possess the stamp.
Signature Creation
To sign a message m:
- Hash the message: h = hash(m)
- Generate a random nonce k (between 1 and q-1)
- Compute r = (g^k mod p) mod q
- Compute s = (k^-1 × (h + x×r)) mod q
- The signature is the pair (r, s)
The nonce k must be unique for each signature—reusing it catastrophically leaks your private key!
Verification
Anyone with your public key can verify:
- Hash the message: h = hash(m)
- Compute w = s^-1 mod q
- Compute u₁ = (h×w) mod q and u₂ = (r×w) mod q
- Verify: r equals (g^u₁ × y^u₂ mod p) mod q
If they match, the signature is authentic.
Key Takeaway: DSA provides secure digital signatures through the discrete logarithm problem, requiring careful key generation, unique random nonces per signature, and mathematical verification that ties the signature to both the message and the signer's private key.