# [BCTF 2016] Hyper RSA

The Plaid Parliament of Pwning participated in (and won) BCTF 2016, hosted by Tsinghua University. Here’s a writeup of one of the problems, which was to decrypt a ciphertext encrypted with a variant of RSA. It was categorized as a cryptography problem and worth 500 points (a hard problem).

We are provided a zipfile containing a censored picture of one run of the program showing the encryption of two messages and their ciphertexts, as well as the server program which implements the Hyper RSA algorithm.

The first message is a random message `m1`, and the second message `m2` is the flag (hidden). Both ciphertexts `c1` and `c2` are shown. The zipfile also contains the source code for the server.

A hint specifies that we can extract the digits from the picture without having to copy them down by hand. Opening the JPEG in a hex editor and scrolling to the bottom reveals that `m1`, `c1`, and `c2`, in plain text, have been appended to the end.

The “Hyper RSA” algorithm consists simply of encrypting a message twice in succession with different RSA keys, i.e.
$c = (m^{e_1} mod n_1) ^ {e_2} mod n_2$

where `n1` < `n2`. The server outputs the `d1` and `d2` for a given `e1` and `e2`, and thus we can trivially obtain the prime factors `p1`, `q1`, `p2` and `q2` (PyCrypto’s `Crypto.PublicKey.RSA` computes `p` and `q` automatically given `n`, `e` and `d`):

```from Crypto.PublicKey import RSA

n1 = 15648839760729136857611980482709455780823249059433822421717774306890912422191494755459005142111607992828285551194094172211798962121953438089140493712726087426107589267481640653515380577953758668008397344082640238769913089651014044547964783609544160815580263066891992072813496322236255529332740322328153851312961936661859569054622011061087082284128807141569973069232563526976554397613026154984099426439128269723550458457280468287574830259658190319585969033124798862730603620119663542163404213185266003198150728644986436777489704208328734400642015199114476591920301342491956560907159473860286478358614493839228472359041
n2 = 27651436873059903761538209234805214287355683678982466405670882487591411436642516539341196342881585483549012954046212429788184908293604454771642818107648395738428697059696871430441866540519287523373879820608795756105878030307235272632107775558053732559632831099019813290110266640343749177716635424859416795786735047143696302657241912433915888805902148923106710885221002650355051396187383500174867165635719900881013089530132697822486081686748180965007087119379517849387088878883805428586240671351051269319387834355886582079118795891068466933583725489045111641949617725339393138570317367622108145858007000011779852522969

e1 = e2 = 65537L
d1 = 801341322260814246824630460655399752818145838891922243118922907272623130275640575542371809160116520803999669038976151516590587254242271361630155437385122135618308277487043746787274626846099365088975410634318638956800407843947741481956296653701423679708979093527160617610847210849213017935527664094073337580381435393973290534456518582972757046608969344358144168412979473661735534751582089315363317465134585473746496679748814555064082863346987139238598778896812527500338856153967668724198040388824191290206624717357686156052566833286119146484827004344810295922696833773843457620396590761038521683261440122811630416689
d2 = 6112369592444250206652792120246931342309257205203457448753438128045787531968813603085828027210972868763821210389054724359391408920906476284797740298236146132148504421988015570026264866754702204115498069199988161171641286983855187064121722759807809689051998476150877140147205896190852409136531995665629661421145487633863099571087668485030471815418539707337877086184665963496813415503578237691985252628347956725542260965108071256348393247267672508371278456781458278900243152599830219742880994068918547883063177015037779478763064694436867660864340069789075521188306329779784328758407937664440952020715843097541060377469

m1 = 5
c1 = 8148957383904486872437828423394164937538328715010815908123576452594275320666784525739878146313196804749598164516555556022796130174158806815977650057288420682101057911994435698789551418753532099866792794103336174859039809215065280033792539448692428913979724682589906786272695510606035436810953248855087491552441188016588591196283340505465679930375746901953008354883148151847641317044080506488273851897144518225216105202686360980631572592060500127238603945606195064022141933818855331043259736453831468578091145713709685544140187848965375739364164364508893499612921555255013961546838234986344590731606667403558040625997

m2 = 6
c2 = 27329182398211347522899299621621113679724446962789840876562317801394564111071637212019506119701609492788475262089552181420526961381419064457579903801235959637592232728341456521117490176148105725533459268071829049691129946006080272549563173732461269479077427460450913074453578152281632632054473142217920030060804696732297435050576686329939098304245739417728714301710598689242692778518299820705103997578604937875292660978826056357830177747872982479026583072444666566525631068826210835394802088986175053586772425867255572780854762523224511193257888117843294675036009361255570186337202498474539261702804344134624782089612

k1 = RSA.construct((n1, e1, d1))
print 'p1 =', k1.p
print 'q1 =', k1.q

k2 = RSA.construct((n2, e2, d2))
print 'p2 =', k2.p
print 'q2 =', k2.q
```

With this information we have the entire private key. However, the exponents `e1` and `e2` used to encrypt the flag are censored out, so we have to find them in order to decrypt the flag.

`e1` and `e2` are each 9 digits long, and we are given (in a second hint) the first digits of each. Thus, we’re looking at testing 108 possibilities for each. We can’t bruteforce both simultaneously – that would be 1016. However, we can apply a meet-in-the-middle attack – encrypt `m1` with all possible `e1` to get all possible intermediate values, then decrypt `c1` with all possible `e2` to find a matching intermediate value (thus “meeting in the middle” of the encryption algorithm). This will only require 2*108 operations. One snag is that RSA decryption is very slow – on the order of O(k3) where `k` is the number of bits in the key. Thus, we have to optimize our attack carefully, and use a lot of CPU power to achieve bruteforce.

We ended up making three major optimizations:

1. When building the table, we use an incremental approach – instead of computing `pow(m1, e1, n1)` for each `e1`, we just multiply in one power of `m1` per iteration, making building the `e1` lookup table extremely fast.
2. Because computing decryptions mod `n2` is slow (because `n2` is long), we do decryptions and checking mod `p2` instead, which is half as long (and thus saves us a factor of 8 on decryption).
3. We use `gmp` instead of Python’s built-in `pow` operators, resulting in approximately a 3x speedup. Note that the bottleneck is in the math operations, so using Python incurs only a very small overhead.

Here’s the bruteforce script:

```from gmpy2 import mpz, powmod, invert

# meet in the middle attack
n1 = mpz(15648839760729136857611980482709455780823249059433822421717774306890912422191494755459005142111607992828285551194094172211798962121953438089140493712726087426107589267481640653515380577953758668008397344082640238769913089651014044547964783609544160815580263066891992072813496322236255529332740322328153851312961936661859569054622011061087082284128807141569973069232563526976554397613026154984099426439128269723550458457280468287574830259658190319585969033124798862730603620119663542163404213185266003198150728644986436777489704208328734400642015199114476591920301342491956560907159473860286478358614493839228472359041)
n2 = mpz(27651436873059903761538209234805214287355683678982466405670882487591411436642516539341196342881585483549012954046212429788184908293604454771642818107648395738428697059696871430441866540519287523373879820608795756105878030307235272632107775558053732559632831099019813290110266640343749177716635424859416795786735047143696302657241912433915888805902148923106710885221002650355051396187383500174867165635719900881013089530132697822486081686748180965007087119379517849387088878883805428586240671351051269319387834355886582079118795891068466933583725489045111641949617725339393138570317367622108145858007000011779852522969)
p1 = mpz(115828295588509413765657818406867516713730517750406039982953961273698342446377470065543059874105959316059071676627111613027995982755516722160046640303691478999889733390879707640738371507340736543076237714407338833975162482946492306016288364033279369606285818202050898542042181475127562843844261502082049451227)
q1 = mpz(135103773056655064969327506003939867649872833235629494898764581981413343302990941336623787091683416428670125487239155394679492615647758178987290636992620311385747374284630346686620855693905295085863655381869122493807428330545415365431415934084226911263424822550817854835936312436952242226359922048497488873683)
p2 = mpz(163285832687189913045952152660621786604149906417402530050953092553171258537152762832184438186860672227164970561277480748279613378334451380709795952602873533444456320203007264412590461372740523801471983692035577494148110307472755151546109784012759812974741115311165842719401610463185434834345546986734727953667)
q2 = mpz(169343760067858061351166362331954299819512318283672226414306253481409314715323098520315259960487582355659180136088759841701142965265979658078717533720357215488070848738430999730412016543181673065902912717103510024351166643904333588480201806104579175415269242403617262452711780440867442673992494021555894641907)

m1 = mpz(1291575311227647404937745977674300102552159140130724372672273512124326901689475940631797723907388299601908770592275163938119318483657985194901345321320)
c1 = mpz(3612783941217721669487918278209911521323696929552012175100130528144953435277957012327876297909487756767163399469731122537754642368918321895211682844060051902226307200945658526452184995263241224610748656158064831467711457662659609765597325107742484418555573571733455873166185394833773943367518472411975358177757721075900099526140241289604501293079211412322023186020382617546224962628798465635111775435684570876736680218992899063074934853328180993221927800114698375815660980849891750946707282694641977171200300901905249566807230865872745785916874656741470951342227797544099362706484433003094851882722308369118455538479)
c2 = mpz(13554020299054897579091249483707073724753575878577890667835151695153327166821147325776948828180031343971239625502353717032241825522884776444516550436927491420615799010177208450427000928631877919824890289537268758084609024561404818087048530732153137144763446412469130412144867577343408806134871838870680552607734311806612058857668100766723847349927926306865890803886354120634869482202437175237946453446209830904959307383604085169656048730378082783123213285644191038076249938111121280355516863102198358773908064076460289440391523937387728878878040531689192081196613749284337216979844083031586740238692461049241310327972)

# test: e1=e2=65537
# m1 = mpz(5)
# c1 = mpz(8148957383904486872437828423394164937538328715010815908123576452594275320666784525739878146313196804749598164516555556022796130174158806815977650057288420682101057911994435698789551418753532099866792794103336174859039809215065280033792539448692428913979724682589906786272695510606035436810953248855087491552441188016588591196283340505465679930375746901953008354883148151847641317044080506488273851897144518225216105202686360980631572592060500127238603945606195064022141933818855331043259736453831468578091145713709685544140187848965375739364164364508893499612921555255013961546838234986344590731606667403558040625997)

cache = {}

cur = powmod(m1, 10000000, n1)
for e1 in xrange(10000000, 20000000):
if e1 % 100000 == 0:
print "build progress:", e1
cache[cur % p2] = e1
cur = (cur * m1) % n1

p2a = p2-1
c1p = c1 % p2

def doit(e2):
if e2 % 100000 == 0:
print "check progress:", e2

try:
dp = invert(e2, p2a)
except Exception:
return None

mp = powmod(c1p, dp, p2)
if mp in cache:
print "FOUND IT!!!", cache[mp], e2
return cache[mp], e2

return None

import multiprocessing
p = multiprocessing.Pool()
results = p.map(doit, xrange(20000000, 30000000))
for r in results:
if r is not None:
print r
```

We were able to obtain a solution in approximately 15 minutes after running it on a 48-core machine. The values were `e1 = 134217757, e2 = 251658263`.

We plugged these in to the HyperRSA decryption algorithm:

```e1 = 134217757
e2 = 251658263

n1 = 15648839760729136857611980482709455780823249059433822421717774306890912422191494755459005142111607992828285551194094172211798962121953438089140493712726087426107589267481640653515380577953758668008397344082640238769913089651014044547964783609544160815580263066891992072813496322236255529332740322328153851312961936661859569054622011061087082284128807141569973069232563526976554397613026154984099426439128269723550458457280468287574830259658190319585969033124798862730603620119663542163404213185266003198150728644986436777489704208328734400642015199114476591920301342491956560907159473860286478358614493839228472359041
n2 = 27651436873059903761538209234805214287355683678982466405670882487591411436642516539341196342881585483549012954046212429788184908293604454771642818107648395738428697059696871430441866540519287523373879820608795756105878030307235272632107775558053732559632831099019813290110266640343749177716635424859416795786735047143696302657241912433915888805902148923106710885221002650355051396187383500174867165635719900881013089530132697822486081686748180965007087119379517849387088878883805428586240671351051269319387834355886582079118795891068466933583725489045111641949617725339393138570317367622108145858007000011779852522969
p1 = 115828295588509413765657818406867516713730517750406039982953961273698342446377470065543059874105959316059071676627111613027995982755516722160046640303691478999889733390879707640738371507340736543076237714407338833975162482946492306016288364033279369606285818202050898542042181475127562843844261502082049451227
q1 = 135103773056655064969327506003939867649872833235629494898764581981413343302990941336623787091683416428670125487239155394679492615647758178987290636992620311385747374284630346686620855693905295085863655381869122493807428330545415365431415934084226911263424822550817854835936312436952242226359922048497488873683
p2 = 163285832687189913045952152660621786604149906417402530050953092553171258537152762832184438186860672227164970561277480748279613378334451380709795952602873533444456320203007264412590461372740523801471983692035577494148110307472755151546109784012759812974741115311165842719401610463185434834345546986734727953667
q2 = 169343760067858061351166362331954299819512318283672226414306253481409314715323098520315259960487582355659180136088759841701142965265979658078717533720357215488070848738430999730412016543181673065902912717103510024351166643904333588480201806104579175415269242403617262452711780440867442673992494021555894641907

m1 = 1291575311227647404937745977674300102552159140130724372672273512124326901689475940631797723907388299601908770592275163938119318483657985194901345321320
c1 = 3612783941217721669487918278209911521323696929552012175100130528144953435277957012327876297909487756767163399469731122537754642368918321895211682844060051902226307200945658526452184995263241224610748656158064831467711457662659609765597325107742484418555573571733455873166185394833773943367518472411975358177757721075900099526140241289604501293079211412322023186020382617546224962628798465635111775435684570876736680218992899063074934853328180993221927800114698375815660980849891750946707282694641977171200300901905249566807230865872745785916874656741470951342227797544099362706484433003094851882722308369118455538479
c2 = 13554020299054897579091249483707073724753575878577890667835151695153327166821147325776948828180031343971239625502353717032241825522884776444516550436927491420615799010177208450427000928631877919824890289537268758084609024561404818087048530732153137144763446412469130412144867577343408806134871838870680552607734311806612058857668100766723847349927926306865890803886354120634869482202437175237946453446209830904959307383604085169656048730378082783123213285644191038076249938111121280355516863102198358773908064076460289440391523937387728878878040531689192081196613749284337216979844083031586740238692461049241310327972

from Crypto.Util.number import inverse

d1 = inverse(e1, (p1-1)*(q1-1))
d2 = inverse(e2, (p2-1)*(q2-1))
m = pow(pow(c2, d2, n2), d1, n1)
print format(m, 'x').decode('hex')
```

to get the flag: `BCTF{learn-y0u-A_haske11-f0r_9rea7-g00d}`