Rating:
# TeamItaly CTF 2023
## [crypto] Big RSA (33 solves)
## Solution
Two steps are necessary to solve the challenge
- First we need to recover k and the multiple of phi in the leak
- then we can factor n using the knowledge of phi*a (with a unknown)
### Recovering k
It's possible to recover the value of k as different values of factorial(k) are distinguishable just from their bitsize
One way of doing so is to use the following relation:
$$(k-1)! < leak/(2^{256}*n^2) < k!$$
### Recovering the multiple of phi(n)
Let e_ = `(e^2)*getPrime(256)`, notice that e_ < k! for all possible values of k. Therefore: `(leak - k)%(k!) == e_t$$`
phi*a can now be recovered from the original equation of the leak
### Factoring n
Given n and a multiple of phi(n), it's possible to easily factor n in the following way:
$$p = gcd(b^{a*phi/2^t}-1, n)$$
see https://math.stackexchange.com/a/191913 for a more detailed explanation of how this works
### Exploit
```python
from sympy import gcd, factorial
from Crypto.Util.number import long_to_bytes
n = 26155610563918771040451217453770153423175480849248932666067623213096628137347700281227651842637531066158966523562535269946270160966349550464316855975843702602386644310622115374093643617687763127399565005930283899166880048303714803385714487858740617133136915034968428269114907303042424391192431406494414712801428682398922655599872605973327217541188045983390427079210204358352343375551675052592229757120847888780576171954181304712725822439789885440973203535622584052397858824995170393109932313608251208103032787250637381098134254687242226624254464180882206386756799922789661143241398308165644172112918996116051241341767
c = 14882143057207490168145609595794327950964467559973424621597752378687475531116051048471999976592360385753040756962986881197575420871063219354858309758384966841729075968439470757951580317772601028800980369844502945471937420415705013093369495725032356110007789188647453706470456907380267324946203780527015651994928850341098799680560649210763871810476662426271293840410794844793663532229448343601068354829550752842074478598115636890530640204633346276888013284576380941564885085920559055293159358576137659586044231684426664502650956119257574114940925398612801662412390652208379645262117964212231444035372237602987220161154
leak = 8882329530176003989563469282320326448513961425520889104820115352134009331360402757127024139665879246460280903840841878434886334764358389863635520069842148223207565079555357126011768633841724238023402746185876779525887392481984149029421348288859961294980594601070755980946189936784537926893399566710815892754474482631518313221065280747677073806153015411511245208373763611976120763693741604815436190527484656588721635559583703292529849150438632820886160326184322723507482566078134710656764953471923255683042573911453728381364857973339477093454501755540396376196910045154990604723000628164844678783206034532184996212426411646863562670787117170937484057232253132378686191307517787281075273286073730517840320844224160937065166742670192503005084799125432651202276745876948826479983116284656814139188066381428020724692363565714860614527931752152240198254329317479816158596931824787225489069026346088037877441040453722896865574447079406031506283100005929709985031578939782011738018467829080816081913925121672327305968766974521281843700741425497908524015911173859409613820295440717780859694704848500536323185048069666385294578000406894438137681553061828379901393410655028227052289995544806138411605538810055799529381568985312754486907514057810886832822416112077637141046599291719695931641341477116694041607732362173173111829958139812135983269100274129925726662395368378059697391687349679786945510641238252220381519030943165126475181808810902040710261462429322977874350519175554159491968977598607860470919877896807912649830555310344788510811708640852621939517683512617800947347015328336403343549764926804605586325355602602157724502283094424228440314761426084409569002423419659272529716195776451657960565924304898320195699180560668631806178645741692749524883469846005409211271022431433039546590781549630715275308124729500303196140494010253387465310270348759187686632848767083559239773341844408450815683523679200221818741654323193797457218877776650125241324891467161777274139708214831833313936201971466603547791591622683172049635972772551806007816208466413199652425970868250229578051299718112290796388965170374760048006586491240415960299655674234758022536120132945656010849673271011148857409644260456852793444292102864629782613888832787049959589501287519423225832100567897316528973935415321329220397090613054817402449251249956025659833660199528249628136823951941068620183704359665779941064385612344970878816496323047753331967618070575102035154652470553061929831610193694052912228006377979477318327954292917783836426814224401489211262556447908499035071972531345812915421543036881828636718727357962701875285833936517812391121587399727281240931927431811181444977909594218984279921315492877394195428208756441893687385105650326859023900280137352737660777503064484456016697716191624303099683835521939233782390584505763849676573364198388306561033652480971048175488758111144736636640190185417713883213429725379415164862080052393396741667399031632758281193771891210430178563364662790052209648349668663621672614807647401120518076403133998551484399204398325200361951412241887720441234483010617920388630542945062451586033688057992061925968617174491390233664273716567854279453909892176120950383253842037120054072618389794275273311333932588139102552015371447182882116160259277516530183031644054520783191752410514938160605548110059282703060409667276475969749797140136872904654013231613962248971564712815341527356396922068564215026284215874684201258558000033165916019163319759952566031082383620943938948623145286816988139057606627616639594815749554968862963450819772941547102531289115954195402127419754744687573822011699197232836491588776322734503766502102575418226503487579619923510951731702344792411606628965837547432575532404303417689912716247856960760491417279481456633424179644033150732614552508566990237704498608189201159580503580410535170284429946552129635519661513317741471932078145289068540132823
def recPhi_(leak):
f_ = factorial(599)
l = leak//(pow(n, 2))
l >>= 256
for x in range(600, 1200):
f_ *= x
if f_ - l > 0:
print(f'k = {x}')
k = x
break
e_ = (leak - k)%(factorial(k))
phi_ = (leak - k - e_)//(factorial(k))
return int(phi_)
def factor(n, t):
for _ in range(10):
for b in range(1, 100, 2):
num = pow(b, t, n)
if gcd(num-1, n) not in [1, n]:
return gcd(num-1, n)
return False
phi_ = recPhi_(leak)
t = 0
p = 0
while phi_%2==0:
phi_ = phi_//2
t+=1
p = factor(n, phi_)
if p:
print('found!')
print(p)
break
p = int(p)
q = n//p
e = 65537
d = pow(e, -1, (p-1)*(q-1))
flag = pow(c, d, n)
print(long_to_bytes(flag).decode())
```
