DSA Fundamentals — the linear signing equation every DSA attack exploits

DSA signs a hash over a prime-order subgroup of Z_p*, and the entire signature is one linear equation in two unknowns — every named DSA attack is really a way to supply the missing second relation.

The signal that betrays it

You're looking at a DSA (not RSA, not ECDSA-over-a-curve) challenge when you see: - Three public parameters (p, q, g): p prime (the field), q a prime divisor of p-1 (the subgroup order), g a generator of the order-q subgroup mod p. - A public key y = g^x mod p, private key x in [1, q-1]. - One or more signatures (r, s) where both r and s are reduced mod q, not mod p — that's the tell that distinguishes DSA/ECDSA-shaped signatures from RSA's single integer signature. - Classic textbook DSA uses a 160-bit q (the old FIPS 186-2 size); modern params use 224- or 256-bit q. A CTF that hands you a suspiciously small or structured q, or a q that visibly divides p-1 with a lot of headroom, is hinting at a specific sub-attack rather than brute force.

Confirm you've parsed the params correctly before hunting for a weakness — verify one signature: ``python def dsa_verify(p, q, g, y, h, r, s): w = pow(s, -1, q) u1 = (h * w) % q u2 = (r * w) % q v = (pow(g, u1, p) * pow(y, u2, p)) % p % q return v == r `` If this doesn't check out, you have the wrong hash function, the wrong endianness on m, or you're truncating/not truncating h to q's bit length — fix that first, it is not the challenge's vulnerability.

How it's exploited

The signing equation is:

s·k ≡ h + x·r (mod q)

Two unknowns, k (the per-signature nonce) and x (the long-term private key), one equation. Nothing here is solvable in isolation — a legitimate DSA implementation with a fresh, uniformly random k per signature and a private q large enough to resist brute force (>= 160 bits) gives you exactly one equation and no way to eliminate a variable. Every real attack is a way to obtain a second, independent linear relation so the 2x2 system in (k, x) becomes solvable, or a way to make k itself guessable/small enough to search. Triage by what extra relation the challenge is handing you:

- Identical k reused across two signatures (same r appears twice, or two signatures from the same key with a comment/hint about nonce generation) → the two equations share k, subtract them and x falls out in closed form. See ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra. - k is short, or you know some of its bits (e.g. it's generated by a biased/predictable RNG, or a side channel leaks the top bits) → each signature becomes a Hidden Number Problem sample; stack several and run lattice reduction. See DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery, Hidden Number Problem — recovering a secret from many small-bounded-error samples. - k is not fully random but follows a KNOWN relation across signatures (an incrementing counter, an LCG, k_{i+1} = a*k_i + b) → still just linear algebra, but now over several signatures instead of two; build the linear system and solve. See Repeated / Linearly-Related Nonce Recovery — when nonces aren't reused, but ARE related by a known formula. - The nonce is derived deterministically (RFC 6979) but the implementation is broken — e.g. it ignores the message and reuses the same HMAC key/seed for k — you're back to plain nonce reuse even though the code "looks" deterministic-safe. See Deterministic Nonce (RFC 6979) Failures — when 'no more RNG risk' still leaks the key. - You can't touch k at all, but you can produce a second valid signature for a message you don't control — that's a different bug class (malleability of an existing (r,s), not the fundamentals equation). See Signature Malleability — a valid (r,s) becomes another valid (r,s) without the key.

Note the same equation shape carries over unchanged to ECDSA (s·k = h + d·r mod n, over the curve's group order instead of q) — everything above is why ECDSA Fundamentals — the s*k = h + d*r identity that routes every nonce attack is a near-duplicate of this page with elliptic-curve group operations swapped in for modular exponentiation. Recognizing "params + (r,s) reduced mod a smaller order" as the family, then figuring out which extra relation the challenge is really giving you, is the whole game — see Discrete Logarithm — the factorization of the group order picks your algorithm for what happens if you're instead handed g^k or g^x directly with no signature at all.

Public-source note: as of FIPS 186-5, NIST deprecated DSA for *signature generation* (verification of legacy DSA signatures is still specified) — a useful sanity check that DSA challenges in current CTFs are deliberately using a legacy/insecure construction, not an oversight, so look for exactly one of the nonce-handling weaknesses above rather than a novel one.

What doesn't work

- Brute-forcing k directly. For any correctly sized q (>=160 bits) this is a discrete-log-hard search space; there is no shortcut that doesn't come from one of the extra relations above. Don't burn time on this unless q is visibly tiny (a deliberately broken toy challenge), in which case just solve the DLP with Baby-Step Giant-Step — the generic meet-in-the-middle solver for a mid-sized discrete log instead of calling it a "DSA attack." - Treating h as the raw message. h must be H(m) truncated/reduced to q's bit length per the spec; plugging in the plaintext message (or the untruncated hash) makes dsa_verify fail and wastes time chasing a phantom bug in the challenge instead of your parsing. - Assuming nonce reuse just because two signatures share the same q/p. Same params only means same domain — the r values must actually match (or you must independently confirm k is shared) before subtracting the equations; two signatures from different keys, or the same key with genuinely fresh k, share nothing you can exploit this way. - Reaching for lattice machinery before checking for exact reuse. If r repeats exactly across signatures, the closed-form nonce-reuse algebra is instant; building an HNP lattice instance for a problem that's really exact reuse is solving the same challenge the slow, error-prone way. - Ignoring the s=0 or r=0 degenerate cases. A correct implementation rejects these and resigns with a fresh k; if a challenge's signer doesn't check for them, that absence of a check can itself be the intended bug rather than anything about k's randomness — read the signing code, don't assume the vulnerability is always nonce-related just because this is DSA.

Related

ECDSA Fundamentals — the s*k = h + d*r identity that routes every nonce attack ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery Repeated / Linearly-Related Nonce Recovery — when nonces aren't reused, but ARE related by a known formula Deterministic Nonce (RFC 6979) Failures — when 'no more RNG risk' still leaks the key Signature Malleability — a valid (r,s) becomes another valid (r,s) without the key Hidden Number Problem — recovering a secret from many small-bounded-error samples Discrete Logarithm — the factorization of the group order picks your algorithm Baby-Step Giant-Step — the generic meet-in-the-middle solver for a mid-sized discrete log