RSA vs RNG (rsa-vs-rng)

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-24 | Status: Solved Techniques: gap_search, hensel_lifting, lcg_related_primes, quadratic_equation_mod_2k, rsa_decrypt

Summary

Task: RSA where primes P,Q are produced by an LCG mod 2^512 (known A,B); get_prime skips composites so Q = A^k·P + C_k (mod 2^512) for a small unknown gap k. Solution: substitute into N=P·Q to get a quadratic A^k·P^2 + C_k·P - N ≡ 0 (mod 2^512); solve it by bit-by-bit Hensel lifting for each k=1,2,3,..., test P|N over the integers (found at k=180), then standard RSA decrypt.

RSA vs RNG (rsa-vs-rng) — cryptohack (Misc, 150 pts)

Description

Source generates RSA primes from a linear congruential generator and encrypts the flag. Given N, E, and the ciphertext (flag.enc), recover the flag.

 python read-only • copy allowed Copy
MOD = 2**512
A = 2287734286...471189     # known LCG multiplier
B = 4179258870...545010537  # known LCG increment
class PRNG:
    def get_num(self):  self.state = (A*self.state + B) % MOD; return self.state
    def get_prime(self):
        p = self.get_num()
        while not isPrime(p): p = self.get_num()   # skip composites
        return p
P = rng.get_prime(); Q = rng.get_prime(); N = P*Q; E = 0x10001

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Analysis

The seed is secret, but A, B, MOD = 2^512 are known. Q is generated after P by some number of LCG steps; because get_prime skips composites, Q is k steps after P for a small unknown gap k (one step per candidate tried). The k-fold LCG iterate is affine:

Q = A^k · P + C_k   (mod 2^512),    C_k = B·(A^{k-1} + … + A + 1)

Substituting into N = P·Q:

N = A^k · P^2 + C_k · P   (mod 2^512)
⟹  A^k · P^2 + C_k · P − N ≡ 0   (mod 2^512)

This is a quadratic in P modulo a power of two, one for each candidate gap k. Quadratics mod 2^512 are solved cheaply by bit-by-bit Hensel lifting: fix P mod 2, mod 4, …, mod 2^512, keeping every partial root that still satisfies the congruence at the current precision. For the correct k one of the recovered roots is the true P; verify by checking P | N over the integers. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

 python read-only • copy allowed Copy
def solve_quadratic_mod2(a, b, c, bits):     # solve a x^2 + b x + c = 0 mod 2^bits
    sols = [0]
    for i in range(bits):
        m = 1 << (i+1); new = []
        for x in sols:
            for bit in (0,1):
                xx = x | (bit << i)
                if (a*xx*xx + b*xx + c) % m == 0:
                    new.append(xx)
        sols = list(set(new))
        if not sols: return []
    return sols

Apow = 1; Csum = 0
for k in range(1, 6000):
    Apow = (Apow*A) % MOD                 # A^k
    Csum = (Csum*A + 1) % MOD             # A^{k-1}+...+1
    Ck   = (B*Csum) % MOD                 # C_k
    for P in solve_quadratic_mod2(Apow, Ck, (-N) % MOD, 512):
        if P and N % P == 0:
            Q = N // P
            if isPrime(P) and isPrime(Q):
                d  = inverse(E, (P-1)*(Q-1))
                pt = pow(int.from_bytes(ct,'big'), d, N)
                print("k =", k, long_to_bytes(pt)); raise SystemExit

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The correct gap is k = 180 (180 LCG outputs were composite and skipped between P and Q). Once P and Q are known it is textbook RSA decryption. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍