Historie šifrování: Od Sparťanů po současnost

Když 8. června 2021 skončila operace Trojan Shield, výsledky byly ohromující: v 16 zemích bylo provedeno přes 800 zatčení a zabaveno téměř 40 tun drog, spolu s 250 zbraněmi, 55 luxusními vozy a více než 48 miliony dolarů v měnách a kryptoměnách. Jak to souvisí s kryptografií (šifrováním)? Na to se podíváme v tomto článku.

Pozadí

Jádrem této akce – jedné z největších svého druhu – byla proprietární aplikace pro zasílání zpráv s názvem ANOM. Aplikace, propagovaná jako bezpečná komunikační platforma založená na šifrování, nabízela funkce nad rámec běžných zařízení, jako například možnost vzdáleně vymazat všechny zprávy a data ze zachyceného telefonu, čímž efektivně zničila všechny usvědčující důkazy.

Problémem pro uživatele bylo, že ANOM provozovala FBI. Jeho mechanismy ochrany soukromí byly jen fasádou: Veškerá komunikace byla kopírována a předávána zúčastněným vládním agenturám. Podle Europolu, agentury EU pro vymáhání práva, bylo shromážděno 27 milionů zpráv z více než 100 zemí.

Tato iluze tajemství a soukromí v komunikaci odráží hlubší roli kryptografie v našem moderním digitálním světě. Operace zdůrazňuje jak sílu, tak zranitelnost šifrování, které je po staletí ústředním bodem zabezpečení komunikace. Ano, staletí. Kryptografie, umění kódování a dekódování tajemství, sahá až do starověkého Řecka.

Samotný termín pochází z řeckého slova pro „skryté písmo“ a jeho původ sahá až ke Sparťanům. Podle historiků používali nástroj zvaný „scytale“ nebo „skytale“ (z řeckého σκυτάλη, což znamená obušek nebo válec) ke skrytí svých zpráv. Nástroj se skládal z tyče, kolem které byl navinut proužek kůže nebo pergamenu. Zpráva byla na proužek napsána po navinutí na tyč a poté odeslána bez ní. K přečtení zprávy by příjemce potřeboval scytalu stejného tvaru. To mu mělo umožnit, správně text rozkódovat.

Římané

O Juliu Caesarovi napsal jeho soudobý historik Suetonius následující:

“Pokud měl cokoli důvěrného sdělit, psal to šifrovaně, to znamená, že změnil pořadí písmen abecedy tak, že nebylo možné rozluštit ani slovo. Pokud si někdo přeje tyto texty rozluštit a pochopit jejich význam, musí nahradit A čtvrtým písmenem abecedy, konkrétně D, a tak dále s ostatními.”

Suetonius popisoval Caesarovu šifru, typ substituční šifry, což znamená, že funguje tak, že písmena abecedy se nahrazují jinými písmeny abecedy. K přečtení zprávy zašifrované Caesarovou šifrou potřebujete znát klíč – počet pozic, o které bylo každé písmeno posunuto (ve výše uvedeném případě čtyři). Pokud klíč neznáte, můžete vyzkoušet různé klíče, dokud nenajdete ten správný. Nanejvýš byste museli vyzkoušet 25 dalších různých posunů (dle písmen abecedy).

Lepší možností by mohlo být zamíchat písmena abecedy a rozhodnout se nahradit například D za A, C za B atd. K dešifrování této zprávy bychom potřebovali pouze mapovací tabulku. Dalo by se pokusit vyzkoušet všechny možné mapovací tabulky, ale rychle by se to ukázalo jako marné. Existuje více než 400 septilionů různých mapovacích tabulek – číslo s 27 desetinnými místy.

Počátky dešifrování

Základní dešifrovací metoda – a účinnější – se nazývá frekvenční analýza, kterou poprvé popsal arabský učenec a vědec z devátého století Abu Yūsuf (801–873). Všechny jazyky mají své pravidelnosti a ve všech jazycích se písmena objevují s určitou pravděpodobností. V angličtině je nejčastějším písmenem E; druhým nejčastějším je T; nejméně častým písmenem je Z. Nejčastějším symbolem v zašifrovaném textu je tedy pravděpodobně E. Druhým nejčastějším symbolem je pravděpodobně T. A tak dále. To znamená, že s trochou počítání a trochou hádání můžeme obejít hrubou sílu a zprávu dešifrovat.

Tato hra na kočku a myš definovala kryptografii po staletí. Kryptografická metoda je vynalezena a považována za bezpečnou, jen aby ji později prolomil útok. Po nějaké době je vynalezena lepší metoda, která je považována za nezranitelnou vůči známým útokům. A cyklus pokračuje.

Tento vývoj kryptografických technik vedl k vývoji stále sofistikovanějších metod. Jedním z takových pokroků je přechod od monoalfabetických šifer, jako je výše popsaná substituční šifra, k polyalfabetickým šifrám, které používají více substitučních pravidel k posílení šifrování.

Pro zašifrování zprávy pomocí polyalfabetické šifry nepoužíváme jednu, ale několik mapovacích tabů.šifry. První písmeno zašifrujeme pomocí první mapovací tabulky, druhé pomocí druhé mapovací tabulky a tak dále, až do poslední mapovací tabulky. Pak tabulky znovu procházíme. Pokud se mapování změní, pak stejné písmeno nebude vždy zašifrováno stejným způsobem. V určitém bodě zprávy může být A namapováno na K, v jiné části na X. To znamená, že přímá frekvenční analýza nebude fungovat.

Příklady

Vyvinutá polyalfabetická šifra, Vigenèrova šifra, pojmenovaná po Blaise de Vigenère (1523–1596), ve skutečnosti vynalezená Giovanem Battistou Bellasem v roce 1553), zůstala neprolomena po tři století až do roku 1863. Stala se známou jako „nerozluštitelná šifra“. Vigenèrovu šifru nakonec prolomil německý pěchotní důstojník, kryptograf a archeolog Friedrich Kasiski, který si uvědomil, že frekvenční analýzu lze aplikovat identifikací počtu různých použitých mapování. To umožňuje samostatnou analýzu segmentů zpráv zašifrovaných stejným mapováním.

Vrcholem hry na kočku a myš v klasické kryptografii však byl stroj Enigma, který Němci používali ve druhé světové válce. Enigma byla impozantní polyalfabetická šifra. Trvalo roky úsilí polských a britských kryptoanalytiků a geniality průkopníka informatiky Alana Turinga, než ji prolomili. Příběh se stal tématem tradic. Enigma byla zlomovým bodem. Kryptoanalýzu prováděli matematici, nikoli lingvisté ani nadšenci do luštění hlavolamů. Aby Alan Turing prolomil šifrování Enigmy, navrhl další stroj s názvem Bombe, který je nyní pečlivě rekonstruován v Bletchley Parku, kde byl původně postaven během války. K prolomení stroje byl zapotřebí stroj.

Dnešní základ

Šifrou, která je dnes základem velké části naší digitální infrastruktury, je Advanced Encryption Standard (AES), vyvinutá belgickými kryptografy Joanem Daemenem a Vincentem Rijmenem. AES funguje na principu opakovaného nahrazování a permutace znaků v textu s využitím matematických principů, zejména teorie čísel, což je odvětví matematiky, které se zabývá studiem celých čísel.

Bez správného klíče je dešifrování zprávy šifrované pomocí AES prakticky nemožné. Jako symetrická šifra používá AES stejný klíč pro šifrování a dešifrování jako ostatní šifry, o kterých jsme diskutovali. Tato symetrie však představuje problém. Odesílatel a příjemce si musí vyměnit klíč a nemohou zašifrovat samotný klíč, protože by to vyžadovalo další klíč. Jak to tedy funguje?

Stručná historie metod tajné komunikace

V roce 1976 publikovali američtí kryptografové Whitfield Diffie a Martin Hellman článek, který navždy změnil kryptografii. V tomto článku popsali Diffie-Hellmanovu výměnu klíčů, metodu, která umožňuje dvěma stranám bezpečně se dohodnout na sdíleném klíči bez setkání nebo soukromé komunikace.

Existuje populární a užitečná analogie, která nahrazuje matematiku barvami, aby ilustrovala, jak funguje Diffie-Hellmanova výměna klíčů. Předpokládejme, že se Alice a Bob dohodnou na společné základní barvě, řekněme žluté. Každý si samostatně vybere tajnou směs barev a namícháje tak, aby vzešla žlutá. Alice pošle svůj výtvor Bobovi a Bob Alici. Po obdržení směsi toho druhého si každý přidá svou vlastní tajnou barvu. Tato finální směs vede ke stejnému odstínu pro Alici i Boba. Třetí strana by znala informaci o žluté barvě, ale nebyla by schopna docílit „jejich“ žluté, protože nezná směs barev.

Ve skutečnosti Diffie-Hellmanova šifra nepoužívá barvy, ale velká čísla. Její bezpečnost závisí na tom, jak obtížné je proces obrátit. Stejně jako nelze snadno oddělit barvy po smíchání, ani odposlouchávač nemůže proveditelně vypočítat sdílený tajný klíč bez znalosti soukromých čísel. Alespoň to si kryptografové myslí. Matematicky nebylo prokázáno, že není možné klíč odvodit (jako rozmícháním barev). To by vyžadovalo řešení tzv. problému diskrétního logaritmu.

Další průlomy

Další průlom nastal v roce 1978, kdy tři vědci, Ron Rivest, Adi Shamir a Leonard Adleman, vytvořili kryptosystém, který nazvali RSA (kombinací prvních iniciál všech jejich příjmení), a zavedli tak veřejný klíč. V kryptosystému s veřejným klíčem existuje jeden veřejný klíč a jeden odpovídající soukromý klíč. Veřejný klíč můžeme použít k zašifrování zprávy, kterou pak lze dešifrovat pouze soukromým klíčem.

Protože veřejný klíč není tajný, pokud chce Alice poslat Bobovi tajnou zprávu, získá jeho veřejný klíč přes jakýkoli vhodný veřejný kanál a poté zprávu zašifruje. Bezpečnost šifrování RSA závisí na obtížnosti rozkladu celého čísla na součin menších, nedělitelných částí, konkrétně prvočísel. Například 60 = 2 x 2 x 3 x 5. Tento proces, známý jako celočíselná faktorizace, nelze provést rychle pro velká čísla. V kryptografii se užívají skutečné vysoká čísla.

Kromě šifrování zpráv nám kryptografie s veřejným klíčem umožňuje vytvářet digitální podpisy. Pokud Alice zašifruje zprávu svým soukromým klíčem, pak ji může dešifrovat pouze někdo s jejím veřejným klíčem. To zajišťuje autenticitu, protože pouze Alice mohla zprávu zašifrovat pomocí svého soukromého klíče.

Hra na kočku a myš samozřejmě zdaleka nekončí. Kryptografie dnes čelí hrozící výzvě: kvantovým výpočtům. Kvantové počítače, až se stanou praktickými, by mohly řešit určité problémy mnohem rychleji než dnešní stroje, což by znemožnilo zabezpečení systémů RSA, Diffie-Hellman a dalších.

Budoucí výzvy

Kvantové výpočty tu ještě nejsou; kvantové počítače jsou sice postaveny, ale ještě nedosáhly velikosti a schopností, aby ohrozily naše kryptografické nástroje. To ale neznamená, že kryptografové nečinně pracují. Začaly práce na postkvantové kryptografii, tedy kryptografických metodách, které, pokud víme, budou nezranitelné vůči útokům kvantových počítačů. Postkvantová kryptografie si klade za cíl nejen chránit naše soukromí v budoucnosti s kvantovými počítači, ale také chránit dnešní data.

Představte si například scénář, kdy někdo ukládá naši aktuální komunikaci s úmyslem ji dešifrovat, až budou kvantové počítače k ​​dispozici. Tato taktika, známá jako „ulož nyní, dešifruj později“, hrozí ohrožením tajemství, která musí zůstat soukromá jak v krátkodobém, tak i dlouhodobém horizontu.

V duchu otevřenosti, který vedl k vývoji AES, je vývoj postkvantové kryptografie otevřeným procesem. Vývoj kryptografie je koneckonců neustálým cyklem průlomů a neúspěchů, který snad nejlépe vystihuje výrok irského dramatika Samuela Becketta: „Zkus to znovu. Znovu selži. Selži lépe.“

SIMPSON, B. History of Cryptography.

NOVOTNÝ, E.  Co je kódování a dekódování: Jak na to?

KOLÍNSKÝ, M. Princip římského šifrování.