27. septembra 2020
História šifrovania od Cézara po súčasnosť

Enigma, časť 1/3: Ako prekabátiť Evu

Začiatok z trojdielnej série, v rámci ktorej sa dozviete ako fungujú šifry, v čom bola Enigma geniálna, prečo bola v druhej svetovej vojne kľúčová a ako sa ju podarilo prelomiť.

Ako sa ľudská spoločnosť stávala komplexnejšou a informácie sa stávali dôležitou komoditou, objavila sa aj snaha informácie skrývať. Spolu s ňou aj snaha skryté informácie odhaľovať. Poháňaný prvou motiváciou si v roku 1918 vynálezca Arthur Scherbius patentoval prístroj na mechanické šifrovanie správ, Enigmu (z gréckeho slova znamenajúceho hádanka). Predpokladal, že to bude hit pre súkromníkov aj pre vlády. Spočiatku nebol, avšak nemecká armáda si postupne uvedomila prednosti strojového šifrovania a vo veľkom nakúpila Enigmu v armádnej verzii (o niečo sofistikovanejšiu ako civilná verzia). Enigma sa stala postupne stala štandardom a väčšina nemeckej vojenskej šifrovanej komunikácie prechádzala cez ňu.

Ako fungovala Enigma, že si zaslúžila takú dôveru?

Začneme zoširoka a na pomoc si prizveme tradičných hrdinov kryptografických príbehov, Alicu, Boba a Evu. Alica chce poslať tajnú správu Bobovi, ale zlá Eva (a anglického eavesdropper) by si ju rada prečítala. Ak by Alica a Bob žili v antike, použili by jednoduchý abecedný posun, napríklad o jedno písmeno (spopularizovaný Cézarom a preto nazývaný Cézarova šifra). Predpokladajme, že text tajnej správy je VEDÁTOR (ako je zvykom, odmyslíme si diakritické znamienka). Alica svoju správu zašifruje jednoducho:

VEDATOR
+
1111111
——-
WFEBUPS

Vyskúšať posun by zrejme napadlo väčšine moderných ľudí, avšak bez databázy šifier v ľudskej kolektívnej pamäti mohlo v staroveku fungovať aj takéto naivné šifrovanie.

O niečo sofistikovanejšie je použiť iný posun ako 1 (samotný Cézar používal posun -3), avšak priemerne odhodlaná Eva nemá problém vyskúšať všetkých 25 možností. Alebo, ak sa chce hrať na chytrú, nemusí skúšať všetky možnosti. Písmená abecedy si nie sú rovné, niektoré sa v texte vyskytujú častejšie ako iné (napríklad v slovenčine sú najčastejšie A, O a E, v angličtine E, T, A,…) [1]. Ak si teda nakreslí grafu početnosti písmen, ľahko uhádne posun. Dodajme, že táto metóda funguje aj keby Alica namiesto posunu použila poprehadzovanú abecedu (napr. F namiesto A, Y namiesto B,…) alebo si vymyslela nejaké nové znaky pre písmená.

Vráťme sa ale k posunom. Nasledujúci krok je použiť viacero posunov. Napríklad prvé písmeno sa posunie o 4, druhé o 7, tretie opäť o 4 a tak ďalej:

VEDATOR
+
4747474
——-
ZLHHXVV

Ak má Eva dostatočnú motiváciu a k dispozícii dlhšiu správu, nezastaví ju ani toto. Môže si totiž znovu spraviť graf početnosti písmen, ale použije iba každé druhé, každé tretie… písmeno. Keď dostane početnosti zodpovedajúce výskytu písmen v danom jazyku, uhádla dĺžku hesla a aj jednotlivé posuny (vlastne, takto môže odhaliť aj jazyk, ak ho nevedela vopred).

Už dosť napálení z neustálych neúspechov použijú Alica a Bob pre každé písmeno nejaký iný, náhodný posun. Napríklad:

VEDATOR
+
3141592
——-
YFHBYXT

A vyhrali.

Moment, čože?

Áno, ak je kľúč tak dlhý ako správa, generovaný naozaj náhodne a použitý len raz, Eva nemá šancu. Dokázateľné matematicky – QED. Pri splnení týchto podmienok Alica a Bob nenechali žiadny záchytný bod, žiadnu pravidelnosť, ktorú by Eva mohla využiť. Každý hypotetický text dešifrovanej správy je rovnako pravdepodobný, medzi posunmi pre jednotlivé písmená nie je žiadny vzťah.

Problém je, že splniť tieto podmienky v reálnej situácii je ťažké. Treba naozajstný generátor náhodných čísel [2]. Kľúče treba generovať rýchlo alebo ich mať predpripravené. To je ťažké pri frekventovanej komunikácii alebo dlhých správach, napríklad ak je cieľom v reálnom čase koordinovať armádu bojujúcu na viacerých frontoch. No a na záver, Alica musí okrem správy Bobovi bezpečne doručiť aj kľúč tak, aby ho nedostala Eva. Dodajme, že ani počítače nepriniesli riešenie. Urýchlili síce zašifrovanie a odšifrovanie, ale tiež zväčšili množstvo dát, ktoré chceme utajiť. Na zaheslovanie terabajtového disku treba terabajtový kľúč. Tieto ťažkosti spôsobujú, že uvedená metóda šifrovania (nazývaná aj Vernamova šifra alebo šifra s jednorazovým kľúčom, anglicky ‘one-time pad‘) sa používa len zriedkavo.

Akýmsi kompromisom medzi absolútnou bezpečnosťou a jednoduchou prevádzkou je pseudonáhodné generovanie kľúča. To bolo použité aj v príklade uvedenom vyššie. Ako kľúč sa použili cifry čísla π (pí). Ak teda chcem [Samuelovi] poslať text nového príspevku pre Vedátora, nemusím mu posielať aj rovnako dlhý kľúč. Stačí, keď sme sa raz dohodli, že budeme kľúč generovať z desatinného rozvoja čísla π a raz sme si vymenili zoznam čísel hovoriacich, na ktorom desatinnom mieste začneme. [Samuel] teda dostane šifrovanú správu, podľa dohody zistí, že pre dnešný deň sme sa dohodli začať na 2702. desatinnom mieste, tak si vygeneruje číslo π a začne čítať. [3]

Enigma pracuje na analogickom princípe. Je to skrinka, ktorá po nastavení krátkym heslom začne generovať kľúč a šifrovať ním dlhú správu. Všetko prebieha automaticky, odosielateľ správy iba píše a ako výstup dostáva hatlaninu. Príjemca si nastaví svoju Enigmu rovnakým heslom, zadáva hatlaninu a dostáva pôvodnú správu. [4] [Lukáš]

Pokračuje v druhej časti.

PS: Keď budete niekoho chcieť informovať o Vedátorovi, pokojne to šírte verejne, žiadne utajovanie nie je nutné!

PS2: To je prvý článok z krátkej série o šifrovaní, na ďalší sa môžete tešiť čoskoro.

– – –

Poznámky:
[1] Frekvencie písmen: https://en.wikipedia.org/wiki/Letter_frequency

[2] Kvantové šifrovanie je založené na tomto princípe, pretože kvantová mechanika dovoľuje generovať naozaj náhodné čísla a navyše poskytuje aj spôsob, ako si ich posielať a zistiť, či ich niekto cestou nečítal.

[3] Toto šifrovanie je v skutočnosti slabé, dovolené posuny sú iba od 0 a 9 (takže Eva vie, že napríklad A sa nikdy nezašifruje na X), použitý pseudonáhodný generátor je ľahko dostupný …

[4] Takýto typ šifrovania sa odborne nazýva symetrická prúdová šifra (symmetric stream cipher). Prúdová, lebo generuje kľúč za behu a symetrická, lebo na zašifrovanie a odšifrovanie sa používa to isté nastavenie. Opakom sú asymetrické šifry, ako napríklad šifry s verejným a súkromným kľúčom.

3 thoughts on “Enigma, časť 1/3: Ako prekabátiť Evu

  1. Spätné upozornenie: Enigma, vojenská vsuvka - Vedátor

Pridaj komentár