CyberYard CTF – M4ths

M4ths Crypto Write-up

Category: Crypto
Prompt: Some gaps are small some are huge
Artifact: ⬇️ challenge.py - ⬇️ out.txt.
Flag format: FlagY{...}

---

intro

The RSA key was generated with: p = getPrime(1024) q = nextprime(p + getrandbits(512)) # q is “close” to p n = p*q e = 0x10001 ct = pow(m, e, n)

Because q − p < 2^512 ≈ n^(1/4), the modulus has close primes. This makes it vulnerable to a (Fermat) Coppersmith-style factorization. After factoring n, compute d, decrypt ct, and the plaintext contains the flag.

---

Challenge Description

If p and q are close:

• a = (p + q)/2 is near sqrt(n)
• a^2 − n = ((q − p)/2)^2 is a small square

Brute-force Fermat is borderline when the gap is ~n^(1/4), but a small-root (Coppersmith) approach around A = ceil(sqrt(n)) finds the tiny x = a − A, then we reconstruct p, q.

---

Steps

1. Parse given n and ct.
2. Let A = ceil(sqrt(n)).
3. Work mod n with f(x) = (A + x)^2 − n. For the correct small x0, f(x0) ≡ 0 (mod n).
4. Use a lattice/small-root routine to recover x0 with bound ~n^(1/4).
5. Set a = A + x0, b^2 = a^2 − n; then p = a − b, q = a + b.
6. Compute φ(n) = (p−1)(q−1), d = e^(-1) mod φ(n).
7. Decrypt m = ct^d mod n → extract flag.

---

Solver

from math import isqrt


n = int("18552214896423000565964954068282406674971502238215699518204084178601023077567456930188156395781444480169555146234541486771975129395421945283826496993577134629895154884651234859474819728020830892121433460525545135205587268408425559426550762417843991744925510144029739862807981944979919916268589586865132555346023498442806710752734146923223300583104281816519175209412466936071517687843790168151470769561076697356665770717280611580181034640693557159172981118154808220340247196391098947022592690509310486372915020481920496588908523098998781484123506337821031358268724386295531256963177210773145861403142734317334978452179")
ct = int("18459930372229983090709259793073039760162724641648071179302308034168492705233927026484739957819997919805563724299301163802794657833298411691334435225417004319062183234585304346867308523296832044235997514383209842727896931538736364988657063157149571233951460519202401843295478583491530387169689999661106298890646815511068619749403350972695081661635128386944078959555401596832292631727796273344063149749279149812751994363266882130576897125326601597821920342681466341364542099588989233325033407384904272804565460157152863222376670867517777186398003282984784986169902365780957994725978466219239319955097268446160554266498")
e = 0x10001


s = isqrt(4*n)
S = s + 1
D2 = S*S - 4*n
D = isqrt(D2)
assert D*D == D2


p = (S - D) // 2
q = (S + D) // 2
assert p*q == n


phi = (p-1)*(q-1)
d = pow(e, -1, phi) 
m = pow(ct, d, n)


from Crypto.Util.number import long_to_bytes
mb = long_to_bytes(m)
start = mb.find(b"FlagY{")
end = mb.find(b"}", start)
flag = mb[start:end+1].decode()
print(flag)

Output:

FlagY{l0ng_fl@g_But_e4sy_Ch4ll3ng3_C0pp3rsm!th_w4s_4_M4ths_G33k}