Big RSA
4 minutos de lectura
Se nos proporciona el código fuente en Python para cifrar la 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
La salida del script está comentada en el propio código.
Análisis del código fuente
El servidor genera dos números primos aleatorios de 1024 bits
p, q = getStrongPrime(1024), getStrongPrime(1024)
Nos dan el módulo público
n = p*q
print(f'{n = }')
Luego, se genera una clave RSA utilizando la función 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)
Como se puede ver, si no se especifica el parámetro e
, el servidor genera un número primo aleatorio de 2047 bits para el exponente público
Después de eso, el servidor genera un valor aleatorio leak
:
k = randint(600, 1200)
f = factorial(k)
leak = (pow(key[3], 2) + (key[3]*key[4] - 1)*f)*getPrime(256) + k
En términos matemáticos, leak
es:
Donde
Posteriormente, el servidor genera una segunda clave RSA (solo
# 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 = }")
Solución
Lo primero que notamos es que el valor correcto de
Nótese que
Y aplicando módulo
Entonces, podemos aplicar el GCD (máximo común divisor) para obtener el número primo
Luego, podemos encontrar el valor de
Después de eso, podemos hallar
Pero en realidad, no necesitamos encontrar
Implementación
Por lo tanto, solo necesitamos escribir el procedimiento anterior y realizar el ataque de fuerza bruta en
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
Si ejecutamos el script, obtendremos la flag:
$ python3 solve.py
flag{gcd_is_always_useful}
El script completo se puede encontrar aquí: solve.py
.