Hrvatski matematički elektronski časopis math.e

http://www.math.hr/~mathe/

Enigma

Hrvoje Čavrak

Sadržaj:

Uvod
Enigma
Matematički opis
Kriptografska složenost
Prvi uspješni napad
Princip napada na Enigmu
Zaključak
Linkovi
Popis literature

Uvod

Zahvaljujući nadljudskim naporima savezničkih kriptoanalitičara došlo je do preokreta tijeka Drugog svjetskog rata. Ispisavši neke od najzanimljivijih stranica u povijesti kriptografije, uspjeli su učiniti ono što se smatralo nemogućim - dešifrirati "Enigmu"...

Nagli razvoj elektrotehnike po završetku Prvog svjetskog rata nameće potrebu uspostave sistema za sigurnu razmjenu informacija. Budući da je tadašnja radiokomunikacijska tehnologija bila jednostavna i nerazvijena, zbog propagacijskih svojstava radiovalova unutar korištenog frekvencijskog opsega, emisije vojnih radiouređaja mogle su primati sve zaraćene strane. Poučeni iskustvom o značenju tajnosti informacije u globalnom ratovanju, vojni stručnjaci zemalja širom svijeta inzistiraju na izradi i implementaciji sustava za kriptografsku zaštitu podataka koji bi omogućio sigurnu komunikaciju s udaljenim postrojbama, jednostavnost korištenja i pouzdanost u terenskim uvjetima.

Sustav za kriptografsku zaštitu informacija "Enigma" potječe iz 1919. godine kada njegov tvorac Arthur Scherbius patentira i proizvodi prvu inačicu sustava. Nakon nekoliko različitih modela 1926. godine mornarica njemačke vojske uvodi sustav "Enigma" za zaštitu informacija, a potom ga, nakon nekoliko izmjena i dorada, usvajaju i kopnena vojska te zrakoplovstvo.

Dolaskom Nacionalsocijalističke stranke na vlast financijska izdvajanja u vojne svrhe višestruko su povećana - Njemačka se sprema za rat. Blitzkrieg ("munjeviti rat"), nova ratna strategija kojom njemački generali namjeravaju brzo i učinkovito slomiti neprijateljski otpor, oslanja se na kvalitetne i sigurne komunikacije među različitim vojnim jedinicama, u čemu "Enigma" igra središnju ulogu.

Nakon objave i početka rata saveznici shvaćaju važnost praćenja njemačkih komunikacija i ulažu golema sredstva u probijanje njihove kriptografske zaštite. Podaci koje su na taj način stekli bili su velika pomoć ratnim uspjesima saveznika.


Enigma

Enigma je elektromehanički uređaj koji se sastoji od tipkovnice s 26 tipki poput pisaćeg stroja, zaslona s 26 žaruljica za prikaz šifriranog izlaza, tri mehanička rotora i električne prespojne ploče, a napaja se putem ugrađene baterije. Pritiskom na tipku kroz mrežu kontakata rotora i prespojne ploče zatvara se strujni krug i pali se odgovarajuća žaruljica koja označava šifrirano slovo.

Mehanički rotori sastoje se od diskova s 26 kontakata kružno smještenih na obodu svake stranice. Svaki kontakt na jednoj strani diska povezan je 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 predstavlja "ulaz" drugom.

Izlaz trećeg rotora povezan je 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 da električni signal šalje natrag kroz rotore, no drugim putem. Kad operater pritisne tipku, električni signal putuje do ulaznog kontakta prvog rotora.

S obzirom da interno ožičenje rotora predstavlja transformaciju slova, električni signal na izlazu prvog rotora predstavlja neko drugo slovo, a postupak se nastavlja kroz reflektor te ponovno kroz sva tri rotora do odgovarajuće žaruljice za indikaciju. Svakim pritiskom na tipku okreću se mehanički rotori, te se na taj način dinamički mijenja električni spojni put između tipke i žaruljice, a svako slovo šifrira drugačije.

 

Arthur Scherbius, (20. listopad 1878. - 13. svibanj 1929.), njemački inženjer, 1919. konstruirao je i patentirao uređaj Enigma te osnovao tvrtku Scherbius & Ritter za njegovu proizvodnju. Tvrtka je kupila patentna prava i na kriptografski uređaj koji je konstruirao Hugo Koch, no zbog nedostatka potražnje i visokih cijena uređaja tvrtka posluje loše, sve dok njemačke oružane snage ne uvode uređaj Enigma kao sustav kriptografske zaštite. Nakon niza preinaka i dorada tvrtka u vojne svrhe isporučuje više desetaka tisuća primjeraka ovog uređaja. Scherbius nije živio dovoljno dugo da svjedoči velikom poslovnom uspjehu: poginuo je u prometnoj nesreći 1929. godine.

Prvi rotor svaki se put okrene za jedan kontakt, a kad učini potpun krug, mehanička poluga okrene sljedeći rotor za jedan kontakt. Na taj način htjelo se izbjeći ponavljanje postavki za šifriranje, čime bi se stvorila jednostavna supstitucijska šifra.

Matematički opis

Enigma je polialfabetska supstitucijska transformacija koja se može matematički prikazati kao produkt permutacija. Razmatrajući varijantu s tri rotora, neka P predstavlja transformaciju prespojne ploče, U transformaciju reflektora, a L, M i R transformacije prvog, drugog i trećeg rotora. Tada se šifrat E može izraziti kao

Nakon svakog pritiska na tipku transformacija se mijenja okretanjem rotora. Ukoliko se prvi rotor R okrene za i mjesta, transformacija postaje , gdje je ciklička permutacija koja preslikava A u B, B u C itd. Također, transformacije drugog i trećeg rotora mogu se prikazati kao j i k okreta rotora M i L. Naposljetku, enkripcijska funkcija može se prikazati kao:

Kriptografska složenost

Tri već ožičena rotora s 26 kontakata čine 17 576 mogućih spojnih kombinacija. Kada bi protivnik mogao isprobati samo jednu kombinaciju u minuti, trebalo bi mu svega dva tjedna da pronađe ispravne postavke rotora. Sigurnost je mogla biti povećana dodavanjem novih rotora, no tada bi se povećale veličina i težina samog uređaja, što nije bilo prihvatljivo. Umjesto toga Scherbius odlučuje povećati sigurnost povećanjem broja mogućih početnih postavki na dva načina: izmjenjivim rotorima i prespojnom pločom.

Mehanicki rotori Enigme Budući da su rotori mehanički gotovo identični, a njihovi električni spojni putevi nužno različiti, njihovom jednostavnom zamjenom mijenja se i način šifriranja samog stroja. Broj mogućih permutacija triju rotora je 3!, tj. broj početnih postavki množi se faktorom 6. Znatno veći doprinos sigurnosti donosi prespojna ploča, koja mijenja električne puteve između tipkovnice i prvog rotora, omogućujući inicijalnu zamjenu slova prije samog procesa šifriranja. Na primjer, moguće je zamijeniti slova "A" i "F" tako da se pritiskanjem tipke "A" odašilje slovo "F" i obratno. U ranoj fazi Drugog svjetskog rata operateri uređaja Enigma koristili su 6 prespojnih kabela, što omogućuje 100 391 791 500 načina za zamjenu 6 parova slova, a 1941. godine standardizirano je korištenje 10 prespojnih kabela, što podrazumijeva 150 738 274 937 250 mogućih kombinacija.



Na prespojnoj ploči postoji 26 priključaka, a svaki prespojni kabel zauzima dva (jedan na svakoj strani). S obzirom na mogućnost izbora broja korištenih kabela (0 ≤ p ≤ 13) možemo izabrati različitih kombinacija korištenih utičnica. Potrebno je odrediti na koliko načina p kabela možemo priključiti na 2p priključaka. Nakon što priključimo jedan kraj prvog kabela, ostaje nam 2p-1 slobodnih priključaka. Spajanjem jednog kraja drugog kabela, ostaje nam 2p-3 slobodnih priključaka. Uvidjevši analogiju, broj načina možemo izraziti s

Kombinirajući ta dva elementa, broj različitih spojnih veza koje je operator Enigme mogao odabrati iznosi:

Broj kombinacija prikazujemo tablicom ovisno o broju korištenih spojnih kabela (p):

p
broj kombinacija
p
broj kombinacija
0
1
7
1 305 093 289 500
1
325
8
10 767 019 638 375
2
44 850
9
53 835 098 191 875
3
3 453 450
10
150 738 274 937 250
4
164 038 875
11
205 552 193 096 250
5
5 019 589 575
12
102 776 096 548 125
6
100 391 791 500
13
7 905 853 580 625


Budući da su skupovi kombinacija (s obzirom na šifriranje) za svaku vrijednost p međusobno disjunktni, možemo ih zbrojiti te konačni ukupni broj mogućih postavki spojne ploče iznosi:

Svaki mehanički rotor moguće je interno spojiti na 26! različitih načina. Ostala dva trebaju biti različito spojena, pa za njihovu izvedbu preostaje 26!-1 i 26!-2 načina. Sveukupno, ožičenje svih triju rotora može biti izvedeno na 65592937459144468297405473480371753615896841298988710328553805190043271168000000 različitih načina.

Ostaje samo reflektor koji može biti spojen na

različitih načina. Kombiniranjem svih navedenih elemenata dobiva se teoretski maksimalan broj različitih postavki Enigme:

3283883513796974198700882069882752878379955261095623685444055315226006433615627409666933182371154802769920000000000,

što je otprilike . Uzevši u obzir veličinu dobivenog broja, dešifriranje Enigme činilo se nemogućom misijom. Rukavica je bačena, čekao se odgovor.

Prvi uspješni napad

Po završetku Prvog svjetskog rata engleski kriptoanalitičari i dalje su pažljivo pratili i nadzirali njemačke radiokomunikacije. 1926. godine počeli su presretati neobične poruke nepoznatog sadržaja, šifrirane novim sustavom Enigma. Svi pokušaji dešifriranja brzo su propali, a količina podataka kojima su obavještajne službe raspolagale naglo se smanjila. Amerikanci i Francuzi također su pokušali napasti sigurnost Enigme, no zbog mirnodopskih uvjeta dešifriranju nisu pridavali veću važnost i financijska sredstva. Nakon Prvog svjetskog rata Poljska je uspostavila nezavisnost, ali je zbog ambicija svojih susjeda za teritorijem prisiljena na oprez i stoga pridaje veliku važnost obavještajnim podacima.

Poljaci u sklopu obavještajne službe osnivaju ured za kriptografiju, Biuro Szyfróv, no prvi njihovi pokušaji dešifriranja Enigme završavaju bezuspješno. Veći napredak ostvaren je akcijom francuske obavještajne službe, kada francuski tajni agent stupa u vezu s bratom načelnika sektora veze njemačke vojske, Hansom-Thilom Schmidtom. Dana 8. studenog 1931. godine u Verviersu u Belgiji uz naknadu od 10,000 njemačkih maraka Schmidt dopušta fotografiranje dvaju dokumenata o novom sustavu za šifriranje ("Gebrauchsanweisung für die Chiffriermaschine Enigma" i "Schlüsselanleitung für die Chiffriermaschine Enigma") koji predstavljaju upute za upotrebu novog sustava. Francuzi su smatrali kako bez ključa ionako ne mogu dešifrirati Enigmu te nisu ni pokušali napraviti repliku samog uređaja.

Budući da su Francuzi i Poljaci po završetku Prvog svjetskog rata potpisali ugovor o vojnoj suradnji, te informacije završavaju u rukama poljskog ureda za kriptografiju. Dokumenti su opisivali i proceduru mjesečne distribucije šifrarnika, knjiga koje sadrže postavke uređaja Enigma potrebne za šifriranje ili dešifriranje poruke. Svaki dan vrijedila je druga šifra, a kao posebna mjera opreza izbjegavalo se korištenje dnevne šifre za samo šifriranje stotina poruka odaslanih tijekom dana jer bi to potencijalnim kriptoanalitičarima dalo velik analitički uzorak. Umjesto toga za svaku poruku odabrana je proizvoljna šifra, šifrirana dnevnim ključem i odaslana na početku poruke. Kako je mogućnost legitimnog dešifriranja poruke ovisila o točno primljenom ključu, on se odašiljao dvaput kako bi se izbjegla moguća pogreška radiooperatera.

Marian Rejewski, (26. kolovoz 1905. - 13. veljače 1980.), poljski matematičar i kriptograf rođen je u mjestu Bydgoszcz. Studira matematiku na sveučilištu u Poznanju i kao pripadnik poljske vojne obavještajne službe zapošljava se u njezinom novootvorenom uredu za kriptografiju (Biuro Szyfrow) gdje radi na projektu dešifriranja Enigme. Neiskusan, ali iznimno talentiran, Rejewski primjenom matematičkih metoda osmišljava način dešifriranja Enigme i omogućuje poljskoj obavještajnoj službi da nekoliko godina prati i nadzire njemačke vojne komunikacije. Uoči njemačke invazije evakuiran je u Francusku, a potom i u Englesku, no tamo nije angažiran na projektu dešifriranja Enigme. Godine 1946. vraća se u Poljsku, gdje radi u tvornici sve do odlaska u mirovinu. Umire u Varšavi 1980. godine, a Poljsko matematičko društvo odlikuje ga posebnom medaljom.  

Dugo vremena smatralo se kako su najbolji kriptoanalitičari stručnjaci za jezik, no Poljaci su regrutirali dvadeset matematičara sa sveučilišta u Poznanju. Najdarovitiji među njima bio je 23-godišnji statističar Marian Rejewski. Radeći potpuno sam, danima je analizirao materijale francuskih obavještajaca. Smatrao je da je ponavljanje najveća opasnost za sigurnost Enigme. Koristeći neoprezno dupliranje ključa na početku njemačkih poruka, počeo je osmišljavati metodu za probijanje Enigme. Ako je ključ ABC, zapisan je dvaput kao ABCABC i šifriran u npr. FOESCG, Rejewski zaključuje da su F i S šifrat istog slova A, kao i parovi (O,C) i (E,G). Svakom presretnutom porukom dobiva dodatni materijal za analizu, pa uskoro počinje uočavati uzorke i veze među parovima te primjećuje lance poput:

AFWA

BQZKVEIB

CHGOYPC

JMXSTNUJ

 

Rejewski oštroumno otkriva da, iako i postavke rotora i prespojne ploče utječu na sadržaj karika lanaca, njihova dužina ovisi isključivo o postavkama rotora. Podsjetimo se, ukupan broj mogućih postavki rotora (105456) dobivamo tako da broj permutacija diskova rotora (6) pomnožimo s brojem mogućih postavki svake permutacije (17576). Time je problem znatno pojednostavljen: umjesto da se zamara milijardama mogućih dnevnih ključeva, Rejewski znatno reducira problem - potrebno je pronaći vezu između 105456 mogućih postavki rotora i njima pripadajućih lanaca. Zahvaljujući francuskoj vezi i Hansu-Thilu Schmidtu, Rejewski je imao pristup replici uređaja Enigma, te su on i njegov tim počeli provjeravati i evidentirati svaku moguću postavku rotora i pripadajuće dužine lanaca. Nakon godinu dana mukotrpnog posla baza podataka bila je gotova, a dešifriranje Enigme postala je stvarnost.

Svakog dana, nakon dovoljnog broja prikupljenih poruka i uočenih lanaca, Rejewski je pomoću baze podataka, koja sadrži sve moguće postavke rotora i rezultirajućih lanaca među njima, pronašao odgovarajući i time otkrio postavke rotora. Ipak, problem još nije bio riješen. Unatoč tome što prespojna ploča može imati milijarde prespojnih kombinacija, pronalazak ispravne postavke rotora sveo je problem na običnu supstitucijsku šifru!

Poljaci su uspješno koristili metodu Rejewskog nekoliko godina, prateći i najtajniju komunikaciju vrhovnog stožera njemačke vojske. Čak i kad su Nijemci promijenili način slanja poruka, Rejewski je pronašao način dešifriranja Enigme. Iako je njegov katalog postao bezvrijedan, osmislio je mehanički uređaj koji bi automatski tražio ispravne postavke rotora. Idejno osmišljen kao adaptacija Enigme, uređaj je konstruiran tako da velikom brzinom provjerava svaku od 17576 mogućih postavki rotora. Zbog nepoznatog redoslijeda rotora paralelno je radilo 6 ovakvih strojeva, od kojih je svaki predstavljao jednu permutaciju poretka diskova rotora. Stroj je nazvan bomba, vjerojatno zbog buke koju su proizvodili rotirajući mehanički dijelovi, a dnevne postavke rotora mogao je naći za otprilike dva sata.

Nažalost, ovako povoljna situacija za Poljake nije dugo potrajala. Nijemci 1939. godine dodaju još dva rotora čime povećavaju broj njihovih mogućih kombinacija i prestaju ključeve u poruci slati dvaput, efektivno eliminirajući poznatu mogućnost napada. Poljaci su, shvativši ozbiljnost situacije i nadolazeću invaziju, odlučili podijeliti rezultate svog rada s engleskim i francuskim saveznicima. Kompletna dokumentacija rada Rejewskog, planovi i nacrti za bombu, kao i replika Enigme poslani su diplomatskom poštom u Pariz, a potom u London. Samo dva tjedna kasnije počeo je Drugi svjetski rat, a Enigma je ponovno utihnula.

Shvativši ratnu opasnost, Britanci su ozbiljno pristupili problemu i, poučeni iskustvom Poljaka, osnovali Vladin ured za šifre (Government Code and Cypher School) sa sjedištem u Bletchley Parku te počeli novačiti matematičare i ostale znanstvenike. Alan Turing i Gordon Welchman, obojica matematičari sa sveučilišta Cambridge, pridružili su se uredu uoči izbijanja sukoba s Njemačkom. Tijekom jeseni 1939. Britanci su uspješno ovladali tehnikama kojima su raspolagali Poljaci. Budući da su imali daleko veće resurse i budžet, uspješno su se nosili sa znatno većim brojem kombinacija rotora i u većini slučaja uspijevali pronaći dnevne postavke. Britanci su počeli pronalaziti vlastite metode za otkrivanje dnevnih ključeva. Njemački operateri često su kao ključ odabirali tri uzastopna slova s tipkovnice uređaja Enigma ili su višekratno koristili jedan te isti ključ, olakšavajući posao kriptoanalitičarima. Također, otkriveno je kako se nijedno slovo ne može šifriranjem preslikati u to isto slovo, što je mnogo puta pomoglo dešifriranju. Alan Turing shvatio je da se dosad korištena metoda oslanja na specifičan način odašiljanja ključa unutar poruke pa njegova promjena može vrlo lako rezultirati nemogućnošću dešifriranja. Umjesto toga, Turing konstruira bombu koja pretražuje sve kombinacije postavki rotora u potrazi za ispravnom, na načelu pretpostavljenog sadržaja poruke ("cribs").   Alan Mathison Turing (23. lipanj 1912. - 7. lipanj 1954.), jedan je od najvećih britanskih matematičara svih vremena. Smatra se ocem modernog računarstva, formalizirao je koncept algoritma i matematičkog modela računala nazvanog Turingov stroj. Rođen je u Paddingtonu, studira na utjecajnom sveučilištu Cambridge. Godine 1936. piše svoj najznačajniji rad, "On Computable Numbers, with an Application to the Entscheidungsproblem", a 1938. doktorira na sveučilištu Princeton. Tijekom Drugog svjetskog rata daje nemjerljiv doprinos dešifriranju njemačkih kriptografskih sustava Enigma i Fish. Zahvaljujući njegovim radovima, konstruirani su posebni strojevi - digitalno računalo Colossus korišteno za probijanje sustava Fish, te usavršena verzija poljskog uređaja za probijanje Enigme, bomba. Godine 1949. postaje zamjenik ravnatelja Računalnog odjela Sveučilišta u Manchesteru gdje razvija programsku podršku za jedno od prvih pravih računala, Manchester Mark I. Proučavao je problem umjetne inteligencije, o čemu je izdao nekoliko radova. Godine 1952. uhićen je i osuđen zbog homoseksualnosti, a 1954. je počinio samoubojstvo, uzevši smrtonosnu dozu cijanida.

Ako je pretpostavljeno slovo "W", a šifrirano "F", Turingova bomba zanemaruje sve rezultate osim onih koji omogućuju zatvaranje strujnog kruga između "W" i "F". U isto vrijeme, Gordon Welchman pažnju posvećuje prespojnoj ploči Enigme, i shvaća da ako neki spoj slovo A zamjenjuje slovom B, tada istovremeno slovo B zamjenjuje slovom A. Konstruira vlastitu prespojnu ploču koja svako slovo spaja sa svima ostalima, tvoreći mrežu dijagonalnih linija. Svoj rad pokazuje Turingu koji ga oduševljeno prihvaća, pa je kombinacijom dvaju metoda potraga za ispravnim postavkama rotora znatno pojednostavljena. Tek nakon nekoliko mjeseci dizajniranja i gradnje, u kolovozu 1940. godine prvi stroj stigao je u Bletchley Park. Unatoč velikom uspjehu u dešifriranju poruka njemačkih kopnenih i zračnih snaga, komunikacijski sistem njemačke mornarice predstavljao je nepremostiv problem. Kolekciji od standardnih pet dodana su još tri rotora, čime je broj mogućih kombinacija znatno narastao, a nije bilo poznato ni njihovo ožičenje.

Sudbina Velike Britanije ovisila je o liniji opskrbe - konvojima teretnih brodova kojima su Sjedinjene Države dopremale prijeko potrebne namirnice, sirovine i oružje. Njemački plan bio je prekid opskrbne linije, čime bi se Velika Britanija bacila na koljena. Admiral Karl Dönitz, zapovjednik njemačke flote, razvio je taktiku koja se oslanjala prvenstveno na komunikaciju među podmornicama, te je stoga inzistirao na njezinoj sigurnosti. Podmornice su patrolirale Atlantikom u potrazi za savezničkim konvojima i nakon opažanja radiovezom javljale njihovu lokaciju drugim podmornicama. Nakon mnoštva potopljenih brodova svibanj 1941. donosi preokret iscrpljenoj Britaniji. Kraljevska mornarica zarobila je njemačku podmornicu U-110 i domogla se opreme za šifriranje, doznavši tako ožičenje rotora i važeću knjigu šifri za dva mjeseca. Nijemci su vjerovali kako je podmornica potonula i nisu mijenjali sustav.

Nakon niza neuspješnih napada na savezničke konvoje, admiral Dönitz posumnjao je u kompromitiranost sustava i naredio promjenu, dodavši još jedan rotor između trećeg rotora i reflektora. Na sreću analitičara u Bletchley Parku u prosincu 1941. prije službene promjene njemačka podmornica greškom šalje poruku korištenjem svih četiriju rotora, te potom uviđa grešku i ponovno je odašilje koristeći samo tri. Iz ove naizgled malene greške analitičari uspijevaju odgonetnuti ožičenje četvrtog rotora. U veljači 1942. njemačka ratna mornarica, Kriegsmarine i službeno uvodi novu šifru koju Britanci nazivaju Shark, a njezine komunikacije opet postaju nedostupne savezničkim snagama.

Struktura organizacije djelatnosti Bletchley Parka

U prvo vrijeme odjeli su bili raspoređeni po barakama brojevi kojih su postali asocijacija na posao koji se u njima obavljao, a nazivi su zadržani i nakon selidbe u veću zgradu.

Neki od odjela bili su:

1 - Prevođenje
2 - Prostor za rekreaciju
3 - Prijevod i analiza poruka
4 - Mornarička obavještajna služba
5 - Vojna obavještajna služba
6 - Kriptoanaliza Enigme
7 - Čitači bušenih kartica
8 - Kriptoanaliza
9 - Plaće i administracija
10 - Meteorološka postaja
11 - Konstrukcija "bombe"

  Ulaskom Sjedinjenih Američkih Država u rat nakon napada na Pearl Harbour, komunikacije njemačke ratne mornarice postaju važne i Amerikancima. Britanci ubrzano razvijaju novu bombu za mornarički sistem s četiri rotora i obećavaju rješenje do kolovoza 1942., no Sjedinjene Države ne žele čekati i kreću s razvojem vlastitog uređaja. Dana 30. listopada 1942. Britanska kraljevska mornarica uspijeva se domoći važnih dokumenata s njemačke podmornice U-559. Njemačke meteorološke postaje bile su opremljene uređajima Enigma sa samo trima rotorima, pa su zato podmorničari četvrti rotor na svojim uređajima postavljali u neutralan položaj i na taj način oponašali Enigmu s trima rotorima. Britanci su uobičajenim načinom pomoću bombi pronašli postavke za prva tri rotora, a potom isprobali svih 26 kombinacija za četvrti i tako dešifrirali Shark. Ipak, to nije bilo moguće bez određene zadrške koja je često rezultirala gubicima.

Turing odlazi u Sjedinjene Države kao savjetnik na projektu razvoja nove inačice bombe s preko 6 tisuća rotora u prosincu 1942. godine, a nove bombe postaju operativne 28. svibnja 1943. Za razliku od britanskih, američke bombe bile su tehnološki daleko brže i savršenije. Najbrži rotor okretao se brzinom od 1725 okretaja u minuti i nakon ostvarenog kontakta nije se mogao trenutno zaustaviti, pa je ugrađena i primitivna tiratronska memorija koja pamti točne vrijednosti svih rotora, te se bomba nakon ostvarenog kontakta sama zaustavlja i vraća na pohranjene parametre. Saveznici su tek tada mogli pouzdano dešifrirati mornarički sustav, koristeći ga za uništenje većine tankera za opskrbu podmornica gorivom. Američki uređaji pokazali su se toliko uspješnima da je Velika Britanija odustala od proizvodnje svojih bombi za sustav s četirima rotorima. Do proljeća 1944. 96 operativnih bombi rutinski je dešifriralo mornaričke komunikacije Kriegsmarine, a nakon otkrivanja dnevnog ključa za dešifriranje i prijevod nakon odašiljanja saveznicima je trebalo oko 20 minuta. Do kraja rata, zahvaljujući uspješnom praćenju njemačkih komunikacija, Sjedinjene Države potopile su ili zarobile 95 njemačkih podmornica.

Princip napada na Enigmu

Zadatak s kojim su bili suočeni Alan Turing i Dillwyn Knox bio je pronaći metodu kojom bi se svakodnevno u što kraćem vremenu mogle pronaći postavke rotora i prespojne ploče Enigme, te dešifrirati njemačke komunikacije za taj dan. Turing i Knox razmatrali su tri metode napada:

a) Napad metodom dvostrukog ključa - metoda se zasniva na proceduralnoj pogrešci njemačkih vojnih snaga čiji su radiooperateri šifrirali dvaput ponovljeni ključ, za slučaj moguće pogreške prilikom odašiljanja. Poljaci su uspješno iskoristili ovu pogrešku i nekoliko godina dešifrirali Enigmu. Turing i Knox su procijenili metodu kao nepouzdanu jer Nijemci lako mogu promijeniti proceduru odašiljanja ključa. Ova odluka pokazala se opravdanom, jer je procedura promijenjena prvog svibnja 1940.

b) Direktna analiza šifrata - ova metoda kasnije je implementirana i u obliku algoritma prilagođena za Colossus seriju računala za napad na šifru Fish kojom su se koristili zaštićeni teleprinteri Geheimschreiber.

c) Napad metodom pretpostavljenog teksta - Turing je shvatio da je potrebno razviti metodu neovisnu o proceduralnim pogreškama koja bi iskorištavala konstrukcijske pogreške Enigme. Analitičari iz Bletchley Parka često su mogli pretpostaviti što je sadržano u poruci, a takve pretpostavke nazivali su "cribs". Iako njihovo pronalaženje nije bila jednostavna zadaća, bilo je dovoljno pronaći jednu pretpostavku svakog dana i konstruirati stroj koji provjerava moguće kombinacije početnih postavki Enigme u potrazi za odgovarajućom. Budući da je pretpostavljeni tekst trebalo ispravno locirati u šifriranoj poruci, metoda razvijena za korelaciju koristila se činjenicom da je šifrirano slovo uvijek različito od originala.

Prvog dana savezničkog iskrcavanja u Normandiji korišten je "crib"

Pretpostavimo da želimo ispravno smjestiti ovaj pretpostavljeni tekst u sljedeći šifrirani niz:

QFZ WRW IVT YRE SXB FOG KUH QBA ISE

To je moguće jedino ako ne pronađemo preklapanja:

 

QFZ WRW IVT YRE SXB FOG KUH QB
WET TER VOR HER SAG EBI SKA YA

 

FZW RWI VTY RES XBF OGK UHQ BA
WET TER VOR HER SAG EBI SKA YA

 

ZWR WIV TYR ESX BFO GKU HQB AI
WET TER VOR HER SAG EBI SKA YA

 

WRW IVT YRE SXB FOG KUH QBA IS
WET TER VOR HER SAG EBI SKA YA

.

RWI VTY RES XBF OGK UHQ BAI SE
WET TER VOR HER SAG EBI SKA YA

Nakon pet pokušaja pronašli smo mjesto u šifriranom tekstu na kojem se nijedan znak ne preklapa, te na taj način našli potencijalnu lokaciju originalnog unutar šifriranog teksta. Još valja utvrditi postoji li transformacija koja preslikava jedan u drugi, te koji su njezini parametri.

123 456 789 012 345 678 901 23
RWI VTY RES XBF OGK UHQ BAI SE
WET TER VOR HER SAG EBI SKA YA

Iskoristit ćemo karakteristiku prespojne ploče koju je Gordon Welchman prvi uočio - uzajamno preslikavanje slova. U nekom položaju, nazovimo ga položaj 1, Enigma će preslikati slovo R u slovo W, no također će preslikati slovo W u slovo R. U položaju 2 preslikat će W u E, no i E u W, itd. Ove parove možemo prikazati vizualno, kao na slici 7.

Svaka transformacija sastoji se od transformacije prespojne ploče, transformacija rotora i reflektora te još jedne transformacije prespojne ploče. Pretpostavimo u gornjem primjeru da su prespojeni E i K, te uočimo transformaciju E u A na položaju 23.

Ako su E i K prespojeni, K će biti ulaz rotoru na položaju 23, koji će ga pretvoriti u neko drugo slovo, nazovimo ga X1. Budući da znamo da se E transformira u A na položaju 23, A mora biti prespojeno sa X1, a X1 će biti ulaz rotoru na položaju 21, transformirajući se u neko slovo X2.

Na položaju 21 A se pretvara u I, dakle X2 mora biti prespojen sa I. Na položaju 3 ulaz u rotor bit će slovo X2 koje se pretvara u neko slovo X3. Budući da je stvarni izlaz T, na prespojnoj ploči zamijenjeni su T i X3. Na položaju 5 ulaz u rotor bit će X3, a izlaz će biti neko slovo X4, koje je prespojeno s E.

Hipoteza koju smo pretpostavili bila je da su prespojeni E i K. Ako kao izlaz ovakve cirkularne provjere dobijemo neko drugo slovo, recimo P, pretpostavka je bila kriva.

Pretpostavka o postavci prespojne ploče može biti točna ako i samo ako zadovoljava ovakvu cirkularnu provjeru, što je temeljna ideja Turingovog napada na Enigmu.


Zaključak

Tijekom Drugog svjetskog rata poginulo je više od 55 milijuna ljudi, uz dotad neviđene štete i razaranja. Britanska i američka vojska velikim su naporima inzistirali na tajnosti projekta dešifriranja Enigme, koji je pod svaku cijenu morao ostati neotkriven. Praćenjem njemačkih komunikacija često su unaprijed znali ciljeve napada, ali to nijednom gestom nisu odali. S današnjeg aspekta otvara se pitanje moralnosti takvih odluka budući da su čitavi gradovi izbrisani s lica zemlje uz desetke tisuća civilnih žrtava kao posljedica njemačkih bombardiranja. To je samo jedan od razloga zašto su sve bombe rastavljene i uništene nakon njemačke kapitulacije, a osoblje koje je na bilo koji način bilo uključeno u projekt, pod prijetnjom prijekog suda i smrtne kazne obvezalo se na strogo čuvanje vojne tajne. Tek 1974. prve informacije vezane uz savezničke uspjehe u dešifriranju Enigme izlaze u javnost, a Marian Rejewski nemalo je iznenađen saznavši da je upravo njegov rad zaslužan za velike uspjehe savezničkih kriptoanalitičara.

Prema procjeni mnogih povjesničara Drugi svjetski rat trajao bi barem godinu dana duže, uz goleme ljudske i materijalne gubitke da saveznici nisu uspjeli dešifrirati Enigmu. S obzirom na uložena materijalna sredstva i ljudski angažman, važnost njezinog dešifriranja može se mjeriti samo s projektom Manhattan, no za razliku od njega, načinio je "bombu" koja je spasila milijune života diljem svijeta.


Linkovi

Da bi čitatelj što bolje shvatio princip rada Enigme, donosimo i simulaciju samog uređaja u obliku Java Appleta koji kao vjerna replika originalnog uređaja s 3 ili 4 rotora podešavanjem proizvoljnih početnih parametara može ispravno šifrirati i dešifrirati.

Navodimo nekoliko internetskih stranica koje se bave tematikom Enigme:

J. Willcox, Solving the Enigma
http://www.nsa.gov/publications/publi00016.cfm

J. Willcox, Bombes: The Secret of Adam and Eve
http://www.nsa.gov/publications/publi00037.cfm

Bletchley Park Trust, Bletchley Park: A brief history
http://www.bletchleypark.co.uk/

G. Ellsbury, The Enigma and the Bombe
http://www.ellsbury.com/enigmabombe.htm


Popis literature

[1] S. Singh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography, Anchor Books/Doubleday, 1999

[2] A. J. Menezes, P. C. Oorschot, S. A. Vanstone: Handbook of Applied Cryptography, CRC Press, Boca Raton, 1996.

[3] H. Sebag-Montefiore, Enigma: The Battle for the Code, John Wiley, New York, 2001.


Uvod
Enigma
Matematički opis
Kriptografska složenost
Prvi uspješni napad
Princip napada na Enigmu
Zaključak
Linkovi
Popis literature