Nonce Encore

A compact classroom DSA signer issued two signatures with the same r value. Use the public transcript to determine what repeated nonce state reveals.

Objective

Recover a repeated DSA nonce and private key with modular arithmetic.
Explain why each signature nonce must be unique and unpredictable.

Before you begin

Open /challenge/insane/nonce and fetch the complete transcript. These are synthetic classroom parameters, not production-strength keys.

Concepts

In DSA, s * k = z + x * r (mod q): z is the message hash integer, x the private key, and k the signing nonce. Two signatures made with the same key and nonce share the x * r term. Write both equations and subtract them to see what cancels. Repeated r is a clue here, not a general proof that every pair of signatures with that value reused a nonce.

Different message hashes z1 and z2 feed separate DSA signing operations. Both operations use the same private key x and reused nonce k, yielding equations with a shared x times r term.

Each DSA signing operation takes a message hash z, private key x, and nonce k. The diagram sends one reused k and the same x to both operations. Their signatures satisfy s1k = z1 + xr and s2k = z2 + xr modulo q. Comparing the equations exposes the shared term. A standard deterministic nonce construction can be safe when bound to key and message; reuse across different messages is the failure here.

Suggested tools

Python: Use exact integers and pow(value, -1, q) for modular inverses.

Tool practice

Rehearse the worked tool exercise before using challenge data.

Use Python integers throughout. For a local modular-arithmetic check, pow(3, -1, 11) is 4 because (3 * 4) % 11 is 1. The / operator performs ordinary division and is unsuitable for these equations. A failed inverse means the operands or modulus need checking.

Investigation

Rehearse modular arithmetic locally

Solve the unrelated equation 3 * v = 7 (mod 11) by multiplying by the modular inverse of 3:

q = 11
inverse = pow(3, -1, q)
v = (7 * inverse) % q
print(inverse, v, (3 * v) % q)  # 4 6 7

The result is an integer modulo 11, not the decimal fraction 7 / 3. pow(base, exponent, modulus) also computes modular exponentiation without building an enormous intermediate integer. Use % q for the signature equations and pow(g, x, p) for the separate public-key check. Keep the transcript's supplied z integers; hashing their decimal text is a new input.

Observe

Record p, q, g, public key y, both hashes, and both (r, s) pairs.

Form a hypothesis

Does the repeated r permit one k and one private key that also reproduce the published public key?

Test carefully

Calculate locally, verify pow(g, x, p) == y, then submit one decimal key.

Progressive hints

Hint 1

Subtract the two signature equations modulo q to isolate the reused nonce.

Hint 2

Use a modular inverse, then substitute the nonce into either signature equation.

Hint 3

Verify the candidate against the published public key before submission.

Troubleshooting and reset

Apply % q after differences so negative intermediate values are normalized. This module is independent of the first four Insane stages.