quickprime

This Challenge was covered in LACTF 2025, this is a writeup.

This is a nice LCG-based challenge and some friends asked me to write a detailed writeup, so here we go!

Handouts

from secrets import randbits
from Crypto.Util.number import isPrime


class LCG:

    def __init__(self, a: int, c: int, m: int, seed: int):
        self.a = a
        self.c = c
        self.m = m
        self.state = seed

    def next(self):
        self.state = (self.a * self.state + self.c) % self.m
        return self.state


while True:
    a = randbits(512)
    c = randbits(512)
    m = 1 << 512
    seed = randbits(512)
    initial_iters = randbits(16)
    if (c != 0 and c % 2 == 1) and (a % 4 == 1):
        print(f"LCG coefficients:\na={a}\nc={c}\nm={m}")
        break

L = LCG(a, c, m, seed)
for i in range(initial_iters):
    L.next()

P = []
while len(P) < 2:
    test = L.next()
    if isPrime(test):
        P.append(test)

p, q = P

n = p * q

t = (p - 1) * (q - 1)

e = 65537

d = pow(e, -1, t)

message = int.from_bytes(open("flag.txt", "rb").read(), "big")

ct = pow(message, e, n)

print(f"n={n}")
print(f"ct={ct}")

Analysis & Solver

This script uses an LCG in order to generate p and q, the vulnerability is that it uses the same LCG with the same seed to generate p and q.

Come to think of it, the vulnerability is this part of the code:

while len(P) < 2:
    test = L.next()
    if isPrime(test):
        P.append(test)

Relationships

Let us look at the relationship between p and q, assume we found p and appended it.

$q = a\times (a\times (a\times... (a\times p + c) ... + c) + c) +c) + c \mod m$

Let us simplify this equation:

$q = A \times p + B \mod m \newline \text {where } B = c \times (a^0 + a^1 + ... + a^{k-1}) \mod m \text { and } A = a^k \mod m$

where k is the number of iterations in the LCG between p and q

for i in tqdm(range(5000)):
    k = i + 1
    A = pow(orig_a, k, m)
    B = 0
    for j in range(k):
        B = (B + pow(orig_a, j, m)) % m
    B = (orig_c * B) % m

what we do here is loop and try different distances up to 5000 LCG iterations.

Verification

Okay, how do we know which k is the real k, and why are we doing this anyways?

Assume we found the correct k, we can rewrite N such that: $N = p \times q \equiv p \times (A \times p +B) \equiv A \times p^2 +B\times p \pmod m$

Moving N to the other side we get:

$$A \times p^2 +B\times p - N = 0 \pmod m$$

This is a quadratic equation under mod m! We can find its roots and we'd find p!!

Okay here's the gameplan, for each 'k', find the p representation of q and try solving the quadratic equation, if you solve it and get a real number, you have found p, challenge solved!

Full Solver

from Crypto.Util.number import isPrime, long_to_bytes
from sage.all import *
from tqdm import tqdm

a = ...
c = ...
m = ...
n = ...
ct = ...

orig_a = a
orig_c = c

PR = PolynomialRing(Zp(2, 512), 'x')
x = PR.gen()

for i in tqdm(range(5000)):
    k = i + 1
    A = pow(orig_a, k, m)
    B = 0
    for j in range(k):
        B = (B + pow(orig_a, j, m)) % m
    B = (orig_c * B) % m
    f = A * x**2 + B*x - n
    roots = [int(ZZ(r)) for r, _ in f.roots()]
    for root in roots:
        if root < 0:
            continue
        p = root
        q = n // p
        if isPrime(p):
            phi = (p - 1) * (q - 1)
            d = inverse_mod(65537, phi)
            pt = pow(ct, d, n)
            print(long_to_bytes(int(pt)))
            exit()
# lactf{w41t_th1s_1snt_s3cur3_4t_4ll_???}

Using 2-adic Math

In the RSA attack script, we see this line:

PR = PolynomialRing(Zp(2, 512), 'x')

This sets up a polynomial ring over 512-bit precision 2-adic numbers, which helps us work with polynomials in a way that makes finding roots (and ultimately factoring n) much easier.

The script is trying to solve a quadratic equation:

$A x^2 + B x - n = 0$

By using PolynomialRing(Zp(2, 512), 'x'), the script takes advantage of 2-adic math to efficiently solve for p. This is a clever trick that makes factoring n much more feasible.