Mathematicky princip RSA enkryptovania

RSA algoritmus bol navrhnuty v roku 1978 Ronom Rivestom, Adi Shamirom a Leonardom Adlemanom.

Tu je relativne jednoducho pochopitelne, matematicke pozadie asymetrickeho RSA enkryptovania s verejnym a sukromnym klucom.

1. Najdime P a Q, dve velke (napri. 1024-bitove) prvocisla

2. Zvolme E take, ze E je vacsie ako 1, E je mensie ako PQ a take, ze E a (P-1)(Q-1) su relativne prvocisla, cim sa mysli, ze nemaju spolocneho delitela. E nemusi byt nutne prvocislo, ale musi byt neparne. (P-1)(Q-1) nemoze byt prvocislo lebo je to parne cislo.

3. Vypocitajme D take, ze (DE - 1) je delitelne (P-1)(Q-1). Matematicky to zapiseme ako DE = 1 (mod (P-1)(Q-1)) a potom D nazyvame multiplikativne inverznym ku E. To dosiahneme lahko -- jednoducho najdeme cele cislo X pre ktore plati D = (X(P-1)(Q-1) + 1)/E kde D je tiez cele cislo, potom pouzijeme danu hodnotu D.

4. Enkryptovacia funkcia je C = (T^E) mod PQ, kde C je sifrovany text (kladne cele cislo), T je otvoreny text (kladne cele cislo), a ^ symbolizuje umocnovanie. Sprava T, ktora ma byt enkryptovana, musi mat mensiu hodnotu ako modul PQ.

5. Dekryptovacia funkcia je T = (C^D) mod PQ, kde C je sifrovany text (kladne cele cislo), T je otvoreny text (kladne cele cislo), a ^ symbolizuje umocnovanie.

Nas verejny kluc je dvojica (PQ, E). Nas sukromny kluc je cislo D (nikomu ho neprezradte). Produkt PQ je modul (casto v literature oznacovany N). E je verejny exponent. D je sukromny exponent.

Vas verejny kluc mozete volne uverejnit preto, lebo nie je znama metoda, ktora dovoluje lahko vypocitat D, P, alebo Q z jedine volne dostupnych (PQ, E) (Vas verejny kluc). Ak P a Q su aspon 1024 bitov dlhe, skor vyhori nase Slnko, ako v sucastnosti najvykonnejsie pocitace faktorizuju Vas modul na P a Q.

Tu je Priklad RSA enkryptovania.

Predpoklady

Napriek tomu, ze je vseobecne povazovane za pravdive, az doteraz nebolo dokazane, ze neexistuje jednoducha faktorizacna metoda. Az doteraz nebolo dokazane, ze jedinym sposobom prelomenia RSA je faktorizacia (rozklad na cinitele) modulu.