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

1.8. Naprave za šifriranje

Kriptosustavi koje smo do sada promatrali mogu se načiniti kompliciranijima, a time i sigurnijima, uporabom naprava za šifriranje. Takve naprave čine procese šifriranja i dešifriranja puno bržim, a također omogućavaju uporabu velikih prostora ključeva.

Najstariju takvu praktičnu napravu, Jeffersonov kotač za šifriranje, izumio je američki državnik Thomas Jefferson krajem 18. stoljeća. Naprava je bila toliko ispred svog vremena, da ju je američka vojska počela koristiti tek 1922. godine.

Jeffersonov kotač se sastoji od drvenog cilindra s rupom u sredini kroz koju je provučena željezna os. Cilindar je presječen na 26 manjih cilindara (diskova) jednakih širina. Ovi diskovi se mogu neovisno jedan od drugoga okretati oko zajedničke osi. Na vanjštini svakog diska nalazi se 26 jednakih kvadratića. Tih 26 kvadratića se na proizvoljan način popunjava s 26 slova engleskog alfabeta, različito od diska do diska.

Jeffersonov kotac

Pošiljalac i primalac imaju dva identična kotača. Da bi šifrirao otvoreni tekst, pošiljalac podijeli tekst na blokove od po 26 slova. Blok se šifrira tako da se rotiranjem diskova u jednom od 26 redaka dobije otvoreni tekst. Tada za šifrat možemo izabrati bilo koji od preostalih 25 redaka. Npr. koristeći kotač sa slike, otvoreni tekst

THOMASJEFFERSONWHEELCHIPER

bi se mogao šifrirati kao

VSJGHLZHWPOMEUBVSLZWQVRPIT.

Primalac dešifrira šifrat tako da rotiranjem diskova u jednom retku dobije šifrat. Sada među preostalih 25 redaka potraži onaj koji sadrži neki smisleni tekst i taj redak predstavlja otvoreni tekst.

Osnovna ideja Jeffersonovog kotača jest kreiranje polialfabetskog kriptosustava korištenjem diskova koji se rotiraju više ili manje neovisno. Ova ideja je bila osnovna i kod mehaničkih i elektromehaničkih naprava koje su izmišljene kasnije. Tako dobiveni kriptosustavi se mogu shvatiti kao šifre Vigenèreovog tipa s ključnom riječi ogromne duljine (obično više od 1010). Stoga su kod njih napadi Kasiskijevom metodom i metodom indeksa koincidencije praktički neprimjenjivi.


Spomenimo najznačajnije takve naprave i njihove izumitelje.


Amerikanac Edward Hugh Hebern izumio je 1915. godine uređaj koji je nazvao električni stroj za kodiranje.

Hebernov elektricni stroj za kodiranje

To je bio električni uređaj kojim su se dva električna pisača stoja spajala pomoću 26 žica, ali s razbacanim rasporedom, pa kad bi se udarila tipka na pisaćem stroju za otvoreni tekst, drugi bi stroj automatski otipkao šifarski ekvivalent tog slova. Dvije godine kasnije, u uređaj je ugradio 5 tzv. "rotora". Rotori su na svakoj strani imali po 26 električnih kontakata. Svaki kontakt na jednoj strani nasumce je spojen žicom s nekim kontaktom na drugoj strani. To zapravo predstavlja jednu monoalfabetsku supstituciju. No, rotiranjem rotora i to tako da najprije prvi napravi cijeli krug, pa se zatim drugi pomakne za jedno mjesto, itd., dobivamo polialfabetsku supstituciju s periodom 265 ≈ 107.


Njemački pronalazač Artur Scherbius je 1918. godine izumio rotorsku napravu koju je nazvao ENIGMA. Razlikovala se od drugih rotorskih naprava po tome što su pomacima rotora upravljali zupčanici, pa se moglo postići da ti pomaci imaju nepravilan slijed.

ENIGMA

Do masovne uporabe ENIGME došlo je neposredno prije i za vrijeme Drugog svjetskog rata. Razbijanje njezine šifre (kombinacijom kriptoanalize i klasične špijunaže) imalo je važnu ulogu za tijek i ishod drugog svjetskog rata. Postojale su različite (vojne i komercijalne) inačice ENIGME. Posebno je bila poznata japanska inačica ENIGME, koju su Amerikanci nazivali PURPLE.

ENIGMA je bila elektromehanička naprava koja se sastojala od tipkovnice s 26 tipki poput pisaćeg stroja, zaslona s 26 žaruljica za prikaz šifriranog izlaza, tri mehanička rotora (šifrarnika) i električne prespojne ploče. Pritiskom na tipku kroz mrežu kontakata rotora i prespojne ploče zatvorio bi se strujni krug i upalila bi se odgovarajuća žaruljica koja označava šifrirano slovo. Mehanički rotori sastojali su se od diskova s 26 kontakata. Svaki kontakt na jednoj strani diska bio je povezan s nekim drugim kontaktom na suprotnoj strani. Većina modela ENIGME sastojala se od tri rotora koji su smješteni u ležište tako da se kontakti susjednih stranica međusobno dodiruju, tj. "izlaz" jednog rotora predstavljao je "ulaz" drugog. Izlaz trećeg (zadnjeg) rotora bio je povezan na reflektor - statičan mehanički disk sličan rotoru, s međusobno prespojenim električnim kontaktima samo na jednoj strani. Njegova je zadaća bila da električni signal šalje natrag kroz rotore, no drugim putem. Prvi se rotor nakon svakog šifriranog slova okretao za jedan kontakt, a kad bi učinio potpun krug, mehanička je poluga okretala sljedeći rotor za jedan kontakt.

Tri ožičena rotora s 26 kontakata daju 263 = 17 576 mogućih kombinacija. To nije dovoljno velik broj da bi dao zadovoljavajuću sigurnost. Scherbius je povećao sigurnost ENIGME povećavajući broj mogućih početnih postavki na dva različita načina: izmjenjivim rotorima i prespojnom pločom. Budući da su rotori mehanički gotovo identični, a njihovi električni spojni putevi različiti, njihovom međusobnom zamjenom mijenja se i način šifriranja samog stroja. Broj mogućih permutacija triju rotora je 6. Znatno veći doprinos sigurnosti donosi prespojna ploča, koja korisniku omogućuje da doda kablove, koji imaju efekt zamjene nekih slova prije ulaska u prvi rotor. Na primjer, kabel se može koristiti za zamjenu slova A i D, tako da kad korisnik pritisne tipku A, električni signal zapravo slijedi put kroz rotore koji bi bez prespojne ploče bio put slova D, i obrnuto. Od 1939. godine standardizirano je korištenje 10 prespojnih kabela, što je davalo 150 738 274 937 250 mogućih kombinacija. te je napad ispitivanjem svih mogućih kombinacija postao nemoguć.

Pa ipak, dvije grupe matematičara-kriptoanalitičara uspjele su pronaći način za dekriptiranje ENIGME. Bile su to poljska grupa, koju je predvodio Marian Rejewski, te britanska grupa, koju je predvodio Alan Turing.

Prvi napredak u kriptoanalizi ENIGME ostvaren je 1931. godine akcijom francuske obavještajne službe, koja je stupila u vezu s bratom načelnika sektora veze njemačke vojske, Hansom-Thilom Schmidtom, koji je uz naknadu od 10 000 tadašnjih njemačkih maraka Francuzima dostavio upute za uporabu ENIGME. Budući da su Francuzi i Poljaci po završetku Prvog svjetskog rata potpisali ugovor o vojnoj suradnji, ti su dokumenti dostavljeni poljskom uredu za kriptografiju Biuro Szyfróv. Dokumenti su opisivali i proceduru mjesečne distribucije knjiga s ključevima koje sadrže postavke uređaja potrebne za šifriranje ili dešifriranje poruke. Svaki mjesec, operateri ENIGME bi dobili novu knjigu s ključevima koja je specificirala koji ključ se rabi koji dan. Što se tiče orijentacije rotora, svaki rotor je imao alfabet ugraviran na vanjskom omotaču, pa bi operater rotirao rotor sve dok se na vrhu ne bi pojavila slova specificirana u dnevnom ključu. Svaki dan vrijedila je druga šifra, no, budući da su se dnevno šifrirale ogromne količine poruka, bilo je potrebno nekako postići da se sve te poruke ne šifriraju doslovno istim ključem, jer bi to znatno smanjilo sigurnost. Stoga su Nijemci uveli distribuciju "ključa za poruku" pomoću dnevnog ključa. Ključ za poruku je imao iste postavke na prespojnoj ploči i isti raspored rotora kao dnevni ključ, ali različitu orijentaciju rotora. Budući da ta orijentacija rotora nije bila u knjizi s ključevima, trebalo ju je sigurno poslati zajedno s porukom. To se radilo na sljedeći način. Pošiljalac bi postavljao svoj stroj prema dogovorenom dnevnom ključu, koji ima orijentaciju šifrarnika npr. CXL. Zatim bi nasumično odabirao novu orijentaciju rotora za ključ za poruke, npr. YAQ i šifrirao YAQ pomoću dnevnog ključa (i to dvaput, da bi primatelj bio siguran da je primio dobar ključ za poruke). Na primjer, pošiljalac je mogao YAQYAQ šifrirati kao MIVWJE. Primijetimo da su dva niza slova YAQ šifrirana različito (prvi kao MIV, a drugi kao WJE) jer se rotori ENIGME rotiraju nakon šifriranja svakog slova. Pošiljalac tada mijenja orijentaciju rotora u YAQ i šifrira ostatak poruke prema ovom ključu za poruke. Kod primatelja je stroj na početku bio postavljen prema dnevnoj orijentaciji CXL. Nakon što se unese prvih 6 slova dobivenog šifrata, MIVWJE, dobiva se YAQYAQ. Primatelj sada zna da treba podesiti orijentaciju šifrarnika na YAQ, koji je ključ za poruke, i onda dešifrirati preostali šifrat da bi dobio originalnu poruku.

Poljski su kriptoanalitičari predvođeni Rejewskim iskoristili ovo ponavljanje za kriptoanalitički napad. Znajući da prvo i četvrto slovo u šifratu odgovaraju istom slovu ključa za poruke, oni su istraživali veze među tim slovima unutar svih poruka dobivenih pomoću istog dnevnog ključa. Imajući na raspolaganju velik broj poruka, mogli su za svako slovo alfabeta naći s njim na ovaj način povezano slovo. Tako bi dobili jednu permutaciju alfabeta A, B, ... , Z. Važno svojstvo permutacija je da se one mogu rastaviti na produkt ciklusa (lanaca). Rejewski je uočio da broj elemenata u ciklusima ovisi isključivo o rotorima, a ne o prespojnoj ploči. Ukupan broj postavki rotora je 105456, što je velik broj, ali ne i ogroman. Zahvaljući Schmidtovoj špijunaži, Poljaci su bili u stanju napraviti repliku ENIGME, te katalogizirati koje postavke rotora daju kakve rastave na produkte ciklusa (za to im je trebala godina dana). Nakon toga, dešifriranje je bilo dosta lako. Trebalo je još odrediti veze na prespojnoj ploči. Ako se krene u dešifriranje s prespojnom pločom bez ikakvih veza, dobit će se uglavnom nerazumljiv tekst. No, vjerojatno će se naići i na djelove teksta koji su "skoro čitljivi", tj. u kojima je dosta jasno koja slova treba zamijeniti da bi se dobio otvoreni tekst. I tako se otkrivaju slova koja su povezana kablovima na prespojnoj ploči. Na ovaj su način Poljaci nekoliko godina uspijevali redovito dešifrirati njemačke poruke, sve dok 1939. godine Nijemci nisu značajno povećali broj mogućih ključeva, uvođenjem većeg broja rotora.

Neposredno prije početka Drugog svjetskog rata, sva je dokumetacija rada Rejewskog poslana Britancima. Oni su u to vrijeme bili oformili veliku grupu kriptoanalitičara različitih profila u Bletchley Parku. Kako je ova grupa bila veća, a imala je i znatno veći proračun od poljskog Biuroa Szyfróv, uspjeli su konstruirati vrlo snažne strojeve (tzv. bombe) pomoću kojih su pokušavali dekriptirati poruke šifrirane ENIGMOM. Nakon što su svladali tehniku koju su koristili Poljaci, grupa iz Bletchley Parka, predvođena Alanom Turingom, izmislila je još neke nove tehnike. Jedna od slabosti, ne same ENIGME, već njezina korištenja u praksi, bilo je korištenje "predvidljiivih ključeva" (tzv. cilija). Tako su operateri često za ključ za poruku koristili tri susjedna slova na tipkovnici. Pored toga, Turing je pronašao efikasan način za dešifriranje ENIGME korištenjem metode vjerojatne riječi. Sve aktivnosti unutar Bletchley Parka su bile prekrivene velom tajnosti punih 30 godina. Tek je 1974. godine britanska vlada dozvolila objavljivanje prvih informacija vezanih uz britansko razbijanje ENIGME.


Šveđanin ruskog podrijekla Boris Hagelin tvorac je niza naprava za šifriranje koje su u širokoj uporabi bile sredinom 20. stoljeća. On je prvi čovjek koji je postao dolarski milijunaš zahvaljujući kriptologiji. Vjerojatno najpoznatiji njegov izum je stroj C-36 iz 1936. godine, koji je u američkoj vojsci imao naziv M-209.

M-209

Osnovne komponente ovog stroja bile su 6 rotora s po 17, 19, 21, 23, 25 i 26 slova, te "kavez" koji je imao 27 šipki montiranih u obliku vodoravnog cilindra koji se okreće. Opisat ćemo matematičkim terminima princip rada stroja M-209.

Neka je M matrica dimenzija 6 × 27 čiji su elementi 0 ili 1, takva da niti jedan stupac od M nema više od dvije jedinice. Jedna takva matrica je ova:

M =
00 01 00 00 10 10 00 11 10 00 00 00 00 1
10 00 10 00 10 01 10 00 10 01 00 10 10 0
00 00 00 00 00 00 00 00 00 00 00 00 00 0
00 11 00 01 01 00 00 10 01 00 01 11 11 1
00 10 10 00 00 01 00 01 00 10 00 00 00 0
00 00 00 01 00 10 01 00 00 01 00 01 00 0

Ako je sada v 6-dimenzionalni vektor redak s komponentama iz {0,1}, onda je vM 27-dimenzionalni vektor redak s komponentama iz {0,1,2}. Npr. za v = (1,0,1,1,0,0) dobivamo
vM = (0,0,1,2,0,0,0,1,1,1,1,0,0,0,2,1,1,1,0,0,0,1,1,1,1,1,2).
Broj pozitivnih komponenti od vM se zove broj bodova od v. U našem primjeru je taj broj jednak 16. Općenito je to neki broj između 0 i 27.

Step figura se konstruira na sljedeći način. Složimo 6 nizova brojeva iz {0,1} jedan na drugi. Nizovi imaju duljine redom 17, 19, 21, 23, 25 i 26. Evo primjera jedne step figure:


  0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0
  0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1
  1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
  1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 
Za razliku od matrica, ovdje nema nikakvih ograničenja vezanih za broj jedinica. Step figura generira beskonačan niz 6-dimenzionalnih vektora koje dobivamo iz njezinih stupaca, s time da kad se neki redak završi, on kreće iz početka. Tako su prva dva vektora u našem primjeru (0,0,0,0,1,1) i (1,1,0,0,0,1), dok su 18., 19. i 20. vektor (0,0,0,0,0,0), (1,0,0,1,0,1) i (1,0,0,0,0,0).

Sada možemo opisati postupak šifriranja. Neka je xi numerička vrijednost i-tog slova u otvorenom tekstu, te hi broj bodova i-tog vektora generiranog step figurom. Tada je šifrat yi jednak
yi = hi - xi - 1.
(*)

U stroju M-209 rotori odgovaraju step figuri, a kavez matrici M. Tako matrica i step figura predstavljaju ključ za šifriranje pomoću M-209.

Uočimo da se jednakost (*) može zapisati i kao

xi = hi - yi - 1.

to znači da se isti ključ koristi za šifriranje i dešifriranje. To je razlog zašto u formuli (*) imamo oduzimanje, a ne zbrajanje. Važno je uočiti da su duljine redaka step figure u parovima relativno prosti brojevi. To povlači da je period niza generiranog step figurom jednak

17.19.21.23.25.26 ≈ 108.

Ipak, u nekim specijalnim slučajevima period može biti puno kraći. Na primjer ako u step figuri nema nula, onda je (1,1,1,1,1,1) jedini generirani vektor, pa je period jednak 1. Općenito, period će biti kratak ako imamo malo jedinica u matrici M ili malo nula ili malo jedinica u step figuri, pa takve ključeve treba izbjegavati.


Primjer 1.14: Zadan je otvoreni tekst

KRALJEVSTVO KRALJEVSTVU NE PROPISUJE ZAKONE

te matrica M i step figura kao gore. Otvoreni tekst ima duljinu 39, a numerički ekvivalenti slova su redom
10, 17, 0, 11, 9, 4, 21, 18, 19, 21, 14, 10, 17, 0, 
11, 9, 4, 21, 18, 19, 21, 20, 13, 4, 15, 17, 14, 15, 
8, 18, 20, 9, 4, 25, 0, 10, 14, 13, 4.
Brojevi bodova vektora generiranih step figurom su redom
10, 17, 16, 9, 9, 9, 7, 0, 0, 0, 0, 12, 0, 0, 18, 7, 
0, 0, 18, 7, 9, 9, 19, 14, 9, 10, 5, 10, 0, 0, 0, 7, 
7, 0, 12, 0, 9, 17, 19, 9, 9, 5, 12, 0.
Sada primjenom formule (*) dobivamo šifrat

ZZPXZ ELHGE LBIZG XVEZN NOFJT SQURH FXCAL WSYV

Uočimo da su se dva pojavljivanja niza slova KRALJEVSTV u otvorenom tekstu šifrirala jednom kao ZZPXZELHGE, a grugi put kao BIZGXVEZNN.



Kao što smo već ranije napomenuli, ključna riječ kod šifriranja strojem M-209 i ostalim sličnim napravama je ogromna (oko 108). Stoga primjena metode Kasiskog ne dolazi u obzir. Ipak, dekriptiranje je moguće ukoliko kriptoanalitičar posjeduje dva ili više šifrata dobivenih šifriranjem različitih otvorenih tekstova jednakim ključevima za šifriranje, ili ključevima koji su "bliski", tako da se ključne riječi dobivene pomoću njih podudaraju na nekim segmentima. U tom slučaju može se primijeniti tzv. Kerckhoffsova metoda superpozicije. Pomoću nje možemo odrediti odgovarajući segment ključne riječi, a potom koristeći razne tehnike u ovisnosti o kojem je stroju riječ, to se može iskoristiti za rekonstrukciju čitavog ključa.

Prikažimo ukratko Kerckhoffsovu metodu. Pretpostavimo da su otvoreni tekst x1x2... i šifrat y1y2... povezani relacijama

yi = xi + ki mod 26     ili     yi = ki - xi mod 26.

Tada iz dva šifrata dobivena istim ključem možemo eliminirati ključ:

yi - y'i = xi - x'i mod 26     ili     yi - y'i = x'i - xi mod 26.

Sada svaku hipotezu o otvorenom tekstu x1x2... možemo testirati na otvorenom tekstu x'1x'2..., te tako hipotezu prihvatiti ili odbaciti. Jasno, metoda je još efikasnija ukoliko imamo više od dva šifrata dobivena istim ključem.


Primjer 1.15: Pretpostavimo da su šifrati

        C R U D L H G C A S
        X V X D U X K U I A
dobiveni istim ključem po pravilu yi = xi + ki mod 26.

Primijenimo na njih Kerckhoffsovu metodu. Na samom početku mogu nam koristiti neka saznanja o vjerojatnim početcima poruka, a također i podatci o najčešćim prvim slovima u riječima (u hrvatskom: S, P, N, D, I, O), drugim slovima (u hrvatskom: A, E, O, R, I, U) i slično.

Pretpostavimo da prvi otvoreni tekst počinje sa SA. Tada iz X - C + S = 23 - 2 +18 = 13 = N, te V - R + A = 4 = E, zaključujemo da drugi otvoreni tekst počinje sa NE. Sada možemo u nekom rječniku pogledati koji su najčešći nastavci riječi koje započinju sa SA, odnosno NE. Dobivamo: za SA to su M, V, N, a za NE to su P, O, D. Pogledajmo sada što pretpostavka da je x3 = M, V ili N daje za x'3. Dobivamo: x'3 = P, Y ili Q. Ovo prilično jasno sugerira da prvi tekst počinje sa SAM, a drugi sa NEP. Četvrto slovo bi trebalo biti jednako u oba otvorena teksta i tu se kao najvjerojatnija nameću slova O i A, s time da je O ipak vjerojatnije. Dakle, imamo: SAMO i NEPO. Sada za vjerojatne nastavke prve riječi u rječniku nalazimo (abecednim redom): B, H, K, O, P, S, T, U, koji za x'5 daju redom K, Q, T, X, Y, B, C, D, dok su vjerojatni nastavci za drugu riječ B, D, K, M, P, R, S, V. Tu još možemo koristiti najfrekventnije bigrame koji počinju sa O, a to su: OS, OD, OV, OJ. Sve u svemu, kao najvjerojatnije nameću se dvije mogućnosti:

    S A M O U             S A M O S      
    N E P O D             N E P O B
U prvom slučaju, vjerojatni nastavci prve riječi su B, P, V, što za x'6 daje R, F, L, dok za nastavke druge riječi imamo M, N, O. Stoga ovu mogućnost možemo barem privremeno odbaciti. U drugom slučaju, vjerojatni nastavak prve riječi je T, a druge I ili J. Budući da x6 = T povlači x'6 = J, čini se vrlo vjerojatnom kombinacija
        S A M O S T
        N E P O B J
Sada je već jasno da je druga riječ NEPOBJEDIV, što za prvu riječ daje SAMOSTALAN.


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