too many primes

Tags

We are given a file named chal.py:

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

So bacically we are given an RSA-like cryptosystem where the modulus N is constructed by multiplying multiple consecutive primes, starting from a 127-bit prime. The public exponent is the standard e = 65537, and we are provided with the ciphertext ct.

Observations

Modulus Construction:

N is built by multiplying consecutive primes starting from a random prime p in the range [2^127, 2^128).
The multiplication continues until N reaches at least 2048 bits in size.

Prime Count Estimation:

Since (2^127)^17 ≈ 2^2159 (which is greater than 2^2048), and (2^127)^16 ≈ 2^2032 (which is less than 2^2048), we deduce that N is the product of 17 consecutive primes.

Factoring Strategy::

Given that N is the product of 17 consecutive primes, we can estimate the approximate value of the first prime by taking the 17th root of N.
We then search for the exact starting prime within a reasonable range around this estimate.

Strategy

Estimate the Starting Prime:

Compute the integer 17th root of N to get an approximate value for the first prime.
Define a search window around this estimate (e.g., ±10000) to find the exact starting prime.

Find Consecutive Primes:

For each candidate prime in the search window, generate the next 16 consecutive primes.
Multiply these primes together and check if the product matches N.

Compute Euler’s Totient Function:

Once the primes are found, compute phi(N) as the product of (p_i - 1) for each prime p_i.

Derive the Private Key:

Compute the modular inverse of e modulo phi(N) to get the private exponent d.

Decrypt the Ciphertext:

Use the private exponent d to decrypt the ciphertext ct and recover the plaintext flag.

Solver

from sympy import nextprime, isprime, integer_nthroot
from math import prod
from Crypto.Util.number import long_to_bytes

N = 34546497157207880069779144631831207265231460152307441189118439470134817451040294541962595051467936974790601780839436065863454184794926578999811185968827621504669046850175311261350438632559611677118618395111752688984295293397503841637367784035822653287838715174342087466343269494566788538464938933299114092019991832564114273938460700654437085781899023664719672163757553413657400329448277666114244272477880443449956274432819386599220473627937756892769036756739782458027074917177880632030971535617166334834428052274726261358463237730801653954955468059535321422372540832976374412080012294606011959366354423175476529937084540290714443009720519542526593306377
ct = 32130352215164271133656346574994403191937804418876038099987899285740425918388836116548661879290345302496993945260385667068119439335225069147290926613613587179935141225832632053477195949276266017803704033127818390923119631817988517430076207710598936487746774260037498876812355794218544860496013734298330171440331211616461602762715807324092281416443801588831683678783343566735253424635251726943301306358608040892601269751843002396424155187122218294625157913902839943220894690617817051114073999655942113004066418001260441287880247349603218620539692362737971711719433735307458772641705989685797383263412327068222383880346012169152962953918108171850055943194

m = 17
root, exact = integer_nthroot(N, m)
print(f"Root: {root}")

low = max(2**127, root - 10000)
high = root + 10000
print(f"Search window: {low} to {high}")

p0 = low
if p0 % 2 == 0:
    p0 += 1
found = False
factors = []

while p0 <= high:
    if isprime(p0):
        product = 1
        factors = []
        p = p0
        for i in range(m):
            factors.append(p)
            product *= p
            if product > N:
                break
            if i < m-1:
                p = nextprime(p)
        if product == N:
            found = True
            print(f"Found factors starting at {p0}")
            break
    p0 = nextprime(p0)

if not found:
    print("Factorization failed.")
    exit(1)

phi = 1
for p in factors:
    phi *= (p - 1)

e = 65537
d = pow(e, -1, phi)
pt = pow(ct, d, N)
flag = long_to_bytes(pt)
print(flag)

Output:

Root: 242444312856123694689611504831894231744
Search window: 242444312856123694689611504831894221744 to 242444312856123694689611504831894241744
Found factors starting at 242444312856123694689611504831894230373
b'uiuctf{D0nt_U5e_Cons3cUt1vE_PriMeS}'

too many primes Flag: uiuctf{D0nt_U5e_Cons3cUt1vE_PriMeS}