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 objave1977.
SertifikacijaPKCS#1, ANSI X9.31, IEEE 1363
Detalji
Veličina sažimanja1.024 - 4.096
Runde1
Najbolja javna kriptoanaliza
768-bitni RSA ključ je probijen.

Istorijat

uredi

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

uredi

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

uredi
  1. Generisaćemo slučajno dva velika prosta broja   i   pri čemu  .
  2. Izračunaćemo sledeće proizvode:  .
  3. i ojlerovu funkciju  .
  4. Odabere se celobrojna vrednost   pri čemu   .
  5. Izračuna se   pri čemu  .
  6. Javni ključ je par  . Privatni ključ je par  .

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

uredi

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

Generisanje ključeva

uredi

Osoba A formira javni i tajni ključ:

  1. izabarala je proste brojeve  ,
  2. izračunala je broj  
  3. izračunala je broj  .
  4. bira slučajno broj   (deo javnog ključa),
  5. odgovarajućim (prošireni Euklidov) algoritmom računa  . tj. tajni ključ

Dakle javni ključ je par  .

Šifrovanje poruke

uredi

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

  1. računa  .
  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

uredi

Koristeći broj d - tajni ključ osoba A računa:  

a taj broj je i originalna poruka m).

Nedostaci algoritma

uredi

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

uredi