rsa easy

Files

main.py

xxxxxxxxxx
from sage.all           import *
from Crypto.Util.number import *

p = getPrime(1024)
q = getPrime(1024)
N = p*q
e = 5

flag = open("flag.txt", "rb").read()

print(f'e = {e}')
print(f'N = {N}')
print(f'l = {len(flag)}')
print(f'c = {pow(bytes_to_long(flag), e, N)}')

output.py

xxxxxxxxxx
e = 5
N = 12738331786144976628408584962601932300503981320657758070592328404991407468813883686645414154009656690238190579172789903683404637273437397117457373561689012444619426823650785246522182691404988042475126388162721182642829957361466397613478409042980767743277584606227337490629695231723390631048248673270268876696120185173349837701768591415602973998294483589229947507282787032145262364771540599514486278946374659551934084334916633373157348397197599205131909762202122809096952440358033382655250548960242984611039926964337280304882882174539682794142960610875918130570131509376815338749964656662270835139574992464445560548559
l = 43
c = 68829034175580818037595385380486058481146119314176779392653265570684777934377061660231023209592412738533887287426451491081941388406918844870814300682923844554566803973117705604463199616847051219603692011646985814554709262873409703222220556412167145138331879306747358983145108299652047663942904777455736334417346180833984486051537873634676492222592723854998319668594793557450355021302157167591762956712631060579566159150846015743846084975678356683223634570347682709248173273897202941560635688805593516302480381214349

Phân tích

File main.py không hề có trick gì trong này cả. p và q được tạo ra bằng 1 cách rất tự nhiên để tránh việc factor được n một cách dễ dàng.

Do đó, việc tạo d bằng cách lấy e^-1 mod (p-1)*(q-1) rồi tính pow(c, d, n) để lấy flag là điều hoàn toàn bất khả thi nha 😗 (khả thi nếu mình có tầm 300 triệu năm gì đó để sống theo Google :))) Vì vậy, về mặt lí thuyết thì thuật toán này là bất khả xâm phạm. Nhưng mà, vấn đề lại nằm ở cái flag được mã hóa :3

l là độ dài của flag và bằng 43 bytes. Điều này suy ra được là flag chỉ có vỏn vẹn 43*8=344 bits thôi, dẫn đến việc flag^5 có tầm 344*5 = 1720 bits, nhỏ hơn n là 2048 bits. Một số có 1720 chữ số thì đương nhiên là phải nhỏ hơn số có 2048 chữ số rồi ;)

Mà ta lại có:

do $fla{g}^5<n$$flag^5 < n$ nên ta có thể suy ra được $fla{g}^5\mathrm{mod}n=fla{g}^5$$flag^5 \mod n = flag^5$ hay $c=fla{g}^5$$c = flag^5$ luôn.

Vì vậy, để lấy flag, ta chỉ cần tính $flag=\sqrt[5]{c}$$flag = \sqrt[5]{c}$ là ra.

flag

xxxxxxxxxx
BKSEC{5mALL-Fl@G-Small-eXp-mak3s-it-3a5y!!}