Enormous

2 minutes to read

We are given the Python source code used to encrypt the flag:

#!/usr/bin/env python3

from Crypto.Util.number import *

m = bytes_to_long(open('flag.txt', 'rb').read())  

n = 1
for i in range(5):
    n *= getPrime(2025)

e = 31
c = pow(m, e, n)

print(f'{n = }')
print(f'{c = }')

And we have the ciphertext $c$ and the modulus $n$ of the RSA implementation. Notice that $e = 31$ is very small and $n$ is very large. Hence, we will be able to perform a 31-root to recover the plaintext $m$, because

$$ c = m ^ e \mod{n} $$

Since $n$ is really large and $e$ is very small, it might happen that $m ^ e < n$, and then the modulus $n$ does not have effect, so $m = \sqrt[e]{c}$. We can compute this $e$-th root using gmpy2 in Python:

$ python3 -q
>>> n = 291803461471835548029967773522617765771350293869936352202474825278720037203079126582761195517055393337441548702117740296881683037727672928813574338546415946481976583248116652581196557944379208515379849557208903959136881415277929278949854798024237931268890091008477560536810024512885987056365875451976655685041061567307476564581225633751629621363138947815696306121690184995538414167930734015725366640439645369938523746682075126307100603220423134559397115857296708492139355989095937406415073168747479949371092134873701556328545495456400479495405193756279972004658782475408189585025641505819277077925673695334900236713191922331469670007945415879984668758786665610223439789798214375546410680980683442235218021025215976372242754132940477478408728993116985028306733912194477013321051867704500024616342520287838575375839552875084135772432229149413294380432533743143268579060594509980073144254923676380538357838797628476519470503636727538392293326221896054673794948778257952143474326337234955144876478098752630600927746134626196808185237724150959895921700993985671689787276218491977409950443800149225682113795630552332504004952619477399053219103742133837193866168480669953649964494066888017534621349322438584844756384881305359216958596115238052386689420189458226861633978864646432620132110836770754297086384562270853072519298962385476479869301761383621785222318621201306854098202131486922131567300293859330130962769515935517026489631422656886068186229630258223006684833047809688321362843298049850048526302305175457080852712874501906848203834687269452532674672111135077303202528935822816608612547229714776677161298357980007749334544698155455911782984751127779599045510344930085038624054982145201414246233123815597579302583147041169085302625820240543206702814039468429064024961160403696288636475388432798179348622575416616596660498584921414806447533272237263496191108268914962604350759322278134843256344477715665697069507629272092477112527371006313935780156040584212958154549663363234981080730341044630508652240837192014074955790169192194298119435104568924354781734446534914749601480158889645876224737439717511154355206076336705115742763304668954084456504898364386765064143296380474352710379369338692522064891115596552538797109330579251735034330969865851105628851397031731926651793499033360226446821843504185544154328716719785183357806999155047816431736359882490550923048419234555352161279478407242984715707163307294861304711709346203477359865199980901678783907976621786706266847296286119737497401164377524189197707568924565911584058570117345183256470833488981286971331095107229945553900124115789585129411526064683438180406246914918344456337671900934740227313729020212681061906134397379053692184471039837008926116046967034965277671872122518335972888506407864660599133420704405557724318002121940379059800231596103401873109461507047985158261487833687090154196870319427268386336264078936523908731859981832206513441924170577885564684644417486126018121796087385930741681311819019125337235246299198151106436637821460451583430819222542798910970466234016929862844811  
>>> c = 226930369324008404506430665129822599607363575603852919162120583266060503841096845215449850837542305149561600338927114119661251460696499327139957176529329816529721270191210916244477856685216908277164786965592514696226839914244875659319076517558315356771625419496558856490589162500644071477833930756663564789474118682399930460441453389184243891216077282099093040608309336018996001999607804378777688916461360425788926205328424150096034051909616660195338367962715944075422262015953517413557051762509103453392458978208273498438562590307215849951642965795004794034627510875473381435541017212698396608282069420063879979294704473018597265098131904018063045638336304539514249356120536639126440406176682131920666202709416873040296025545675588170167188101050321143515763604977360112398853875935854811777919563324598193504991150103686515910286033304218405898596673422366231606745906059933502082246405148016608529329647781881278472976090154368272290761619490459310416194216982004034487788734832367018517887748097898401525507381806366491661667977442619626223736995461937920878273486909559233659993985592623485669719325763874250803422121180632196849036588606681806804779542977650673644965059641304478487892054477356779339273971259597178303031111140283501709064199430436811542668710546345343441829103999774652299936885473523503009793950905394505839067527152330406049376043739899459809162044962915696399547788486686478589032533842260339084289115269117632962020418999678475193626806742925843561762423017088328632995430074096317560695952243685718370993439935920576217955150699936307124819436288798249076737597129112939696691564055039464675485835224015600323880336127740300585706502138276566411354270875449815373574454780958012435380709513462476775660322560648809380299392885568074034592363611854633574329130489038883130308557866650522882369513797748667234932757559604717587488355500387902038121779580165322861111064918787012060293221646897837406810365496082480818926712329359069411884747738664835433270202960934930293501624299923646957173316725913900452048522962309107483401916982942273644258253234270266404355705906353284060421906451579547553536945596143114182089674169040390233403896259650990843716723248382763373947627940237097774346467516704409787940216547116621556170101766022005778473958237584851951344954861454573678221816288918395713861770977183669035942556070546761545743731295074496369509049235313470403093920087296483871093325318582310743131764728865964884228088025170409263061963059341395163695331110078909587683201275928829278515137618074138615962652765840849275249482071226860249873486273492767754112528529082909363770315076153401338000909130399064593162194239842969972233531547178659983688101566357539063657007915493318885261560981584227020995472033268237671253586876466785624983819848898009727296036477735934655396784185145970437264598583023149435320752783415451501056661506420824553646380553999069539369921607338465904854175989857439546309918605715931884872868486467592929171204176835962074595013700782437300593834359405047404582902352876008272897313
>>> import gmpy2
>>> gmpy2.iroot(c, 31)
(mpz(200356292991524037137861561536744232032744458778044360811305506965391630908660572435153888208107258), False)

But we see it output False, which means that the root is not exact. Hence, we can think that the modulus has some effect, but it must be short. Therefore, $m = \sqrt[e]{c + k \cdot n}$, where $k$ is some integer.

We can use a for loop until we get that the root is exact, and then print the value formatted as bytes:

>>> for k in range(n):
...     m, ok = gmpy2.iroot(c + k * n, 31)
...     if ok:
...         print(k, bytes.fromhex(hex(m)[2:]).decode())  
...         break
...
28 ictf{d0nt_f0rget_t0_pad_y0ur_pl@intexts!}

And there we have the flag, notice that $k = 28$, so indeed, $m = \sqrt[31]{c + 28 \cdot n}$, which is the vulnerability of using large modulus and short exponents for RSA.