You are given an RSA modulus n, public exponent e = 65537, and ciphertext c which is the encryption of a secret flag. However, instead of a standard product of two large primes, the generator code builds n by multiplying together many small primes (10–16 bit), each raised to a small random exponent (2–5):
n = 1
while n.bit_length() < 4096:
i = random.randint(10,16) # prime size in bits
reps = random.randint(2,5) # exponent
p = getPrime(i)
if n % p != 0:
n *= p**reps
The flag is encoded as an integer m = bytes_to_long(flag), then encrypted by
c = m**e mod n
Because n factors into many small primes (each ≤ 16 bits) with small exponents, it can be factored instantly.
Once we have the full factorization
n = ∏ pᵢᵉⁱ
we can decrypt via the following strategy:
Local decryption modulo each prime power
For each factor pᵉ, compute
φ(pᵉ) = pᵉ – pᵉ⁻¹
dᵢ = e⁻¹ mod φ(pᵉ)
mᵢ = cᵈⁱ mod pᵉ
Reconstruct the full message Apply the Chinese Remainder Theorem (CRT) on the congruences
m ≡ mᵢ (mod pᵉ) ∀ factors pᵉ
to recover m mod n, which since m < n is exactly the flag.
Load parameters and factor n.
Use a fast integer‐factorization library to get a dictionary of {p: exponent}.
from sympy import factorint
factors = factorint(n)
For each prime power, compute local decryption.
from Crypto.Util.number import inverse
recovered = []
mods = []
for p, exp in factors.items():
pe = p**exp
phi = pe - p**(exp - 1)
d = inverse(e, phi)
# decrypt c modulo p^exp
m_i = pow(c % pe, d, pe)
recovered.append(m_i)
mods.append(pe)
Combine via CRT.
from sympy.ntheory.modular import crt
flag_long, _ = crt(mods, recovered)
Convert back to bytes and print.
from Crypto.Util.number import long_to_bytes
flag = long_to_bytes(flag_long)
print(flag.decode())
from Crypto.Util.number import inverse, long_to_bytes
from sympy import factorint
from sympy.ntheory.modular import crt
# Given values (paste n, e, c here)
n = 84957339878841249042661992015318775914153057891067549723671982778975957526984361748735670333426792012519248099265537115315835602057882318543112781196438953840653279029957533208045448649312183873062132255928109150470090982541502003013666939934181439934181416473581073990221728448342533549843710383544743220364127453679761909368982493089369740815066106196444062558446312836612656666434089655206650558129894180991572670565328419648196602807190683488653617068325238542193033423978598565191919683033996144778397817249870630736098769732268174866389943010980427234356604782502318622853423388492983406635687647680770869588481426436811952986075832678887752706507835771052708232550208582584262345437818916577580806059662945066377375408508814381061305598911972399165132279018674832071994673661875185328115121586302490349253912699566783660070599552395205352917554104371784905394477629626963439266490743240318198729049054547013391348516066097465180775402810975266096525722415778248668765855332776864126033830969325570615444114396786906102536716873598804164196155179833683285635189223166238933318740720918827120989416013091102543382987278707392961157272937695585450287755023671116911370689655292160336521776501052329465384315585357461493649222793172462113102463
e = 65537
c = 451467878285576791404235802214429569253109773711090918534628431778262944423526345801603109891522352972355141416588813909085924706837952458706193199834519045371927818238556780860886634058725269800849600081838312880449603496051681734903678943757577874520242879899933629542062868531904015416065187313178140188174911091773607618594530027928998649844885248640287662394976410489195654582817654879323243967025800260947461894"
# 1. Factor n into {p: exp}
factors = factorint(n)
# 2. Decrypt each prime‐power component
recovered = []
mods = []
for p, exp in factors.items():
pe = p**exp
phi = pe - p**(exp - 1)
d = inverse(e, phi)
m_i = pow(c % pe, d, pe)
recovered.append(m_i)
mods.append(pe)
# 3. Reconstruct m via CRT
flag_long, _ = crt(mods, recovered)
# 4. Convert to bytes
flag = long_to_bytes(int(flag_long))
print(flag.decode())
byuctf{3ulers_ph1_function_15_v3ry_us3ful_4nd_th15_I5_a_l0ng_fl4g}