Preco je tazke prelomit sifru RSA ?

Cielom tohto clanku je zoznamit citatela so zakladnymi principmi sifry RSA. Tento text neobsahuje ziadne matematicke dokazy. Co sa tyka matematiky, tak k pochopeniu clanku si vystacite s ucivom zakladnej skoly:-) Clanok pisem hlavne pre ludi, ktori sice poznaju vseobecny princip asymetrickeho sifrovania a aku ulohu zohrava verejny/sukromny kluc, ale nedostali sa hlbsie k fungovaniu sifry RSA. Ak algoritmus RSA dobre poznate, stale si tento clanok mozete precitat a do komentarov citatelov upozornit na chyby/nepresnosti.

Najprv vysvetlim zopar pojmov, s ktorymi budem neskor pracovat.

Eulerova totient funkcia.
Mozno to znie strasne, ale ide o celkom jednoduchu vec. Totient funkciu budem dalej znacit Phi. Na "vstupe" dostane prirodzene cislo n a vrati pocet cisel, ktore su mensie alebo rovne n a zaroven nemaju s cislom n ziadneho spolocneho delitela okrem cisla 1. Napriklad Phi(24) = 8 (odpovedajuce 8 cisel su: 1,5,7,11,13,17,19,23).
Tato totient funkcia ma niekolko jednoduchych vlastnosti, ktore sa vyuzivaju prave pri sifrovani RSA.
1. Ak je p prvocislo, potom Phi(p) = p - 1.
2. Ak cisla p,q nemaju spolocneho delitela okrem 1, potom Phi(p * q) = Phi(p) * Phi(q). (Priklad Phi(5*8) = Phi(5) * Phi(8) = 4 * 4 = 16. S cislom 40 su nesudelitelne tieto cisla: 1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39)

Dalej si vysvetlime zaklady modularnej aritmetiky.
Z bezneho zivota sme zvyknuti na fakt, ze cisiel je nekonecne vela. Ale ukazuje sa, ze niekedy je celkom vyhodne si predstavit, ze cisel mame iba konecny pocet. Samozrejme iba samotne cisla by nam boli na nic. Tak sa na nich definuju rozne operacie (plus, krat). Tieto operacie sa urcia tak, aby platili niektore zakladne vlastnosti, na ktore sme zvyknuti z matematiky zakladnej skoly. Uvediem konkretny priklad. Majme mnozinu cisel (0,1,2,3,4,5,6). Dalej si k nim definujme operacie plus a krat. pricom a plus b = a + b (mod 7). To "mod 7" znamena, ze delime cislom 7 a vysledkom je zvysok. Teda napr. 3 + 4 = 0 (mod 7), pretoze 3 + 4 = 7 & 7 dava po deleni 7 zvysok 0. Obdobne nadefinujeme na nasej mnozine cisel operaciu krat modulo n. a krat b = a * b (mod n). Kedze uz mame zavedene nasobenie modulo n, mozme si zaviest umocnovanie modulo n. V mnozine realnych cisel sme zvyknuti napriklad na to, ze ku kazdemu cislu existuje opacne. Napriklad k 7 je opacne cislo -7. Ale na nasej mnozine cisel mozme tiez najst k lubovolnemu cislu opacne. Pomozeme si faktom, ze sucet cisla n a (-n) je 0. Povedzme ze v nasej mnozine cisel hladame cislo opacne k 4. To je 3. Pretoze 4 + 3 = 0 (mod 7). Dalej sme zvyknuti z realnych cisel na operaciu deleno. Kedze uz vieme nasobit, staci nam, ak ku kazdemu cislu dokazeme najst jeho prevratenu hodnotu. Cize k cislu a hladame cislo b, aby platilo a krat b = 1 (mod 7). Cislu b potom hovorime, ze je multiplikativny inverz cisla a. (A naopak a je multiplikativny inverz cisla b). Lahko ku kazdemu cislu z nasej mnoziny (okrem 0, samozrejme:-) najdeme inverz, napr k cislu 5 je inverzne vzhladom na nasobenie cislo 3, pretoze 5 krat 3 = 1 (mod 7) Nasa mnozina ma celkom peknu vlastnost - ku kazdemu cislu okrem 0 dokazeme najst cislo inverzne. To ale nemusi platit o vsetkych takto "umelo" vytvorenych mnozinach cisel.

Teraz si konecne mozme napisat vzorcek, na ktorom je postaveny cely algoritmus RSA.
Nech n je prirodzene cislo, m je z mnoziny {0..n - 1} a dalej nech plati, ze e * d = 1 (mod Phi(n)).
Potom: m^(e*d) = m (mod n)

Zaujima Vas, ako sa da tento vzorcek pouzit na sifrovanie a nasledne desifrovanie? Jednoducho. Povedzme, ze mame spravu m reprezentovanu cislom. (Urcite si dokazete predstavit nejaky sposob, ako textovu spravu skonvertovat na cislo a naopak) Takze mame tajnu spravu m. Ak ju chceme zasifrovat, jednoducho ju umocnime na cislo e. Na to, aby sme spravu desifrovali, iba vysledok umocnime na d. Podla hore uvedeneho vzorceka dostaneme naspat cislo m - povodna sprava.

Popiseme si to este raz v terminologii asymetrickeho sifrovania. Alica chce odoslat spravu m Bobovi. Pred tym ju samozrejme musi zasifrovat Bobovym verejnym klucom. Bobov verejny kluc je dvojica (e, n). Alica teda spocita e-tu mocninu spravy m. Vypocet samozrejme robi modulo n. Bob prijme zasifrovanu spravu. Bobov sukromny kluc tvori dvojica (d, n). Zasifrovanu spravu umocni na d (mod n) a dostane povodnu spravu.

A preco je tazke prelomit RSA, alebo znamena RSA Really Stupid Algorithm?
Pozrime sa, co ma k dispozicii utocnik. Predpokladajme, ze sa mu podarilo zachytit zasifrovanu spravu, teda vysledok m^e. Takisto ma utocnik Bobov verejny kluc, cize pozna hodnotu cisla n a sifrovaci exponent e. Jedina vec, ktora mu chyba, je desifrovaci exponent d. Utocnik samozrejme vie, ako RSA funguje a preto vie, ze medzi e,d plati vztah: e * d = 1 (mod Phi(n))
Takze utocnik si jednoducho vypocita najprv Totient funkciu cisla n Phi(n). A potom jednoducho (napr. pomocou rozsireneho euklidovho algoritmu) najde multiplikativny inverz cisla e. A dostane hladany desifrovaci exponent d.

A kde je hacik?
Cela bezpecnost algoritmu RSA je zalozena na predpoklade, ze utocnik nedokaze zistit hodnotu Phi(n), a to napriek tomu, ze pozna n. To, aby to utocnik nedokazal zistit, sa dosahuje tak, ze za n sa vezme velmi velke cislo. To znamena, ze utocnik by musel skontrolovat vsetky cisla od 0 po n - 1, zistit, ktore z nich maju s cislom n najvacieho spolocneho delitela 1 a spocitat ich pocet. Tak by dostal Phi(n) a uz by mu nic nebranilo v uspesnom desifrovani:-)

Aj vy ste si vsimli, ze tu nieco nesedi?
Z toho co som napisal v predchadzajucom odstavci sa moze zdat, ze s bezpecnostou RSA je vsetko v najlepsiom poriadku. Ale stale to ma maly nedostatok. Nikde som nenapisal, ako Bob dokaze vygenerovat dvojicu (sukromny kluc, verejny kluc).
Ked si totiz Bob zvoli dostatocne velke cislo n, ma skoro taky isty problem, ako nas utocnik. Totiz musi najst dvojicu cisel (e,d) tak, aby platilo e * d = 1 (mod Phi(n)). Cize musi najprv zistit hodnotu Phi(n). A ak to dokaze Bob, preco to nedokaze nas utocnik? Tu si pomozeme na zaciatku clanku uvedenou vlastnostou Totient funkcie, a to Phi(a * b) = Phi(a) * Phi(b) (Cisla a,b musia byt nesudelitelne). Takze Bob si nevyberie za cislo n len tak hociktore velke cislo, ale najprv si vyberie 2 prvocisla p,q. Kedze p,q su prvocisla, dokaze hned urcit, ze Phi(p) = p - 1, Phi(q) = q - 1. (Tato vlastnost je tiez uvedena na zaciatku clanku) A ako cislo n si Bob zvoli sucin prvocisel p * q. A samozrejme dostane, ze Phi(n) = Phi(p * q) = Phi(p) * Phi(q) = (p - 1)*(q - 1). Takze teraz Bob pozna Phi(n). Zvoli si cislo e, take aby najvaci spolocny delitel cisel e, Phi(n) bol 1. (To mu zaruci ze bude k nemu existovat multiplikativny inverz). Dalej si Bob pomocou rozsireneho euklidovho algoritmu spocita multiplikativny inverz k cislu e, ako vysledok dostane d. A teraz uz Bob ma verejny kluc (e, n) a sukromny kluc (d, n) a Bob moze veselo sifrovat :-)

Zhrnutie na zaver:
Generovanie paru klucov:
1. Bob si vytvori 2 velke prvocisla p,q.
2. Bob si spocita n = p * q.
3. Bob si spocita Phi(n) = (p - 1)*(q - 1)
4. Bob si vyberie 1 < e < Phi(n) tak aby cislo e nemalo s Phi(n) ziadneho spolocneho delitela
5. Bob si spocita d pomocou rozsireneho euklidovho algoritmu ako multiplikativny inverz k e. (e * d = 1 (mod Phi(n))
6. Bob ma verejny kluc (e,n) a sukromny kluc (d, n)

Sifrovanie:
C(m) = m^e (mod n)

Desifrovanie D(c) = c^d (mod n)

Takze preco je tazke rozlusknut RSA?
Utocnik stoji pred problemom z cisla n spocitat Phi(n). Ale pretoze utocnik pozna fungovanie algoritmu RSA, vie ze cislo n bolo vytvorene ako sucin 2 velkych prvocisel. Ak sa mu tie prvocisla podari najst, moze si spocitat Phi(n) a pomocou neho desifrovaci exponent d (Spocita si to rovnakym sposobom akym Bob generoval svoj par klucov)

A ako to suvisi s digitalnym podpisom?
Povedzme, ze Bob chce poslat Alici spravu m, ale chce aby mala Alica istotu, ze sprava pochadza od neho. Bob si vygeneruje verejny kluc (n, e) a sukromny kluc (n, d). (Kde e je "sifrovaci" exponent a d "desifrovaci"). Bob vytvori podpisanu spravu S = m^d (mod n) a tuto spravu posle Alici. Pretoze uz vieme, ze plati m^(e*d) = m (mod n), staci, ak si Alica zisti Bobov verejny kluc (e, n) a spocita povodnu spravu m = S^e (mod n).
Alica teda vie, ze povodna sprava bola umocnena sukromnym klucom, ktory odpoveda Bobovmu verejnemu klucu a teda sa moze domnievat, ze spravu napisal skutocne Bob a tato sprava nebola po ceste zmenena.