Vloga statistike pri dešifriranju Enigme

film igra imitacij
Film Igra imitacij (foto: BagoGames via Flickr)

Te dni se v kinodvoranah vrti zgodovinska drama Igra imitacije, ki je nastala po knjižni predlogi Andrewa Hodgesa, Alan Turing: The Enigma. Film pripoveduje zgodbo o britanskem matematiku Alanu Turingu, očetu računalništva in umetne inteligence, ki se je med 2. svetovno vojno s skupino strokovnjakov trudil razvozlati sporočila nemških vojaških podmornic, šifrirana z napravo Enigma. Zgodovinarji ocenjujejo, da so odkritja Turinga in njegovih kolegov pripomogla k skrajšanju vojne za vsaj dve leti ter s tem rešila vsaj 14 milijonov življenj.

film igra imitacij
Film Igra imitacij (foto: BagoGames via Flickr)

Pri dešifriranju Enigme in strategiji uporabe rezultatov je imela zelo pomembno vlogo tudi statistika. Preden predstavim vlogo statistike, bom na kratko pojasnila problem, s katerim so se srečali Turing in kolegi.

Enigma je šifrirna naprava, ki je bila sprva razvita za rabo v komercialne namene, nato pa je nekoliko spremenjeno verzijo naprave že leta 1926 začela uporabljati nemška mornarica.

Delovanje lepo ponazori simulacija – recimo, da kot čistopis (osnovno sporočilo) vnesemo nemško besedo UNTERSEEBOOT (podmornica). Pri določenih nastavitvah dobimo tajnopis YHBHHDQOWXNZ. Če to nastavitev spremenimo, kar so Nemci počeli na dnevni ravni, se tajnopis spremeni v eno izmed več kot sto miljard variacij. Vendar so bile v postopku šifriranja določene proceduralne pomanjkljivosti, kar so uspeli izkoristiti poljski kriptologi, ki so v obdobju od 1932-1939 na podlagi teorije permutacijskih grup uspeli razviti več sofisticiranih metod za rekonstrukcijo kodirnih ključev (t.i. indikatorjev) ter tudi mehansko napravo imenovano bomba. Poljska bomba pa ni bila več učinkovita, ko so Nemci leta 1938 trem obstoječim rotorjem dodali še dva, med katerimi so lahko izbirali, kar je število razporeditev rotorjev povečalo iz šest (P=3!) na šestdeset (V=5!/2!). Poljaki niso imeli sredstev, da bi nadaljevali z razvojem, na srečo pa so svoje znanje predali Britancem, ki so v Bletchley parku nadaljevali njihovo delo.

SLIKA 1: Enigma, električna naprava za šifriranje sporočil (foto via Wikipedia). Več o Enigmi tu.

enigma

Prvi prispevek Alana Turinga h kriptologiji je bila leta 1940 izbojšana verzija bombe, elektromehanske naprave za dešifriranje sporočil, katere prvo verzijo je imenoval Victory (v filmu je imenovana Christopher, po Turingovi prvi ljubezni). Za razliko od Poljakov so Turing in sodelavci za analizo tajnopisov namesto negotove metode indikatorjev razvili postopek, ki je temeljil na uporabi poznanih čistopisov (t.i. “crib-based” dešifriranje), za katere so domnevali, da se pogosto pojavljajo. Veliko nemških sporočil se je npr. začelo z vremensko napovedjo, torej so poskusili iskati tajnopise za besedo WETTER (vreme) ter na tej podlagi ugotoviti ključ. V filmu ima to vlogo pozdrav “Heil Hitler”. Velja omeniti, da bomba ni bila samo ena, ampak se ji je že po petih mesecih pridružil drugi model, do konca vojne pa jih je bilo že preko dvesto. Za upravljanje naprav so v Bletchley parku potrebovali veliko delovne sile – za prikaz njihovega dela priporočam ogled video pogovora z Jean Valentine, eno izmed upravljalk bombe. Več o življenju “razbijalcev kod” lahko preberete tudi na strani, ki jim jo je posvetil Google Cultural Institute.

Pri učinkovitosti bombe je imela pomembno vlogo tudi statistika, saj je Turing s statističnimi testi uspel zmanjšati število začetnih nastavitev, ki jih je bilo treba pregledati.

Razvil je tudi kriptoanalitski postopek imenovan banburismus, ki na podlagi zaporednih pogojnih verjetnosti sklepa o verjetnosti nastavitev Enigme. O uporabljenih postopkih je Turing napisal dva znanstvena članka, ki pa sta bila do leta 2012 vladna tajnost. V članku “On Statistics of Repetitions” je izoblikoval statistični preizkus za preverjanje, ali dva tajnopisa uporabljata isti ključ (glej sliko), v eseju “The Applications of Probability to Cryptography” pa je prikazal uporabo analize verjetnosti na širokem naboru problemov v kriptografski analizi.

SLIKA 2: Turingov članek: “On Statistics of Repetitions

alan turing

Po tem, ko je Turingu in kolegom uspelo razbiti kodo, seveda niso mogli v svoj prid uporabiti vsake informacije, saj bi Nemci lahko hitro zaznali in spremenili postopek šifriranja sporočil. Turing je vojski pomagal pri odločanju, kateri dešifrirane informacije lahko uporabijo, pri čemer se je spet posluževal statističnih metod. Princip lahko preprosto razložimo na primeru. Recimo, da imamo nemškega oficirja, ki opazuje dogajanje na morskih bojiščih. Enota opazovanja je podmornica, spremenljivka pa podatek, ali je bila podmornica potopljena ali ne. Poleg tega ima še podatek, kdaj je bilo poslano sporočilo z informacijo o položaju posamezne podmornice. Izračuna lahko teoretično verjetnost dogodka, da je podmornica potopljena, nato pa izračune primerja z empiričnimi podatki. Če se vrednosti ujemajo, lahko sklepa, da je do potopov prišlo naključno. V primeru velikega odmika od pričakovane vrednosti (npr. več podmornic potopljenih ne dolgo za tem, ko je bil centrali sporočen njihov položaj), pa seveda oficir posumi na nepravilnost. Turingova naloga je bila simulirati podatke, ki bi za opazovalce delovali, kar se da naključno. Naključnost so lahko simulirali na dva načina: bodisi so z napadom počakali nekaj dni (v upanju, da se ne bodo premaknile predaleč), bodisi podmornice sploh niso napadli (trajnostna strategija). Več o tem lahko preberete v knjigi Cryptonomicon.

Zgodba o Alanu Turingu in razbijanju Enigme je vsekakor ena izmed najbolj navdihujočih zgodb na področju matematike in statistike.

Britanski matematik in komunikator znanosti James Grimes jo je s pridom uporabil v projektu Enigma, v okviru katerega je obiskoval britanske šole in učencem demonstriral delovanje naprave ter predstavljal Turingovo delo. Kot pravi v spodnjem pogovoru (glej video), se mu zdi zelo pomembno mlade navduševati za znanost. Statistika je ena izmed najbolj uporabnih aplikacij matematike, zato je pomembno, da se razlaga na kakovosten način. Poudari, da je znanje statistike koristno prav za vsakogar, saj nam pomaga bolje razumeti različne vsakdanje pojave.

Tudi Grimes si je ogledal film Igra imitacije in je nad njim navdušen, čeprav je že med gledanjem trailerja opazil veliko netočnosti. Toda vse jim je oproščeno, ker bo film gledalce spodbudil, da izvejo več o tematiki. Po ogledu filma je kot strokovnjak za Turinga napisal zelo humorno objavo, kjer sam sebi odgovarja na pogosto postavljena vprašanja o filmu. Tudi sama, vsem klišejem in zgodovinskim netočnostim navkljub, film nadvse priporočam in ga pozdravljam kot še eno reprezentacijo statistike v popkulturi, o čemer smo na blogu Udomačena statistika že pisali.

 

Ana Slavec (foto: osebni arhiv AS).
Ana Slavec (foto: osebni arhiv AS).

Avtorica: Ana Slavec, sociologinja, doktorska študentka statistike na Univerzi v Ljubljani in mlada raziskovalka na Fakulteti za družbene vede. Ukvarja se z anketno metodologijo, predvsem z izboljševanjem ubeseditve anketnih vprašanj. Piše za blog Udomačena statistika. Na Twitterju je @aslavec.

 

Opomba: Zapis je bil izvorno objavljen na blogu Udomačena statistika.

 

Več od Metina lista

Ko mati država odpove

Avtor: Marko Vrtovec, izvršni direktor Fundacije Univerze v Novi Gorici Dobrodelnost v...
Beri dalje