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

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

We are given the public modulus $n = p \cdot q$:

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

After that, the server generates a random value $k \in [600, 1200]$ and computes its factorial $f = k!$. We are given this 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:

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

Where $r$ is an unknown 256-bit prime number.

Afterwards, the server generates a second RSA key (only $e = 65537$ and $d$ are modified), to encrypt the 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 = }")

Solution

The first thing we notice is that the correct value of $k$ can be obtained with brute force since $k \in [600, 1200]$. Assumming we have the right $k$, we get:

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

Observe that $f = k!$, so it is a huge number (using the Stirling formula, we can see that $k! > 2^{8000}$). If we divide the above expression by $f$ (integer division), we will get:

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

And applying modulo $f$, we have:

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

So, we can apply the GCD to obtain the prime number $r$.

Then, we can find the 2047-bit $e$ of the first RSA key by computing the square root (after dividing $r$).

After that, we can find $d$. We know that $e \cdot d - 1 \equiv 0 \pmod{\phi(n)}$. Therefore, we can express the previous congruence as $e \cdot d - 1 = z \cdot \phi(n)$ for some $z \in \mathbb{Z}$.

But actually, we don’t need to find $\phi(n)$, since inverses modulo $z \cdot \phi(n)$ are also inverses modulo $\phi(n)$. So, if we compute $d_x = 65537^{-1} \mod{z \cdot \phi(n)}$, we will decrypt $m$ correctly since:

$$ \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} $$

Implementation

So, we only need to script the above procedure and perform the brute force attack on $k$. This is the relevant part:

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.