## 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__}`
