david lim

david lim

A typical Pokémon fan.

RSA Madness [CRYPTO]

5 minute read

5 RSA challenges with various tools and techniques.

Challenge 1: RSA1 [EASY]

100 points, 346 solves

📁 Challenge Description

rsa1.txt

n = 287838647563564518717519107521814079281
e = 7
c = 258476617615202392748150555415953446503

🚩 Solution

The public key n and e are too small for RSA security.

Go to factorDB, insert n value and get p and q.

#!/usr/bin/env python3
from Crypto.Util.number import *

p = 15631612382272805561
q = 18413880828441662521
n = 287838647563564518717519107521814079281
e = 7
c = 258476617615202392748150555415953446503

print("FLAG:", long_to_bytes(pow(c, inverse(e, (p-1)*(q-1)), n)).decode())
# byuctf{too_smol}

FLAG: byuctf{too_smol}

Challenge 2: RSA2 [MEDIUM]

100 points, 323 solves

📁 Challenge Description

rsa2.txt

n = 546014635841741214724882952304387823741798461149589549073179989118942746109940806878269775538274570065946589413677004071487344751464649121103982272835006900203922112014630898761428602513684456008956735791010937229939856259403186940249737579526542460562078728957198932156520780835942292131829398548678970431263462917223085165930683353518778015361505451889259321493813123084031407195410778661720394898118828299025325200597986154170392835072784810370185329392356423340408483449291280713796374297147668615988522804223480631576577707073715128342533703842150980913675658012799681575774731843549389349977365287936534707998476564357339504431638612839358093914282814270477657856345062084136585402704930924062452984009716927826681976269057923158930326380110735873715506666086031427627450725825495228912040943784627278987497908133546573083543604901933763330940965980882566819970423354937076331119777415405707162588442490342746115310986462330781467571631209829523895479737199963129517613642920935109776495829400236613168913129178658637967592913193540283532220304664924612246117951571439486418122093867454452618997458068515332016877486822805232899716524040444751997121936138984564834862354469295078855441829018404782747219665338778379471257704041
e = 65537
c = 497483520135207500611760341868934810216889295862727367409205471739457798733223813938415492642898622071289502771394670201759355356873731071744923938304067196827981196823596976532284031567818944043351160692892539254848854527943095670705184836531463778923699513154523281624336593518751911469590777921172775020125081803529411082078530404614569485860638460689961289946436553586222781503048987585305336865777424252321433817251942278548031598867440246798562662298880488044382840476214732326114298681849826143159014132251265975612736174765852107701466877003101250308950535660691651846052082123375934624356694170453897672257371991315676787548733520567289929667876604682273501711766130944645562650989837328685043543330211830184365436596077862055649246517141787872170320358968622818470064395975654949073402489903952399985907827496667385839890041608685588908200009780210043116940593521695695047783434230143405184690206691002634954008353327872663055826018481013718627348218684688250775372760462829705754318024652361552668830110066219305953343851243676904796434142570868419087560131333056695456062994781034014322792678534785191950145702468201676105282230660132801024614625267740668507168119879074770666830923799616054485447308126877109671082189614

🚩 Solution

Even though the public key n and e are large enough, the n value is known in factorDB.

Hence, insert n value and get p and q.

#!/usr/bin/env python3
from Crypto.Util.number import *

n = 546014635841741214724882952304387823741798461149589549073179989118942746109940806878269775538274570065946589413677004071487344751464649121103982272835006900203922112014630898761428602513684456008956735791010937229939856259403186940249737579526542460562078728957198932156520780835942292131829398548678970431263462917223085165930683353518778015361505451889259321493813123084031407195410778661720394898118828299025325200597986154170392835072784810370185329392356423340408483449291280713796374297147668615988522804223480631576577707073715128342533703842150980913675658012799681575774731843549389349977365287936534707998476564357339504431638612839358093914282814270477657856345062084136585402704930924062452984009716927826681976269057923158930326380110735873715506666086031427627450725825495228912040943784627278987497908133546573083543604901933763330940965980882566819970423354937076331119777415405707162588442490342746115310986462330781467571631209829523895479737199963129517613642920935109776495829400236613168913129178658637967592913193540283532220304664924612246117951571439486418122093867454452618997458068515332016877486822805232899716524040444751997121936138984564834862354469295078855441829018404782747219665338778379471257704041
e = 65537
c = 497483520135207500611760341868934810216889295862727367409205471739457798733223813938415492642898622071289502771394670201759355356873731071744923938304067196827981196823596976532284031567818944043351160692892539254848854527943095670705184836531463778923699513154523281624336593518751911469590777921172775020125081803529411082078530404614569485860638460689961289946436553586222781503048987585305336865777424252321433817251942278548031598867440246798562662298880488044382840476214732326114298681849826143159014132251265975612736174765852107701466877003101250308950535660691651846052082123375934624356694170453897672257371991315676787548733520567289929667876604682273501711766130944645562650989837328685043543330211830184365436596077862055649246517141787872170320358968622818470064395975654949073402489903952399985907827496667385839890041608685588908200009780210043116940593521695695047783434230143405184690206691002634954008353327872663055826018481013718627348218684688250775372760462829705754318024652361552668830110066219305953343851243676904796434142570868419087560131333056695456062994781034014322792678534785191950145702468201676105282230660132801024614625267740668507168119879074770666830923799616054485447308126877109671082189614
p = 23354146979807319379999035616961227366315140956417473671454187034894451162291754802462941941792796900830979379875976598091266482784685424013905480696388873312112449447015212036533336920764065285748033710474328055812364692120325949818178301777905279103958955246642416286153474237338739835798119305508201074075918506331902107847659951627678483765213310235851319160745426496852724170929530989982548624157909773262752522594414435161921211944019434983046703898010646693649668494220236993757035493132421299985405030215783112721654976457363937286689672094963265015048673356916456174809392166143308820305157390154213277022361
q = 23379772179812068808174060753537744579203831235837216258047345717791206838844783973094148970269358352883567686183840162453475135997997950171025172534250066839781721720291637394109275750765747393807129441718738564581300844549866075387635571271298099970059805382997224172143494300775742278526976057440901844970233807992493192827375594281731619879000721912671268883932814086571959959837609600236134071446484378655039534937911808777812990351810838102078057859303673209338100518315299313874836179635779981742550281014611235035038725280128727341135995530457136512443488805309366834219571741391932893715725604175334445964881

print("FLAG:", long_to_bytes(pow(c, inverse(e, (p-1)*(q-1)), n)).decode())
# byuctf{rsa_is_only_secure_when_p_and_q_are_unknown}

FLAG: byuctf{rsa_is_only_secure_when_p_and_q_are_unknown}

Challenge 3: RSA3 [MEDIUM]

100 points, 222 solves

📁 Challenge Description

rsa3.txt

n1 = 26936730986023789726214222876998431579035871765812234385674097050592112272540329063679602773116293498245937781951160051718036177035087801218359133356523071700951108999020905116034905584806261203518345118128714311038590925635180342040347317022008233631809623824589107373210514331169745651687793393307158179191306187356408951648269495142386375021669218752561961647301029204701333026044435685936341126368602940601101599988477874713569476970068734357580527463645209944448988010693985476127837819331701523891965427561798033127731232916390511986369304971158889254173850566560028528340860519614489276904182246324437302697433
e1 = 65537
c1 = 25934221721388531303090294836956821212346696995428676440185777623629033147440636130540319272854260855117016879903925227836710795492438220977864741830686432435183222727791461378988782191893620213711460265022633971293289987925875691438890670054518553696690583070284033592035281829227897938832962322172505881421894428362134145126751766514249801481330619906708370005958557827981820321861133293595400304305721764486699677941331024345924352161482159664366018182446127343098427579677894070842066840562853624060861183697917208697602208453017595582242281467105778066369782229287834403074433848470534633158573935584429007575715

n2 = 20923351960149847207730448386993771286287991808293298691185156471519720793292179321382926775933281826329369963004005667653815105072159583791658532166606431385861980687037872135521884790087813454844716254644626942821490878728677736261700329782075809716063515721266692286574071240561529911159730824490258866613280873755548760004314650585913096197607936750263556276920577987540676841745347308103070523989154846358123142014592046611945781700690640990848003152423310523158983857208127158850925297742214928064334410930947749935069628731105093722212442331657106356911123912454871778728334875010902513275561639806401894881233
e2 = 65537
c2 = 5993773597007465934515223705550947500391213737662065644971977783446564890828050443747162704068048188331597029929182281837445674583301936037963788912954366180921337518251139032904603786774772009913305609053718347365864177247549192649908207240197602397010006677485658506955283638199651692990436006544549785434255965098715363287267470252318128158357490592521797199393154974403123099999366644663048724011101287811844340320520544010179529188112211115440469084617438296961494801221969674213288489675624156545941630517075958425681203711654677553772595530799489102830165490202523397154229276688719481530893488434863906070343

🚩 Solution

Unfortunately, BYUCTF challenge creators maybe did not verify whether both ns are crackable in factorDB. Hence, we can crack one of the n to get the primes p and q via factorDB again.

#!/usr/bin/env python3
from Crypto.Util.number import *

n1 = 26936730986023789726214222876998431579035871765812234385674097050592112272540329063679602773116293498245937781951160051718036177035087801218359133356523071700951108999020905116034905584806261203518345118128714311038590925635180342040347317022008233631809623824589107373210514331169745651687793393307158179191306187356408951648269495142386375021669218752561961647301029204701333026044435685936341126368602940601101599988477874713569476970068734357580527463645209944448988010693985476127837819331701523891965427561798033127731232916390511986369304971158889254173850566560028528340860519614489276904182246324437302697433
e1 = 65537
c1 = 25934221721388531303090294836956821212346696995428676440185777623629033147440636130540319272854260855117016879903925227836710795492438220977864741830686432435183222727791461378988782191893620213711460265022633971293289987925875691438890670054518553696690583070284033592035281829227897938832962322172505881421894428362134145126751766514249801481330619906708370005958557827981820321861133293595400304305721764486699677941331024345924352161482159664366018182446127343098427579677894070842066840562853624060861183697917208697602208453017595582242281467105778066369782229287834403074433848470534633158573935584429007575715
p1 = 158954135912536259649845552382757849078339820320889922784576644780347102092039759071735700930458068125729993437629627127489937677182234654634528546796102749001441786797851584837364751075271572884183286900728332748215222105328915933271749659017999737220238175387228902907641858812820949035828633637080555842217
q1 = 169462284396585911849574285651271443371876901092320858398545983156942539436929846404404679656482378298122786540995721429096585253848180086811629361617206413459150016149567031889102951830833040736468496796020866541776202762448423458853776925394946588441545505005536816213547053664824743158608813965992840726449

print("FLAG:", long_to_bytes(pow(c1, inverse(e1, (p1-1)*(q1-1)), n1)).decode())

After getting the flag, I finally get the intended solution. Both ns share one common prime. Hence, we can construct the final script.

#!/usr/bin/env python3
from Crypto.Util.number import *
from sage.all import *

e = 65537
n1 = 26936730986023789726214222876998431579035871765812234385674097050592112272540329063679602773116293498245937781951160051718036177035087801218359133356523071700951108999020905116034905584806261203518345118128714311038590925635180342040347317022008233631809623824589107373210514331169745651687793393307158179191306187356408951648269495142386375021669218752561961647301029204701333026044435685936341126368602940601101599988477874713569476970068734357580527463645209944448988010693985476127837819331701523891965427561798033127731232916390511986369304971158889254173850566560028528340860519614489276904182246324437302697433
c1 = 25934221721388531303090294836956821212346696995428676440185777623629033147440636130540319272854260855117016879903925227836710795492438220977864741830686432435183222727791461378988782191893620213711460265022633971293289987925875691438890670054518553696690583070284033592035281829227897938832962322172505881421894428362134145126751766514249801481330619906708370005958557827981820321861133293595400304305721764486699677941331024345924352161482159664366018182446127343098427579677894070842066840562853624060861183697917208697602208453017595582242281467105778066369782229287834403074433848470534633158573935584429007575715
n2 = 20923351960149847207730448386993771286287991808293298691185156471519720793292179321382926775933281826329369963004005667653815105072159583791658532166606431385861980687037872135521884790087813454844716254644626942821490878728677736261700329782075809716063515721266692286574071240561529911159730824490258866613280873755548760004314650585913096197607936750263556276920577987540676841745347308103070523989154846358123142014592046611945781700690640990848003152423310523158983857208127158850925297742214928064334410930947749935069628731105093722212442331657106356911123912454871778728334875010902513275561639806401894881233

p = int(gcd(n1, n2))
q1 = n1 // p

print("FLAG:", long_to_bytes(pow(c1, inverse(e1, (p-1)*(q1-1)), n1)).decode())
# byuctf{coprime_means_factoring_N_becomes_much_easier}

FLAG: byuctf{coprime_means_factoring_N_becomes_much_easier}

Challenge 4: RSA4 [HARD]

100 points, 272 solves

📁 Challenge Description

rsa4.txt

n1 = 25204912957894049536633029588071532883154221495361435745558539407530325536509218257991893451902442183954212400671502526830623527340613723328379300388737939211263541814108106183164630301938900862986688763583982133846507136234797325243547177627054271161715200611591594812723672399437505379398941496184886411879923583394041753902383846644013849190900416111230521180435101859101110596828380586449182686175177638441549656137307050392520754146511496313215137339773851458160180450925216541537448515297981124184019831730808991821344392915274230294654187421183676471212265322367890189804699510021526923237231850244056681024361
e1 = 3
c1 = 8177192204481601898705460379101384591996531766013815643642297541939314169289538943467463950155787562006058743758523755363825964609610993939021120980839831173842134605117089923025444468026164578567348718360392736482132312367435114106411271743218631041094275894508404221506482038656928803775293360599721583316194630449469869000491476753827928793659938654925187969087524783314008405767753004191090522037968098548258698350055999105058915648497702724525585509

n2 = 17730912385401458370516374144454354828481353051514329263921774569034415114147424203611660978860008058118764431105602401970281692066419254457694301039461623568501484102567802483628476717695013320444442267232019104240173401975387173805390636521671252624249730700497552226732834062715286458634274525026438931671208367178653031967364951679420066768732647183187381700016195545187024094717207787859217993871236368911145957298126589666514319408022801341248744002320245345234912423717815146532293315342644702101415345900126397475592837306256140915525455824350305349773210334856093169535686115299159772550674315375987529523179
e2 = 3
c2 = 8177192204481601898705460379101384591996531766013815643642297541939314169289538943467463950155787562006058743758523755363825964609610993939021120980839831173842134605117089923025444468026164578567348718360392736482132312367435114106411271743218631041094275894508404221506482038656928803775293360599721583316194630449469869000491476753827928793659938654925187969087524783314008405767753004191090522037968098548258698350055999105058915648497702724525585509

n3 = 23693871552180460990138635073805949225912252125308334418081834697641804631104724668330415198785050388969117484647897131795893896100932121531733121069301557203541651575306855376180158639595396645851251320756224273151350168394783274111111375428683335001923152182758469432988805562827169898721409159172411067426322303967736140645806651181720610635139163613355013365367013643617931710120446074129630384181873406149243284193113399417540744056880787819360491511062694356302764642727497777585348003477373456680752873785829149551421840290660162776229985812994060664107888011786183808824620497078292008444842754064007647832261
e3 = 3
c3 = 8177192204481601898705460379101384591996531766013815643642297541939314169289538943467463950155787562006058743758523755363825964609610993939021120980839831173842134605117089923025444468026164578567348718360392736482132312367435114106411271743218631041094275894508404221506482038656928803775293360599721583316194630449469869000491476753827928793659938654925187969087524783314008405767753004191090522037968098548258698350055999105058915648497702724525585509

🚩 Solution

This RSA challenge can be cracked using Håstad’s Broadcast Attack as the scenario satisfies the conditions:

  • The EXPONENT e = 3
  • The MODULUS n contains at least 3 cases ( n1, n2, n3, …)

By using a public Håstad’s Broadcast Attack script, we can easily get the flag directly.

#!/usr/bin/env python3
import gmpy2
gmpy2.get_context().precision = 4096
from binascii import unhexlify
from functools import reduce
from gmpy2 import root

def crt(items):
    
    N = 1
    for a, n in items:
        N *= n

    result = 0
    for a, n in items:
        m = N // n
        r, s, d = xgcd(n, m)
        if d != 1:
            raise "Input not pairwise co-prime"
        result += a * s * m

    return result % N

def xgcd(a, b):
    x, y = 0, 1
    lastx, lasty = 1, 0

    while b:
        a, (q, b) = b, divmod(a, b)
        x, lastx = lastx - q * x, x
        y, lasty = lasty - q * y, y

    return (lastx, lasty, a)

if __name__ == '__main__':

    c = 8177192204481601898705460379101384591996531766013815643642297541939314169289538943467463950155787562006058743758523755363825964609610993939021120980839831173842134605117089923025444468026164578567348718360392736482132312367435114106411271743218631041094275894508404221506482038656928803775293360599721583316194630449469869000491476753827928793659938654925187969087524783314008405767753004191090522037968098548258698350055999105058915648497702724525585509
    e = 3
    n1 = 25204912957894049536633029588071532883154221495361435745558539407530325536509218257991893451902442183954212400671502526830623527340613723328379300388737939211263541814108106183164630301938900862986688763583982133846507136234797325243547177627054271161715200611591594812723672399437505379398941496184886411879923583394041753902383846644013849190900416111230521180435101859101110596828380586449182686175177638441549656137307050392520754146511496313215137339773851458160180450925216541537448515297981124184019831730808991821344392915274230294654187421183676471212265322367890189804699510021526923237231850244056681024361
    n2 = 17730912385401458370516374144454354828481353051514329263921774569034415114147424203611660978860008058118764431105602401970281692066419254457694301039461623568501484102567802483628476717695013320444442267232019104240173401975387173805390636521671252624249730700497552226732834062715286458634274525026438931671208367178653031967364951679420066768732647183187381700016195545187024094717207787859217993871236368911145957298126589666514319408022801341248744002320245345234912423717815146532293315342644702101415345900126397475592837306256140915525455824350305349773210334856093169535686115299159772550674315375987529523179
    n3 = 23693871552180460990138635073805949225912252125308334418081834697641804631104724668330415198785050388969117484647897131795893896100932121531733121069301557203541651575306855376180158639595396645851251320756224273151350168394783274111111375428683335001923152182758469432988805562827169898721409159172411067426322303967736140645806651181720610635139163613355013365367013643617931710120446074129630384181873406149243284193113399417540744056880787819360491511062694356302764642727497777585348003477373456680752873785829149551421840290660162776229985812994060664107888011786183808824620497078292008444842754064007647832261
    C = crt([(c, n1), (c, n2), (c, n3)])
    M = int(root(C, e))
    M = hex(M)[2:]
    print("FLAG:", unhexlify(M).decode('utf-8'))
# byuctf{hastad_broadcast_attack_is_why_e_needs_to_be_very_large}

FLAG: byuctf{hastad_broadcast_attack_is_why_e_needs_to_be_very_large}

💡 BONUS: The FLAG can also be retrieved using RsaCtfTool. The command below used n1, e1, and c1 as example.

python3 RsaCtfTool.py -n 25204912957894049536633029588071532883154221495361435745558539407530325536509218257991893451902442183954212400671502526830623527340613723328379300388737939211263541814108106183164630301938900862986688763583982133846507136234797325243547177627054271161715200611591594812723672399437505379398941496184886411879923583394041753902383846644013849190900416111230521180435101859101110596828380586449182686175177638441549656137307050392520754146511496313215137339773851458160180450925216541537448515297981124184019831730808991821344392915274230294654187421183676471212265322367890189804699510021526923237231850244056681024361 -e 3 --uncipher 8177192204481601898705460379101384591996531766013815643642297541939314169289538943467463950155787562006058743758523755363825964609610993939021120980839831173842134605117089923025444468026164578567348718360392736482132312367435114106411271743218631041094275894508404221506482038656928803775293360599721583316194630449469869000491476753827928793659938654925187969087524783314008405767753004191090522037968098548258698350055999105058915648497702724525585509

Challenge 5: RSA5 [HARD]

100 points, 164 solves

📁 Challenge Description

rsa5.txt

n = 158307578375429142391814474806884486236362186916188452580137711655290101749246194796158132723192108831610021920979976831387798531310286521988621973910776725756124498277292094830880179737057636826926718870947402385998304759357604096043571760391265436342427330673679572532727716853811470803394787706010603830747
e1 = 65537
c1 = 147465654815005020063943150787541676244006907179548061733683379407115931956604160894199596187128857070739585522099795520030109295201146791378167977530770154086872347421667566213107792455663772279848013855378166127142983660396920011133029349489200452580907847840266595584254579298524777000061248118561875608240
e2 = 65521
c2 = 142713643080475406732653557020038566547302005567266455940547551173573770529850069157484999432568532977025654715928532390305041525635025949965799289602536953914794718670859158768092964083443092374251987427058692219234329521939404919423432910655508395090232621076454399975588453154238832799760275047924852124717

🚩 Solution

This RSA challenge can be cracked using Common Modulus Attack of RSA where the FLAG is encrypted using the same modulus n but different exponents e.

Simulate the attack via this site and you will easily get the FLAG.

#!/usr/bin/env python3
from Crypto.Util.number import *
from sage.all import *

n = 158307578375429142391814474806884486236362186916188452580137711655290101749246194796158132723192108831610021920979976831387798531310286521988621973910776725756124498277292094830880179737057636826926718870947402385998304759357604096043571760391265436342427330673679572532727716853811470803394787706010603830747
e1 = 65537
c1 = 147465654815005020063943150787541676244006907179548061733683379407115931956604160894199596187128857070739585522099795520030109295201146791378167977530770154086872347421667566213107792455663772279848013855378166127142983660396920011133029349489200452580907847840266595584254579298524777000061248118561875608240
e2 = 65521
c2 = 142713643080475406732653557020038566547302005567266455940547551173573770529850069157484999432568532977025654715928532390305041525635025949965799289602536953914794718670859158768092964083443092374251987427058692219234329521939404919423432910655508395090232621076454399975588453154238832799760275047924852124717

gcd, a, b = xgcd(e1, e2)
print("FLAG:", long_to_bytes((inverse(c1, n)**(-a) * c2**b) % n).decode())
# byuctf{NEVER_USE_SAME_MODULUS_WITH_DIFFERENT_e_VALUES}

FLAG: byuctf{NEVER_USE_SAME_MODULUS_WITH_DIFFERENT_e_VALUES}