Rating:

## LCGSign - Crypto 400 Problem - Writeup by Robert Xiao (@nneonneo)

In this challenge, two messages have been signed using DSA (Digital Signature Algorithm).
Crucially, the two messages are related through the secret "random", which has been
generated by a linear-congruential random number generator (an LCG). LCGs are not
cryptographically secure, and we'll use the arithmetic relationship between the signatures
to break the scheme and recover the secret key.

Let A=713030730552717 and B=123456789 be the two parameters of the LCG, and let N=2^1024.

Let z1, k1, r1, s1 be parameters of the first message, and likewise z2, k2, r2, s2
be parameters of the second message.

`k2 = (k1*A+B) mod N`, so we can express `k2` as `k1*A+B-tN` for some `t`.

Mod q, we have

r1 = g^k1 mod p
s1 = k1^-1 * (z1+x*r1)
r2 = g^{k1*A+B-tN} mod p
s2 = (k1*A+B-tN) ^ -1 * (z2+x*r1)

and so

(s1*k1 - z1) * r1^-1 = x
(s2*(k1*A+B-tN) - z2) * r2^-1 = x

This is a system of two linear equations with three unknowns (k1, t, x). We'll need to
eliminate one of the unknowns to make this solvable.

Observe that

r2 = g^{k1*A+B-tN} mod p = (g^k1)^A * g^B * g^{-tN} mod p = r1^A * g^B * g^{-tN} mod p

and thus

(g^N)^t = r1^A * g^B * r2^-1 mod p

Now, we'll need to know `r1 mod p` and `r2 mod p`; we only have `r1 mod p mod q` and
`r2 mod p mod q`. Since p = q*2+1, this is quite straightforward: if we have `a = r mod p mod q`, then
`r mod p` is either `a` or `a+q`, and we can just try all four combinations (`r1,r2`, `r1+q,r2`, `r1,r2+q`, `r1+q,r2+q`)
until we find one that works.

The equation `(g^N)^t = r1^A * g^B * r2^-1 mod p` is solvable by taking the discrete log of the RHS to the base `g^N`.
Unfortunately, `p` is very big and `p-1` has a huge prime factor (q), so we can't compute general discrete logs.

However, in this case, we can bound the exponent `t`: since `t = floor((k1*A+B)/N)`, and `k1

Original writeup (https://github.com/pwning/public-writeup/blob/master/mma2015/crypto400-lcgsign/writeup.md).