RSA je kriptografski sustav javnog ključa koji pruža enkripciju podataka i sigurnost komunikacije. Kao i kod ostalih sustava javnog ključa, enkripcijski je ključ javan i različit od dekripcijskog koji je tajan (privatni ključ). 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 grešaka u korištenju (npr. kratak ključ) i implementacijskih (npr. pogreška u računanju). Zato RSA uz pravilnu upotrebu smatramo sigurnim.
RSA algoritam se odvija u 4 koraka: generiranje ključa, distribucija ključa, enkripcija i dekripcija.
c ≡ me mod(n)
cd ≡ (me)d ≡ m mod(n)
Glavni problem RSA sustava je resursna i vremenska zahtjevnost generiranja većih ključeva. Zato se u praksi RSA često koristi samo za sigurnu razmjenu tajnog ključa, a daljnja komunikacija se odvija koristeći simetričnu kriptografiju (npr. uz pomoć RSA-a se razmjeni tajni AES ključ kojim se nastavlja daljnja komunikacija).
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.
cd ≡ (me)d ≡ m mod(n)
cd ≡ (me)d /d√
c = me /e√
m = e√c
Sada kada znamo matematički najlakši način dekripcije poruke, možemo napisati jednostavnu skriptu koja će nam dati rješenje. Skripta računa broj m (plaintext) i, budući da je u zadatku rečeno da je poruka pisana u heksadekadskom zapisu, pretvara m u heksadekadski broj. Nakon toga dekodira poruku i ispisuje 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, s obzirom na to 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 još korisnih brojeva. Najčešći e je 65537 pa ćemo se njime koristiti. Zadani n rastavit ćemo na njegove komponente, tj. na 2 prosta broja p i q. Ovo nije trivijalan zadatak pa ćemo se koristiti gotovim alatima dostupnim na internetu kao što su https://gitlab.inria.fr/cado-nfs/cado-nfs.
Nakon što smo dobili e, p i q, možemo doći i do m:
𝜑 = (p - 1)(q - 1)
d = e-1 mod(𝜑)
cd = m mod(n) ↔ m = cd 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