1. Uvod. 1
1.1. Kriptografija. 1
1.2. Asimetrični kriptosustavi 1
2. Pregled asimetričnih algoritama. 2
2.1. Kratka povijest 2
2.2. Terminologija. 2
2.3. Stvarni algoritmi 3
2.3.1. RSA. 4
2.3.2. Rabin. 4
2.3.3. ElGamal 5
2.3.4. McEliece. 6
2.3.5. Blum-Goldwasser 6
3. Diffie-Hellman. 8
4. Zaključak. 8
5. Literatura. 9

1. Uvod

1.1. Kriptografija

Kriptografija (kriptiranje) je postupak transformiranja podataka (koje svi mogu čitati) u nečitljivu formu za svakog tko nema ključ za dekripciju. Svrha joj je čuvanje privatnosti čuvajući informaciju skrivenom svakome kome nije namijenjena.

Koristi se u komunikaciji preko nesigurnog kanala. Klasični scenarij glasi:

1.    osoba A želi poslati osobi B poruku, koju smije samo ona pročitati
2.    osoba A kriptira poruku sa enkripcijskim ključem i šalje je osobi B
3.    kriptiranu poruku dobiva osoba B i dekriptira ju s dekripcijskim ključem
4.    napadač, osoba C, može pokušati dobiti tajni ključ ili otkriti poruku direktno iz kriptiranog teksta

U sigurnim kriptosustavima poruka ne može biti otkrivena osim sa dekripcijskim ključem.  Postoje dvije vrste kriptosustava:

1.    simetrični (sustavi s tajnim ključem) – enkripcijski ključ je jednak dekripcijskom
2.    asimetrični (sustavi s javnim ključem) – ključevi nisu jednaki

 
Vrh dokumenta

1.2. Asimetrični kriptosustavi

Asimetrični kriptosustavi (kriptosustavi s javnim ključem) su izmišljeni u kasnim sedamdesetima. Postoje dva ključa: javni ključ e i odgovarajući tajni ključ d. Sa javnim ključem e može osoba B kriptirati poruku, a dekriptirati je može samo osoba A koja zna tajni ključ d.

Javni ključ ne treba biti tajna, zapravo, može biti dostupan svima, a njegova točnost nam garantira da jedino osoba A može čitati poruku.

Glavni cilj asimetričnog kriptosustava je da pruža privatnost ili povjerljivost. Kako je javni ključ poznat svima, sam ne pruža vjerodostojnost informacije i autentičnost (može se dogoditi da se netko lažno predstavi kao osoba A ili B). Za to nam služe neke dodatne tehnike (digitalni potpis,…).

Vrh dokumenta

 
2. Pregled asimetričnih algoritama
2.1. Kratka povijest

Asimetrični kriptosustavi su sporiji nego simetrični. Zbog toga, asimetrični kriptosustavi nam služe za razmjenu ključeva koji se koriste u simetričnom kriptosustavu. Prvi su to ideju primijenili Whitfield Diffie i Martin Hellman stvorivši protokol zamjene ključeva koji je počeo eru asimetričnih kriptosustava. Nedugo poslije toga Ron Rivest, Adi Shamir i Leonard Adleman stvorili su prvi pravi asimetrični kriptosustav sposoban za kriptiranje i digitalni potpis. Poslije toga su slijedile mnoge druge ideje (problem naprtnjače, konačna polja, rešetke, …). Mnoge od njih su nesigurne. Diffie-Hellmanov protokol i RSA su ostali dva najjača do sad.

 
Vrh dokumenta

2.2. Terminologija

Glavni sastojak asimetričnog kriptosustava je težak problem za računanje. Sigurnost kriptosustava je bazirana na činjenici da se tajni ključ d može izračunati iz javnog ključa e samo rješavajući težak problem.

Evo nekoliko osnovnih pojmova:

ˇ         Algoritam. Eksplicitni opis kako neki problem treba biti riješen. Efikasnost se može mjeriti kao broj elementarnih koraka koje treba poduzeti da bi se riješio problem (primjer: ako algoritmu treba vrijeme O(n) znači da mu treba n elementarnih koraka, ali se ne specificira koliko traju ti koraci).

ˇ         Složenost izračunavanja. Problem je polinomne složenosti (P) ako koristi manje od O(n^t) koraka, gdje je t neki konačni broj. Ako se pogođeno rješenje problema može provjeriti u polinomnom vremenu onda se kaže da je NP. Skup problema koji leže u NP je jako velik (uključuje i problem faktorizacije brojeva). Problem je NP-težak ako nema nijednog problema u NP kojeg je lakše riješiti. Ne postoji ni jedan algoritam polinomne složenosti da riješi NP-težak problem. U asimetričnim kriptosustavima napadač je zainteresiran za rješavanje pojedinih instanci problema (faktorizacija danog broja), radije nego da rješava cijeli problem (algoritam koji faktorizira bilo koji broj). To zabrinjava jer instance problema koji je NP-težak se općenito mogu laganije riješiti.

ˇ         Prosti (prim) brojevi. Broj je prost ako nema drugih djelitelja osim jedinice i samog sebe (2, 3, 5, 7, 11, …). Ima ih beskonačno mnogo, a najveći poznati je 2^6972593-1.

ˇ         Faktorizacija. Svaki prirodni broj se može prikazati jedinstveno kao produkt prostih brojeva. Vještina faktorizacije je stara koliko i matematika sama, ali brzi algoritmi faktorizacije su stari samo nekoliko desetljeća. Jedan mogući algoritam je da se ispitni broj podijeli sa svim malim prostim brojevima do drugog korijena tog broja. Efikasan je samo za brojeve do 10¹⁶. U asimetričnim kriptosustavima brojevi su veličine 10³⁰⁰ i trebalo bi provjeriti dijeljenje sa 10¹⁴⁷ prostih brojeva (teorem o prostim brojevima), a taj broj uvelike prelazi broj atoma u svemiru. Lagana instanca faktoriziranja bi bila u slučaju da broj ima male proste faktore (759375=3⁵*5⁵). U kriptografiji se zato koriste brojevi sa velikim prostim faktorima (RSA koristi dva velika prosta broja). Trenutačno je jedan od najboljih algoritama je NFS (number field sieve) algoritam. Ne postoji dokaz da je faktorizacija brojeva NP-težak problem.

ˇ         Diskretni logaritmi. Druga važna klasa problema je problem nalaženja n ako je zadan samo y takvih da je y=gⁿ. Problem je lagan za brojeve, ali kad se radi o malo drugačijem okruženju, postaje jako težek. Priroda tog problema je u tome da ako podijelimo beskonačan skup brojeva u konačan skup ostataka kod dijeljenja. Intuitivno, uzmu se svi brojevi i namataju se oko kruga (u krugu je m brojeva). Brojevi 0, 2m, 3m, … su svi na istoj točki na krugu i zato spadaju u istu klasu. Svaka klasa ima barem jednog člana iz 0…m-1. Zato se svaki broj može zapisati kao n=k*m+t, 0<=t<m (to se piše n º t (mod m) ). Može se pokazati da se može zbrajati, oduzimati i množiti te klase brojeva modulo m. Ta struktura gdje je m prost broj se zove Galoisovo polje GF(m). U tim poljima je dijeljenje brojeva različitih od nule dobro definirano. Problem diskretnog logaritma u GF(p) je: ako su dana dva broja a i g različita od nule, manji od p, izračunaj n takav da je a=gⁿ. Može se izabrati g tako da rješenje n postoji za bilo koji a. Ovaj problem se smatra jednako težak kao i faktorizacija. Problem se može primijeniti u mnogo područja, kao što su eliptičke krivulje.

ˇ         Problem naprtnjače. Ako je dan mali skup brojeva, problem je u izboru podskupa tih brojeva tako da je njihova suma jednaka danom broju. Primjer: dan je skup (2, 3, 5, 7) i broj 10, možemo naći rješenje 2+3+5=10. Dokazano je da je problem NP-težak i čini se da je superiorniji faktorizaciji i diskretnom logaritmu. Nažalost, svi kriptosustavi koji su koristili ovu ideju su razbijeni jer instance tog problema nisu stvarno NP-teške.

ˇ         Rešetke. Definira se vektorska baza w_i = < w₁, ..., w_n> za i=1,…,m, i rešetku koju generira baza. Elementi rešetke su od t₁w₁ + t₂w₂ + ... + t_mw_m, gdje su t_i cijeli brojevi. Problem nalaženja najkraćeg vektora (Euklidova udaljenost) u rešetki je NP-težak problem (za velike rešetke). Ipak, LLL-algoritam (Lenstra, Lenstra i Lovasz) izračunava približno rješenje u polinomnom vremenu. Efikasnost tog algoritma izlazi iz činjenice da su u mnogim slučajevima približna rješenja dovoljno dobra, i iznenađujuće u većini slučajeva LLL daje najkraći vektor.   Ovaj algoritam se često koristi za razbijanje kriptosustava baziranih na problemu rešetki ili naprtnjača. Također se upotrebljava za napade protiv RSA i DSS.

Vrh dokumenta

2.3. Stvarni algoritmi

Širok interes u asimetrične kriptosustave je proizveo nekoliko važnih kriptosustava. Kao ideja vodilja, asimetrični kriptosustav je izveden iz teškog problema: uzme se teški problem (NP-težak) za koji se instanca može riješiti u polinomnom vremenu. Za enkripciju poruke, poruka se pretvori u laganu instancu teškog problema, onda se koristi javni ključ za pretvaranje laganog problema u teški. Rezultat se tada šalje primatelju kroz nesigurni kanal. Za dekripciju se koristi tajni ključ za pretvaranje teškog problema u lagani, zatim rješavanje laganog da bi se dobila originalna poruka. Svi asimetrični kriptosustavi koriste isti princip, ali se razlikuju u detaljima.

Evo nekih koji se češće koriste:

ˇ         Faktorizacija

1.     RSA
2.     Rabin
3.     Blum-Goldwasser

ˇ         Diskretni logaritmi

1.     Diffie-Hellman
2.     ElGamal
3.     generalizirani ElGamal
4.     DSS
5.     LUC
6.     XDR

ˇ         Naprtnjača

1. Rivest-Chor
2. Merkle-Hellman

ˇ         Rešetka

1. NTRU

ˇ         Linearni kod

1. McEliece

 
2.3.1. RSA

RSA (Rivest, Shamir, Adleman) je najrašireniji asimetrični kriptosustav. Baziran je na problemu rastavljanja velikih prirodnih brojeva na proste faktore.

Osoba A stvara ključeve:

1.    nađi dva velika prosta broja p i q (> 10¹⁰⁰)
2.    izračunaj n=p*q i z=(p-1)*(q-1)
3.    odaberi e takav da su e i z relativno prosti(nemaju zajedničkih djelitelja osim 1) i 1<e<z
4.    nađi d takav da je e*d=k*z+1, 1<d<z, k=1,2,3,…
5.    javni ključ je (n,e), a tajni (n,d)

Osoba B kriptira poruku m, dobiva kriptiranu poruku c i šalje je osobi A:

1.     saznaj javni ključ osobe A (n,e)
2.     reprezentiraj poruku sa brojevima m iz intervala [0, n-1]
3.     izračunaj c=m^e mod n
4.     pošalji poruku c osobi A

Osoba A dekriptira poruku c i dobiva originalnu poruku m:

1.    koristi tajni ključ (n,d)
2.    izračunaj m=c^d mod n

Primjer (s malim brojevima):

A bira brojeve p=2357, q= 2551,n=p*q= 6012707,z=(p-1)*(q-1)=6007800, e=3674911, d=422191.
Neka je poruka m=52334673.

Enkripcija:
B računa:

c=m^e mod n = 52334673^3674911 mod 6012707 = 3650502 i šalje ga A-u.

Dekripcija:
A računa:

m=c^d mod n = 3650502⁴²²¹⁹¹ mod 6012707 = 5234673

Vrh dokumenta

 
2.3.2. Rabin

Rabin kriptosustav je bio prvi matematički dokazani kriptosustav da je ekvivalentan faktorizaciji. Dekripcija je malo teža. Problem je u tome što treba odlučiti koji je izlaz od nekoliko mogućih točan.

Osoba A stvara ključeve:

1.    nađi dva velika prosta broja p i q (> 10¹⁰⁰)
2.    izračunaj n=p*q
3.    javni ključ je (n), a tajni (p,q)

Osoba B kriptira poruku m, dobiva kriptiranu poruku c i šalje je osobi A:

1.     saznaj javni ključ osobe A (n)
2.     reprezentiraj poruku sa brojevima m iz intervala [0, n-1]
3.     izračunaj c=m² mod n
4.     pošalji poruku c osobi A

Osoba A dekriptira poruku c i dobiva originalnu poruku m:

1.    koristi tajni ključ (p,q)
2.    nađi kvadratne korijene  m₁, m₂, m₃ i m₄ od c modulo n
3.    poslana poruka je ili m₁ ili m₂ ili m₃ ili m₄; A nekako odlučuje koji od njih je m

Algoritam za nalaženje korijena od c modulo n = p*q ako izaberemo p i q takve da je p=k*4+3 i q=l*4+3, k,l=0,1,2,…:

1.    upotrijebi prošireni Euklidov algoritam i nađi cijele brojeve a i b takve da je a*p+b*q=1
2.    izračunaj r=c^(p+1)/4 mod p
3.    izračunaj s=c^(q+1)/4 mod q
4.    izračunaj x=(a*p*s+b*q*r) mod n
5.    izračunaj y=(a*p*s-b*q*r) mod n
6.    četiri korijena su: x, -x mod n, y i –y mod n 

Ova nejednoznačnost se može u praksi izbjeći dodajući prespecificiranu redundanciju čistom tekstu prije enkripcije. Onda, sa velikom vjerojatnošću, samo jedan od četiri korijena ima tu redundanciju. Ako nijedan od korijena nema redundanciju, c se odbacuje.

Primjer (s malim parametrima):

Osoba A bira p=277, q= 331,n=p*q=91687

Enkripcija:

Neka je poruka 10-bitna m=1001111001. Sada B replicira zadnjih 6 bitova i dobiva 16-bitovnu poruku m=1001111001111001 (m=40569).

B računa c=m² mod n = 40569² mod 91687 = 62111 i šalje A-u.

Dekripcija:

A pomoću p i q izrčunava:

m₁ = 69654; m₂ = 22033; m₃ = 40569; m₄ = 51118,

a binarnoj notaciji:

m₁ = 10001000000010110; m₂ = 101011000010001;

m₃ = 1001111001111001; m₄ = 1100011110101110:

Kako jedino m₃ ima odgovarajuću redundanciju, A dekriptira c u m₃ i dobiva originalnu poruku m=1001111001

Vrh dokumenta

2.3.3. ElGamal

ElGamal kriprosustav se može gledati Diffie-Hellmanov kriptosustav u razmjeni ključeva. Temelji se na problemu diskretnog logaritma i Diffie-Hellman-ovom problemu.

Osoba A stvara ključeve:

1. generiraj veliki slučajni broj p i generator a multiplikativne grupe Z_p^* brojeva modulo p
2. izaberi slučajan broj a, 0<a<p-1, i izračunaj a^a mod p
3. javni ključ je (p,a,a^a), a tajni (a) 

Osoba B kriptira poruku m, dobiva kriptiranu poruku c i šalje je osobi A:

1. saznaj javni ključ osobe A (p,a,a^a)
2. reprezentiraj poruku sa brojevima m iz intervala [0, p-1]

3. odaberi slučajni broj k, 0<k<p-1
4.    izračunaj g=a^a mod p  i  d=m*(a^a)^k mod p
5.    pošalji poruku c=(g,d) osobi A

Osoba A dekriptira poruku c i dobiva originalnu poruku m:
1. izračunaj g^p-1-a mod p (napomena: g^p-1-a=g^-a=a^-ak)
2. izračunaj m=(g^-a)*d mod p 

Primjer (s malim parametrima):

Osoba A bira p=2357 i generator a=2 od Z₂₃₅₇^* i a=1751 i računa a^a mod p = 2¹⁷⁵¹ mod 2357 = 1185.

Javni ključ osobe A je (p=2357, a=2, a^a=1185).

Enkripcija:

Neka je poruka m=2035, B bira slučajni broj k=1520 i računa g=2¹⁵²⁰ mod 2357=1430  i  d=2035*1185¹⁵²⁰ mod 2357=697 i šalje osobi A (1430,697).

Dekripcija:

A računa g^p-1-a=1430⁶⁰⁵ mod 2357=872 i m=872*697 mod 2357=2035

Vrh dokumenta

2.3.4. McEliece

McEliece kriptosustav je baziran na kodovima za ispravak pogrešaka. Prvo se izabere neki kod za koji je poznat neki efikasni dekodirajući algoritam, a zatim zamaskirati kod kao općeniti linearni kod. Kako je problem dekodiranja linearnog koda je težak, opis originalnog koda može poslužiti kao tajni ključ, a opis transformiranog koda kao javni ključ.

Ovaj sustav je prvi koji je koristio slučajne brojeve u enkripciji. Iako je vrlo efikasan, u praksi se malo koristi jer su javni ključevi jako veliki.

Osoba A stvara ključeve:

1. prirodni brojevi k, n i t su konstantni kao parametri sustava

2.    odaberi generatorsku matricu G (kxn) za binarni (n,k)-linearni kod koji može ispraviti t grešaka, i za koju je poznat efikasni algoritam dekodiranja

3. odaberi matricu S (kxk) koja nije jedinična
4. odaberi permutacijsku matricu P (nxn)
5. izračunaj G=S*G*P (kxn)
6. javni ključ je (G,t), a tajni (S,G,P)

Osoba B kriptira poruku m, dobiva kriptiranu poruku c i šalje je osobi A:

1. saznaj javni ključ osobe A (G,t)

2.    reprezentiraj poruku kao binarni string m duljine k
3.    izaberi slučajni binarni vektor z duljine n koji ima najviše t jedinica(1)
4.    izračunaj binarni vektor c=m*G+z
5.    pošalji poruku c osobi A

Osoba A dekriptira poruku c i dobiva originalnu poruku m:

1. izračunaj c=cP^-1

2. upotrijebi dekodirajući algoritam za kod generiran s G i dekodiraj c u m

3.    izračunaj m=mS^-1

Vrh dokumenta

2.3.5. Blum-Goldwasser

Blum-Goldwasser je vjerojatnosni kriptosustav. Koristi Blum-Blum-Shub generator za generiranje pseudoslučajnih bitovnih sekvenci. S njima se radi "isključivo ili" (XOR) s tekstom poruke.

Osoba A stvara ključeve:

1. nađi dva velika prosta broja p i q (> 10¹⁰⁰), p=k*4+3 i q=l*4+3

2.    izračunaj n=p*q

3. upotrijebi prošireni Euklidov algoritam i nađi cijele brojeve a i b takve da je a*p+b*q=1
4. javni ključ je (n), a tajni (p,q,a,b)

Osoba B kriptira poruku m, dobiva kriptiranu poruku c i šalje je osobi A:

1. saznaj javni ključ osobe A (n)

2.    neka je k=[log₂n] i h=[log₂k]
3.    reprezentiraj poruku m kao string m=m₁m₂…m_t duljine t, gdje je svaki m_i binarni string duljine h
4.    izaberi sjeme x₀ (može se izabrati kao x₀=r² mod n, r=1,2,…,n)
5.    za i od 1 do t radi:

a.     izračunaj xi=x_i-1² mod n
b.     neka je p_i zadnjih h manje značajnih bitova od x_i
c.      izračunaj c_i=p_i XOR m_i

6.    izračunaj x_t+1=x_t² mod n
7.    pošalji poruku c=(c₁,c₂,..,c_t,x_t+1) osobi A

Osoba A dekriptira poruku c i dobiva originalnu poruku m:

1. izračunaj d₁=((p+1)/4)^t+1 mod (p-1)
2. izračunaj d₂=((q+1)/4)^t+1 mod (q-1)

3.    izračunaj u=x_t+1^d1 mod p
4.    izračunaj v=x_t+1^d2 mod q
5.    izračunaj x₀=v*a*p+u*b*q mod n
6.    za i od 1 do t radi:

a.     izračunaj xi=x_i-1² mod n
b.     neka je p_i zadnjih h manje značajnih bitova od x_i
c.      izračunaj m_i=p_i XOR c_i

Primjer (s malim parametrima):

Osoba A bira p=499, q= 547,n=p*q=272953, a=-57, b=52

Enkripcija:

k=18, h=4

m=m₁m₂m₃m₄m₅ (t=5), m₁=1001, m₂=1100, m₃=0001, m₄=0000, m₅=1100

x₀=159201 (399² mod n) i izračunava:

i x₆=139680.

B šalje A c=(0010,0000,1100,1110,0100,139680).

Dekripcija:

A računa d₁=((p+1)/4)⁶ mod (p-1)=463, d₂=((q+1)/4)⁶ mod (q-1)=337, u=x₆⁴⁶³ mod p=20, v=x₆³³⁷ mod q=24, x₀=v*a*p+u*b*q mod n=159201.

A izračuna x₁ i p₁ iz x₀ isto kao i B u enkripciji i dobiva m_i=p_i XOR c_i.

Vrh dokumenta

3. Diffie-Hellman

U mnogim kriptografskim protokolima dvije osobe žele početi komunicirati. Ali, ako pretpostavimo da inicijalno ne posjeduju bilo kakav tajni ključ i tako ne mogu koristiti kriptosustav s tajnim ključem.

Diffie-Hellmanova metoda se upotrebljava za dogovor tajnog ključa preko nesigurnog kanala. Bazirana je na problemu Diffie-Hellmanovom problemu: za zadane g, p, g^x mod p i g^y mod p, nađi g^xy mod p. Ovaj problem je smatran teškim, a u nekim svojim instancama je težak kao i problem diskretnog logaritma. Diffie-Hellmanov protokol se generalno smatra sigurnim.

Obje osobe rade isti postupak:

1. izaberi s drugom osobom velik prost broj p i bazu g (g<p).
2. odaberi tajni ključ x (x<p)
3. izračunaj javni ključ y=g^x mod p
4. pošalji drugoj osobi poruku (y)

5.     primi poruku (y') od druge osobe
6.     izračunaj tajni ključ z=(y')^x mod p

Primjer (s malim parametrima):

Neka je p=65537 i g=3.

Osoba A odabere tajni ključ x_a=39470 i izračuna javni ključ y_a=50022 i pošalje ga B-u.

Osoba B odabere tajni ključ x_b=19488 i izračuna javni ključ y_b=25158 i pošalje ga A-u.

A prima y_a'=25158 i izračuna z=57044.

A prima y_b'=5022 i izračuna z=57044.

Implementacija Diffie-Hellman protokola u Javi.

Vrh dokumenta

4. Zaključak

Rješenje problema identifikacije, autentičnosti i privatnosti na računalnim sustavima leži u polju kriptografije. Zbog ne-fizičke prirode medija, tradicionalne metode fizičkog označavanja medija s potpisom su beskorisne. Zbog toga, neke oznake moraju biti kodirane na informaciju da identificiraju izvor, potvrde autentičnost  sadržaja i pružaju privatnost.

Zaštita privatnosti koristeći simetrični kriptosustav (kao DES) je relativno lagana u malim mrežama, zahtijevajući razmjenu tajnih enkripcijskih ključeva između stranaka. Kako se mreža širi, sigurna razmjena ključeva postaje skuplja. Ovo rješenje postaje nepraktično već za srednje velike mreže.

DES ima dodatni nedostatak, zahtjeva dijeljenje tajnog ključa. Svaka osoba mora vjerovati drugoj da će čuvati njihov tajni ključ. Kako korisnik mora imati drugačiji ključ za svaku osobu s kojom komunicira, moraju vjerovati svakoj osobi s jednim od njihovih tajnih ključeva. To znači da u praktičnim implementacijama, sigurna komunikacija se može održati između ljudi koji su prije imali neku međusobnu vezu.

Bolji način je asimetrična kriptografija. Bolje nego da se koristi isti ključ za enkripciju i dekripciju, koristi se par ključeva. Svaki ključ izvodi jednosmjernu transformaciju podataka. Svaki ključ je inverz drugog (što jedan napravi, samo drugi može poništiti). Isto tako, korisnik može poruku kriptirati svojim tajnim ključem. To pruža osnovni digitalni potpis jer ako korisnik može dekriptirati poruku sa nečijim tajnim ključem, onda se zna da je poruku napisala prava osoba.

5. Literatura

1. http://cacr.math.uwaterloo.ca/hac/
2. http://www.apocalypse.org/pub/u/seven/diffie
3. http://www.swcp.com/~mccurley/talks/msri2/
4.    http://www.ssh.fi/tech/crypto/algorithms.cfm#asymmetric
5.    http://security.tao.ca/crypt_basics.shtml
6.    http://www.verisign.com/repository/crptintr.html
 

Vrh dokumenta