# quickprime

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

## Handouts

```python

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](https://l0mb4rd.gitbook.io/crypto/cryptography-notes/introduction-to-cryptography-notes/breaking-randomness) 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:

```python
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

```python
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

```python
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:

```python
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.