Hacknite Wiki

RSA je kriptografski sustav javnog-ključa koji pruža enkripciju podataka i sigurnost komunikacije. Kao i kod ostalih sustava javnog ključa, enkripcijski ključ je javan i različit od dekripcijskog ključa, koji je tajan (privatni kjuč). Javni ključ sustava temeljen je na umnošku dvaju velikih prostih brojeva koji su tajni, a od kojih dobivamo i privatni ključ.

Sigurnost RSA sustava se temelji na činjenici da je teško pronaći faktore produkta dvaju velikih prostih brojeva. Ne postoji objavljena metoda koja takav problem pouzdano rješava za dovoljno velik ključ. Napadi na RSA mogući su kod matematičkih (npr. kratak ključ) i implementacijskih (npr. pogreška u računanju) grešaka u korištenju. RSA, uz pravilnu upotrebu, stoga smatramo sigurnim.

RSA algoritam se odvija u 4 koraka: generiranje ključa, distribucija ključa, enkripcija i dekripcija.

1. Slučajno izaberimo 2 velika prosta broja p i q
2. Izračunajmo n = pq
3. Izračunajmo 𝜑_(𝑁) = (𝑝 − 1)(𝑞 − 1) koja će biti tajna
4. Odaberimo cjelobrojni e tako da vrijedi 2 < e < 𝜑_(𝑁)
5. Izračunajmo d kao d ≡ e−1 (mod λ_(n))

c ≡ m^e mod(n)

c^d ≡ (m^e)^d ≡ m mod(n)

Glavni problem RSA sustava je resursna i vremenska zahtjevnost generiranja većih ključeva, što je zašto se u praksi u pravilu koristi samo kao sustav javnog ključa za sigurnost komunikacije (e-mail, digitalni potpisi…), dok se tajnost samih podataka osigurava kombiniranjem RSA sa simetričnim enkripcijskim algoritmima.

Nepoznatom kriptografskom tehnikom je šifrirana vrlo bitna poruka. Doduše... kako pročitati poruku ako je
u heksadecimalnom obliku? Flag je u formatu CTF2022[brojevi]

n = 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000032620000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000002536257
e = 5
c = 92260048134780451430743670477111543438924684573046367556601992909235481070476207627157450280593865611
012706620334747312329287157051261420568964568896236178920279295535597399319671817735848009861634962584298
31826686059321141234157025789273804698859757

U ovom zadatku, zadani su nam parametri n, c i e. Trebamo dekripcijom doći do m. Da bismo to obavili na najlakši mogući način, promotrimo prvo matematiku funkcije dekripcije RSA algoritma.

c^d ≡ (m^e)^d ≡ m mod(n)
c^d ≡ (m^e)^d /d√
c = m^e /e√
m = e√c

Sada kada znamo matematički najlakši način dekripcije poruke, možemo napisati jednostanu python skriptu koja će nam dati rješenje.

import gmpy2
 
c = 92260048134780451430743670477111543438924684573046367556601992909235481070476207627157450280593865611
012706620334747312329287157051261420568964568896236178920279295535597399319671817735848009861634962584298
31826686059321141234157025789273804698859757
e = 5
 
plaintext = gmpy2.iroot(c,e)
print(plaintext)
hex_string = hex(int(plaintext[0]))
print(bytes.fromhex(hex_string[2:])).decode("ASCII")

Dobivamo rješenje CTF2022[487200747574]

Nakon prvog RSA zadatka, Marko je otprilike shvatio funkcioniranje algoritma. Međutim, sada je naišao na
novi problem: poznatih brojeva je još manje nego u prošlom zadatku, a ne zna ni kako faktorizirati velike
brojeve. Doduše, čuo je kako bi alat https://gitlab.inria.fr/cado-nfs/cado-nfs mogao biti od pomoći.
Također, obzirom da broj e nije poznat, pitao je prijatelja za pomoć, a on mu je rekao da je e onaj koji 
se najčešće koristi, što god to značilo. Flag je u formatu CTF2021[brojevi]

Zadano:
n = 1306669742744796749498943411816234417330843064608069219396331
c = 134574356578714976505253204571948000299853829171428860751796

Da bismo dobili rješenje, moramo prvo naći jiš korisnih brojeva. Stoga ćemo prvo rastaviti n na njegove komponente, tj. na 2 prosta broja p i q. Ovo nije trivijalan zadatak pa ćemo koristiti gotove alate dostupne na internetu kao što su https://gitlab.inria.fr/cado-nfs/cado-nfs.

Nakon što smo dobili p i q, možemo doći i do m, proučimo matematiku radi koje je to moguće:
𝜑 = (p - 1)(q - 1)
d = e-1 mod(𝜑)
c^d = m mod(n) ←–vrijedi—> m = c^d mod(n)

Programski, to rješenje možemo zapisati kao:

n = 1306669742744796749498943411816234417330843064608069219396331
q = 2381330959053608086744420842569
e = 65537
c = 134574356578714976505253204571948000299853829171428860751796
p = 548714044881898853851432478099
 
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(hex(m))

Dobivamo zastavicu, rješenje je CTF2021[487200747574]

[1] Christof Paar, Jan Pelzl, Understanding Cryptography, Springer-Verlag Berlin Heidelberg, 2009.
[2] https://platforma.hacknite.hr/challenges
[3] Kriptografija i kriptoanaliza, predavanja, FER
[4] Budin, L.; Golub, M; Jakobović, D., Jelenković, L (2010.) (2013.), Operacijski sustavi, Element, Zagreb
[5] Dan Boneh, Twenty years of attacks on the RSA cryptosystem