PRIROČNIK ZA TEORETIČNO RAČUNALNIŠTVO

Kriptografija

2. Osnove

Kriptografija se ukvarja s sporočanjem ob prisotnosti nasprotnika. Primer njenega klasičnega cilja je zasebnost: sogovornika bi si želela zasebnega „pogovora”, tako da nasprotnik ne bi vedel ničesar o sporočenem.

Izum radia je dal ogromen elan kriptografiji, saj lahko nasprotnik prisluškuje z velike razdalje. Na potek druge svetovne vojne je pomembno vplivala uporaba, zloraba in razbitje kriptografskih metod, uporabljenih za radijski prenos podatkov [92]. Nekateri menijo, da so računski stroji, ki so jih Britanci načrtovali in tudi zgradili za razbijanje nemške šifre Enigma2, prvi resnični „računalniki”. Lahko bi celo trdili, da je kriptografija mati (ali vsaj botra) računalništva.

Običajna kriptografska rešitev problema zasebnosti je kriptografska metoda s tajnimi ključi, ki jo sestavljajo:

Za uporabo kriptografske metode s tajnimi ključi se morata sogovornika, ki si želita zasebnega sporočanja, dogovoriti o ključu K, ki ga bosta ohranila tajnega (od tod ime metodi s tajnimi ključi). Namesto besedila M si sporočita tajnopis C = E(K,M). Sprejemnik lahko dešifrira tajnopis in pride do besedila M z uporabo ključa K, saj je M = D(K,C).

Kriptografsko metodo imamo za varno, če je za prisluškovalca, ki pozna E(K,M), a ne pozna K, praktično nemogoče odkriti M ali katerikoli njegov del. To je neformalna definicija varnosti; kasneje bomo spoznali, kako je bila formalizirana in razdelana v podrobnosti.

Medtem ko je kriptografija odraščala, je zadostila več drugim potrebam poleg zasebnosti in obravnavala nasprotnike kot občutno bolj zvite od pasivnega prisluškovalca. Pomemben dosežek je overovitev, kjer želi prejemnik sporočila preveriti, ali je bilo to od nasprotnika kaj spremenjeno, ter ali je pošiljatelj v resnici poslal sporočilo tako kot je bilo sprejeto. Digitalni podpisi so posebna tehnika potrjevanja pristnosti; v elektronskem sporočanju pomenijo isto, kar pomenijo lastnoročni podpisi v sporočanju na papirju.

A nadaljujmo z našo zgodbo. V naslednjih dveh razdelkih si bomo ogledali dve „predrevolucionarni” (to je pred letom 1976 nastali) kriptografski tehniki, ki ne smeta manjkati v nobenem pregledu tega področja: Vernamov kod (one-time pad) in postopek DES (Data Encription Standard). Potem pa bomo začeli pregled „moderne” kriptologije.

Opomba o terminologiji: kriptografska metoda se nanaša na vsako shemo, ki deluje v sistemu sporočanja v prisotnosti nasprotnikov, s ciljem premagati nasprotnikove zle namene. To je rahlo ohlapen pojem, toda takšno je tudi področje. Kriptografija se nanaša na umetnost načrtovanja kriptografskih metod, kriptografska analiza pa na umetnost njih razkrivanja. Kriptologija je unija kriptografije in kriptografske analize. Vseeno pa ni neobičajno, da tudi strokovnjaki, ki delajo na tem področju (vključujoč avtorja), uporabljajo (ali zlorabljajo) besedo „kriptografija” v pomenu kriptologije.

2.1 Metoda z enkratnim ključem: Vernamov kod

Vernamov kod je skoraj popolna kriptografska rešitev problema zasebnosti. Iznašel ga je leta 1917 Gilbert Vernam [92] za uporabo v telegrafiji, kar je vzpodbudilo veliko kasnejših raziskav v kriptografiji. Vernamov kod je kriptografska metoda s tajnimi ključi, kjer je ključ tako dolg kot sporočilo, ki ga šifriramo. Poleg tega pa ključ po enkratni uporabi zavržemo.

Predpostavimo, da si želita sogovornika A in B zasebnega sporočanja s pomočjo Vernamovega koda in da sta se prej že dogovorila o tajnem ključu K, ki je niz n naključno izbranih bitov. Če želi A poslati n bitov dolgo sporočilo M osebi B, ji pošlje tajnopis C = M Ĺ K, kjer je C ekskluzivna disjunkcija istoležnih bitov (XOR ali vsota po modulu 2) iz M in K (primer: 0011 Ĺ 0101 = 0110). Oseba B lahko prejeti tajnopis dešifrira in tako dobi M, saj je M = C Ĺ K. Ko želimo poslati naslednje sporočilo, moramo uporabiti nov ključ – zaradi enkratne uporabe ključa ima metoda v angleščini ime „enkratna prevleka” (one-time pad).

Ruske vohune so ujeli s še neuporabljenimi listi z natisnjenimi ključi (prevlekami) za uporabo pri šifriranju po Vernamovem kodu. Po šifriranju sporočila bi vohun uničil stran s ključem, ki ga je uporabil za šifriranje. Potem bi si lahko oddahnil, saj je tajnopis, čeprav bi ga prestregli, dokazano nemogoče dešifrirati in tako obdolžiti vohuna. Dokaz je preprost: prestreženi tajnopis C ne nudi prisluškovalcu nobenega podatka o M, saj ima lahko vsako sporočilo M tajnopis C (če je ključ K enak C Ĺ M).

Vernamov kod je dokazljivo varen v smislu teorije informacij, saj prisluškovalec nima nikoli dovolj podatkov za dešifriranje tajnopisa in nobena računalniška zmogljivost mu ne more pomagati. Osnovo za kriptografsko varnost v teoriji informacij je razvil Shannon [146], kasneje pa jo je podrobneje razdelal Hellman [89]. Gilbert, MacWilliams in Sloane [72] so razširili poglede na problem overovitve v teoriji informacij.

Vernamov kod sicer dokazano omogoča varnost, a je neroden za uporabo, saj moramo dolg ključ generirati, razdeliti in shraniti. Zato se v praksi le redko uporablja.

2.2 Postopek DES

Ta razdelek opisuje postopek DES (Data Encription Standard), ki je naša druga „predrevolucionarna” kriptografska metoda. Sodobne kriptografske metode uporabljajo razmeroma kratke ključe (od 56 do 1000 bitne) in so varne bolj s stališča izračunljivosti kot pa teorije informacij. S tem mislimo, da je nasprotnikova naloga prej prezahtevna (ali v praksi neizvedljiva) kot pa tudi nemogoča v teoriji informacij. DES je dober primer kriptografske metode s tajnimi ključi, ki je bila izdelana kot varna (glede izračunljivosti). Raziskovalci pri IBM so ga v letih 1970 izdelali, ameriški urad za standarde (U.S. National Bureau of Standards) pa je prevzel DES kot standard za šifriranje gospodarskih in vladnih podatkov, ki niso državne skrivnosti [120]. Postopek DES je zelo razširjen, predvsem v bančništvu. Njegova prihodnost kot standarda je nejasna, saj ni gotovo, koliko časa bo še ameriški urad NBS podpiral DES kot standard3.

Orišimo sedaj delovanje postopka DES. Njegov algoritem uporabi kot vhod 64-bitno sporočilo M in 56-bitni ključ K, kot izhod pa vrne 64-bitni tajnopis C. DES najprej napravi začetno fiksno permutacijo P bitov iz M in dobi M’. Ta permutacija nima navidez nobenega kriptografskega pomena. Drugo, DES razdeli M’ na 32-bitno levo polovico L0 in 32-bitno desno polovico R0. Tretje, DES izvrši naslednje operacije za i = 1, ..., 16 (torej 16 stopenj):

Li = Ri–1,
Ri = Li–1 Ĺ f(Ri–1, Ki–1).

Pri tem pomeni f funkcijo, ki vzame 32-bitno desno polovico in 48-bitni stopenjski ključ in vrne 32-bitni rezultat. Funkcija f je določena z 8 substitucijskimi funkcijami ali S-preslikavami, katerih vsaka preslika 6-bitni vhod v 4-bitni rezultat. Vsak stopenjski ključ Ki vsebuje različno podmnožico 56 bitov ključa. In končno, pol-tajnopis C’ = (R16,L16) (opazimo zamenjavo obeh polovic) še permutiramo s P–1, da dobimo končni tajnopis C. Preprosto lahko preverimo, da je postopek DES obrnljiv po zgornji definiciji, neodvisno od izbire f.

V značilni izvedbi postopka DES šifriramo sporočilo M tako, da ga najprej razbijemo na 64-bitne bloke, potem pa šifriramo vsak blok posebej, nad vsakim blokom pa še izvedemo ekskluzivno disjunkcijo (XOR) s tajnopisom prejšnjega bloka. To je znano pod imenom veriženje šifriranih blokov (cipher-block chaining) in preprečuje, da bi imeli ponavljajoči se deli besedila ustrezne ponavljajoče dele tajnopisa. Ostali načini delovanja pri uporabi postopka DES, kot tudi predlagane tehnike za ravnanje s ključi, je objavil ameriški urad NBS.

Diffie in Hellman [53] trdita, da je izbira 56-bitnega ključa za postopek DES lahko usodna ob napadu z grobo silo. Za 20 milijonov dolarjev bi bil namreč kdo sposoben zgraditi računalnik z 220 čipi, od katerih bi vsak lahko preveril 220 ključev vsako sekundo. Tako bi lahko ob iskanju ključa, ki omogoča preslikavo čistopisa v tajnopis, v 216 sekundah (18,2 urah) pregledal celoten prostor ključev4.

Hellman nam pokaže, kako lahko ob napadu pri znanem čistopisu zlomimo DES z obsežnim preračunavanjem, ki izčrpno preišče celoten prostor ključev in shranjuje zbrane rezultate, tako da ta časovno in prostorsko zelo zahtevna metoda da rezultate, ki pomagajo reševati problem kasnejšega določanja neznanega ključa, uporabljenega za šifriranje znanega čistopisa [91].

2 Enigma je stroj iz druge svetovne vojne, ki je postal sinonim za šifriranje. Imel je 2•1020 uporabniško nastavljivih ključev, kar je več, kot jih ima danes najširše uporabljani postopek DES.

3 Urad NBS ni podaljšal veljavnosti standardu. Zamenjal naj bi ga čip Clipper, ki ga je razvila ameriška agencija za državno varnost NSA (National Security Agency).

4 Podatki so iz leta 1990. S pomočjo linearne in diferencialne kriptografske analize so precej omajali DES, tako da je danes možno s strojem, sestavljenim iz hitrih DES čipov razbiti DES v realnem času.