Home osobnost <strong>Charles Babbage a Vigenèrova šifra</strong>

Charles Babbage a Vigenèrova šifra

0
<strong>Charles Babbage a Vigenèrova šifra</strong>

DHBSLKW CACCAMI B VJHETISOWB SOJSA

Kdo byl Charles Babbage?

Charles Babbage byl ve své době považován za originálního myslitele (Gleick, 2013, s. 68), jeho skutečným zájmem nebyly pouze přísně matematické postupy, ale oblasti zabývající se informacemi, jejich odesíláním, kódováním, analýzou a zpracováním. Pro své výzkumy a vynálezy dokázal vytvářet „jazyk symbolů, do kterých by se dalo kódovat řešení“ (Gleick, 2013, s. 94). Jeho osobitost dokládá mj. fakt, že proces kódování informací dokázal vnímat z jakéhokoliv reálného prostředí – všiml si jako první, že letokruhy stromů lze považovat za důkaz toho, jakým způsobem „kóduje“ příroda zprávy o minulosti (Gleick, 2013, s. 102). Ve svých poznámkách Babbage podotkl: „Hlavním cílem všech mých bádání bylo úsilí rozpoznat takové zákony myšlení, díky nimž člověk činí objevy“ (překlad vlastní) (Franksen, 1985, s. 119). Nebyl jen matematikem, vědcem a vynálezcem, svou energii efektivně uplatnil i v kryptologii a kryptoanalýze, byl také prvním známým člověkem, který rozluštil Vigenèrovu šifru (Cimino, 2018, s. 47). Článek se v historické rovině obecně zaměřuje nejen na život a zásadní dílo Charlese Babbage, ale právě na jeho vztah k šifrování.

Matematický génius Charles Babbage

Zajímavou postavou kryptoanalýzy byl pro období 19. století bezesporu britský matematický génius Charles Babbage, který se proslavil zejména koncepčním návrhem moderního počítače. Narodil se 26. prosince 1791 v Londýně v bohaté rodině, jeho otec byl londýnský bankéř Benjamin Babbage. O možnost přístupu k rodinnému majetku Charles přišel ve chvíli, kdy se proti otcově vůli oženil, i nadále ale zůstal dostatečně finančně zabezpečen a mohl se jako nezávislý vědec věnovat svým badatelským zájmům (Singh, 2009, s. 72). Vedle technických zařízení, která ho proslavila, byl autorem i dalších vylepšení, objevů a vynálezů – např. vynalezl rychloměr, lapač krav (zařízení připevněné na železniční lokomotivu určené pro odhánění dobytka z kolejí), zmodernizoval poštovní systém a světelný systém vysílající kódované signály, sestavil první tabulky úmrtnosti využívané v pojišťovnictví, sestrojil malou kalkulačku (Cimino, 2018, s. 47; Gleick, 2013, s. 102; Houser, 2003). V roce 1821 se Babbage spolu s astronomem Johnem Herschelem zabýval matematickými tabulkami používanými při technických, navigačních a astronomických výpočtech. V ručně sestavovaných tabulkách Námořního almanachu našli velké množství chyb, které mohly být příčinou závažných nepřesností při výpočtech a následkem toho různých technických katastrof a ztroskotání lodí (tabulka Nautické efemeridy pro nalezení zeměpisné šířky a délky na moři obsahovala více než tisíc chyb). Babbage k tomu řekl: „Přeji si při Bohu, aby byly výpočty prováděny párou!“ (Cimino, 2018, s. 47). Věřil, že dokáže navrhnout a vytvořit stroj poháněný párou, který by zautomatizoval proces matematických výpočtů (Petzold, 2000). Cesta od myšlenky skutečně vedla k návrhu stroje, který by dokázal sestavovat výpočty v tabulkách bez chyb, a to až na dvacet desetinných míst. Vytvořený prototyp zapůsobil na Královskou společnost a Babbage tak získal od britské vlády finanční podporu na ostrou verzi svého Diferenčního stroje (Difference Engine). Na jeho sestrojení pracoval více než deset let, nikdy ho ale zcela nedokončil, od svého úsilí Babbage ustoupil v roce 1833. V průběhu let ovšem tento matematický génius začal pracovat i na „analytickém stroji“, u něhož byla předpokladem programovatelnost, a to pomocí děrných štítků. Ty byly upraveny z karet používaných v tkalcovských stavech firmy Joseph-Marie-Jacquard (Petzold, 2000). Stroj pro analýzu výpočetních operací byl konstruován ze čtyř částí, které lze nalézt u moderních počítačů – mill/mlýn (centrální procesor), store/úložiště (paměť), reader/čtenář (vstupní zařízení), printer/tiskárna (výstupní zařízení) (Holzheu, 2020, Wilde, c2022). V otázce programování byla Babbageovi velkou oporou hraběnka Augusta Ada Lovelace, známá nejen jako dcera anglického spisovatele G. G. Byrona, ale zejména jako nadaná matematička a první programátorka, která zevrubně popsala funkci Babbageova „analytického stroje“ a navrhla způsob, jak stroj pomocí děrných štítků programovat (Lihou, 2016). Zajímavostí je, že během druhé světové války se právě elektronická realizace Babbageova stroje zasloužila o jistý pokrok v kryptoanalýze. Již za svého života se ovšem Babbage výrazně přičinil o rozvoj této oblasti.

Kryptoanalytik Charles Babbage

Vedle vynálezů, plánování a sestrojování analytických a počítacích strojů se Babbage již od dětství zajímal o luštění různých forem šifer, teorii šifrování, otevírání zámků, analýzu magických čtverců a logických her (piškvorky, šachy). Ve své autobiografii mimo jiné napsal: „Prolamování šifer je jeden z nejúchvatnějších druhů umění, u něhož jsem promrhal více času, než by si zasloužilo.“ (Gleick, 2013, s. 102). V londýnské společnosti měl mezi svými současníky pro své odborné znalosti a zkušenosti pověst znamenitého kryptoanalytika. Dokázal mimo jiné rozluštit a přečíst těsnopis prvního anglického královského astronoma Johna Flamsteeda nebo zašifrované zápisky Henrietty Marie Bourbonské, manželky krále Karla I. Spolupracoval také na expertízách v právních případech (Franksen, 1985, s. 20–26). Kryptologie Babbage zaujala natolik, že se rozhodl realizovat celkovou analýzu angličtiny a vytvořit sady různě tematických frekvenčních slovníků a vše racionálně popsat (včetně četnosti výskytů dvojitých písmen). Vznikl tak návrh metodiky pro řešení různých hlavolamů a rébusů, jako křížovek a přesmyček, slova byla ve slovnících uspořádána podle počtu písmen, která obsahovala. Při dešifrování používal zejména mechanické pomůcky, jako jsou šifrovací disky a mechanické posuvníky (Franksen, 1985, s. 16, 2013).

Babbageův zájem o kryptologii a kryptoanalýzu brzy dospěl do sběratelské roviny, odhaduje se, že nejaktivnější byl při budování své sbírky mezi lety 1820 a 1830. Babbageova rozsáhlá knihovna obsahuje původní vydání děl v té době významných osobností matematických a fyzikálních věd i knihy o kryptografii (Franksen, 1985, s. 40–41). Zejména v letech 1818 až 1822 také vytvořil sérii matematických esejí, ovšem kromě jedné a části druhé eseje nebyly nikdy publikovány, přestože byly předloženy Cambridge Philosophical Society. V esejích se zabýval třemi matematickými tématy, jež jsou zvláště důležitá pro pochopení jeho práce v oboru kryptografie, jsou jimi notace (jediné téma, o němž publikoval), integrita zajišťující neměnnost dat a „nový způsob analýzy“, který se tehdy nazýval geometrie situace (Franksen, 1985, s. 59). Plánoval také sám vydat publikaci o šifrování The Philosophy of Decyphering (Filozofie dešifrování), na níž pracoval řadu let až do roku 1857. O tomto záměru svědčí rozsáhlá korespondence (Franksen, 1985, s. 34–39). Stejně jako sestavení „analytického stroje“, ani tento projekt se nepodařilo Babbegovi dokončit. (Cimino, 2018, s. 47; Houser, 2003).

Vigenèrova šifra

Vigenèrova šifra je historická polyalfabetická šifra, jejímž šifrovacím principem je periodické užití krátkého hesla (kratší, než je otevřený text) a cyklicky posunuté abecedy. Při šifrování dochází k přepínání mezi abecedami pomocí tohoto klíče. Hlavní výhodou Vigenèrovy šifry je eventualita zakódování stejného písmena abecedy více způsoby, a to podle délky klíče. Systém je připisován francouzskému diplomatovi Blaise de Vigenèrovi (Singh, 2009, s. 75). Jde o jednu z nejsložitějších šifer, které byly vymyšlené, a je možné ji stále užívat. Dlouhou dobu se šifru nedařilo prolomit a začalo se jí říkat le chiffre indéchiffrable – nerozluštitelná šifra (Cimino, 2018, s. 39–40, 205). Pro její použití je nutné pracovat s tabulkou Vigenèrova čtverce (tzv. Tabula rectaObr. 1) (Ivánek, 2022), která má 26 písmen v řádku a 26 písmen ve sloupci.

Obr. 1 Vigenèrův čtverec (zdroj: Ivánek, 2022)  

Celý systém funguje tak, že odesílatel předává šifrovanou zprávu příjemci, který musí znát daný klíč. Tím může být určité slovo, věta, ale i jen shluk náhodných písmen. Klíčové slovo pak při šifrování určují řádky, původní slovo text sloupce. Jako příklad šifrovaného textu je uveden Obr. 2.

Obr. 2  Příklad šifrování textu (zdroj: autorka, MS Excel)  

Platí také pravidlo, že čím delší je klíč, tím je šifra složitější. Cyklický posun abecedy při práci s výše zmiňovanou tabulkou je důvodem toho, že při dešifrování textu a hledání klíče není možné užít jednoduchou frekvenční analýzu, ale je třeba přistupovat k ní postupně v jednotlivých krocích, což vysvětluje Cimino (2018, s. 49): „[…] v textu zašifrovaném Vigenèrovou šifrou se často opakují určité posloupnosti písmen. Vzdálenost těchto delších opakování je většinou násobkem délky hesla, protože jde převážně o opakování v otevřeném textu. Na základě takových delších opakování můžeme zjistit délku hesla. […] Polyalfabetická šifra vytvořená pomocí Vigenèrova čtverce je tedy ve skutečnosti několik periodicky se opakujících monoalfabetických záměn a každou z nich lze prolomit pomocí frekvenční analýzy.“

Kryptoanalýza Vigenèrovy šifry probíhá ve dvou krocích. Prvním z nich je hledání periody, které je založeno na „analýze koincidencí v šifrovaném textu a/nebo analýze odstupu stejných posloupností v šifrovaném textu“ (Jiroušek, 2006, s. 245). Následně se provádí frekvenční kryptoanalýza – v tomto případě je nutné u pravděpodobnosti výskytu písmen v rámci frekvenční analýzy pamatovat na užitý jazyk šifrovaného textu (Jiroušek, 2006, 245–246).

V roce 1854 zřejmě jako první šifru rozluštil právě Charles Babbage, který ovšem svůj postup dešifrování „nerozluštitelné šifry“ nezveřejnil. Zhruba o deset let později (1863) prolomil šifru pruský důstojník Friedrich Wilhelm Kasinski, a to pomocí kryptoanalýzy při hledání periodické posloupnosti písmen v šifrovaném textu, kdy je třeba si všímat sekvencí alespoň 3 znaků a určit jejich společného dělitele (tzv. Kasinskiho metoda) (Ivánek, 2022). Cimino (2018, s. 43) uvádí domněnku, že ač šlo v tomto případě o šifru s vysokou funkčností, co se bezpečnosti týče, nebyla ve své době příliš využívána, a to zejména z toho důvodu, že dešifrování „vyžadovalo čas a úsilí a v bitvě je zásadní věc rychlost“. Nicméně v době, kdy byla Vigenèrova šifra Babbagem a Kasinskim prolomena, již nebyla dostatečně bezpečná, protože kryptoanalýzou bylo možné získat důvěrnou zprávu. Kryptografové se v té době snažili konstruovat nové šifry, což se nedařilo, a v profesionální oblasti došlo k úpadku. Naopak se zvýšil zájem o luštění šifer mezi laickou veřejností. (Singh, 2009, s. 85).

Charles Babbage a Vigenèrova šifra

Jak již bylo zmíněno, Babbage byl velkým příznivcem kryptologie. V 19. století se hojně využíval elektrický telegraf, díky němuž bylo možné odesílat a přijímat zprávy Morseovou abecedou. Ovšem každý, kdo systém znal, mohl zprávy rozkódovat. Veřejný zájem se proto obrátil k možnosti využít šifrování pomocí známých či nových šifer. V popředí zájmu stála také Vigenèrova šifra, již se snažila řada odborníků prolomit už od jejího vzniku (Cimino, 2018, s. 47). V roce 1854 se to podařilo právě Babbageovi, který ovšem, zřejmě z důvodů bezpečnosti státu, princip šifry veřejně nevysvětlil a nepublikoval. O tom, že šifru prolomil, svědčí veřejná debata Babbage s bristolským zubařem Johnem Hallem Brock Thwaitesem v Journal of the Society of Arts (List společnosti nauk) (Franksen, 1985, s. 20; Singh, 2009, s. 75), který v té době veřejnosti ohlásil novou šifru. Ta ale byla dle Babbage pouze obdobou Vigenèrovy šifry, což také doložil prolomením Thwaitesova textu. Tento veřejný spor je zřejmě nejdůležitějším zdrojovým dokumentem o Babbageově práci v oboru kryptoanalýzy a svědectvím o jeho profesionálních dovednostech a schopnostech v oblasti kryptografie (Franksen, 1985, s. 17, 251–263). Babbageův způsob prolomení šifry pomocí jeho charakteristického matematického přístupu ke kryptografii vyšel najevo až ve 20. století při studiu písemných poznámek. Z nich bylo zřejmé, že pro kryptoanalýzu zjevně použil stejnou metodu, kterou v roce 1863 vyvinul Kasinski (Cimino, 2018, s. 48–49).

Originální myslitel a jeho odkaz

Britský matematik Charles Babbage zemřel 18. října 1871 v Londýně. Nekrolog v Timesech oznamoval úmrtí „originálního myslitele, který byl jedním z nejaktivnějších a nejoriginálnějších“ (Gleick, 2013, s. 68). Pohled Gleicka (2013, s. 68) na osobnost Charlese Babbage, „který příliš nezapadal do své doby“, je poněkud kontroverzní. Babbage je na jedné straně vnímán jako velký myslitel, zejména v oblasti matematických věd, strůjce moderního stroje, vynálezce. Druhá jeho stránka je popisována méně pozitivně – Gleick vzpomíná jeho nezdary s dokončením projektů, na nichž pracoval. V kronice vynálezů zaujímá nepříliš příznivé místo nedokončený Diferenční stroj a „analytický stroj“, zároveň je v pramenech upozorňováno na nepublikovanou knihu o filozofii šifrování. Tyto pomyslné nezdary Babbageova života je možné vnímat jako nepatrný zlomek v poměru k odkazu, který Babbage zanechal dalším generacím v oblasti matematické a informační vědy, ale i ve filozofických otázkách, kryptologii a kryptoanalýze.

Použitá literatura

CIMINO, Al, 2018. Příběh kryptologie: od starověkých šifer po kvantovou kryptografii. Praha: Dobrovský. Knihy Omega. ISBN 978-80-7390-887-4. Dostupné v KUK.

FRANKSEN, Ole Immanuel, 1985. Mr. Babbage‘s secret: the tale of a cypher – and APL. New Jersey: Prentice-Hall, Inc., Englewood Cliffs. ISBN 0-13-604729-7. Dostupné také z: https://archive.org/details/mrbabbagessecret0000fran

GLEICK, James, 2013. Informace: historie, teorie, záplava. Praha: Dokořán. Zip.
ISBN 978-80-7363-415-5. Dostupné v KUK.

HOLZHEU, Michael, 2020. Charles Babbage’s analytical engine. In: Youtube [online].
6. 3. 2020 [cit. 2022-11-27]. Dostupné z: https://www.youtube.com/watch?v=eMy4vSZ-J_I

HOUSER, Pavel, 2003. Charles Babbage: nejen parní počítač, ale také luštění šifer.
In: Science World [online]. 30. 4. 2003 [cit. 2022-11-27]. Dostupné z: https://www.scienceworld.cz/neziva-priroda/charles-babbage-nejen-parni-pocitac-ale-take-lusteni-sifer-3069/

HYMAN, Anthony, ed., 1989. Science and reform: selected works of Charles Babbage. Cambridge: Cambridge University Press. Dostupné také z: https://archive.org/details/sciencereformsel0000babb/mode/2up. Úvodní obrázek.

IVÁNEK, Jiří, 2022. Teorie kódování a šifrování: klasické substituční šifry. In: Moodle UK pro výuku 1 [online]. 2022 [cit. 2022-11-28]. Dostupné z: https://dl1.cuni.cz/pluginfile.php/1476239/mod_resource/content/0/Klasick%C3%A9%20substitu%C4%8Dn%C3%AD%20%C5%A1ifry.pdf. Prezentace v rámci výuky předmětu Kódování informací 2022/2023, přístup omezen pro přihlášené účastníky.

JIROUŠEK, Radim, 2006. Principy digitální komunikace. Voznice: Leda.
ISBN 80-7335-084-X.

LIHOU, Jason, 2016. Charles Babbage. In: Youtube [online]. 23. 8. 2016 [cit. 2022-11-27]. Dostupné z: https://www.youtube.com/watch?v=NSAXbsbiid0

PETZOLD, Charles, 2000. Code: the hidden language of computer hardware and software. Redmond: Microsoft Press. ISBN 978-0-7356-1131-3.

SINGH, Simon, 2009. Kniha kódů a šifer: tajná komunikace od starého Egypta po kvantovou kryptografii. 2. vyd. v českém jazyce. Praha: Dokořán. Aliter. ISBN 978-80-7363-268-7. Dostupné v KUK.

WILDE, Robert, 2022. První počítač. In: EFerrit [online]. c2022[cit. 2022-11-27]. Dostupné z: https://cs.eferrit.com/prvni-pocitac/

LEAVE A REPLY

Please enter your comment!
Please enter your name here