Files:

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$.

  • With probability $1/p$, $\,$ $p \mid n_i$. Then from $d, \, x_i \equiv 1 \pmod{n_i}$ we also have $d, \, x_i \equiv 1 \pmod p$, so $x_i \equiv d^{-1} \pmod p$.
  • Otherwise $(1-1/p)$, $\,$ $x_i \bmod p$ is essentially uniform in $\mathbb{Z}_p$.

Then, among the $x_i \bmod p$, the residue $d^{-1} \bmod p$ shows up as the most common value $1/p$. If we invert residues before counting (i.e., look at $(x_i \bmod p)^{-1}$), the mode lands directly on $d \bmod p$.

Formally, for $r\in\mathbb{Z}_p$: $$ \Pr[x \equiv r] = \begin{cases} \frac{2}{p}-\frac{1}{p^2} & r = d^{-1},\\ \frac{1}{p}-\frac{1}{p^2} & r \neq d^{-1}. \end{cases} $$

With $N=30{,}000$ samples, the gap $\approx N/p$ is large for small $p$.

Method

  1. Pick small primes: enumerate primes $p$ (e.g., all $p\le 10{,}000$, excluding $2$).
  2. Recover $d \bmod p$: for each $p$, histogram the values $(x_i \bmod p)^{-1} \in \mathbb{Z}_p$ (ignore zeros). The peak of the histogram gives $d \bmod p$.
  3. Lift via CRT: combine the congruences $d \equiv d_p \pmod p$ progressively using the Chinese Remainder Theorem until the accumulated modulus $M$ exceeds $2^{1024}$. The unique lift $A\in[0,M)$ is then the true $d$.
  4. Derive key & decrypt: compute $K=\text{SHA256}(\text{str}(d))$ and decrypt the given ciphertext under the provided IV (AES-CBC, PKCS#7).

This entire method is implemented in the code below.

import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

values = [...]

def primes(n):
    s = bytearray(b"\x01")*(n+1)
    s[:2] = b"\x00\x00"
    for p in range(2, int(n**0.5)+1):
        if s[p]:
            s[p*p:n+1:p] = b"\x00"*(((n-p*p)//p)+1)
    return [i for i,b in enumerate(s) if b]

L = 10000
P = [p for p in primes(L) if p > 2]

def mode_inv(vs, p):
    c = [0]*p
    for a in vs:
        r = a % p
        if r:
            c[pow(r, -1, p)] += 1
    x = max(range(p), key=c.__getitem__)
    return x, c[x]

A, M = 0, 1
for p in P:
    x, _ = mode_inv(values, p)
    k = ((x - A) % p) * pow(M, -1, p) % p
    A = (A + k * M) % (M * p)
    M *= p
    if M.bit_length() > 1034:
        break

d = A

iv_hex  = "701116fad3bfd0a822fa4b0d0499df8e"
enc_hex = "788d8072f6427b5da87556f3464d09dec6b260bbf34721e1bd27d844491294c95364541d19b7409aebd548df3342280281d39a27bff0cccc4fe3dca3012b3e2a"

def dec(x):
    k = hashlib.sha256(str(x).encode()).digest()
    iv = bytes.fromhex(iv_hex)
    ct = bytes.fromhex(enc_hex)
    try:
        return unpad(AES.new(k, AES.MODE_CBC, iv).decrypt(ct), 16)
    except Exception:
        return None

print(d.bit_length())
print(dec(d))

Flag

b'crew{1nvertin9_w17h_3rr0rs_4065fad3e73c13b3f467cfc7887ff960}'