Differences

This shows you the differences between two versions of the page.

--- rsa [2023/09/25 08:47] – created katarina
+++ rsa [2023/11/27 09:22] (current) – external edit 127.0.0.1
@@ Line 1: / Line 1: @@
 ====RSA====
+**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.
+===Generiranje ključa:===
+  - Slučajno izaberimo 2 velika prosta broja p i q
+  - Izračunajmo n = pq
+  - Izračunajmo 𝜑<sub>(𝑁)</sub> = (𝑝 − 1)(𝑞 − 1) koja će biti tajna
+  - Odaberimo cjelobrojni e tako da vrijedi 2 < e < 𝜑<sub>(𝑁)</sub>
+  - Izračunajmo d kao d ≡ e−1 (mod λ<sub>(n)</sub>)
+===Enkripcija===
+c ≡ m<sup>e</sup> mod(n)
+===Dekripcija===
+c<sup>d</sup> ≡ (m<sup>e</sup>)<sup>d</sup>  ≡ 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ču kriptografiju (npr. pomoću RSA-a se razmjeni tajni AES ključ kojim se nastavlja daljnja komunikacija).
+===PRIMJER: Zadatak s Hacknite platforme – Mod n je potreban?===
+<file>
+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
+</file>
+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<sup>d</sup> ≡ (m<sup>e</sup>)<sup>d</sup>  ≡ m mod(n) \\
+c<sup>d</sup> ≡ (m<sup>e</sup>)<sup>d</sup>   	/<sup>d</sup>√\\
+c = m<sup>e</sup>		                /<sup>e</sup>√\\
+m = <sup>e</sup>√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.
+<code python>
+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")
+</code>
+Dobivamo rješenje CTF2022[487200747574]
+===PRIMJER: Zadatak s Hacknite platforme – RSA2===
+<file>
+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
+</file>
+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(𝜑)\\
+c<sup>d</sup> = m mod(n)  <-> m = c<sup>d</sup> mod(n)\\
+Programski, to rješenje možemo zapisati kao:
+<code python>
+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))
+</code>
+Dobivamo zastavicu, rješenje je CTF2021[487200747574]
+===Izvori===
+[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\\