Tags: rsa crypto
Rating:
The problem give us 2 files: `chal.sage` and `out.txt`, detailed as follow:
`chal.sage`
```sage
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long
import random
import binascii
from secret import flag
e = 3
BITSIZE = 8192
key = RSA.generate(BITSIZE)
n = key.n
flag = bytes_to_long(flag)
m = floor(BITSIZE/(e*e)) - 400
assert (m < BITSIZE - len(bin(flag)[2:]))
r1 = random.randint(1,pow(2,m))
r2 = random.randint(r1,pow(2,m))
msg1 = pow(2,m)*flag + r1
msg2 = pow(2,m)*flag + r2
C1 = Integer(pow(msg1,e,n))
C2 = Integer(pow(msg2,e,n))
print(f'{n = }\n{C1 = }\n{C2 = }')
```
----
`out.txt`
```txt
n = 823652328526060931201375649241006048943627312591742662481083103378002522077877852124731191042617160616707714556599692967069663667698601996983528940331840856212083763983210643933408040552418340463683380557808507002495230815546453104038740886365473259236836768987811419579308089803722619415774848441151249684528573808701348303730672001325400435253430057941264536553439343549378798471521843765967413899839467956313753964739101523564712402586172009670872793597148015854112713073516537134244622001863136944934492241145306737850771111625635504275979597201321615004183224138178242850606020061860874365891414739635021953470569531263648279914661978749409495850032838932287660547294983608500552408270453150111004704982673000064474229357303826290412232101668643442191345117752836713723186345029858940323602239828980619674790421554523298312252632246856653570861376722546483845572057592874642653507921669598604980999675710944351125800581153679737947035951167396427406664211538456926422574733908468243848301080202616710219948021550303624199272309262465841979895988543037749409344273271528685813232663250051559875409936374630801262025889212026998068310718442102601557388789291924368011403387710015947533663816312246609754580679612583443687679604653697210741383870120265666560114312552082718765229857906075466911647146394186461224534740685587572846934610230530077015354170886197688407248753878297395666994564903309464938353409270895657559261894379593177576322878056778321362020242262629594237747578073010697822390042229221755183530894661801846645578606229378188194698297341498164221255458973569036112042793665638020083355322818801649079577206155596664351547761867936241825962264402061264130743855926770190009644935373522637016531313612905118696369479379392748765790270985780979092810127202612369788297683386941277137962371308477169065442960974519121200614968578299255908217109555425373639991249942561881066593925137769635916819686179968920303847549317832449280869569173490086055713440659573036379376871313591502012736961740953226823792006776306025493582816361497869257717651668075570919074032100188984609089237083774415809378590512597855039607625398955711313352280354581208986236739705133090250836743923077744209886105632205516098409509945870967048379575392597005574605671295696290105152505109115729545462303929321064678575733744453013844396847747874774560936394947704938716022268449263762808882912779863563062087323815155503567025604594567944510834845389179609006394130719657363087
C1 = 138604270237134534112743212644616449187692378939637896055320936677529897960835117799077267347298678107031857708834234867949004008866584408288272718174944005247281182704110071985982762860316789278723189738430436690943806868878982562799129736576593875631850056775539229239799682738700710216806174002449616599477466210310386600736499714740361747969973718347095697189605303148613119104798603461313289164107162759182110107568729898709265252329895862170091572165860623096748730108315029720395180483240857815537765987240293780559413621634616731611457999105645890254616180108684484111551400204145466579713376335168837095473428132610657311922576659063964864816927637794472255883920363962994040086056352213615355155336047742875321877777043584327913192448537029767660816802421871457551873100279391823455263903450304034557919732645143487533538943198997776987742643929566403463889152262047049873409325737357390275038091407938919150758822963329761264354005399142689352595527066743969291045496548965996410916410974600827179080229802502026992567559903302198282019316525974045236753071662259094177004561587843521123352176047829889922474932560434065169177898287264496750729243672
C2 = 138604270237134534112743212644616449187692378939637896055320936677529897960835117799077267347298678107031857708834234867949004008866584408288272718174944005247281182704110071985982762860316789278723189738430436690943806868878982562801315565156426103645734001592666235894224346424366448014174339619953344112868374944069699668659552171905796026764359565068714399719527680623357405851675409955573477228301886561411896147227291350808930951282598922176120977605666135963906053158934308125639347521515926780372069545707019601637468577493997742590807146827349865640857651027809446746299962731018358206171079317925725680542147150070051957133849278906576405074966481232057919403951090124732230438431203080079109828298282999845576767904877434936923847105040157703725014937676457110907557409863930279230474134789746314617582331031090955073528453085567165286271224442421785911327002274933133905582320854345262688022854226418394665705506630780960278867388105443056536999414456768050350078505683642885335398895190922264436040594316438930099159076822113725497974332635130516805301785291427363314598707750026963533325470071715793252887081074252099626695293515248472454824781000
```
We have:
+ `msg1^3 = C1 (mod n)`
+ `msg2^3 = C2 (mod n)`
+ `msg1 = flag * 2^{m} + r1`
+ `msg2 = flag * 2^{m} + r2`
+ With `m = 510` , `1<=r1<=r2<=2^m`
We will analyze a little bit about number digit of `msg1,C1,C2` and `n`
We have:
+ `n` has `2466` digits
+ `C1` and `C2` have also `1161` digits
+ `2^m` has approxiate `153` digits => `msg1^3` has approxiate `459*flag`
While `C1` has `1161`
So from those, we have: `msg1^3=C1` and `msg2^3=C2`
Now, we have `C1,C2`, actually we need compute only `msg1` is enough !
Now, we will use `Divide and Conquer Algorithm` to compute cube root of `C1`
This is the code find n'th root of number x
```py
def nth_root(x, n):
# Start with some reasonable bounds around the nth root.
upper_bound = 1
while upper_bound ** n <= x:
upper_bound *= 2
lower_bound = upper_bound // 2
# Keep searching for a better result as long as the bounds make sense.
while lower_bound < upper_bound:
mid = (lower_bound + upper_bound) // 2
mid_nth = mid ** n
if lower_bound < mid and mid_nth < x:
lower_bound = mid
elif upper_bound > mid and mid_nth > x:
upper_bound = mid
else:
# Found perfect nth root.
return mid
return mid + 1
```
And this solution of this problem
```py
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long,long_to_bytes
import random
import binascii
from secret import flag
###### PROBLEM ######
# e = 3
# BITSIZE = 1024
# key = RSA.generate(BITSIZE)
# n = key.n
# flag = bytes_to_long(flag)
# print("n: ",n)
# print("flag: ",flag)
# m = BITSIZE//(e*e) - 50
# r1 = random.randint(1,pow(2,m))
# r2 = random.randint(r1,pow(2,m))
# msg1 = pow(2,m)*flag + r1
# msg2 = pow(2,m)*flag + r2
# C1 = pow(msg1,e,n)
# C2 = pow(msg2,e,n)
# print(f'{n = }\n{C1 = }\n{C2 = }')
# print("Test 1:",pow(msg1,3)-C1)
# print("Test 2:",pow(msg2,3)-C2)
###### SOLUTION ######
def nth_root(x, n):
# Start with some reasonable bounds around the nth root.
upper_bound = 1
while upper_bound ** n <= x:
upper_bound *= 2
lower_bound = upper_bound // 2
# Keep searching for a better result as long as the bounds make sense.
while lower_bound < upper_bound:
mid = (lower_bound + upper_bound) // 2
mid_nth = mid ** n
if lower_bound < mid and mid_nth < x:
lower_bound = mid
elif upper_bound > mid and mid_nth > x:
upper_bound = mid
else:
# Found perfect nth root.
return mid
return mid + 1
m = 510
C1 = 138604270237134534112743212644616449187692378939637896055320936677529897960835117799077267347298678107031857708834234867949004008866584408288272718174944005247281182704110071985982762860316789278723189738430436690943806868878982562799129736576593875631850056775539229239799682738700710216806174002449616599477466210310386600736499714740361747969973718347095697189605303148613119104798603461313289164107162759182110107568729898709265252329895862170091572165860623096748730108315029720395180483240857815537765987240293780559413621634616731611457999105645890254616180108684484111551400204145466579713376335168837095473428132610657311922576659063964864816927637794472255883920363962994040086056352213615355155336047742875321877777043584327913192448537029767660816802421871457551873100279391823455263903450304034557919732645143487533538943198997776987742643929566403463889152262047049873409325737357390275038091407938919150758822963329761264354005399142689352595527066743969291045496548965996410916410974600827179080229802502026992567559903302198282019316525974045236753071662259094177004561587843521123352176047829889922474932560434065169177898287264496750729243672
g1 = nth_root(C1,3)
K = pow(2,m)
r1 = g1 % K
# print(r1)
flag = (g1-r1)//K
print(long_to_bytes(flag))
#flag_final = 154393050551454020090514297200922012210056319897965118750440811938341742022936780608133963214043027836777756205300371216004407768274132755769040020127958503581173320507900533732136817550207767148177469879490070754935314884923896381309
# flag_final1 = 2689276504310631707478400123130984936310976782319770622603922543360881069490035758414301813498217745374830369542722941247551735690124561015564676628519906993119832597021135435970751146045680238055519831015820279678694558572703641886454848236967291037462015700658168832646801086807243098003268469538880
# print(long_to_bytes(flag_final1))
```
And we will get flag
~~~
crew{l00ks_l1k3_y0u_h4v3_you_He4rd_0f_c0pp3rsm1th_sh0r+_p4d_4tt4ck_th4t_w45n't_d1ff1cult_w4s_it?}
~~~
