Big RSA
4 minutes to read
We are given the Python source code to encrypt the flag:
from Crypto.Util.number import getPrime, getStrongPrime, bytes_to_long
from sympy import factorial
from random import randint
from secret import flag
p, q = getStrongPrime(1024), getStrongPrime(1024)
def RSAgen(e = None):
d = 0
if not e:
while(d.bit_length() < 2047):
e = getPrime(2047)
d = pow(e, -1, (p-1)*(q-1))
else:
d = pow(e, -1, (p-1)*(q-1))
return (p*q, p, q, e, d)
n = p*q
print(f'{n = }')
key = RSAgen()
k = randint(600, 1200)
f = factorial(k)
leak = (pow(key[3], 2) + (key[3]*key[4] - 1)*f)*getPrime(256) + k
# 2048 bit e is very expensive, i should use standard e for my encryption
key = RSAgen(65537)
e = key[3]
flag = bytes_to_long(flag)
c = pow(flag, e, n)
print(f"{c = }")
print(f"{leak = }")
#OUTPUT
#
#n = 26155610563918771040451217453770153423175480849248932666067623213096628137347700281227651842637531066158966523562535269946270160966349550464316855975843702602386644310622115374093643617687763127399565005930283899166880048303714803385714487858740617133136915034968428269114907303042424391192431406494414712801428682398922655599872605973327217541188045983390427079210204358352343375551675052592229757120847888780576171954181304712725822439789885440973203535622584052397858824995170393109932313608251208103032787250637381098134254687242226624254464180882206386756799922789661143241398308165644172112918996116051241341767
#c = 14882143057207490168145609595794327950964467559973424621597752378687475531116051048471999976592360385753040756962986881197575420871063219354858309758384966841729075968439470757951580317772601028800980369844502945471937420415705013093369495725032356110007789188647453706470456907380267324946203780527015651994928850341098799680560649210763871810476662426271293840410794844793663532229448343601068354829550752842074478598115636890530640204633346276888013284576380941564885085920559055293159358576137659586044231684426664502650956119257574114940925398612801662412390652208379645262117964212231444035372237602987220161154
#leak = 8882329530176003989563469282320326448513961425520889104820115352134009331360402757127024139665879246460280903840841878434886334764358389863635520069842148223207565079555357126011768633841724238023402746185876779525887392481984149029421348288859961294980594601070755980946189936784537926893399566710815892754474482631518313221065280747677073806153015411511245208373763611976120763693741604815436190527484656588721635559583703292529849150438632820886160326184322723507482566078134710656764953471923255683042573911453728381364857973339477093454501755540396376196910045154990604723000628164844678783206034532184996212426411646863562670787117170937484057232253132378686191307517787281075273286073730517840320844224160937065166742670192503005084799125432651202276745876948826479983116284656814139188066381428020724692363565714860614527931752152240198254329317479816158596931824787225489069026346088037877441040453722896865574447079406031506283100005929709985031578939782011738018467829080816081913925121672327305968766974521281843700741425497908524015911173859409613820295440717780859694704848500536323185048069666385294578000406894438137681553061828379901393410655028227052289995544806138411605538810055799529381568985312754486907514057810886832822416112077637141046599291719695931641341477116694041607732362173173111829958139812135983269100274129925726662395368378059697391687349679786945510641238252220381519030943165126475181808810902040710261462429322977874350519175554159491968977598607860470919877896807912649830555310344788510811708640852621939517683512617800947347015328336403343549764926804605586325355602602157724502283094424228440314761426084409569002423419659272529716195776451657960565924304898320195699180560668631806178645741692749524883469846005409211271022431433039546590781549630715275308124729500303196140494010253387465310270348759187686632848767083559239773341844408450815683523679200221818741654323193797457218877776650125241324891467161777274139708214831833313936201971466603547791591622683172049635972772551806007816208466413199652425970868250229578051299718112290796388965170374760048006586491240415960299655674234758022536120132945656010849673271011148857409644260456852793444292102864629782613888832787049959589501287519423225832100567897316528973935415321329220397090613054817402449251249956025659833660199528249628136823951941068620183704359665779941064385612344970878816496323047753331967618070575102035154652470553061929831610193694052912228006377979477318327954292917783836426814224401489211262556447908499035071972531345812915421543036881828636718727357962701875285833936517812391121587399727281240931927431811181444977909594218984279921315492877394195428208756441893687385105650326859023900280137352737660777503064484456016697716191624303099683835521939233782390584505763849676573364198388306561033652480971048175488758111144736636640190185417713883213429725379415164862080052393396741667399031632758281193771891210430178563364662790052209648349668663621672614807647401120518076403133998551484399204398325200361951412241887720441234483010617920388630542945062451586033688057992061925968617174491390233664273716567854279453909892176120950383253842037120054072618389794275273311333932588139102552015371447182882116160259277516530183031644054520783191752410514938160605548110059282703060409667276475969749797140136872904654013231613962248971564712815341527356396922068564215026284215874684201258558000033165916019163319759952566031082383620943938948623145286816988139057606627616639594815749554968862963450819772941547102531289115954195402127419754744687573822011699197232836491588776322734503766502102575418226503487579619923510951731702344792411606628965837547432575532404303417689912716247856960760491417279481456633424179644033150732614552508566990237704498608189201159580503580410535170284429946552129635519661513317741471932078145289068540132823
The output of the script is commented belowin the same script.
Source code analysis
The server generates two prime random 1024-bit numbers
p, q = getStrongPrime(1024), getStrongPrime(1024)
We are given the public modulus
n = p*q
print(f'{n = }')
Then, an RSA key is generated using the function RSAgen
:
def RSAgen(e = None):
d = 0
if not e:
while(d.bit_length() < 2047):
e = getPrime(2047)
d = pow(e, -1, (p-1)*(q-1))
else:
d = pow(e, -1, (p-1)*(q-1))
return (p*q, p, q, e, d)
As can be seen, if no parameter e
is specified, the server generates a random 2047-bit prime number for the public exponent
After that, the server generates a random value leak
:
k = randint(600, 1200)
f = factorial(k)
leak = (pow(key[3], 2) + (key[3]*key[4] - 1)*f)*getPrime(256) + k
In math terms, leak
is:
Where
Afterwards, the server generates a second RSA key (only
# 2048 bit e is very expensive, i should use standard e for my encryption
key = RSAgen(65537)
e = key[3]
flag = bytes_to_long(flag)
c = pow(flag, e, n)
print(f"{c = }")
Solution
The first thing we notice is that the correct value of
Observe that
And applying modulo
So, we can apply the GCD to obtain the prime number
Then, we can find the 2047-bit
After that, we can find
But actually, we don’t need to find
Implementation
So, we only need to script the above procedure and perform the brute force attack on
for k in range(600, 1200 + 1):
f = factorial(k)
e2_r = (leak - k) % f
ed_1_r = (leak - k) // f
r = gcd(e2_r, ed_1_r)
if isPrime(r) and r.bit_length() == 256:
e = isqrt(e2_r // r)
d = (ed_1_r // r + 1) // e
if isPrime(e) and e.bit_length() == 2047 and d.bit_length() >= 2047:
z_phi_n = e * d - 1
d_x = pow(65537, -1, z_phi_n)
print(long_to_bytes(pow(c, d_x, n)).decode())
break
Flag
If we run the script, we will get the flag:
$ python3 solve.py
flag{gcd_is_always_useful}
The full script can be found in here: solve.py
.