Writeups for USC CTF FALL 2024

In this CTF, i solved 2/4 chals which is some basic theorem in RSA and Diffie-Hellman but there something new to me. That confused me a little bit in coding the sol chals(i know the theory but i am so noob at coding SAGE lol.)

D’ LO

Challenge code:

from Crypto.Util.number import *

FLAG  = b"REDACTED"

p = getPrime(256)
q = getPrime(256)
e = 7
n = p*q
d = int(pow(e, -1, (p-1)*(q-1)))

c = pow(bytes_to_long(FLAG), e, n)
print(f"n = {n}")
print(f"c = {c}")
print(f"d_low = {hex(d)[70:]}")

"""
n = 9537465719795794225039144316914692273057528543708841063782449957642336689023241057406145879616743252508032700675419312420008008674130918587435719504215151
c = 4845609252254934006909399633004175203346101095936020726816640779203362698009821013527198357879072429290619840028341235069145901864359947818105838016519415
d_low = b9b24053029f5f424adc9278c750b42b0b2a134b0a52f13676e94c01ef77
"""

Problem: Common RSA ctf chals but we have 240 bits leak of private key’LSB.

Solution: We use theorem 9 and 10 in this paper to solve this shit. Just read it and do it.

from Crypto.Util.number import *
from sage.all import *
N = 9537465719795794225039144316914692273057528543708841063782449957642336689023241057406145879616743252508032700675419312420008008674130918587435719504215151
c = 4845609252254934006909399633004175203346101095936020726816640779203362698009821013527198357879072429290619840028341235069145901864359947818105838016519415
leak = int("b9b24053029f5f424adc9278c750b42b0b2a134b0a52f13676e94c01ef77",16)

t = leak.bit_length()
e = 7


for k in range(1,e + 1):
    p = var('p')
    f = e*leak*p -k*p*(N - p + 1) + k*N - p
    result = solve_mod([f==0], 2**t)
    for root in result:
        root = ZZ(root[0])
        p_hi = PolynomialRing(Zmod(N),'p_hi').gen()
        k = p_hi*2**t + root
        k = k.monic()
        roots = k.small_roots(X=2**(16), beta=0.49)
        if roots:
            p = int(roots[0]*2**t + root)
            q = N//p
            phi = (p-1)*(q-1)
            d = inverse(e,phi)
            m = pow(c,d,N)
            print(long_to_bytes(int(m)).decode())
# b"CYBORG{H0w_w3ll_d0_y0u_th1nk_d'lo_w1ll_d0_7h15_53ason??}"

It’s Not Called Data Loss Prevention

Challenge code:

from Crypto.Util.number import *

p = 72582273207584409523836416205503873456840672244861668902068962428022358668644213717033410220094858213785909158082084409697781833525734642650576180002727864094178853739590888445753712196268567738582111704293273201721006648707008913242412196989487167851968618303659742648153352883917176492356546118351747721810800909873736282570227177961197335450387989276806079489
g = 3
FLAG = b"REDACTED"
a = pow(g, bytes_to_long(FLAG), p)
print(a)

"""
24393771488717960431147269064624631828310604373526026598603386491263061338072489803153972728250242949112187407825532440328751180404635401465476512488685185622725060580628770654048867200033806585934697471249921972700552978079752695585970921337459580789152970187925768085334409084092041192304935279345047595337816976845617649400223935358270007572542969925561362228
"""

Problem: Diffie-Hellman chal but p - 1 factors are smooth except last factor which is around 220 bits which is infesible to discreate log.

Solution: Luckily, the flag is smaller than subgroup’s order when we remove the last factor so we can solve this by using polig hellman. Check out this wiki for more information.

p = 72582273207584409523836416205503873456840672244861668902068962428022358668644213717033410220094858213785909158082084409697781833525734642650576180002727864094178853739590888445753712196268567738582111704293273201721006648707008913242412196989487167851968618303659742648153352883917176492356546118351747721810800909873736282570227177961197335450387989276806079489
g = 3
a = 24393771488717960431147269064624631828310604373526026598603386491263061338072489803153972728250242949112187407825532440328751180404635401465476512488685185622725060580628770654048867200033806585934697471249921972700552978079752695585970921337459580789152970187925768085334409084092041192304935279345047595337816976845617649400223935358270007572542969925561362228
order1 = p - 1
factors = [2**10, 787**4, 32587**3, 708667**7, 19964029**6, 856892137**2, 1279562789201591523940850597505137258079950871699945159663662131835076279131726053889024495522041177924458398143694947568877887370555653768499066503948935672363148134562050374459082232131445656948264915239888005511288832804262243257]
from sage.all import *
 

K = GF(p)
res = []
for i in factors[:-1]:
    g_i = K(pow(g, order1 // i, p))
    a_i = K(pow(a, order1 // i, p))
    order = ZZ(i)
    x = discrete_log(a_i, g_i, ord=order)
    res.append(x)
b = crt(res, factors[:-1])
from Crypto.Util.number import *
print(long_to_bytes(b).decode())

#CYBORG{p0hl1g_h3llm4n_f7w!!}