> For the complete documentation index, see [llms.txt](https://l0mb4rd.gitbook.io/crypto/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://l0mb4rd.gitbook.io/crypto/cool-ctf-challenges/quickprime.md).

# 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](/crypto/cryptography-notes/introduction-to-cryptography-notes/breaking-randomness.md) 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.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://l0mb4rd.gitbook.io/crypto/cool-ctf-challenges/quickprime.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.