Uporaba kriptografije v internetu
Kazalo   
 

Algoritmi z javnim ključem (asimetrični algoritmi)

Naloga, najti način šifriranja podatkov, kjer bosta znana metoda in ključ za šifriranje, pa vendar bo podatke lahko dešifriral samo naslovnik, se zdi težko uresničljiva. Najti je treba tako transformacijo, za katero je težko ali nemogoče izvesti inverzno transformacijo, če nimamo dodatne informacije (privatnega ključa). Za take transformacije se uporablja izraz One-Way Function oziroma Trap-door one-way function: inverzna operacija je lahka, če imamo neko dodatno informacijo (trap-door), sicer pa skoraj nemogoča.


Koncept javnega in zasebnega ključa sta prva predstavila Whitfield Diffie in Martin Hellman (1975) - The Diffie-Hellman key agreement protocol. Kot že ime pove, to ni algoritem za šifriranje podatkov, temveč postopek za kreiranje in izmenjavo skritega ključa po javnem omrežju.

Imamo parametra p in g, ki sta oba javno znana. p je praštevilo, g (generator) pa celo število, manjše od p, iz katerega lahko dobimo katerokoli število od 1 do p-1, če ga potenciramo in vzamemo vrednost po modulu p.

Alica si izbere naključno število a, Bob pa svojega (b). Ti dve števili morata ostati skriti. Potem Alica izračuna svoj javni ključ ga mod p, Bob pa svojega gb mod p. Ti števili si izmenjata. Njun skrivni ključ Alica izračuna takole: kab (gb)a mod p, Bob pa poišče vrednost kba (ga)b mod p. Ker je kab = kba , imata skupni skrivni ključ, ki ga lahko uporabita kot ključ za šifriranje podatkov s katerim od simetričnih algoritmov.

Če je praštevilo p dovolj veliko, je skoraj nemogoče izračunati gab mod p iz ga mod p in gb mod p. Najti bi morali diskretni logaritem a iz ga mod p, to pa spada v enak težavnostni razred kot faktorizacija velikega števila.


Decembra 1997 je postalo znano, da so angleški znanstveniki James Ellis, Clifford Cocks in Malcolm Williamson, zaposleni v tajni službi angleške vlade GCHQ (Government Communications Headquarters), odkrili oba postopka - Diffie Hellman in RSA - več let pred Diffiejem in Hellmanom, niso pa smeli tega objaviti, ker je šlo za vojaško skrivnost. Na straneh angleške vlade lahko najdemo nekaj dokumentov o tem:

Ni pa še znano, ali so do podobnih odkritij prišli tudi v NSA.


Danes se najbolj uporablja algoritem RSA, ki ima ime po svojih avtorjih (Ronald Rivest, Adi Shamir, Leonard Adleman) - MIT, 1977. Metoda je v ZDA patentirana, patent je potekel septembra 2000. Do tega časa je bilo treba za uporabo v ZDA plačevati licenčnino, zato algoritem ni bil vključen v nekatere produkte.

Metoda temelji na predpostavki, da je razmeroma lahko najti dve veliki praštevili, če pa poznamo samo njun zmnožek, je težko najti faktorja. Vzemimo primer s 3-številčnima prašteviloma: 191 x 283 = 54053. Če hočemo faktorirati to število, ga moramo deliti z vsemi praštevili do 191 oziroma v splošnem do njegovega kvadratnega korena. V praksi pa so ta števila več kot stoštevilčna.

Osnovo metode prestavlja naslednji izrek iz teorije števil, ki ga pripisujejo Eulerju:
Naj bosta p in q različni praštevili, velja naj tudi ed 1 mod (p-1)(q-1).

Potem sledi (Te)d T mod pq.

Če nam T predstavlja blok teksta, ga zašifriramo takole: s Te mod pq
dešifriramo pa: T sd mod pq.
Če označimo n = pq, javni ključ sestavljata n ter e, skriti ključ pa p, q in d.

Kako bomo izbrali vrednosti p, q, e in d? p in q morata biti veliki praštevili- več sto-mestni števili, razmeroma blizu skupaj. V praksi za e običajno izberemo 3 (glej opombo) ali pa 65537 (216+1). Zdaj izračunamo produkt (p-1)(q-1). Drugo predpostavko iz gornjega izreka lahko izrazimo tudi takole:
ed -1 je deljivo s (p-1)(q-1) oziroma v obliki Diofantske enačbe: ed + k(p-1)(q-1) = 1. Ta pa je rešljiva s celimi števili, če velja, da sta števili e in d tuji proti p-1 in q-1 (nimajo skupnih deliteljev). Izberemo tako število, ki je večje od p+1 oziroma q+1 in manjše od produkta (p-1)(q-1). Zdaj izračunamo število d iz formule ed mod (p-1)(q-1) 1.

Sporočilo, ki ga želimo šifrirati, najprej razbijemo na bloke, krajše od pq, - danes je to ponavadi 512 ali 1024 bitov. Izračunamo vrednost s Te mod pq za vsak kos sporočila. Ta števila združimo in dobimo šifrirano sporočilo. Pri dešifriranju spet najprej razbijemo sporočilo na bloke in na vsakem uporabimo formulo T sd mod pq.

Za ponazoritev naredimo primer za majhna števila. Na internetu najdemo različne programe za ponazoritev RSA, n.pr. RSA Demo Applet Richarda Holowczaka.

Vohun bi moral najprej najti števili p in q iz njunega produkta, to pa je po sedaj znanih metodah pri velikih p in q dolgotrajen postopek. Znan je naslednji primer:
Martin Gardner je avgusta 77 objavil v Scientific Americanu 129 številk dolgo število in ponudil 100 dolarjev za razbitje na faktorje. Uganko je rešila mednarodna skupina iz več kot 600 prostovoljcev jeseni 1994.

Leta 1999 so uspeli faktorirati 155-mestno število (kar ustreza 512 bitom), konec leta 2003 pa 174-mestno število (576 bitov). Sledilo je faktoriranje 193-mestnega števila (640 bitov), ki so ga dosegli novembra 2005. Najnovejši dosežek pa je faktoriranje 307-mestnega števila (števila 21039 - 1) marca 2007. Tu gre za posebno število, katerega faktorizacija je lažja, vendar znanstveniki, ki so dosegli ta uspeh pravijo, da so pri tem izboljšali postopek faktorizacije. Tri sodelujoče skupine so porabile enajst mesecev. Po drugi strani pa še vedno čaka na faktorizacijo 704-bitno število, za kar je ponujena nagrada 30000$.

Prisiljeni smo uporabljati vedno daljše ključe (s tem mislimo produkt pq). Tako bo potrebno opustiti 1024-bitne ključe in začeti uporabljati 2048 bitov, za pomembne operacije pa vsaj 3072 bitov (n.pr. za ključe overiteljev oziroma certifikatskih agencij). Zaenkrat nihče ne bo šel razbijat ključa običajnega uporabnika, ker je na voljo veliko lažjih načinov, da se pride do njegovih podatkov (luknje v operacijskih sistemih, trojanski konji, phishing, ...). Po drugi strani pa imajo zlikovci na voljo vojske ugrabljenih računalnikov (botnetov), ki bi jih v bodočnosti lahko uporabili tudi za take naloge.

Znani so tudi asimetrični algoritmi, ki temeljijo na eliptičnih krivuljah (ECC - elliptic curve cryptosystems). Ideja je znana že od leta 1985. Najdlje na tem področju je kanadska firma Certicom. V primerjavi z RSA zadoščajo krajši ključi, zato kaže, da bodo v bodočnosti ti algoritmi prevladali vsaj pri uporabi v manj zmogljivih napravah. Da se že zdaj bolj ne uporabljajo, je kriva patentna zaščita.
dolžina ključa ECC dolžina ključa RSA
106 bitov 512 bitov
132 bitov 768 bitov
160 bitov 1024 bitov
191 bitov 1536 bitov
211 bitov 2048 bitov

Asimetrični algoritmi se uporabljajo za izmenjavo skupnih ključev in za digitalno podpisovanje, za masovno šifriranje podatkov pa ne, ker so počasnejši od simetričnih algoritmov.

ime matematična osnova namenuporaba
Diffie-Hellman diskretni logaritmi izmenjava skritega ključav protokolih IPSEC, SSL, ...
ElGamal diskretni logaritmi digitalen podpis, enkripcijaza digitalen podpis v DSS
RSA faktoriranje velikih števil digitalen podpis, enkripcijazaenkrat najbolj pogosto uporabljen asim.algoritem
ECC eliptične funkcije digitalen podpis, enkripcijanaslednik RSA ?


September 2006: Opomba glede uporabe javnega RSA eksponenta 3:
Daniel Bleichenbacher je na konferenci Crypto 2006 opozoril na luknjo v kriptografskih knjižnicah, ki jih uporabljajo nekateri brskalniki in drugi programi, in ki omogočijo napadalcu, da ponaredi digitalno potrdilo, če se za podpisovanje uporabi potrdilo z javnim RSA eksponentom 3. MSIE nima te napake, za Mozillo, Firefox in OpenSSL so na voljo popravki.

Oktober 1996, zadnje ažuriranje maja 2007

URL: http://www.ca.gov.si/kripto/kr-asim.htm