[Prethodno poglavlje]   [Sljedeće poglavlje]   [Sadržaj]

3. Kriptosustavi s javnim ključem

3.1. Ideja javnog ključa

Svi kriptosustavi koje smo do sada proučavali bili su simetrični, tj. sustavi s tajnim ključem. Naime, pošiljalac i primalac bi tajno izabrali ključ K, koji bi onda generirao funkcije za šifriranje eK i dešifriranje dK. Pritom je dK ili isti kao eK ili se iz njega lako dobije (npr. u DES-u se kod dešifriranja samo obrne redoslijed međuključeva). Za sigurnost ovih kriptosustava nužna je tajnost ključa. No, to je i njihov veliki nedostatak, budući da prije šifriranja pošiljalac i primalac moraju biti u mogućnosti razmijeniti tajni ključ preko nekog sigurnog komunikacijskog kanala (ili se osobno susresti). Štoviše, oni bi morali često mijenjati ključeve, budući da šifriranje više poruka istim ključem znatno smanjuje sigurnost. To može biti veliki problem ako npr. pošiljalac i primalac žive u udaljenih mjestima i žele sigurno komunicirati pomoću e-maila.


Godine 1976. Whitfield Diffie i Martin Hellman su ponudili jedno moguće rješenje problema razmjene ključeva, zasnovano na činjenici da je u nekim grupama potenciranje puno jednostavnije od logaritmiranja.

Pretpostavimo da se osobe A i B žele dogovoriti o jednom tajnom slučajnom elementu u cikličkoj grupi G, kojeg bi onda poslije mogli koristi kao ključ za šifriranje u nekom simetričnom kriptosustavu. Oni taj svoj dogovor moraju provesti preko nekog nesigurnog komunikacijskog kanala, bez da su prethodno razmijenili bilo kakvu informaciju. Jedina informacija koju imaju jest grupa G i njezin generator g.

Diffie-Hellmanov protokol za razmjenu ključeva:
  1. Osoba A generira slučajan prirodan broj a ∈ {1, 2, ... , |G| - 1}. Ona pošalje osobi B element ga.
  2. Osoba B generira slučajan prirodan broj b ∈ {1, 2, ... , |G| - 1}, te pošalje osobi A element gb.
  3. Osoba A izračuna (gb)a = gab.
  4. Osoba B izračuna (ga)b = gab.
Sada je njihov tajni ključ K = gab.

Njihov protivnik koji može prisluškivati njihovu komunikaciju preko nesigurnog komunikacijskog kanala zna sljedeće podatke: G, g, ga, gb, te treba iz ovih podataka izračunati gab. Ako protivnik iz poznavanja g i ga može izračunati a (tj. ako može riješiti problem diskretnog logaritma), onda i on može pomoću a i gb izračunati gab.


Diffie i Hellman se smatraju začetnicima kriptografije javnog ključa. Ideja javnog ključa se sastoji u tome da se konstruiraju kriptosustavi kod kojih bi iz poznavanja funkcije šifriranja eK bilo praktički nemoguće (u nekom razumnom vremenu) izračunati funkciju dešifriranja dK. Tada bi funkcija eK mogla biti javna. U provedbi ove ideje ključnu ulogu igraju tzv. osobne jednosmjerne funkcije. Za funkciju f kažemo da je jednosmjerna (one-way) ako je f lako, a f -1 teško izračunati. Ako je pritom f -1 lako izračunati ukoliko nam je poznat neki dodatni podatak (trapdoor - skriveni ulaz), onda f nazivamo osobna jednosmjerna funkcija. Uočimo da se i u klasičnoj kriptografiji tajnost u suštini zahtijeva samo od funkcije za dešifriranje dK. Banalan primjer: kod Cezarove šifre nije problem što svi znaju da se slova šifriraju tako da se pomiču za 3 mjesta udesno, već je problem što iz tog podatka baš svatko može zaključiti da se dešifriranje provodi pomicanjem za 3 mjesta ulijevo. No, i kod svih ostalih kriptosustava koje smo dosad susreli, veza funkcija eK i dK je bila vrlo jednostavna, pa skrivanje jedne, a otkrivanje druge funkcije nije imalo nikakvog smisla.

Kriptosustav s javnim ključem se sastoji od dviju familija {eK} i {dK} funkcija za šifriranje i dešifriranje (ovdje K prolazi skupom svih mogućih korisnika) sa svojstvom:
  1. Za svaki K je dK inverz eK.
  2. Za svaki K je eK javan, ali je dK poznat samo osobi K.
  3. Za svaki K je eK osobna jednosmjerna funkcija.
eK se zove javni ključ, a dK tajni ili osobni ključ.

Ako pošiljalac A želi poslati poruku x primaocu B, onda B najprije pošalje A svoj javni ključ eB. Potom A šifrira svoju poruku pomoću eB i pošalje primaocu šifrat y = eB(x). Konačno, B dešifrira šifrat koristeći svoj tajni ključ dB:   dB(y) = dB(eB(x)) = x.

Ukoliko grupa korisnika želi komunicirati na ovaj način, situacija je još jednostavnija. Naime, tada svi korisnici stave svoje javne ključeve u neku javnu, svima dostupnu datoteku. Sada B ne mora slati svoj javni ključ osobi A, već A jednostavno pročita eB iz datoteke.

shema

Ovdje se može postaviti pitanje kako osoba B može biti sigurna da joj je upravo osoba A poslala poruku. Naime, svatko ima pristup funkciji eB, pa se može lažno predstaviti kao osoba A. Dakle, postavlja se pitanje vjerodostojnosti ili autentičnosti poruke. To se može riješiti na sljedeći način:

Neki kriptosustavi omogućavaju čak da korisnici digitalno potpišu svoju poruku. To je važno zbog toga što tada A ne može kasnije zanijekati da je upravo on poslao konkretnu poruku. Pretpostavimo da je P = C. Tada A može potpisati poruku x tako da osobi B pošalje šifrat z = dA(y) = dA(eB(x)). Kad B primi poruku za koju pretpostavlja da mu je poslao A, on najprije primijeni javni ključ eA, a potom svoj tajni ključ dB:

dB(eA(z)) = dB(eA(dA(eB(x)))) = x.

Sada B zna sigurno da je poruku poslao A, jer je samo on mogao upotrijebiti funkciju dA. Da je umjesto te funkcije upotrijebljena neka treća funkcija dC, kao rezultat ne bi dobili smislenu poruku. Nadalje, ukoliko bi A kasnije zanijekao da je on autor poruke, B bi mogao "sucu" pokazati poruke x i z. Sudac bi provjerio da vrijedi eB(x) = eA(z) i to bi bio dokaz da je A pošiljalac.


Glavne prednosti kriptosustava s javnim ključem u usporedbi sa simetričnima su:

Pa ipak, u realnom svijetu kriptografija javnog ključa ne predstavlja zamjenu za simetrične kriptosustave. Ona se ne koristi za šifriranje poruka, već za šifriranje ključeva. Naime, osobe A i B komuniciraju pomoću simetričnog kriptosustava s ključem kojeg su razmijenili pomoću kriptosustava s javnim ključem. To se zove hibridni kriptosustav.

Osnovni razlog zašto se javni ključ ne koristi za šifriranje poruka, jest da su algoritmi s javnim ključem puno sporiji (oko 1000 puta) od modernih simetričnih algoritama.

Drugi nedostatak kriptosustava s javnim ključem jest da su slabi na napad "odabrani otvoreni tekst". Ako je y = e(x), gdje otvoreni tekst može poprimiti jednu od n vrijednosti, onda, budući je e javna, kriptoanalitičar treba samo šifrirati svih n mogućih otvorenih tekstova i rezultat usporediti s y. Tako neće otkriti tajni ključ d, ali će otkriti otvoreni tekst x. Jasno, ovaj napad je primjenjiv ako je n mali (npr. ako je x neki iznos u kunama za kojeg je razumno pretpostaviti da je manji od 1000000).


U modernoj kriptografiji, koja se koristi u komercijalnom svijetu (tipična situacija je da osoba A želi kupiti nešto od osobe B preko interneta), pojavljuju se, uz klasične, i neki sasvim novi problemi:

  1. POVJERLJIVOST (confidentiality): Poruku koju osoba A šalje osobi B ne može pročitati nitko drugi.
  2. VJERODOSTOJNOST (autenticity): Osoba B zna da je samo osoba A mogla poslati poruku koju je ona upravo primila.
  3. NETAKNUTOST (integrity): Osoba B zna da poruka koju je poslala osoba A nije promijenjena prilikom slanja.
  4. NEPOBITNOST (non-repudiation): Osoba A ne može kasnije zanijekati da da je poslala poruku.

Kako smo već rekli, kriptosustavi javnog ključa su mnogo sporiji od simetričnih. Stoga je njihova uporaba u 1. problemu ograničena na razmjenu ključeva za simetrične šifre. S druge strane, "digitalni potpisi", koji se koriste u rješavanju 2., 3. i 4. problema, zahtijevaju uporabu kriptografije javnog ključa.


[Prethodno poglavlje]   [Sljedeće poglavlje]   [Sadržaj]
Web stranica kolegija Kriptografija Andrej Dujella - osobna stranica