Multi ﾊﾟﾜｰ RSA Full Week Engineering CTF 2025
- 4 mins read
Challenge Description
Source code
Chall
from sage.all import *
from Crypto.Util.number import *
import gmpy2
import random
from sympy import nextprime
FLAG = b'fwectf{REDACTED_REDACTED_REDACTED}'
m = bytes_to_long(FLAG)
r = random.randint(5, 30)
p = getPrime(256)
q = getPrime(256)
if p < q:
p, q = q, p
N = pow(p, r) * q
phi = pow(p, r - 1) * (p - 1) * (q - 1)
e = 65537
c = pow(m, e, N)
print(f'c = {c}')
print(f'e = {e}')
print(f'N = {N}')
d1 = getPrime(2000)
d2 = nextprime(d1 + getPrime(1000))
e1 = gmpy2.invert(d1, phi)
e2 = gmpy2.invert(d2, phi)
print(f'e1 = {e1}')
print(f'e2 = {e2}')
Output.txt
c = 150585797027649865489287786588283519376444271481829451206461043013638461851456443295639137583076309442211685140040715015672365662062445178352437695738282641956247465007835614325215320828570574978027697247110122408959329602493024795984675855072829968568063483443564884590062240635887431125362354037916695863432044462478632010854829416594987121310115447040797978156754180611417998692235678830822995195693412798239945582015522540243621848514340825137784617038883681762243778481350214509050715611993272169019595988822536735533532328109537622265977681155970778571399007023021359255926523887958105866659589793221135086136634321526143644058657686559455390271432068714110879919249854512706311908215475720874421301327375628026151554425480889625476443996963226739224141229051215116294621373720061550447360540466603611877916643506521674077637662746353412174577577517713229695736915310128634392507257018082205528441763251409689312355800240394928915067047489667210410718244921919018887791400482889355718347742440819608756821762567978878895290820251733297461964155473495597853211579186825851137994290776971434620034797987966563429453923909529541320143776397669267613997300604747811315937419659086723279726826646032780534551617458772078374711989147497752615265133572176138301527850632921359443303144256863024531079818868821758707284519856822245327421770110054277128452078605253184196998977317191651032204260679733274112559665428206212555513334541342029165221468784610288416686450162503789244926494714898635616996486140153083238632042007797793700563323218257129418795358543031202313561185588455593386153322727840291176790523913519542549216392301233455213647649027484109309089206606335520666724332245092640179790951481672640009520232615798668179089441370616468610644268539377884248767999193537928526046999022147158284677984579677312334741055670888654273143019369722889958102904924117413980953194821337321878279459444456391516721152204499246038472658108777670283734288457011883626451484055732662043231790974669769949105126075064121602546376952003206428494498829916276757539596132583838525916520286113969608190165961798389572158151878875500492540747108296198243292566008234833
e = 65537
N = 186468293083788781245499353512563129672312798029703904462936796596026120571080426862373632093518207360391666952453308555988614378903855020162320651304963730462668109416515599034788196838330392323014227902075936472408096760922362616639831532722796773044161215603161573173693396763848532916596270542508246600865336824042340247413113147406841036910189001075097670228541035790259078800598326610948022398352585923649531112759445985740346135428877322273556322542215020775992731058099305658619025609383729517239811673596072211108962991986901295709256060275331345666057130911453857078541419835856196753136664547254360862900351337626911283810534959854452952272035002742600178127259539214115953749657961050280108421405551206427544090699506875821129502984234774688377256310602196702176007042636404063776926466585683290760236194258669323601484216988981113466416405284959939812524546732701485183931884838692814562595191552224757937077488587067020793692692549938889591330072594717978441992795102999379303433207854356430437846345643266409739062915660544094498466397963646286252575273661019638807620280311533417717322466737567313846948246565804965079064097678541329903335139345823245801485851723772625368820657081414997271906611200756811167771754039199663511386284954358869993716532869728924931127279616476581118702229755968849120582675066084548348641091550633395996908836876499056736123107365637770245726218450365257927541692911169875941639963606762719472741281838412109552457222110661735681401203267804449363273688233013042050750830535778904458171623334164553955827238989238553731488016772701812203067882783550639709170454593937643386446256536119770989304864520889045556071269357480411824619830061505470986036143575914439137724990710287384145813135368196679314377112131761811940172598300544938844479133061210634426452190259178180635554381170513818865646521472300868854934387822644776013828828533387245770709879233807065640965155395836324727727247566385145338896343366468455003789992017616034872629717115885307603763663604867417148970196011250152501225642510419108907592141672752218085088428240372007994449852792767351434018043118658591114512322934390623465185608109909287
e1 = 41580201693720582480693330964943873953272761954440070167783695980849492986662882513949168242004211132670119356752908751569637864785219861514846064298150109789186060860480552700920272463488413243406347872787482976412247245447832054401920594283666788061207365372191406054243898945396093580724391257502862264542139892002113479274778815312220710067519175895385029728136011707878570503892737327311559220318356052978117942035853947664507847769494960999568852350903791440660149716513527902855811711244727464905711093905648316805999328017344077741109433923704200400909675649273690871091313094751105766025879326677544581537926603326267474079786157380975934855898690386484742475696802305967739089815897725317069013189207569982900053713459672998534905787251877552189174587775147542089885096510488094105071666800247101089674649502031584763839755525727965498486527987626650988652717016765563711049277022756500157982361607140778095658226557996921026130637701014127285732701887164908135560640420831336153612762215604492226275755304784484586433397754740117463505077153516054839486722481181167234229522839072562070104349846627036424367454820389259772812583287412268551592814838917235531904330269843311050451607079925393154706621947637894340627920099890436967089957279051662270031234850834868788996666439029630296451502714368722270484850158064364294201493953114172135159291698520360808866584806672889034144771436797735399804868018466668980453787245180038654345402748074831992415906097556738039279373205673388915847115097595687636844845281031267671590617631079664730977219356874731914430598632093802245785346918434058687175986926298508052091652105059279150133460800817344425839682126964963172665944796661520065067011564066759081570107543463219913557175490516674841445611024874076012796831045476624324336824144536686982822389532337716389606704464995869146017139606884400942152132650479156746875064775899199421858957623079678439410930007225084885887507916565931484847922437795803010981718194290457886234411319205609157105187496215942426263799468200530172714083518151428613800222887516185125589229285415586754359693123597271154802410446280090888946329676448819766565178085178413
e2 = 85039848098040198629810228227981333547571544556783337097791600722534400132636079696903303346248897364881224585886454806975154545966948446220731675563154086955028649334868794080881245005339585924134379510941267320612901825195331762039504494208113074000658589388417531708151776552001429290730079651850438354450134417941536114627588684047285304149442482520534706112915132300363334355877266504867840336875699380810203774027956821177301695145239460742602239474808009495484157876332743288399678455954261820744636650959513617108267284843582028632761292881550278978932484825724119492458352905716592760686190086451077741620824644825883637432247606542138083779285819850363414635029032877436967954280148470447811352539940377678100502742624065767900310440814168233290500834855710005707058159197563629326782049935503972263918251175766238816831480903704391181267515124468008074136167514887505816881460820657424954418139484799844694782547580350564364558817948882864222013820625021944986053685725745314774681293740590727701113298280323591219898133230776271582267346789673381184226867314871136250586292185846670779312885676712427749758340163573785341699633900956786017292343325059891658652266756606090187161788473402586895334792711643881433133624951181775727523533052371714916897497811035395454066372050989114435626744825554699077429987277061832895800546415012022003883511707438045038605628208211909421854504776635296074426208716798470239164727186799413913395180313824277747343105859814610954674052243548895700598370536537947368616622939415516698306638823827111837566750309493160547631614984324373110960297446703268022461052398627980535338158153120866719678508677569334532530529647580833323049593479237592627920937370843841953419429014918761884065528591917331618164304459336833062437365299224341702429186447625010865403846061689858277518844804864401686840751180716835568865211637737929233885813901317995949748419432175395134689356497511677848916131101942879850703634693483037253067856351005939346103168898195695634993164654145535921173796299479632825317904540020964320393080050237770370124344704355059640345255127574387631628640364876804621760107827456260120265498390309061
Solution :
1- Explanation :
The challenge implements a variant of RSA, where the modulus is of the form
$$ N = p^r \cdot q, \quad r \in [5,30] $$instead of the usual $ N = p \cdot q $
As a result :
$$ \varphi(N) = p^{r-1}(p-1)(q-1). $$Step 1 – What are $e_1$ and $e_2$?
The code generates two huge random numbers $d_1, d_2$ and computes:
$$ e_1 = d_1^{-1} \pmod{\varphi(N)}, \quad e_2 = d_2^{-1} \pmod{\varphi(N)}. $$So :
$$ e_1 d_1 \equiv 1 \pmod{\varphi(N)}, \quad e_2 d_2 \equiv 1 \pmod{\varphi(N)}. $$Step 2 – Relation between $e_1, e_2$ and $\varphi(N)$
We have that : $ e_1 d_1 - k_1 \varphi(N) = 1 $ and $ e_2 d_2 - k_2 \varphi(N) = 1 $ with $ e_1 > e_2 $.
Hence $ e_1 d_1 \equiv 1 \pmod{\varphi(N)} $ and $ e_2 d_2 \equiv 1 \pmod{\varphi(N)} $.
Multiplying the first equation by $ e_2 $ and the second by $ e_1 $ and subtracting, we get
$$ e_1 e_2 (d_1 - d_2) \equiv e_2 - e_1 \pmod{\varphi(N)}. $$Since $\varphi(N) = p^{r-1}(p-1)(q-1)$, we get :
$$ e_1 e_2 (d_1 - d_2) \equiv e_2 - e_1 \pmod{p^{r-1}}. $$Now, we have the modular linear equation :
$$ e_1 e_2 x - (e_2 - e_1) \equiv 0 \pmod{p^{r-1}} $$That is if $ \lvert d_{1} - d_{2} \rvert < \frac{N^{r(r-1)}}{(r+1)^{2}} $ computing :
$$ \gcd(e_{1}e_{2}x - (e_{2} - e_{1}), N) = \gcd\!\big(p^{r-1}(p-1)(q-1)y, \; p^{r}q\big) = g, $$will lead to determining $ p $, hence factoring $ N $ as follows:
$$ p = g^{\tfrac{1}{r-1}} \quad \text{when } g = p^{r-1}, $$or
$$ p = g^{\tfrac{1}{r}} \quad \text{when } g = p^{r}, $$or
$$ p = \frac{N}{g} \quad \text{if } g = p^{r-1}q. $$Step 3 – Using Coppersmith’s method
We set up the polynomial:
$$ f(x) = e_1 e_2 \cdot x - (e_1 - e_2) $$over $\mathbb{Z}_N$.
By applying Coppersmith’s small root attack, we can recover the small solution $x$.
we chose beta = 0.2 since r is at least equal to 5
Step 4 – Extracting $p$
From the relation, we compute:
$$ g = \gcd(e_1 e_2 \cdot x - (e_1 - e_2), N). $$This gcd leaks either:
$$p^{r-1}$$or
or
So we try possible values of $r$ (between 5 and 30 as given) and test if $g$ is a perfect $(r-1)$-th or $r$-th power.
This gives us the correct $p$.
Step 5 – Recovering $q$ and the private key
Once $p$ and $r$ are known:
$$ q = \frac{N}{p^r} $$and then
$$ \varphi(N) = p^{r-1}(p-1)(q-1). $$Finally, compute:
$$ d = e^{-1} \pmod{\varphi(N)}. $$Now decryption is straightforward:
$$ m = c^d \bmod N. $$Step 6 – Getting the flag
Decrypting yields the plaintext, and we recognize the flag format:
2- Solver script :
from Crypto.Util.number import long_to_bytes
c = 150585797027649865489287786588283519376444271481829451206461043013638461851456443295639137583076309442211685140040715015672365662062445178352437695738282641956247465007835614325215320828570574978027697247110122408959329602493024795984675855072829968568063483443564884590062240635887431125362354037916695863432044462478632010854829416594987121310115447040797978156754180611417998692235678830822995195693412798239945582015522540243621848514340825137784617038883681762243778481350214509050715611993272169019595988822536735533532328109537622265977681155970778571399007023021359255926523887958105866659589793221135086136634321526143644058657686559455390271432068714110879919249854512706311908215475720874421301327375628026151554425480889625476443996963226739224141229051215116294621373720061550447360540466603611877916643506521674077637662746353412174577577517713229695736915310128634392507257018082205528441763251409689312355800240394928915067047489667210410718244921919018887791400482889355718347742440819608756821762567978878895290820251733297461964155473495597853211579186825851137994290776971434620034797987966563429453923909529541320143776397669267613997300604747811315937419659086723279726826646032780534551617458772078374711989147497752615265133572176138301527850632921359443303144256863024531079818868821758707284519856822245327421770110054277128452078605253184196998977317191651032204260679733274112559665428206212555513334541342029165221468784610288416686450162503789244926494714898635616996486140153083238632042007797793700563323218257129418795358543031202313561185588455593386153322727840291176790523913519542549216392301233455213647649027484109309089206606335520666724332245092640179790951481672640009520232615798668179089441370616468610644268539377884248767999193537928526046999022147158284677984579677312334741055670888654273143019369722889958102904924117413980953194821337321878279459444456391516721152204499246038472658108777670283734288457011883626451484055732662043231790974669769949105126075064121602546376952003206428494498829916276757539596132583838525916520286113969608190165961798389572158151878875500492540747108296198243292566008234833
e = 65537
N = 186468293083788781245499353512563129672312798029703904462936796596026120571080426862373632093518207360391666952453308555988614378903855020162320651304963730462668109416515599034788196838330392323014227902075936472408096760922362616639831532722796773044161215603161573173693396763848532916596270542508246600865336824042340247413113147406841036910189001075097670228541035790259078800598326610948022398352585923649531112759445985740346135428877322273556322542215020775992731058099305658619025609383729517239811673596072211108962991986901295709256060275331345666057130911453857078541419835856196753136664547254360862900351337626911283810534959854452952272035002742600178127259539214115953749657961050280108421405551206427544090699506875821129502984234774688377256310602196702176007042636404063776926466585683290760236194258669323601484216988981113466416405284959939812524546732701485183931884838692814562595191552224757937077488587067020793692692549938889591330072594717978441992795102999379303433207854356430437846345643266409739062915660544094498466397963646286252575273661019638807620280311533417717322466737567313846948246565804965079064097678541329903335139345823245801485851723772625368820657081414997271906611200756811167771754039199663511386284954358869993716532869728924931127279616476581118702229755968849120582675066084548348641091550633395996908836876499056736123107365637770245726218450365257927541692911169875941639963606762719472741281838412109552457222110661735681401203267804449363273688233013042050750830535778904458171623334164553955827238989238553731488016772701812203067882783550639709170454593937643386446256536119770989304864520889045556071269357480411824619830061505470986036143575914439137724990710287384145813135368196679314377112131761811940172598300544938844479133061210634426452190259178180635554381170513818865646521472300868854934387822644776013828828533387245770709879233807065640965155395836324727727247566385145338896343366468455003789992017616034872629717115885307603763663604867417148970196011250152501225642510419108907592141672752218085088428240372007994449852792767351434018043118658591114512322934390623465185608109909287
e1 = 41580201693720582480693330964943873953272761954440070167783695980849492986662882513949168242004211132670119356752908751569637864785219861514846064298150109789186060860480552700920272463488413243406347872787482976412247245447832054401920594283666788061207365372191406054243898945396093580724391257502862264542139892002113479274778815312220710067519175895385029728136011707878570503892737327311559220318356052978117942035853947664507847769494960999568852350903791440660149716513527902855811711244727464905711093905648316805999328017344077741109433923704200400909675649273690871091313094751105766025879326677544581537926603326267474079786157380975934855898690386484742475696802305967739089815897725317069013189207569982900053713459672998534905787251877552189174587775147542089885096510488094105071666800247101089674649502031584763839755525727965498486527987626650988652717016765563711049277022756500157982361607140778095658226557996921026130637701014127285732701887164908135560640420831336153612762215604492226275755304784484586433397754740117463505077153516054839486722481181167234229522839072562070104349846627036424367454820389259772812583287412268551592814838917235531904330269843311050451607079925393154706621947637894340627920099890436967089957279051662270031234850834868788996666439029630296451502714368722270484850158064364294201493953114172135159291698520360808866584806672889034144771436797735399804868018466668980453787245180038654345402748074831992415906097556738039279373205673388915847115097595687636844845281031267671590617631079664730977219356874731914430598632093802245785346918434058687175986926298508052091652105059279150133460800817344425839682126964963172665944796661520065067011564066759081570107543463219913557175490516674841445611024874076012796831045476624324336824144536686982822389532337716389606704464995869146017139606884400942152132650479156746875064775899199421858957623079678439410930007225084885887507916565931484847922437795803010981718194290457886234411319205609157105187496215942426263799468200530172714083518151428613800222887516185125589229285415586754359693123597271154802410446280090888946329676448819766565178085178413
e2 = 85039848098040198629810228227981333547571544556783337097791600722534400132636079696903303346248897364881224585886454806975154545966948446220731675563154086955028649334868794080881245005339585924134379510941267320612901825195331762039504494208113074000658589388417531708151776552001429290730079651850438354450134417941536114627588684047285304149442482520534706112915132300363334355877266504867840336875699380810203774027956821177301695145239460742602239474808009495484157876332743288399678455954261820744636650959513617108267284843582028632761292881550278978932484825724119492458352905716592760686190086451077741620824644825883637432247606542138083779285819850363414635029032877436967954280148470447811352539940377678100502742624065767900310440814168233290500834855710005707058159197563629326782049935503972263918251175766238816831480903704391181267515124468008074136167514887505816881460820657424954418139484799844694782547580350564364558817948882864222013820625021944986053685725745314774681293740590727701113298280323591219898133230776271582267346789673381184226867314871136250586292185846670779312885676712427749758340163573785341699633900956786017292343325059891658652266756606090187161788473402586895334792711643881433133624951181775727523533052371714916897497811035395454066372050989114435626744825554699077429987277061832895800546415012022003883511707438045038605628208211909421854504776635296074426208716798470239164727186799413913395180313824277747343105859814610954674052243548895700598370536537947368616622939415516698306638823827111837566750309493160547631614984324373110960297446703268022461052398627980535338158153120866719678508677569334532530529647580833323049593479237592627920937370843841953419429014918761884065528591917331618164304459336833062437365299224341702429186447625010865403846061689858277518844804864401686840751180716835568865211637737929233885813901317995949748419432175395134689356497511677848916131101942879850703634693483037253067856351005939346103168898195695634993164654145535921173796299479632825317904540020964320393080050237770370124344704355059640345255127574387631628640364876804621760107827456260120265498390309061
R = Zmod(N)
PR = PolynomialRing(R, 'x')
x = PR.gen()
f = x - R(e1-e2)/R(e1*e2)
x0 = f.small_roots(X=2^1024, beta=0.2)[0]
g = gcd(e1*e2*int(x0) - (e1-e2), N)
p_candidates = []
def find_p(r):
# case 1 : g = p ^ (r - 1)
p_candidate = Integer(g).nth_root(r - 1, truncate_mode=True)[0]
if p_candidate > 1 and p_candidate^(r - 1) == g:
p_candidates.append((p_candidate, r))
# case 2 : g = p ^ r
p_candidate = Integer(g).nth_root(r,truncate_mode = True)[0]
if p_candidate > 1 and p_candidate^r == g:
p_candidates.append((p_candidate, r))
# case3 : g = p^(r-1) * q
p_candidate = N // g
p_candidates.append((p_candidate,r))
return p_candidates
for r in range(5,31):
find_p(r)
q_candidate = 0
for item in p_candidates:
if item is None:
continue
p_candidate, r = item
q_candidate = N // (p_candidate ^ r)
if N != p_candidate ^ r * q_candidate : continue
phi = (p_candidate ** (r-1)) * (p_candidate - 1) * (q_candidate - 1)
d = pow(e,-1,phi)
pt = long_to_bytes(pow(c,d,N))
if b'fwectf{' in pt :
print("p: ", p_candidate)
print("q: ", q_candidate)
print("r: ", r)
print("flag: " , pt)
break
else :
print("failed")