How does the DSA (Digital Signature Algorithm) work, and how does it differ from RSA signatures?

DSA is a signature-only scheme built on the discrete-logarithm problem: signing and verification are entirely different operations (unlike RSA, where they mirror each other), it can't encrypt, and every signature is randomised by a fresh secret $k$.

* Unlike RSA, signing and verifying are different computations, the output is a pair (r, s), and a fresh random k is mandatory — reusing it leaks the secret x. *

DSA works inside a small prime-order subgroup, which is what keeps signatures short even though the modulus is large. Key generation fixes that group and the signer's keypair:

• Choose a large prime $p$ (~3072 bits) and a prime $q$ (~256 bits) dividing $p-1$.
• Pick a generator $g$ of the order-$q$ subgroup of $\mathbb{Z}_p^*$.
• Secret key: random $x \in \{1, \dots, q-1\}$; public key: $y = g^x \bmod p$.

Signing message $m$ is probabilistic — it draws a fresh random $k$ every time:

1. Pick random $k \in \{1, \dots, q-1\}$.
2. $r = (g^k \bmod p) \bmod q$.
3. $s = k^{-1}\,(H(m) + x \cdot r) \bmod q$, giving the signature $(r, s)$.

Verification recombines the public values and checks they reproduce $r$:

1. $w = s^{-1} \bmod q$.
2. $u_1 = H(m)\cdot w \bmod q$ and $u_2 = r \cdot w \bmod q$.
3. Accept if $(g^{u_1} y^{u_2} \bmod p) \bmod q = r$.

The contrast with RSA is the point of the scheme:

NIST published DSA in 1991 as a patent-free, signature-only alternative to RSA, sidestepping both RSA's licensing and Schnorr's patent. Because the random $k$ must be unique and secret for every signature, reusing or leaking it exposes the private key $x$ — the flaw that famously broke the Sony PlayStation 3's code signing. Its elliptic-curve form, ECDSA, applies the identical structure over an EC group and is today's dominant signature standard.

Go deeper:

• Digital Signature Algorithm — full key-gen/sign/verify equations and the k-reuse break (the flaw that leaked the PS3 signing key).