nomnom

An archive of all my CTF writeups

View on GitHub

UIUCTF 2022 - asr Challenge Writeup

Description

Oh no I dropped my d. Good thing I’m not telling you my n.

Challenge Source Code

from secret import flag
from Crypto.Util.number import bytes_to_long, getPrime, isPrime
from math import prod

small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
def gen_prime(bits, lim = 7, sz = 64):
    while True:
        p = prod([getPrime(sz) for _ in range(bits//sz)])
        for i in range(lim):
            if isPrime(p+1):
                return p+1
            p *= small_primes[i]

p = gen_prime(512)
q = gen_prime(512)
n = p*q
phi = (p-1)*(q-1)
e = 0x10001
d = pow(e, -1, phi)

msg = bytes_to_long(flag)
ct = pow(msg, e, n)

print("e = ", e)
print("d = ", d)
print("ct = ", ct)
'''
e = 65537
d = 195285722677343056731308789302965842898515630705905989253864700147610471486140197351850817673117692460241696816114531352324651403853171392804745693538688912545296861525940847905313261324431856121426611991563634798757309882637947424059539232910352573618475579466190912888605860293465441434324139634261315613929473
ct = 212118183964533878687650903337696329626088379125296944148034924018434446792800531043981892206180946802424273758169180391641372690881250694674772100520951338387690486150086059888545223362117314871848416041394861399201900469160864641377209190150270559789319354306267000948644929585048244599181272990506465820030285
'''

Understanding The gen_prime Function

As we can see, the function generates 512//64 = 8 64-bit primes, takes the product of all of these primes and stores the result in p. Then there’s a loop that runs 7 times and each iteration of that loop there’s a check for whether p+1 is a prime, if it is then the function returns p+1, and if it isn’t then p keeps on getting multiplied by small_primes[i] where i is the iteration number of the loop.

What we can conclude from this is the following:

Writing The Solution

The rest of the source code is really easy to understand. We see that we are given d, e, ct. We can use this information to find p and q. We know that d*e = 1 (mod ϕ(n)) so in other words, d*e = 1 + k*ϕ(n) which means d*e - 1 = k*ϕ(n). By defintion, ϕ(n) | (d*e - 1). Since we can calculate d*e - 1 and it is fairly smooth, we can factor d*e - 1. The product of some combination of the factors will give us p-1, and from our conclusions about the gen_prime function we know that p-1 consists of 8 64-bit prime numbers. After factoring d*e - 1, we find that there are 16 64-bit prime numbers which means that the product of some combination of 8 of them is equal to p-1 and the product of the other 8 is equal to q-1. Realizing that, the solution becomes trivial. We just have to brute force some combination of 8 primes, maybe multiply in some small primes as well until p+1 is prime. Then we take the other 8 64 bit prime numbers and do the same thing we did to find p-1; that will give us q-1. after getting p-1 and q-1 the challenge basically becomes a simple textbook rsa problem.

Solver Script:

from math import gcd, prod
import itertools

def isPrime(n, k=5):
    from random import randint
    if n < 2: return False
    for p in [2,3,5,7,11,13,17,19,23,29]:
        if n % p == 0: return n == p
    s, d = 0, n-1
    while d % 2 == 0:
        s, d = s+1, d//2
    for i in range(k):
        x = pow(randint(2, n-1), d, n)
        if x == 1 or x == n-1: continue
        for r in range(1, s):
            x = (x * x) % n
            if x == 1: return False
            if x == n-1: break
        else: return False
    return True

e = 65537
d = 195285722677343056731308789302965842898515630705905989253864700147610471486140197351850817673117692460241696816114531352324651403853171392804745693538688912545296861525940847905313261324431856121426611991563634798757309882637947424059539232910352573618475579466190912888605860293465441434324139634261315613929473
c = 212118183964533878687650903337696329626088379125296944148034924018434446792800531043981892206180946802424273758169180391641372690881250694674772100520951338387690486150086059888545223362117314871848416041394861399201900469160864641377209190150270559789319354306267000948644929585048244599181272990506465820030285

kphi = d*e - 1
kphi_factors = []

#16 64-bit prime factors
kphi_factors.append(10357495682248249393)
kphi_factors.append(10441209995968076929)
kphi_factors.append(10476183267045952117)
kphi_factors.append(11157595634841645959)
kphi_factors.append(11865228112172030291)
kphi_factors.append(12775011866496218557)
kphi_factors.append(13403263815706423849)
kphi_factors.append(13923226921736843531)
kphi_factors.append(14497899396819662177)
kphi_factors.append(14695627525823270231)
kphi_factors.append(15789155524315171763)
kphi_factors.append(16070004423296465647)
kphi_factors.append(16303174734043925501)
kphi_factors.append(16755840154173074063)
kphi_factors.append(17757525673663327889)
kphi_factors.append(18318015934220252801)


all_combinations = []
for i in itertools.combinations(kphi_factors,8):
    all_combinations.append(i)
small_primes = [2, 3, 5, 7, 11, 13, 17]

product = prod(kphi_factors) # product of the 16 64-bit prime factors

for sets in all_combinations:
    p=1
    saved = 1
    for j in sets:
        p *= j
    saved = p # saving p before multiplying in the small primes (used to find q)
    if not isPrime(p+1):
        for j in small_primes:
            p*=j
            if isPrime(p+1):
                break
    if not isPrime(p+1):
        continue
    q = (product//saved)
    if not isPrime(q+1):
        for j in small_primes:
            q*=j
            if isPrime(q+1):
                break
    if not isPrime(q+1):
        continue
    p=p+1
    q=q+1
    phi_n = (p-1)*(q-1)
    if gcd(e, phi_n) == 1 and p*q != 0:
        n = p*q
        flag = hex(pow(c,d,n))[2:]
        flag = ''.join(chr(int(flag[i:i+2],16)) for i in range(0,len(flag),2))
        if 'ctf' in flag:
            print(flag)

flag: uiuctf{bru4e_f0rc3_1s_FUn_fuN_Fun_f0r_The_whOLe_F4miLY!}