Cyber Mimic Defense Quals 2025 CTF - Unsafe Parameters

Is having more n really safer? I have a bad feeling

task.py

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import sha3_512
from secret import *

def genParams():
    ns = []
    es = []
    ps = []
    d = getPrime(425)
    for _ in 'flag{':
        p, q, r = [getPrime(512) for _ in range(3)]
        ps.append((p, q, r))
        n = p * q * r
        totient = (p - 1) * (q - 1) * (r - 1)
        es.append(inverse(d, totient))
        ns.append(n)

    return (ns, es), (d, ps)

pub, priv = genParams()

key = sha3_512(str(sum(sum(psum) for psum in priv[1])).encode()).digest()[:16]
ct = AES.new(key, AES.MODE_ECB).encrypt(pad(flag, 16))

print(f'ns = {pub[0]}')
print(f'es = {pub[1]}')
print(f'ct = {ct}')

"""
ns = [7296263645762064..., ]
es = [2712649737283172..., ]
ct = b'J\x08\x0c\xfe\x0eC\n\x96!\xb3\x05\xa9\x9b\xf9\n\xe3-\xf2m\xdb&.\xb5h\xe1\x0e\xd6\x89\x14\x87Z\x0b0p\xbb\xd9\x93\xd7\x1cT\xa2\xf36\x02\x8e:\\\x92'
"""

The challenge

In this challenge, we have an multi-prime RSA setup where the private exponent d is common across five different moduli.
d is a 425 bit prime number.
For each moduli, its corresponding public exponent e is calculated as $pow(d_i, -1, phi)$
where $phi$ is $(p-1) (q-1) (r-1)$
We are given the list of N and e values.
The flag is encrypted with the sum of all primes for all moduli and an AES key is derived from its hash to encrypt the flag.

Solution

A quick google search helped me find this paper: ‘Common Private Exponent Attack on Multi Prime RSA’

In it, the lattice mentioned below is constructed with the N and e values. Running LLL on this lattice gives us a short vector $v_n$, where the first value is the product of d and M. $M = N_n^{1-1/r}$ Where $N_n$ is the largest N among the set and $r$ is the number of primes in the modulus.

RR_high = RealField(200
M = floor(RR_high(ns[-1]) ** (RR_high(2)/3))
print(f"M = {M}")

mat = Matrix(ZZ, 6, 6)
mat[0, 0] = M
for i in range(5):
    mat[0, i+1] = es[i]
    mat[i+1, i+1] = -ns[i]

reduced = mat.LLL()

for row in reduced:
    b = row[0]
    d = int(abs(b)/ M)
    if d.bit_length()==425 and isPrime(d):
        print(row)
        print(f"Recovered d: {d}")
        break

I got this particular vector in the reduced basis (after running LLL)

(12250680517548692673411332455628451315725265633083374063454908834464509499393601500141632491786811127752973220061490408924980677170123738304956286616151158958194691874384365019277886399844855655731317945818177431929207700728668128124299731686874090698917637005507895274483338232637217819385463510611136588919633396138647106376176896610083968400119032926756495227978618259958047588007162951430339883567063256610140469473947666683996930048, -7225120759751547423091271813691828793088572650495920365187734864423659776227862049671265355020973838808385052854224462806634895578408256283786165562219714269698559801217599777198657597560471843974618013456786206777430404697255876532487853352232212174830063035765328572738808378124921967684560621230729193819115710961551881323985964153793229673989178458383904809049286274490906781963014065785442241150515316316789025242047279664781231474, -1624508364043092226331807786641127820687740678229974560551374262622397258195738774720140562575985596927551318740322860863641614551249550081142192923002825056700804615094581445385124536349026110059671839885990944481007411143129824747767798889802188225470933863884133773783280773995398007792458382072625478592552509400369252306729954038315036496253615288576041503193544358635270145022001132607473628698978069014894873009281889919279218641, -2995998493187476994103851252147470760308670891170399010457187157313184798652486565263540900594664260174403475992823396008808247923664787128113441265503449107470907797918582749682214383865199289958769184835951188650527786719597237148408645464051135943296489731167929577944204486811704102391220316926301044118098625071378993619810290070034324107225032652852661163983876005071554811715699159340083606910122989542901826331167852600410247770, -11487278321710934976817512755703251250789595566291929803005518263458282372940369730884459421154068010949108465281639752097727428091990716559017476852832138212211723773704365501672540635904556891487350141744940434263501023592361298320001558640815871231657468209282746055092753452045115810360427193877471012735642370209809674662272496270256436902112124045633640112807879847176812827138791219754716955978783772019781509240519786934653417557, -19369940653230739886936172171456599319175125527099036695461960590314805657455093494772390451303893767758391902490257851976419773187571976551404120780649347409158004449051702986785476545276164345626965692557596438388398057871159973299787689482936649205710197717904860109197671157040057747832500418044444228238264229626743746333568045589358817928091710411912275498770494830629671897805186732944875802435942645951330069701411546959766677219)

GCD of the first value with M, gave me M which confirms that this vector is the one I am looking for. Therefore, d = 79707249059210800427586261608616662408613108106616463837006013556788454508274558925787023296092333364088239266520329780878389357 this is a 425 bit prime.

Now, given d, the task is to factor all the $N_i$ s to and add them up to derive the AES key.
I used the approach mentioned in this webpage:

I had to modify this algorithm to account for the fact that 3 primes make up each N. This involved dividing N by each recovered prime and starting the algorithm over again until we factor N completely.

def factorise_n_given_d(d,n,e,r):
    k = d*e - 1
    factors = []

    while True:
        g = randint(2,n-1)
        t = k
        while t % 2 == 0:
            t //= 2
            x = pow(g,t,n)
            y = gcd(x-1,n)
            if x > 1 and y > 1:
                if is_prime(y):
                    factors.append(y)
                    n //= y
                else:
                    factors.append(n//y)
                    n = y
                if len(factors) == r-1:
                    factors.append(n)
                    return factors

Flag

flag{9b31dd3e-aa6a-4c4d-b796-bff4e4dfe0cc}

Solve Script

from hashlib import sha3_512
from sage.all import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Util.number import isPrime

ns = [729626364576206469704240917876675932841677846807662743683194531189219993605123671836962855605283722577718230552963049472251011326675202612492908848548419883361685662678347011887752523869081347313358470192291106167923273619672010347904232948623232956703976722596246251219832472749781700661621717970912452690860710243752051416797956410009096107757901714990018414837758557784033898837218196380413347278999394220278929595840196278059116531409774355756772349502091527, 1905432596115201099512716986634374621489368222604315919606798930577721863294916275385323430940054377575273762764157350871093106918016952598143825002497857813393515175754983371150373414986745909170502391681896252141058196242286758315439213464335711981585004206505072743627148478873299089587473670712150938286701206231734068594554186483978059254161949801153805752489828395472590106405761648181381945795038085612905557546907903561767813822101495476457137965288880829, 1364349980724204783960363890369037262456777329397270902364257972605993939460160766530889520645888701966401869980072151818996346007664249855901114579605632358191242379651843548926065735575249122023543206153088606751338328933651430885645444839242513718915066302971957689904414300766000572990594260836480347717506097403302570129593533017205416936506156113683938133811098995666977893386015199252455279325252257306124895958614122639652100229863446635612470942945471629, 801368910415539931617837996119032301790585643652894417707002521182569449104238101253556548156062846942011258499343192564944616333555000780965111384091131074358231330717413121484815002612991437436336271715078003900216545055505405363415778086330672269759661284535787363323398929120499505051378299467980018690275341014026390376705451595348674549031968858607633947674244014656615045639930798213161815130251215148286379903187335369475976106390101774566278602818405563, 966507016385573035667733231340091844033410158675175976938028218854439065352997895173668326599042719776214706325758565722305289931861889759808022284179479582700755314576250841330755684569639628012527976286442288571350327307582007959428925460653350857512795573323486273071975979456828134582982048746188934676698845075430701350305713747666370252912970653968385390246217234899448990236850880873105998296512557366752267827688836849041157572772272378435636367162425013]
es = [271264973728317298627822473902975461834475616151421882685140849409171660245987005602120200976835072966082573357282000859946014645129524701781302678299643424924092704444611429422064341444927220441684375194952864825982915148126084102832224731498348832396834993134927447743362540828447462072582023959357845229307404791804881057335208287771899121154533179273274029972648764343120454360366227609296867085751393693129946684282269737380796082741762647814800935844443493, 1003585299728442138241618739786172474341836074346983356412903232651178484164007865852681323340512406956827176253325249434459143223478630158795320316445722303141000749369087588146876087005139101967705654538148200848735795226715484701026716263131990473014248826031226350016169675911701420383849573743077161936130739955632072650333006768068396767746102320645544271946493533626477749495460960365939362830334782483616521427745117179433129272929291131199903349977861093, 528794486797786998573050589647661205854628331390578568482905276781799068613879068393786314280307765489986817827366340249545226369795434498075653554440390174127680889163962386407937584138342055553885382937486807537913781141805602397908008361192107987266566035872632130183102501118938531330140154852996630732644530954025739132771439783366022539476194754352734861357158197716623228211860189868592877935421689151152269864018399507621324672725433395533000425391708101, 63082374875671578481986217433413118060930080658278695174993640397998104913203950822096713822227514918774669078130439943184022889683633824002111416144422250644695809731240622289790840695469043596475009958463780096705571401137513331089894183226911665633164170027318352120002851940432163291498705806239158684141492080194438572549164494596965748695244152843943149994989589419519395650481254722496058552304954140980743159877918387972030837603120258130045817858729621, 120373323462979513980656435521004077312964483601298713849302793507801996545855844801219890178210569842943901523332883574699699439655256681068585396438543716728771762620808023696864023456625376138578749985774885652016790204471223404504866831356254849552890279653807176865165230965065842479979722094076544915080001416276324550993965426099480075249719779502220020343237480355441663501565965298776708377675024327374331823503627493136287447543537154779812201209689733]
ct = b"J\x08\x0c\xfe\x0eC\n\x96!\xb3\x05\xa9\x9b\xf9\n\xe3-\xf2m\xdb&.\xb5h\xe1\x0e\xd6\x89\x14\x87Z\x0b0p\xbb\xd9\x93\xd7\x1cT\xa2\xf36\x02\x8e:\\\x92"

paired = sorted(zip(ns, es))
ns, es = zip(*paired)
ns = list(ns)
es = list(es)

RR_high = RealField(200)
M = floor(RR_high(ns[-1]) ** (RR_high(2)/3))

mat = Matrix(ZZ, 6, 6)
mat[0, 0] = M
for i in range(5):
    mat[0, i+1] = es[i]
    mat[i+1, i+1] = -ns[i]

reduced = mat.LLL()

for row in reduced:
    b = row[0]
    d = int(abs(b)/ M)
    if d.bit_length()==425 and isPrime(d):
        print(f"Recovered d: {d}")
        break

def factorise_n_given_d(d,n,e,r):
    k = d*e - 1
    factors = []

    while True:
        g = randint(2,n-1)
        t = k
        while t % 2 == 0:
            t //= 2
            x = pow(g,t,n)
            y = gcd(x-1,n)
            if x > 1 and y > 1:
                if is_prime(y):
                    factors.append(y)
                    n //= y
                else:
                    factors.append(n//y)
                    n = y
                if len(factors) == r-1:
                    factors.append(n)
                    return factors

primes = []
for i in range(5):
    primes.extend(factorise_n_given_d(d, ns[i], es[i], 3))

key = sha3_512(str(sum(primes)).encode()).digest()[:16]
flag = AES.new(key, AES.MODE_ECB).decrypt(ct)
flag = unpad(flag,16).decode()
print(flag)

References

1. http://ijeie.jalaxy.com.tw/contents/ijeie-v7-n2/ijeie-2017-v7-n2-p79-87.pdf
2. https://di-mgt.com.au/rsa_factorize_n.html