babyRSA

lol
author: hadnot
18 solves

First crypto from grey finals, I blooded this as the first solve of the comp lmao

babyrsa.py

from Crypto.Util.number import bytes_to_long, getPrime, isPrime

with open("flag.txt", "r") as f:
    flag = f.read().encode()

assert(len(flag) == 48)

def gen_safe_prime():
    while True:
        p = getPrime(256)
        q = 2*p + 1
        if isPrime(q):
            return p,q

p, P = gen_safe_prime()
q, Q = gen_safe_prime()
r, R = gen_safe_prime()

N1 = p*Q
N2 = q*R
N3 = r*P

e = 0x10001

flag = flag[:16], flag[16:32], flag[32:]
m1, m2, m3 = map(bytes_to_long, flag)

c1 = pow(m1, e, N1)
c2 = pow(m2, e, N2)
c3 = pow(m3, e, N3)

print(f"N1 = {N1}")
print(f"N2 = {N2}")
print(f"N3 = {N3}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")
print(f"c3 = {c3}")

#N1 = 12495068391856999800077002030530346154633251410701993364552383316643702466683773454456456597802923936206937481367758944533287430192110874917786936470363369
#N2 = 8077707147198053886290544832343186898331956960638623080378558119874814319984246411074010515131637149736377313917292767376808884023937736055240325038442951
#N3 = 10898848501176222929758568549735934974173617359760346224710269537956982757903808181573409877312658404512178685311838325609151823971632352375145906550988157
#c1 = 11727185096615670493479944410151790761335959794363922757994065463882149941932060937572492050251349085994568934453243128190891922383731914525051578359318783
#c2 = 2327979828535262192716931468063741561142276160684415064469817644730647222015445750643448615540518244828488228477943010970450757391003276726177736335376022
#c3 = 4544692061471147250554940137677403449389851357903927336833646427737782533445020327768883285489907725322030741572216172954958842207101301502851102081477126

So $p, q, r$ are primes generated such that $2p+1, 2q+1, 2r+1$ are also prime. Then, the flag is split up into three segments, and each one is encrypted with RSA with moduli $p(2q+1), q(2r+1), r(2p+1)$. The instasolve is just z3.

solver = z3.Solver()
p = z3.Int("p")
q = z3.Int("q")
r = z3.Int("r")
solver.add(p*(2*q+1)==N1)
solver.add(q*(2*r+1)==N2)
solver.add(r*(2*p+1)==N3)
solver.check()
solver.model()
# [r = 59354006955050413613870498562109333667808649546777985016017887869485489005019, p = 91812238636475438242501026992766637917068104247851477367725195205999180512451, q = 68046856156783230865426295103370139965710038400513223000658211481103876983409]

Then just standard RSA decrypt

from Crypto.Util.number import long_to_bytes as ltb
r = 59354006955050413613870498562109333667808649546777985016017887869485489005019
p = 91812238636475438242501026992766637917068104247851477367725195205999180512451
q = 68046856156783230865426295103370139965710038400513223000658211481103876983409

t1 = (p-1)*2*q
t2 = (q-1)*2*r
t3 = (r-1)*2*p
e = 0x10001
d1 = pow(e, -1, t1)
d2 = pow(e, -1, t2)
d3 = pow(e, -1, t3)

ltb(pow(c1, d1, N1)) + ltb(pow(c2, d2, N2)) + ltb(pow(c3, d3, N3))

Giving the flag grey{3_equations_3_unknowns_just_use_groebnerXD}. Sorry boring sol