## 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 beengenerated by a linear-congruential random number generator (an LCG). LCGs are notcryptographically secure, and we'll use the arithmetic relationship between the signaturesto 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, s2be 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 toeliminate 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