RSA (algoritam)

RSA je algoritam za asimetričnu kriptografiju, prvenstveno namenjen šifrovanju podataka ali se danas koristi i u sistemima elektronskog potpisa. RSA danas predstavlja industrijski standard u oblasti asimetrične kriptografije i zaštiti podataka, tako da je široko primenjen u mnogim sigurnosnim protokolima i sistemi elektronskog poslovanja.

RSA

Opšte
Projektant(i)	Ronald Rivest, Adi Šamir, Leonard Ejdlman
Datum objave	1977.
Sertifikacija	PKCS#1, ANSI X9.31, IEEE 1363
Detalji
Veličina sažimanja	1.024 - 4.096
Runde	1
Najbolja javna kriptoanaliza
768-bitni RSA ključ je probijen.

Istorijat

RSA je algoritam za asimetričnu kriptografiju nastao 1977. na MIT univerzitetu. Tvorci ovog algoritma su Ronald Rivest, Leonard Ejdlman i Adi Šamir, gde RSA predstavlja akronim njihovih prezimena.

Kliford Koks, britanski matematičar koji je radeći za jednu vladinu agenciju za komunikacije, još je 1973. godine objavio u internim dokumentima potpuno ekvivalentni sistem za asimetričnu kriptografiju, ali zbog poverljivosti tih dokumenata, to je tek objavljeno 1997.

Algoritam je patentiran od strane MIT-a 1983. u SAD , pod šifrom U.S. Patent 4,405,829. Patentna prava su istekla 21. septembra 2000.

Opis algoritma

U RSA algoritmu ključnu ulogu imaju veliki prosti brojevi. Sigurnost RSA zasniva se na složenosti faktorizacije velikih brojeva. Smatra se da je određivanje originalne poruke na osnovu šifrata i ključa za šifrovanje ekvivalentno faktorizaciji proizvoda dva velika prosta broja.

Postupak generisanja ključa za RSA algoritma

1. Generisaćemo slučajno dva velika prosta broja $p\,$ i $q\,$ pri čemu $p\neq q$.
2. Izračunaćemo sledeće proizvode: $n=pq\,$.
3. i ojlerovu funkciju $\phi (n)=(p-1)(q-1)\,$.
4. Odabere se celobrojna vrednost $e$ pri čemu $1<e<\phi (n)\,$ .
5. Izračuna se $d\,$ pri čemu $de\equiv 1{\pmod {\phi (n)}}$.
6. Javni ključ je par $(n,e)\,$. Privatni ključ je par $(n,d)\,$.

Vlasnik privatnog (neko kaže i tajnog ključa) d, slobodno može da objavi brojeve n i e, tako da svako ko želi da mu uputi tajnu poruku može to i učiniti, a njen sadržaj može čitati samo vlasnik privatnog ključa, dok ostali dobijaju besmislen tekst.

Šifrovanje poruke

Ilustrativan je brojni primer (doduše sa malim brojevima ali je jasniji)

Generisanje ključeva

Osoba A formira javni i tajni ključ:

1. izabarala je proste brojeve $p=2357,q=2551\,$,
2. izračunala je broj $n=p*q=6012707\,$
3. izračunala je broj $t=(p-1)*(q-1)=6007800\,$.
4. bira slučajno broj $e=3674911\,$ (deo javnog ključa),
5. odgovarajućim (prošireni Euklidov) algoritmom računa $d=422191\,$. tj. tajni ključ

Dakle javni ključ je par $(n=6012707,e=3674911)$.

Šifrovanje poruke

Da bi osoba B koja poseduje taj javni ključ, šifrovala poruku $m=5234673$ , osobi A mora da:

1. računa $c=m^{e}\mod n=5234673^{3674911}\mod 6012707=3650502$.
2. Taj broj c = 3650502 (šifrat originalne poruke m) osoba B, šalje osobi A, koja pristupa dešifrovanju. odnosno koristeći broj d - tajni ključ računa:

Dešifrovanje poruke

Koristeći broj d - tajni ključ osoba A računa: $c^{d}\mod n=3650502^{422191}\mod 6012707=5234673$

a taj broj je i originalna poruka m).

Nedostaci algoritma

Prosti brojevi koji se koriste u ovom algoritmu uglavnom sadrže nekoliko stotina cifara i zbog toga se ovde javljaju više problema praktične prirode. Da bi se pomnožili toliko veliki brojevi, moraju se koristiti posebni algoritmi za množenje. Sem toga lako se da primetiti da je za takve operacije potrebno više vremena, pa su tako ovi algoritmi šifrovanja mnogo sporiji u odnosu na simetrične algoritme. DES algoritam šifrovanja je oko 100 do 1000 puta brži u odnosu na RSA algoritam. Sem ovoga algoritmi za faktorizaciju brojeva postaju svakim danom sve bolji, kao i neumoljiv razvoj kompjutera učinili su da danas 512 bitni RSA algoritam ne bude dovoljan za bezbedno šifrovanje poruka, za 1024 bitne algoritme pretpostavlja se da će biti bezbedni barem još 15-tak godina.

Reference

• mr Dragan Vidaković, Mala Škola Kriptografije
• R. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, Vol. 21 (2), pp.120-126. 1978. Previously released as an MIT "Technical Memo" in April 1977. Initial publication of the RSA scheme.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.7: The RSA public-key cryptosystem, pp.881-887.