3.5 RSA kriptografija

RSA (Rivest, Shamir, Adleman) je algoritam koji je uveden 1977. godine i koji se i danas intenzivno koristi u mnogim oblastima primene računara. U nastavku ćemo opisati ovaj algoritam i time prikazati kako se algoritmi i koncepti koje smo do sada u ovom poglavlju upoznali lepo kombinuju i daju veoma ozbiljnu, realnu primenu.

Osnovna podela kriptografskih algoritama je na:

• simetrične, koji podrazumevaju da se za šifrovanje i dešifrovanje poruka koristi isti ključ i
• asimetrične, koji podrazumevaju da se za šifrovanje i dešifrovanje poruka koriste različiti ključevi.

Obe vrste algoritama se koriste u savremenoj elektronskoj komunikaciji, najčešće zajedno. Simetrična kriptografija je brža, ali je veliki problem razmena ključeva između stranaka koje komuniciraju. Asimetrična kriptografija ne zahteva razmenu ključeva, ali je sporija i manje sigurna. Obično se danas asimetrična kriptografija upotrebljava u prvoj fazi komunikacije tokom koje se ustanovljava identitet stranaka koje komuniciraju i vrši razmena simetričnog ključa koji se dalje koristi u drugoj fazi komunikacije (na primer, tako radi protokol TLS, koji je osnova šifrovane komunikacije na vebu).

Asimetrična kriptografija podrazumeva da osoba koja prima poruke ima svoj:

• javni ključ koji je poznat svima i koji onaj ko šalje poruku koristi za šifrovanje, i
• tajni ključ koji je samo njoj poznat koji ona koristi za dešifrovanje.

RSA se smatra začetnikom asimetrične kriptografije. I šifrovanje i dešifrovanje se vrše pomoću stepenovanja po modulu \(n\). U algoritmu RSA javni ključ je par brojeva \((e, n)\), a tajni ključ \((d, n)\) (koristimo slovo \(e\) za encryption, tj. šifrovanje, a \(d\) za decryption, tj. dešifrovanje)¹. Šifruje se poruka (message) \(m\) i dobija se šifrat (cypher) \(c\) tako da važi \(c = m^e \,\mathrm{mod}\,n\). Veći dokumenti se dele na manje poruke i svaka poruka \(M\) se predstavlja brojem manjim od \(n\) i zasebno se šifruje. Veličina poruke zavisi od veličine ključeva. Poruke ne mogu da budu veće od veličine ključa. Ako se brojevi \(d\) i \(e\) predstavljaju sa po \(4096\) bitova, poruke \(m\) su obično veličine oko \(500\) bajtova i često se dopunjavaju dodatnim nasumično generisanim bajtovima, da bi se sprečilo da se iste poruke uvek šifruju na isti način. Ključno svojstvo koje mora biti ispunjeno je da se operacije šifrovanja i dešifrovanja poništavaju, tj. da se dešifrovanjem šifrata \(c\) izračunavanjem \(c^d \,\mathrm{mod}\,n\) dobija originalna poruka \(m\). Da bi ovo svojstvo važilo, dovoljno je da brojevi \(e\) i \(d\) budu međusobno inverzni po modulu \(\varphi(n)\). Ovo je jednostavna posledica Ojlerove teoreme i dokazaćemo je u narednoj teoremi.

Dakle, ako javni ključ sadrži broj \(e\), tada deo tajnog ključa \(d\) treba da izaberemo kao njegov inverz po modulu \(\varphi(n)\). Pretpostavljamo da su brojevi \(e\) i \(n\) poznati napadaču, ali želimo da on ne može u razumnom vremenu da izračuna broj \(d\) na osnovu njihove vrednosti. Šta je to što će nama omogućiti da prilikom generisanja ključeva izračunamo \(d\), a što nedostaje napadaču da bi i on to mogao efikasno da uradi? To što mi u trenutku generisanja ključeva možemo da znamo vrednost \(\varphi(n)\), a napadaču je potrebno ogromno vreme da od \(n\) izračuna \(\varphi(n)\). Šta bi nama omogućilo da brzo izračunamo \(\varphi(n)\)? Ako bismo znali faktorizaciju broja \(n\), onda bi izračunavanje Ojlerove funkcije bilo jako jednostavno. Pretpostavićemo zato da smo broj \(n\) odabrali u startu tako da bude jednak proizvodu neka dva prosta broja \(p\) i \(q\). Njih ćemo iskoristiti prilikom generisanja ključeva \(e\) i \(d\) i izračunavanja vrednosti \(\varphi(n)\) i zaboraviti odmah nakon toga (nigde ih nećemo zapisati). Poznavanje faktorizacije \(n=p\cdot q\) nam omogućava da efikasno izračunamo vrednost \(\varphi(n) = (p-1)\cdot(q-1)\) (koju ćemo takođe zaboraviti odmah nakon generisanja ključeva), a zatim da na osnovu vrednosti dela javnog ključa \(e\) izračunamo njegov modularni inverz \(d\) (po modulu \(\varphi(n)\)), što se lako radi korišćenjem proširenog Euklidovog algoritma.

Dakle, algoritam RSA radi na sledeći način.

1. Generisanje ključeva započinje generisanjem dva prosta broja \(p\) i \(q\) i određivanjem vrednosti modula \(n = p \cdot q\). Brojevi \(p\) i \(q\) su tajni, jednokratno se upotrebljavaju i odmah zaboravljaju (nigde se ne skladište). Brojevi \(p\) i \(q\) se generišu korišćenjem generatora nasumičnih brojeva, sve dok se ne ustanovi da su prosti. Brojevi \(p\) i \(q\) moraju biti veliki i njihova razlika mora biti velika.

2. Izračunava se vrednost Ojlerove funkcije \(\varphi(n)\) (i ona je tajna, upotrebljava se jednokratno i nigde ne skladišti). U pogavlju 3.3 o multiplikativnim funkcijama je dokazano da je u slučaju \(n=p\cdot q\) vrednost \(\varphi(n)\) jednaka \((p-1)\cdot (q-1)\), tako da se ona lako izračunava kada se znaju brojevi \(p\) i \(q\).

3. Bira se vrednost javnog ključa \(e\), takva da je \(2 \leq e < \varphi(n)\) i da je \(e\) uzajamno prosto sa \(\varphi(n)\). Vrednost \(e\) se često bira kao mali broj (kada je \(e\) mali broj, stepenovanje se brže vrši). Može se odabrati da je \(e\) prost broj (čime se obezbeđuje da se lakše ispita da li je uzajamno prosto sa \(\varphi(n)\)). Još češće, uzima se neka vrednost oblika \(2^k+1\) (npr. \(2^{16}+1 = 65537\)), u čijem je binarnom zapisu malo jedinica, što obezbeđuje efikasno modularno stepenovanje.

4. Vrednost \(d\) se određuje kao modularni multiplikativni inverz vrednosti \(e\) po modulu \(\varphi(n)\), tj. tako da važi da je \(e\cdot d \equiv 1 (\mathrm{mod}\ \varphi(n))\). Ona postoji (jer je \(e\) odabrano tako da je uzajamno prosto sa \(\varphi(n)\)) i može se efikasno izračunati nekim od ranije opisanih algoritama (pre svega proširenim Euklidovim algoritmom). Ako se \(e\) odabere kao mali broj, vrednost \(d\) može biti prilično veliki broj, što znači da će se šifrovanje vršiti brže nego dešifrovanje.

5. Poruka \(m\) se šifruje izračunavanjem vrednosti \(c = (m^e) \,\mathrm{mod}\,n\).

6. Poruka se dešifruje izračunavanjem vrednosti \(m = (c^d) \,\mathrm{mod}\,n\).

Dešifrovanje je korektno na osnovu teoreme 3.5.1. Uslov da je broj \(m\) uzajamno prost sa \(n\) se lako obezbeđuje. Ako je \(m\) manje od prostih brojeva \(p\) i \(q\), ono je uzajamno prosto sa njima, pa i sa njihovim proizvodom. Čak i ako se za \(m\) uzme neka veća vrednost, verovatnoća da ona bude umnožak nekog od brojeva \(p\) ili \(q\) je mala.

RSA se može upotrebiti i za potpisivanje poruka. Da bi postupak bio brži, umesto potpisivanje cele poruke obično se potpisuje samo njena heš-vrednost². Na osnovu poruke \(m\) može se izračunati njena heš-vrednost \(h(m)\) i uz originalnu poruku može se poslati potpis \(h(m)^d\) (primetimo da se heš-vrednost stepenuje korišćenjem tajnog ključa pošaljioca \(d\), koji se inače koristi za dešifrovanje). Primalac poruke \(m\) dešifruje potpis \(h(m)\) korišćenjem javnog ključa \(e\) pošiljaoca (koji mu je poznat), stepenujući dobijeni potpis brojem \(e\). Time će rekonstruisati vrednost \(h(m)\). Takođe, na osnovu poruke \(m\), primalac može ponovo da izračuna vrednost \(h(m)\) i ako se ta vrednost poklopi sa onom dobijenom dešifrovanjem potpisa, može da tvrdi da poruka \(m\) nije u međuvremenu menjana, kao i da ju je poslala osoba koja je bila u posedu tajnog ključa \(d\).

RSA algoritam, dakle, počiva na sledećim činjenicama:

• Ako su \(e\) i \(d\) inverzni elementi po modulu \(\varphi(n)\), tj. ako je \(\congmod{e\cdot d}{1}{\varphi(n)}\), tada (na osnovu Ojlerove teoreme) važi \(\congmod{m^{ed}}{m}{n}\) za sve brojeve \(m\) uzajamno proste sa \(n\).
• Ako se zna broj \(\varphi(n)\), tada se multiplikativni inverz broja \(e\) po modulu \(\varphi(n)\) može brzo izračunati.
• Ako se znaju prosti brojevi \(p\) i \(q\) takvi da je \(n=p\cdot q\), tada se vrednost \(\varphi(n)\) može izračunati jako brzo.
• Ako se zna vrednost \(n\), ali ne i brojevi \(p\) i \(q\), tada se vrednosti \(p\) i \(q\), niti vrednost \(\varphi(n)\), praktično ne mogu izračunati.
• Ako se nekom greškom sazna par vrednosti poruka \(m\) i šifrat \(c = m^e \,\mathrm{mod}\,n\), to ne omogućava da se u razumnom vremenu odredi ključ \(d\). Naime, iako važi \(c^d \,\mathrm{mod}\,n = m\), pronalaženje \(d\) zahteva izračunavanje diskretnog logaritma, što praktično nije moguće uraditi.

Sigurnost algoritma RSA se, dakle, zasniva na težini faktorizacije velikih brojeva, težini izračunavanja Ojlerove funkcije i težini izračunavanja diskretnog logaritma. Naime, iako je informacija o broju \(n\) javna, ona nam ne omogućava da efikasno izračunamo vrednost \(\varphi(n)\) koja je potrebna da bi se od javnog ključa \(e\) izračunao tajni ključ \(d\) (kao njegov inverz po modulu \(\varphi(n)\)). Sigurnost algoritma RSA bi se narušila ako bi se broj \(n\) mogao efikasno faktorisati ili ako bi se \(\varphi(n)\) moglo izračunati bez faktorizacije broja \(n\), na neki efikasniji način. Pretpostavimo da je \(n\) jednako proizvodu dva velika prosta broja \(p\) i \(q\), koji nemaju sličan red veličine. Tada je problem faktorizacije broja \(n=p\cdot q\) jako težak. U poglavljima 3.2 i 3.3 posvećenim faktorizaciji brojeva i njenim primenama prikazani su algoritmi faktorizacije broja \(n\) i izračunavanja \(\varphi(n)\) čija je složenost jednaka \(O(\sqrt{n})\), što je za velike vrednosti broja \(p\) i \(q\) (vrednosti sa nekoliko stotina, pa i hiljada binarnih cifara) neizvodivo u razumnom vremenu. Tada ni najnapredniji poznati algoritmi nemaju nikakvu šansu da izvrše faktorizaciju, niti da izračunaju vrednost \(\varphi(n)\) u nekom razumnom vremenu (danima, mesecima, godinama), čak ni uz masovnu paralelizaciju. Naglasimo da brojevi \(p\) i \(q\) ne smeju da budu sličnog reda veličine, tj. da imaju sličan broj cifara, inače bi bili bliski vrednosti \(\sqrt{n}\) i mogli bi se brzo odrediti Fermaovim algoritnom faktorizacije (koji je opisan u poglavlju 3.2.1). Preporučuje se, na primer, da se brojevi bitova brojeva \(p\) i \(q\) razlikuju bar za \(2\).

Faktorizacija omogućava jednostavno izračunavanje Ojlerove funkcije broja \(n=p\cdot q\), ali važi i obratno. Ako je pored broja \(n\) poznata i vrednost Ojlerove funkcije \(\varphi(n)\), onda se brojevi \(p\) i \(q\) mogu jednostavno odrediti. Naime, pošto važi \(\varphi(n)=(p-1)\cdot (q-1)\), množenjem izraza sa desne strane znaka jednakosti dobijamo da je \(n-\varphi(n)+1=p+q.\) Na osnovu vrednosti \(p+q\) i \(p\cdot q\) se mogu odrediti brojevi \(p\) i \(q\) kao rešenja kvadratne jednačine \(x^2-(n-\varphi(n)+1)x+n=0.\)

Za sada nije poznat efikasan algoritam za faktorizaciju velikih brojeva \(n\) niti za izračunavanje vrednosti \(\varphi(n)\), ali nije ni dokazano da takav algoritam ne postoji (ovo je slično kao kod NP kompletnih problema, međutim, nije dokazano da su ovi problemi NP kompletni – ovi problemi su u klasi NP, ali je moguće da su lakši od NP kompletnih problema). Kada bi se našao efikasan algoritam kojim se rešava neki od ovih problema, to bi moglo imati ozbiljan uticaj na sigurnost i bezbednost podataka.