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):

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):

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?}
~~~

Original writeup (https://github.com/Em0t3t/Fundamental-you-should-know/blob/main/template_for_crypto.md).