Write-ups

Summary

A 1024-bit prime $d$ is sampled. For $i=1..30{,}000$, a 1024-bit random modulus $n_i$ (MSB set) is chosen and the value

$$ x_i = d^{-1} \bmod n_i $$

is published without revealing $n_i$. The AES key is SHA256(str(d)). The IV and ciphertext of the flag (AES-CBC) are provided.

Goal: recover $d$ from the list of $x_i$ only, then decrypt the flag.

Solve

Consider the residues $x_i \bmod p$ for a small prime $p$.

Summary

Work over the binary extension field with nbits = 64*3 = 192. The internal state evolves affinely and the output is the top 64 bits of the 192-bit state.

$$S_{t+1}=a,S_t+b \text{ in } \mathbb{F}_{2^{192}}$$ $$y_t=\lfloor S_t / 2^{128}\rfloor \in {0,\ldots,2^{64}-1}$$

The challenge prints 200 outputs values $= [y_0,\ldots,y_{199}]$, then takes two more outputs $v_1=y_{200}$, $v_2=y_{201}$ to form the AES-ECB key (big-endian):

$$\text{key}=(v_2 \ll 64)\ | \ v_1$$