# Xorsa writeup - UMassCTF 2025

## Intro
I've recently played in the awesome UMassCTF 2025 with my team [Flag Fortress 2](https://ctftime.org/team/302712)♥️
We ended up with 6th place on the scoreboard! :D
I had a fantastic time and I really loved all the challenges this year.

---

## Challenge details

**Category:** Cryptography
**Points:** 488 (19 solves)
**Challenge Description:**

oops, i leaked a bit more than half of the xor of the primes

**Challenge files:** `main.py`, `output.txt`

---

## Solution
### TL;DR
We can use `n` and the leaked partial XOR of `p` and `q` to generate a list of candidates for the most significant bits of `p`.
Then, we can apply Coppersmith's method to each candidate to recover the remaining lower bits of `p` and validate the result.

---

### Analysis
Let's break down `main.py`:

from Crypto.Util import number

flag = b"REDACTED"
bits = 1024

p = number.getPrime(bits)
q = number.getPrime(bits)

n = p * q
phi = (p - 1) * (q - 1)
e = 65537
d = number.inverse(e, phi)
extra = 75

c = pow(int.from_bytes(flag, 'big'), e, n)
print(f"n: {hex(n)}")
print(f"e: {hex(e)}")
print(f"c: {hex(c)}")
print(f"partial p^q: {hex((p^q) >> (bits // 2 - extra))}")

I won't go into detail regarding how RSA encryption works.
The interesting part here is the partial leak of the XOR of the primes p and q.

The `output.txt` file contains the values of `n`, `e`, the encrypted flag `c` and the partial leak of `p ^ q` - namely, only the 587 most significant bits: `(p ^ q) >> (bits // 2 - extra)`.

In order to decrypt the flag, we need to factor `n` into `p` and `q`, and use that knowledge to find the private exponent `d`.

---

### Step 1: Generate Candidates for the Primes

The leaked XOR of the primes (`p ^ q`) reveals the 587 most significant bits. Using this information, we can recursively reconstruct these bits for either `p` or `q` (in this case, we arbitrarily choose `p`):

- **XOR Constraint**:
- For each bit position `i`, the XOR relationship `p[i] ^ q[i] = leak[i]` must hold.
- Based on the value of `leak[i]`, the possible bit pairs for `p[i]` and `q[i]` are:
- If `leak[i] = 1`: The pairs are `(0, 1)` or `(1, 0)`.
- If `leak[i] = 0`: The pairs are `(0, 0)` or `(1, 1)`.

- **Pruning Candidates**:
- At each step, we calculate the minimum and maximum possible values of `p` and `q` given the most significant bits by filling their remaining bits with `0` or `1`, respectively.
- A candidate is discarded if either:
- The product of the minimum values exceeds `n`, *or*
- The product of the maximum values is less than `n`.
- This ensures that only candidates satisfying the condition $p_{min} \cdot q_{min} \leq n = p \cdot q \leq p_{max} \cdot q_{max}$ are kept.

By applying these constraints, we generate a list of candidates for the most significant bits of `p` that meet the XOR constraint and are consistent with `n`.

### Step 2: Recover the Full Primes Using Coppersmith's Method

After generating candidates for the most significant bits of `p`, we use **Coppersmith's method** to recover the full primes:

- **Polynomial Construction**:
- For each candidate `p_high`, we construct the polynomial `f(x) = p_high + x` over the ring `Zmod(n)`.
- The goal is to find small roots of this polynomial, as these roots correspond to the missing lower bits of `p`.

- **Root Finding**:
- Using SageMath's [small_roots](https://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/polynomial_modn_dense_ntl.html#sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots) method, we search for small roots of `f(x)` within the range of the missing bits.
- We set `beta=0.5`, assuming without loss of generality that $p \geq q$. This implies $p^2 > pq = n$, which leads to $p > \sqrt{n} = n^{0.5}$.
- The upper bound for the root is `X = 1 << MISSING_BITS` because we are missing exactly 437 bits from `p`. When combined with `p_high`'s `KNOWN_BITS`, we reconstruct the full 1024 bits of `p`.

- **Validation**:
- For each root `x0`, we compute `p = f(x0)` and check if `n % p == 0`.
- If it is, we calculate `q = n // p` to recover the second prime.

### Step 3: Decrypt the Flag

Once `p` and `q` are recovered, the private key `d` is computed as `d = pow(e, -1, (p-1)*(q-1))`.
The flag is then decrypted using `m = pow(c, d, n)` and converted back to bytes.

---

## Solve script

from Crypto.Util.number import long_to_bytes
from sage.all import PolynomialRing, Zmod
from tqdm import tqdm
from halo import Halo

n = 0x46dbd0780b618c8dea0dc6b13a47a5b40bca30b96ed5b15e1be1ffad2fbab901bd0e26c8f3e2fa80cf208e3ba936acb3eef98002459833f96901e1fedb5e97432e05d5ad892beea06a96c059b5c6652a2241bcdaf91ccb4320298868ed3e0929778030e0cce2316b7677cc5574676545aacdef446f078fc08b56415315750ce659fc61db73f633b47a1c874145dd8676e70079ab40587be81c4a9673ded5e61e11c705e45fb4a910a7a1be2b3c3d0af8555a7d9a7aa90d4e4ec0bceb14cdbb1e4c91e379fa6961411139306b6add555734feeb77d51b40e568185b20c141bb4d07b96a1944d187cf8b6019dcdcb27a7309839393e6a63cfaffb9f11d26b503df
e = 0x10001
c = 0x389d979c400a145704d5685bce1f65f642e66c2778e62a7d0519addef8c92d9df42677df805a4e99962b14fb5acd512a7ab65f811842547a1a6670f73b6232e8790887584884caa66dad345c6aeb559402c16990eed47212f0794e11972a1e92030b84663de7cd472ed85c98a6cc42f79f02f7243755f0950894c741740400d0c2c84c6bc1c0380a4ca16eab0ad7ccc3314174c96ecad28bbd364c4ea56e3bc8a7e62c3351307fd1ebe18d3f6e82d778d77e75677a858c4993e4df53ff4d38ce69427b5170631ded7c34d1cc907681a3252d159105891348b4ca84e811611f2f04e6fa2ef6e006e0855f939f41bddcb585777d14942c7f10b2fdd979515cba5f
leak = 0x643e09f2948d2df7b16ffe591ac61e2a57b4cca7ead6a49e10b52593e5f9eb28be9d17eec9f04b6295221968d8bbfb698f87fe6f64b243b5cfd8fcf428b2599bc7fe54dcc695e3fad9

BITS = 1024
EXTRA_BITS = 75

KNOWN_BITS = BITS // 2 + EXTRA_BITS
MISSING_BITS = BITS // 2 - EXTRA_BITS

xor_bits = f"{leak << MISSING_BITS:b}".zfill(BITS)

candidates = []

def extend_msb(p_bits: str, q_bits: str, depth: int) -> None:
    if depth == KNOWN_BITS:
        p_candidate = int(p_bits + '0' * (BITS - depth), 2)
        q_candidate = int(q_bits + '0' * (BITS - depth), 2)
        if p_candidate * q_candidate <= n:
            candidates.append(p_candidate)
        return

    bit = xor_bits[depth]
    bit_options = [('0', '1'), ('1', '0')] if bit == '1' else [('0', '0'), ('1', '1')]

    for bit_p, bit_q in bit_options:
        extended_p = p_bits + bit_p
        extended_q = q_bits + bit_q

        min_p = int(extended_p + '0' * (BITS - depth - 1), 2)
        min_q = int(extended_q + '0' * (BITS - depth - 1), 2)
        max_p = int(extended_p + '1' * (BITS - depth - 1), 2)
        max_q = int(extended_q + '1' * (BITS - depth - 1), 2)

        if min_p * min_q <= n <= max_p * max_q:
            extend_msb(extended_p, extended_q, depth + 1)

with Halo('', animation='dots') as spinner:
    spinner.text = "Searching for candidates..."
    extend_msb("", "", 0)
    spinner.succeed(f"Found {len(candidates)} candidates.")

print("[*] Starting Coppersmith attack...")
for p_high in tqdm(candidates, leave=False):
    PR = PolynomialRing(Zmod(n), 'x')
    x = PR.gen()
    f = p_high + x

    roots = f.small_roots(X=1<<MISSING_BITS, beta=0.5)
    if roots:
        x0 = int(roots[0])
        p = int(f(x0))
        if n % p == 0:
            q = n // p
            phi = (p-1)*(q-1)
            d = pow(e, -1, phi)
            m = int(pow(c, d, n))
            flag = long_to_bytes(m)
            tqdm.write(f"[+] Found p: {p}")
            tqdm.write(f"[+] Flag: {flag}")
            break