Course contentsShow
← Computer Science
Lesson 2437 of 2,87254. Cryptography FundamentalsFree lesson

DSA (Digital Signature Algorithm)

Overview of DSA: key generation, signature creation, and verification process.

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:

  1. 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
  2. Private key (x): a random integer between 1 and q-1
  3. 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:

  1. Hash the message: h = hash(m)
  2. Generate a random nonce k (between 1 and q-1)
  3. Compute r = (g^k mod p) mod q
  4. Compute s = (k^-1 × (h + x×r)) mod q
  5. 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:

  1. Hash the message: h = hash(m)
  2. Compute w = s^-1 mod q
  3. Compute u₁ = (h×w) mod q and u₂ = (r×w) mod q
  4. 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.