## Concept
* RSA with broken prime generator
* factor the modulus

## Observations
* The primes are generated in chunks of 64 bit.
* The methods starts with a random seed an proceeds deterministically, but it is *not* necessary to recover the initial seed.
* The value of s at the beginning of the final iteration suffices.

## Approach
* Let $s_p$ be the value of $s$ in the final loop for generating $p$ and likewise $s_q$ for $q$.
* Then, we have $p = \sum_{k=0}^{15} (a^k \cdot s_p \bmod 256) \cdot 2^{1024-64k}$, likewise for $q$.
* We plug in the formulas in $n=pq$ and expand, to get the leading terms $s_ps_q \cdot 256^{15\cdot 64} + ((as_p \bmod 2^{64})s_q + (as_q\bmod 2^{64})s_p) \cdot 2^{14\cdot 64}$ and the lowest term $a^{30}s_ps_q$.
* The second highest term may cause a carry bit for the highest term (or maybe not).
* Hence, we get the higher bits from $s_ps_q$ via $n >> (2048 -64) -1$. (If we assume no carry bit, we do not get a solution.)
* As $a$ is odd, we can invert it modulo $2^{64}$, so from the lowest term we obtain $s_ps_q \bmod 2^{64} = a^{-30}\cdot n \bmod 2^{64}$
* Having both the upper 64 bits and the lower 64 bits, we know $s_ps_q$.
* As this is a (relatively) small number of 128 bit, we can factor it into $s_ps_q = 3 \cdot 5 \cdot 41 \cdot 43 \cdot 509 \cdot 787 \cdot 31601 \cdot 258737 \cdot 28110221 \cdot 93627982031$ (10 primes)
* This leaves $2^{10} = 1024$ possibilities for $s_p$, which divisor it is. (512 if we use symmetry, so wlog $3\mid s_p$)
* We try all choices, and construct $p$ accordingly.
* If $p$ is a prime, we check whether it is a divisor of $n$. (In fact, there is only one prime among our 512 attempts.)
* If so, we have factored $n$, so we completely broke the key and compute the flag:
`CTF{__donald_knuths_lcg_would_be_better_well_i_dont_think_s0__}`