Lámání šifer: Už jen krůček k univerzálnímu počítači

Lámání šifer: Už jen krůček k univerzálnímu počítači – OBSAH

1. Zdánlivě neprolomitelný kód
2. Návrh univerzálního počítače pro prolomení Lorenzovy šifry
3. Turingův stroj – co je a co není?

Zdánlivě neprolomitelný kód

Jméno geniálního britského matematika Alana Turinga je pevně spojeno s prolomením německé šifry Enigma. Šlo o mimořádný výkon, ale je nutno říci, že Turing šifru nelámal sám – základy přinesli polští kryptoanalytici, jako byl matematik Marian Rejewski, který rekonstruoval principy funkce Enigmy a v roce 1938 navrhl lámací zařízení, „kryptologickou bombu“ spolu s Henrykem Zygalskim, který objevil první z technik zrychlující lámání šifer. V červenci 1939 se o toto tajemství podělili s Francouzi a potom s Brity.

Turing navrhoval metody, jak zrychlit hledání klíče – a jeho „Bomba“ vycházela jak z polských principů, tak z jeho vlastních myšlenek. Nešlo o univerzální počítač, bylo to stále specializované zařízení, jehož hlavním úkolem bylo ze zachycených zpráv odvodit platný denní klíč. Enigma totiž šifrovala i dešifrovala symetricky – pokud se jí Spojenci zmocnili, mohli dekódovat německé zprávy, pokud měli správný denní klíč, což byl problém, protože ten Němci každý den měnili. Hlavní problém s Enigmou tedy nebyl v tom, že by se nevědělo, jak funguje, ale šlo o to rozlomit klíče rychle, aby se daly číst zprávy včas. Také se musela lámat opakovaně, protože během války Němci zvýšili složitost šifrování.

Návrh univerzálního počítače pro prolomení Lorenzovy šifry

K univerzálním počítačům nás nedovedla ani Enigma, ani Bomba, ale snaha o prolomení jiné a složitější šifry – Lorenzovy šifry. Byl to komplikovanější systém, který používal Hitler a nejvyšší velení – a šlo o systém tak efektivní, že byla odtajněna až v roce 2002! Lorenzovy šifru prolomil Bill Tutte – a to zcela teoreticky, aniž by kdy viděl stroj pro její šifrování. Pro lámání Lorenzovy šifry byly mezi lety 1943 a 1945 vytvořeny stroje Colossus – celkem vzniklo dvanáct strojů, které sice ještě neměly operační paměť tak, jak ji známe dnes, ale pracovaly se vstupní a výstupní děrnou páskou a už dost připomínaly skutečné počítače. Turingovi se občas připisuje i práce na Colossu, ale šlo o nezávislý směr kryptoanalýzy, kde oba týmy sdílely spíše jen společné koncepty a myšlenky.

Z hlediska dějin výpočetní techniky je významnější Turingova revoluční práce z roku 1936 „On Computable Numbers, with an Application to the Entscheidungsproblem“, která se týká tak zvaného rozhodovacího problému, tedy schopnosti v konečném čase určit, zda je nějaký logický výrok univerzálně platný, tedy zda se dá v konečném počtu kroků dokázat logickým vyvozováním. Turing navrhl stroj, který byl tento problém schopen řešit – a zároveň dokázal, že existují problémy, které rozhodnout nedokáže.

Turingův stroj – co je a co není?

Jeho myšlenkový model, Turingův stroj, není skutečný počítač, je to jenom jeho model. Do značné míry je to ale standardní model klasického univerzálního počítače: Každý počítač, který dokáže řešit ty samé úlohy, co jeho abstraktní model, se nazývá turingovsky úplný (Turing-complete). Je to etalon výpočetní síly, protože pokud dokážete, že vámi navržený počítač je turingovsky úplný, přesně víte, které třídy úloh vyřešit dokáže a které už vyřešit nezvládne.

Turingův stroj v žádném muzeu nenajdete, protože to je jenom myšlenkový koncept. Jeho model ale najdete například postavený z redstone v Minecraftu – a prakticky každý moderní stroj, který před vámi stojí, je turingovsky úplný. Geniální matematický model tak vlastně není nikde – a přesto je všude.

V souvislosti se vzestupem umělé inteligence je třeba ještě zmínit vyhlášený Turingův test. Měřit inteligenci je složité – a proto Turing navrhl test, který má mít schopnost rozeznat, zda je zařízení inteligentní, nebo ne: Testující osoba sedí u terminálu a komunikuje přes něj, přičemž neví, zda je na druhé straně počítač, nebo člověk. Pokud to není schopna rozeznat, prošel stroj Turingovým testem. Dnes mu také říkáme emulační test, protože počítač emuluje lidskou komunikaci. Dnes to jde chatovacím umělým inteligencím tak dobře, že se Turingův test považuje za překonaný – a hledají se jiné metriky, jak měřit schopnosti umělé inteligence, například se nechá řešit standardizované testy pro studenty a porovnává se s nimi.

Alan Turing byl nepochybně jedním z nejvýznamnějších matematiků 20. století, jehož práce zásadně ovlivnila nejen vývoj moderní kryptografie, ale také základy teoretické informatiky a umělé inteligence. Ačkoli jeho přínos k prolomení šifry Enigma byl neocenitelný, nelze zapomínat na předchozí úsilí polských kryptoanalytiků, kteří připravili půdu pro Turingovy inovace. Jeho koncept Turingova stroje položil teoretické základy pro dnešní univerzální počítače, a jeho Turingův test i nadále zůstává významným bodem diskusí o povaze inteligence počítačů.

Michal Rybka

Michal Rybka je publicista a nadšenec s 20 lety zkušeností v IT a gamingu. Je kurátorem AlzaMuzea a YouTube kanálu AlzaTech. Napsal několik fantasy a sci-fi povídek, které vyšly v knižní podobě, a pravidelně pokrývá páteční obsah na internetovém magazínu PCTuning.