Space Papaya

This is a challenge from Cryptography section of Standcon 2021. The challenge used bad parameters for RSA encryption

Statement

I’ve been promised some space payayas but Thanos has encrypted it Could you help me get to my delicious goodness??

#!/usr/bin/env python3
from gmpy2 import *

p = next_prime(mpz_random(random_state(), 2**4096))
q = next_prime(p)
e = 65537
n = p * q

m = int(MESSAGE.encode().hex(), 16)

c = powmod(m, e, n)

print('n: {}'.format(n))
print('e: {}'.format(e))
print('c: {}'.format(c))

# n: 194362842708866084215953237234010601714782092068657017473036251138431676671868175490629669131293355984477767779272247912898398003959598463151066327473719826508089049945621257750848449074932994104814837269421034757100838633416457369464538335095187107124930210006276919089438600966775135156325573710403062047464883549122709123350776456864832248893144446427550937016055121611927144077249211333929866196092711899598411273258926755835322801924551532228696950330545602277465654578138211698686416187777914526845287508335161840449532353167124783735356724420020001236913091469220071460852670489823002071147052631961616736127542307774553784213551564976856862680192529610361702034557744944910925361832621941572380183550749898722374949514136460106207058164376880193895095890731337592265596372136311383975505976373658539080754488958878095929819739059683095890843634555379298978595862942651406158169690562827703147073676346785373790083861582561563008369782363501250191378992269292876039816066218709174263118734404595822048356915079954616024173040278438553459313402270428924062608121168067858306151528190868319071885225544108264749925782330560592480215417954913785029628131817946912132072071073028544681943321456215850218595253490676706062275706321000094834565990465219492368108372464243357854880130522009562946069931768188707691738519573044108555326442766896720655950851164470011771898369770346952788889888492093755625144273054698093660448370077627755233718711030066641378367031583966313900302554231887044203179482191397744246669757016815802390996997529280308699365864745829622981997926231390088157384772877949116604666434897004907955030386342793095734076042434116395844774091900169206181916763238708781774871037938343903139193853528470631949004956352291136030226647324347066772397900205516364442447205487793826622232753382956298250824843380629813818205906683470702831540412778050975345092843721732642350276838457054614948850604421694716563394223556916722778907958340426218859169271015308289476166790080639494788055226687567028709925056618087462428702997126125118029596845966551281440608686343474201915276278183257597304657555212877310709706767336727956810525772106318192285540421821451870148936086342692819049576874727321875121881832817291330007033448759929549864436079804109819708577707453355419019938895736691749711920076052148328406790627343167155687496921184728015803775794667189219633138620080230753579310617631968722793155536612115409526848248365291605624225739530401807631
# e: 65537
# c: 48231407940727026948672141996334529816590411386860292966914913052426047651987115807777841403140631401701249166736959609586369772130907665951564333728016264781106888841594995016670252351243877043043931895035854072541505075903498699581537787497372368026387461275304338678342882903111473016523122047215378268701734813840019057484437006734608455311609606589978328615886021809161996407351531878330820646743145761284259656979198538333302516658013752884296025359474328771699801774792040803990528899610805832697102960908000990289217674047087227612100839918274810879461691566218620108094572187135662070276143399213929056836949141685032577775184655073850890039819023606342148129988769179828433133474387630746462392553047809255640475195268000075192882984582676932698012626821016591108454125334943555006192200330741124548142161400440375747011531508789850387965540536344945763731373457679082441847778497960038863971948480784876442032472906163053089647045655001542030261262366802020060960874257117691078438824193893194414541917317612137645261904776291223687776582045621554101330940016490033717225542054294550509723890916037908439996672821935786685430873048747351042450242135132402651504861858744900133079753832853206911330310597784333649988497694115288456557414447667162368132351388665881330668539885411369791455480519780053033578607022175215519541686716889470249651075696960031469802931249420275612918537198815728307645858921412505760969514941201413816870042202876699227452040578555623960644754047671586444437939411346055325470287778116774616418405759426544629377975037932066699294880194784853999718178319023949211409048595187949438738050805752373774067262605283342238201172745181281789835988232279319864794958750383869310348406998847103542030538181779060240394157480926897363819838099821784624349518599583933815726206097153419947746982886708613483961746873726951138409665385485483718572380938222490388874840647413038783667362727632810016605914301245603947756748870162828963959855754534784070704364459621393050570977513255324417271658411232766634623398123418984633536742998705987579502631970588156672642641810685697296750600811292822227321148497030230391951474359873858004455962186711399896745959043999926635601785091266948248579919445401875107488515808513058701412149085423586181153312241453589223174436758137842395277731895460702559785230565410482969668156381371880091047940473364486255074425419927756644949215073309100344302265133911935519226690015718699828070058406043592623

Observation

First thing to notice is \(p\) is generated based on \(q\). Since \(q\) is the next prime of \(p\), we know that \(p - q\) should be quite small.

Knowing this helps us in factorizing the number \(N = p \cdot q\) using fermat’s factorization method.

Solution

If we can find a number \(A\) such that

\[A^{2} - N = B^{2}\]

Then we can factorize \(N\)

\[A^{2} - B^{2} = N\] \[(A - B)(A + B) = N\]

where \((A - B) = q\) and \((A + B) = p\)

And since \(p - q = (A + B) - (A - B) = 2B\) is small,

We only have to look at small number to be the candidates of \(B\).

So just try all possible \(A\) close to \(\sqrt{N}\) to make sure \(A^{2} - N = B^{2}\) is also small.

By looping through the numbers, we then factorized \(N\). The RSA is now broken!

Alternatively, just use RSACtfTool

Here’s the python code for the complete solution.

import gmpy2
from Crypto.Util.number import long_to_bytes

n = 194362842708866084215953237234010601714782092068657017473036251138431676671868175490629669131293355984477767779272247912898398003959598463151066327473719826508089049945621257750848449074932994104814837269421034757100838633416457369464538335095187107124930210006276919089438600966775135156325573710403062047464883549122709123350776456864832248893144446427550937016055121611927144077249211333929866196092711899598411273258926755835322801924551532228696950330545602277465654578138211698686416187777914526845287508335161840449532353167124783735356724420020001236913091469220071460852670489823002071147052631961616736127542307774553784213551564976856862680192529610361702034557744944910925361832621941572380183550749898722374949514136460106207058164376880193895095890731337592265596372136311383975505976373658539080754488958878095929819739059683095890843634555379298978595862942651406158169690562827703147073676346785373790083861582561563008369782363501250191378992269292876039816066218709174263118734404595822048356915079954616024173040278438553459313402270428924062608121168067858306151528190868319071885225544108264749925782330560592480215417954913785029628131817946912132072071073028544681943321456215850218595253490676706062275706321000094834565990465219492368108372464243357854880130522009562946069931768188707691738519573044108555326442766896720655950851164470011771898369770346952788889888492093755625144273054698093660448370077627755233718711030066641378367031583966313900302554231887044203179482191397744246669757016815802390996997529280308699365864745829622981997926231390088157384772877949116604666434897004907955030386342793095734076042434116395844774091900169206181916763238708781774871037938343903139193853528470631949004956352291136030226647324347066772397900205516364442447205487793826622232753382956298250824843380629813818205906683470702831540412778050975345092843721732642350276838457054614948850604421694716563394223556916722778907958340426218859169271015308289476166790080639494788055226687567028709925056618087462428702997126125118029596845966551281440608686343474201915276278183257597304657555212877310709706767336727956810525772106318192285540421821451870148936086342692819049576874727321875121881832817291330007033448759929549864436079804109819708577707453355419019938895736691749711920076052148328406790627343167155687496921184728015803775794667189219633138620080230753579310617631968722793155536612115409526848248365291605624225739530401807631
e = 65537
c = 48231407940727026948672141996334529816590411386860292966914913052426047651987115807777841403140631401701249166736959609586369772130907665951564333728016264781106888841594995016670252351243877043043931895035854072541505075903498699581537787497372368026387461275304338678342882903111473016523122047215378268701734813840019057484437006734608455311609606589978328615886021809161996407351531878330820646743145761284259656979198538333302516658013752884296025359474328771699801774792040803990528899610805832697102960908000990289217674047087227612100839918274810879461691566218620108094572187135662070276143399213929056836949141685032577775184655073850890039819023606342148129988769179828433133474387630746462392553047809255640475195268000075192882984582676932698012626821016591108454125334943555006192200330741124548142161400440375747011531508789850387965540536344945763731373457679082441847778497960038863971948480784876442032472906163053089647045655001542030261262366802020060960874257117691078438824193893194414541917317612137645261904776291223687776582045621554101330940016490033717225542054294550509723890916037908439996672821935786685430873048747351042450242135132402651504861858744900133079753832853206911330310597784333649988497694115288456557414447667162368132351388665881330668539885411369791455480519780053033578607022175215519541686716889470249651075696960031469802931249420275612918537198815728307645858921412505760969514941201413816870042202876699227452040578555623960644754047671586444437939411346055325470287778116774616418405759426544629377975037932066699294880194784853999718178319023949211409048595187949438738050805752373774067262605283342238201172745181281789835988232279319864794958750383869310348406998847103542030538181779060240394157480926897363819838099821784624349518599583933815726206097153419947746982886708613483961746873726951138409665385485483718572380938222490388874840647413038783667362727632810016605914301245603947756748870162828963959855754534784070704364459621393050570977513255324417271658411232766634623398123418984633536742998705987579502631970588156672642641810685697296750600811292822227321148497030230391951474359873858004455962186711399896745959043999926635601785091266948248579919445401875107488515808513058701412149085423586181153312241453589223174436758137842395277731895460702559785230565410482969668156381371880091047940473364486255074425419927756644949215073309100344302265133911935519226690015718699828070058406043592623

for i in range(1000):
    a = gmpy2.iroot(n, 2)[0] + i + 1
    t = gmpy2.iroot(a*a - n, 2)
    if t[1]:
        b = t[0]
        p = (a - b)
        break

q = n//p
phi = (p-1) * (q-1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

flag : STC{where_did_my_space_papayas_go}