UIUCTF 2025 - crypto/too many primes

This weekend, I looked at a couple cryptography challenges from UIUCTF 2025 hosted by SIGPwny. I wanted to quickly walk through an RSA challenge "too many primes."

We are given challenge code and a flavortext, "Normal RSA uses two primes - that's too few in my opinion, so I've added some more."

from sympy import nextprime, randprime
from sympy.core.random import seed
from math import prod, gcd
from Crypto.Util.number import bytes_to_long
# from secret import phi_N, FLAG

p = randprime(2**127, 2**128)
N = 1
while N < 2**2048:
	N *= p
	p = nextprime(p)

assert gcd(phi_N, 65537) == 1

pt = bytes_to_long(FLAG)
ct = pow(pt, 65537, N)
print("N = ", N)
print("ct = ", ct)
# N =  34546497157207880069779144631831207265231460152307441189118439470134817451040294541962595051467936974790601780839436065863454184794926578999811185968827621504669046850175311261350438632559611677118618395111752688984295293397503841637367784035822653287838715174342087466343269494566788538464938933299114092019991832564114273938460700654437085781899023664719672163757553413657400329448277666114244272477880443449956274432819386599220473627937756892769036756739782458027074917177880632030971535617166334834428052274726261358463237730801653954955468059535321422372540832976374412080012294606011959366354423175476529937084540290714443009720519542526593306377
# ct =  32130352215164271133656346574994403191937804418876038099987899285740425918388836116548661879290345302496993945260385667068119439335225069147290926613613587179935141225832632053477195949276266017803704033127818390923119631817988517430076207710598936487746774260037498876812355794218544860496013734298330171440331211616461602762715807324092281416443801588831683678783343566735253424635251726943301306358608040892601269751843002396424155187122218294625157913902839943220894690617817051114073999655942113004066418001260441287880247349603218620539692362737971711719433735307458772641705989685797383263412327068222383880346012169152962953918108171850055943194

My first thought is that this looks like normal RSA with a 2048-bit modulus, which isn't feasible to factor. However, the hint about “adding more primes” made me think. Reading the generation loop shows that it starts with a random 128-bit prime and repeatedly multiplies by the next prime until N crosses 2**2048. That means N isn’t the product of two large primes like normal RSA, but instead about seventeen consecutive primes, each roughly the same size and all clustered closely together.

You can approximate the smallest one by taking the 17th root of N, since multiplying seventeen similar-sized numbers is roughly equivalent to raising one of them to the 17th power. From there it's possible to brute force around that estimate. We check if the candidate is prime, generate the next sixteen primes, and verify if their product matches N.

Once the factorization is done, the rest is standard RSA. Compute φ(N) as the product of (p_i - 1) for each prime, calculate the modular inverse of e = 65537 to get d and decrypt the ciphertext.

Even though the modulus here is still 2048 bits, the structure makes it trivial to break.

solve script

from Crypto.Util.number import long_to_bytes, inverse

N = 34546497157207880069779144631831207265231460152307441189118439470134817451040294541962595051467936974790601780839436065863454184794926578999811185968827621504669046850175311261350438632559611677118618395111752688984295293397503841637367784035822653287838715174342087466343269494566788538464938933299114092019991832564114273938460700654437085781899023664719672163757553413657400329448277666114244272477880443449956274432819386599220473627937756892769036756739782458027074917177880632030971535617166334834428052274726261358463237730801653954955468059535321422372540832976374412080012294606011959366354423175476529937084540290714443009720519542526593306377
ct = 32130352215164271133656346574994403191937804418876038099987899285740425918388836116548661879290345302496993945260385667068119439335225069147290926613613587179935141225832632053477195949276266017803704033127818390923119631817988517430076207710598936487746774260037498876812355794218544860496013734298330171440331211616461602762715807324092281416443801588831683678783343566735253424635251726943301306358608040892601269751843002396424155187122218294625157913902839943220894690617817051114073999655942113004066418001260441287880247349603218620539692362737971711719433735307458772641705989685797383263412327068222383880346012169152962953918108171850055943194
e = 65537

root, exact = integer_nthroot(N, 17)
if not isprime(root):
    root = prevprime(root)

while True:
    primes = [root]
    for _ in range(16):
        primes.append(nextprime(primes[-1]))
    prod = 1
    for p in primes:
        prod *= p
    if prod == N:
        break
    root = prevprime(root)

phi_N = 1
for p in primes:
    phi_N *= (p - 1)

d = inverse(e, phi_N)
pt = pow(ct, d, N)
print(long_to_bytes(pt).decode())

flag

uiuctf{D0nt_U5e_Cons3cUt1vE_PriMeS}