Telur

Overview

We are given two files, chall.py and out.txt. The challenge is standard RSA, except that in addition to the ciphertext it leaks a high-precision floating-point ratio of the next primes after p and q.

from sage.all import next_prime
from sage.all import RealField
from sage.all import ZZ
from Crypto.Util.number import getPrime
from Crypto.Util.number import bytes_to_long as b2l

def get_primes(bit_length):
    return getPrime(bit_length), getPrime(bit_length)

FLAG = b'CTFITB{*}'

p, q = get_primes(512)
n = p * q
e = 0x10001

ct = pow(b2l(FLAG), e, n)

tp = next_prime(p)
tq = next_prime(q)

leak = RealField(2048)(ZZ(tp)/ZZ(tq))
print(f'ct = {ct}')
print(f'e = {e}')
print(f'n = {n}')
print(f'leak = {leak}')

The output gives us:

where tp = next_prime(p) and tq = next_prime(q).

Analysis

Because tp and tq are just the next primes after p and q, we have

tp = p + Δp,   tq = q + Δq

where Δp and Δq are small prime gaps (typically on the order of log²(p)). Substituting into the leak:

leak = tp / tq = (p + Δp) / (q + Δq) ≈ p / q

So leak is an excellent approximation of p / q. Combined with n = p * q we can recover the factors:

p ≈ leak · q     and     n = p · q   ⟹   q ≈ sqrt(n / leak)

We compute q ≈ sqrt(n / leak), then search a small window around that estimate for the exact integer that divides n. Once we have p and q, RSA decryption is textbook:

φ(n) = (p − 1)(q − 1)
d = e⁻¹ mod φ(n)
m = ctᵈ mod n

Solution script

from sage.all import next_prime, RealField, ZZ

# Values from out.txt (truncated here)
ct = 9229995533077049076663819006507979028483850644581393807002652610474135173266...
e = 65537
n = 8219337357553566323507439596651371739519111787761764797257613250795921839516...
leak = RealField(2048)("1.4242443141467315872647656461032070506667095788432453981293820183900855547...")

# Step 1: initial estimate for q
q_approx = int((n / leak).sqrt())

# Step 2: find the nearest q that actually divides n
for q in range(q_approx, q_approx + 10000):
    if n % q == 0:
        p = n // q
        break

# Step 3: verify the factorization
assert p * q == n

# Step 4: private exponent
phi_n = (p - 1) * (q - 1)
d = pow(e, -1, phi_n)

# Step 5: decrypt
m = pow(ct, d, n)

# Convert back to bytes
flag = m.to_bytes((m.bit_length() + 7) // 8, 'big').decode()
print(f"Flag: {flag}")

The estimate lands within a few thousand of the real q, so the short trial-division loop recovers the factorization immediately and RSA decryption yields the flag.