<- TEAMITALY CTF

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$ y $q$:

p, q = getStrongPrime(1024), getStrongPrime(1024)

Nos dan el módulo público $n = p \cdot q$:

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 $e$.

Después de eso, el servidor genera un valor aleatorio $k \in [600, 1200]$ y calcula $f = k!$. Se nos da este valor 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:

$$ L = \left(e^2 + (e \cdot d - 1) \cdot f\right) \cdot r + k $$

Donde $r$ es un número primo desconocido de 256 bits.

Posteriormente, el servidor genera una segunda clave RSA (solo $e = 65537 $ y $d$ se modifican), para cifrar la flag:

# 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 $k$ se puede obtener con fuerza bruta ya que $k \in [600, 1200]$. Suponiendo que tenemos el valor de $k$ correcto, tenemos:

$$ L - k = \left(e^2 + (e \cdot d - 1) \cdot f\right) \cdot r $$

Nótese que $f = k!$, que es un número gigantesco (usando la fórmula de Stirling, podemos ver que $k! > 2^{8000}$). Si dividimos la expresión anterior entre $f$ (división entera), obtenemos:

$$ \frac{L - k}{f} = (e \cdot d - 1) r $$

Y aplicando módulo $f$, tenemos:

$$ L - k \mod{f} = e^2 r $$

Entonces, podemos aplicar el GCD (máximo común divisor) para obtener el número primo $r$.

Luego, podemos encontrar el valor de $e$ de 2047 bits de la primera clave RSA calculando la raíz cuadrada (después de dividir entre $r$).

Después de eso, podemos hallar $d$. Sabemos que $e \cdot d - 1 \equiv 0 \pmod{\phi(n)}$. Por lo tanto, podemos expresar la congruencia anterior como $e \cdot d - 1 = z \cdot \phi(n)$ para un cierto $z \in \mathbb{Z}$.

Pero en realidad, no necesitamos encontrar $\phi(n)$, dado que los inversos en módulo $z \cdot \phi(n)$ también son inversos en módulo $\phi(n)$. Entonces, si calculamos $d_x = 65537^{-1} \mod{z \cdot \phi(n)}$, descifraremos $m$ correctamente ya que:

$$ \begin{align} c^{d_x} & = c^{(65537^{-1} \mod{z \cdot \phi(n)})} \\ & = c^{65537^{-1} + l \cdot z \cdot \phi(n)} = c^{65537^{-1}} \cdot c^{l \cdot z \cdot \phi(n)} \quad l \in \mathbb{Z} \\ & = c^{65537^{-1}} = (m^{65537})^{65537^{-1}} \\ & = m \mod{n} \end{align} $$

Implementación

Por lo tanto, solo necesitamos escribir el procedimiento anterior y realizar el ataque de fuerza bruta en $k$. Esta es la parte relevante:

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.