1.8. Naprave za šifriranje

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.

THOMASJEFFERSONWHEELCHIPER

VSJGHLZHWPOMEUBVSLZWQVRPIT.

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 10¹⁰). 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.

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 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 26³ = 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 "predvidljivih 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.

Od brojnih inačica ENIGME spomenimo samo tzv. ZAGREB ENIGMU 16081 iz 1943. godine (o njezinim specifičnostima je govorio profesor Nicolas Courtois u svom predavanju na 20th Central European Conference on Cryptology, Zagreb, 24.-26.6.2020.).

Š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.

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 =

0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 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 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 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 

Sada možemo opisati postupak šifriranja. Neka je x_i numerička vrijednost i-tog slova u otvorenom tekstu, te h_i broj bodova i-tog vektora generiranog step figurom. Tada je šifrat y_i 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

x_i = h_i - y_i - 1.

17^.19^.21^.23^.25^.26 ≈ 10⁸.

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

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.

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.

ZZPXZ ELHGE LBIZG XVEZN NOFJT SQURH FXCAL WSYV

Kao što smo već ranije napomenuli, ključna riječ kod šifriranja strojem M-209 i ostalim sličnim napravama je ogromna (oko 10⁸). 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 x₁x₂... i šifrat y₁y₂... povezani relacijama

y_i = x_i + k_i mod 26     ili     y_i = k_i - x_i mod 26.

y_i - y'_i = x_i - x'_i mod 26     ili     y_i - y'_i = x'_i - x_i mod 26.

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

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 x₃ = M, V ili N daje za x'₃. Dobivamo: x'₃ = 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'₅ 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

        S A M O S T
        N E P O B J