KRIPTOSISTEMI
(RSA)
Vedran Škrnjug, 36344699
UVOD
Kriptosistemi (cryptosystems) dijele se u dvije grupe,
simetrični i asimetrični kriptosistemi. Simetrični kriptosistemi koriste
jedan ključ, tajni (secret key), za kriptiranje i dekriptiranje podataka,
dok asimetrični koriste dva ključa. Jedan, javni (public key), za kriptiranje
podataka i drugi, tajni (secret key), za dekriptiranje. Asimetrični kriptosistemi
nazivaju se još i kriptosistemi s javnim ključem (public key cryptosystems).
Kod simetričnih kriptosistema javlja se problem dostave tajnog ključa.
Paradoks je u tome što u slučaju da već postoji tajni put kojim možete
dostaviti tajni ključ onda ste mogli usput poslati i poruku, pa vam tajni
ključ niti ne treba. Iz tog razloga uložen je napor u pronalaženje drugog
pristupa kriptiranju podataka, što je rezultiralo pronalaskom asimetričnih
kriptosistema (kriptosistemi s javnim ključem).
Kriptosistemi s javnim ključem pojavili su se (izmišljeni su) krajem sedamdesetih
godina kao rezultat istraživanja asimetričnih algoritama enkripcije. Cilj
je bio razviti dovoljno snažan algoritam koji bi pokušaj dekripcije njime
kodiranih podataka produžio i do nekoliko tisuća godina. Također se pridavala
pažnja i razmjeni ključeva za dekriptiranje podataka, te se kao krajnji
proizvod dobio algoritam koji koristi dva ključa, od kojih onaj tajni
(dekripcija) zna sam korisnik (osoba A) kojem je podatak namijenjen, dok
je drugi ključ javno dostupan svima (osobe ¬A) koji imaju potrebu dopisivati
se s osobom A.
Druga ideja razmatrana
u to doba bavila se problemom tajne razmjene ključeva. Nakon ostvarene
komunikacije dvije bi strane razmijenile generirani zajednički tajni ključ
i iskoristile ga za enkripciju/dekripciju podataka.
Ideju o razmjeni ključeva primjenili su (nalazeći inspiraciju u teoriji
brojeva) Whitfield Diffie i Martin Hellman i tako pokrenuli upotrebu kriptosistema
s javnim ključevima. Ubrzo nakon toga (1978. g.) Ron Rivest, Adi Shamir
i Leonard Adleman razvili su prvi pravi kriptosistem s javnim ključem
(RSA algoritam) koji je bio u stanju kriptirati i dekriptirati podatke
uz mogučnost postavljanja digitalnog potpisa.
Kasnije, kroz godine ponuđena su još mnoga rješenja sigurnih kriptosistema,
međutim samo su se Hellman-Diffie i RSA zadržali u svijetu kriptografije
do danas.
Digitalni potpisi
Hash funkcije
Hash funkcije (matematički sažetci) koriste se za sažimanje izvornog
podatka (poruke) na veličinu prikladniju za digitalno potpisivanje.
Uzmemo li poruku duljine manje od 2^64 bita (2305843009213693952 slova)
i podvrgnemo je hash funkciji dobijemo matematički sažetak veličine
160 bita. Na taj se sažetak konkatenira javni ključ i/ili podaci o vlasniku
javnog ključa i/ili vremenska oznaka (timestamp) te se sve to propusti
kroz kriptografski algoritam.
Digitalni potpisi
Neki kriptosistemi s javnim ključem mogu se iskoristiti za digitalno potpisivanje
poruka. Digitalni potpis je mala količina podataka stvorena pomoću tajnog
ključa dok za provjeru autentičnosti potpisa postoji javni ključ. Algoritam
mora biti takav da bez znanja tajnog ključa nije moguće stvoriti potpis
koji bi prošao provjeru autentičnosti.
Digitalni potpisi se koriste za provjeru autentičnosti poslane poruke odnosno za provjeru da li je poslana od osobe koja tvrdi da ju je poslala. Mogu se iskoristiti za umetanje vremenske oznake u poruku (naravno kriptirane) i to na način da treća osoba od povjerenja digitalno potpiše poruku i tako tvrdi da je poruka postojala u određeno vrijeme.
Digitalni potpisi mogu se koristiti i kao potvrda da određeni javni ključ pripada određenoj osobi. To se napravi tako da se potpiše kombinacija javnog ključa i podataka o toj osobi pomoću provjerenog ključa (trusted key). Digitalni potpis treće osobe (vlasnik provjerenog ključa), javni ključ i podaci o vlasniku javnog ključa nazivaju se potvrde ili certifikati (certificates).
RSA kriptosistem (opis algoritma)
Osnovna ideja RSA algoritma sastoji se od pronalaženja tajnog i javnog
ključa iz dva slučajno izabrana velika prosta broja. cijeli se postupak
može podijeliti na pet koraka:
1. korak
Odabir prostih brojeva
P i Q (predlaže se velicina cca. 1024 bita)
2. korak
Odabir broja E takvog da je E manji od umnoška P*Q i takvog da su
E i (P-1)(Q-1) relativno prosti brojevi. Pritom E ne mora biti prosti
broj medutim mora biti neparan.
3. korak
Izracunati D takav da je (D*E-1) dijeljivo sa (P-1)(Q-1), odnosno
DE = 1 (mod (P-1)(Q-1)). D se naziva umnožim inverzom (multiplicative
inverse) od E.
4. korak (enkripcijska funkcija)
C = encrypt(T) = (T^E) mod P*Q, gdje je T izvorni podatak (plaintext)
uz pretpostavku da je T pozitivan cijeli broj.
5. korak (dekripcijska funkcija)
decrypt(C) = (C^D) mod P*Q, gdje je C kriptirani podatak (ciphertext),
C je takoder pozitivni cijeli broj.
Javni ključ u ovoj priči je par (P*Q, E), tajni ključ je D. Umnožak P*Q
je modulo, E je javni eksponent, D je tajni eksponent. Iz navedenih relacija
može se zaključiti da puštanje javnog ključa u opticaj realno ne ugrožava
sigurnost kriptiranog podatka. Izaberemo li 1024 bitne brojeve P i Q i
pomnožimo ih,
(2^1024 = 1,797693134862315907729305190789e+308) dobijemo broj približne
veličine 10^616, faktorizacija
dobivenog broja trajala bi dovoljno dugo da podatak kriptiran tim ključem
smatramo sigurnim.
Sigurnost kriptosistema
Dobar kriptografski algoritam je onaj kojeg je vrlo teško ili nemoguće
probiti. Teoretski, svaki algoritam koji koristi ključ može se probiti
pokušavanjem svih mogučih kombinacija ključa. Ukoliko se koristi čista
snaga procesora za isprobavanje svih kombinacija, vrijeme razbijanja raste
eksponencijalno s dužinom ključa.
(prema podacima s interneta)
Za razbijanje 32 bitnog ključa potrebno je 2^32 koraka i to je moguće
u razumnom vremenu napraviti na kučnom računalu.
Za razbijanje 40 bitnog kjluča potrebno je 2^40 koraka i taj pokušaj probijanja trajao bi cca. tjedan dana.
Za 56 bitni ključ (DES) potreban je velik broj umreženih kučnih računala
s distribuiranim zadacima i to bi trajalo nekoliko mjeseci.
64 bitni ključ u mogučnosti su razbiti vladine organizacije, velike firme
i vjerojatno organizirani kriminalci u roku od nekoliko godina.
Za 80 bitni ključ potrebno je desetak godina, dok je za 128 bitni ključ potrebno i nekoliko desetaka godina.
Međutim, dužina ključa nije jedina bitna stvar kod kriptositema. Mnogi algoritmi se mogu razbiti bez pokušavanja svih kombinacija ključa.
Sigurnost RSA kriptosistema
(u slučaju probijanja traženjem svih kombinacija ključa)
(prema podacima s interneta)
Faktorizacija 256 bitnog može se izračunati na kučnom računalu.
Za 512 bitni broj potrebna je računalna infrastruktura na fakultetskom
nivou.
Faktorizacija 1024 bitnog tenutno se zbog dužine računa smatra sigurnom.
Za 2048 bitova potreban je račun u trajanju od nekoliko desetaka godina.
Korištena literatura
http://www.itl.nist.gov/fipspubs
http://whatis.techtarget.com
http://www.ssh.fi/tech/crypto
http://world.std.com/~franl/crypto/rsa-guts.html
http://pgp.rasip.fer.hr
http://www.rsasecurity.com/rsalabs