Foto: © BillionPhotos.com / Dollar Photo Club
Foto: © BillionPhotos.com / Dollar Photo Club

Vývoj šifer: Když substituce nestačí

Jednoduchá monoalfabetická substituce byla dostatečně bezpečná po celá staletí. To se však změnilo v důsledku rozvoje frekvenční analýzy – nejprve v arabském světě, později v Evropě. Tragická poprava Marie Stuartovny je dramatickou ilustrací slabin monoalfabetické substituce. Bylo zřejmé, že v bitvě mezi kryptografy a kryptoanalytiky mají navrch ti druzí. Každý, kdo odesílal šifrovanou zprávu, musel počítat s tím, že špičkový nepřátelský kryptoanalytik ji může rozluštit a přečíst si všechna tajemství v ní obsažená.
Před kryptografy tedy stála úloha vymyslet novou, silnější šifru, na niž by luštitelé nestačili. Přestože se taková šifra objevila až koncem 16. století, její počátky lze vysledovat až k florentskému polyhistorovi Leonu Battistovi Albertimu, který se narodil roku 1404 a patřil ke klíčovým osobnostem renesance. Byl to malíř, skladatel, básník a filozof, rovněž autor prvních vědeckých pojednání o perspektivě, traktátu o mouše domácí a pohřebního oratoria za svého psa. Nejvíce se proslavil jako architekt, postavil první římskou fontánu Trevi a napsal De re aedificatoria, první tištěnou knihu o architektuře, jež posloužila jako katalyzátor přechodu od gotického slohu k renesančnímu.
Někdy v 60. letech 15. století se Alberti procházel vatikánskými zahradami, kde potkal svého přítele Leonarda Data, jenž pracoval jako sekretář u papežského stolce. Dali se do řeči o kryptografii. Náhodná konverzace inspirovala Albertiho k eseji na dané téma. V něm popsal šifru, kterou pokládal za zcela novou. V té době se u substituční šifry používala vždy jedna šifrová abeceda k zaši­fro­vání celé zprávy. Alberti namísto toho navrhl použít dvou či více šifrových abeced, které by se při šifrování pravidelně střídaly a zmátly tak potenciální kryptoanalytiky:

Otevřená abeceda a b c d e f g h i j k l m n o p q r s t u v w x y z
Šifrová abeceda 1 F Z B V K I X A Y M E P L S D H J O R G N Q C U T W
Šifrová abeceda 2 G O X B F W T H Q I L A P Z J D E S V Y C R K U H N

Zde máme například dvě šifrové abecedy. Zprávu můžeme zašifrovat tak, že abecedy mezi sebou stále střídáme. Zprávu nazdar zašifrujeme tak, že první písmeno šifrujeme podle první abecedy, takže namísto n dostaneme S. Druhé písmeno zprávy pak šifrujeme podle druhé abecedy a dostaneme G. Třetí písmeno šifrujeme opět podle první abecedy, čtvrté podle druhé abecedy, páté podle první, šesté podle druhé. Celý šifrový text pak zní SGWBFS. Klíčová výhoda Albertiho systému spočívá v tom, že opakovaný výskyt písmene v otevřeném textu nevede nutně k opakovanému výskytu jiného písmene v šifrovém textu. Například opakující se a ve slově nazdar je jednou šifrováno jako G, podruhé jako F. Stejně tak opakující se S v šifrovém textu znamená jednou n, podruhé r.
Přestože Alberti narazil v kryptografii na největší objev tisíciletí, dál jej nerozvinul. Tento úkol zbyl na jeho pokračovatele. Prvním z nich byl Johannes Trithemius, německý opat narozený roku 1462, dalším italský vědec Giovanni Porta, jenž se narodil roku 1535, a konečně Blaise de Vigenčre, francouzský diplomat narozený roku 1523. Vigenere se seznámil s pracemi Albertiho, Trithemia a Porty, když byl ve svých šestadvaceti letech vyslán na dvouletou diplomatickou misi do Říma. Je třeba říci, že jeho zájem o kryptografii byl zcela praktický, plně svázaný s jeho diplomatickou službou. Ve věku třiceti devíti let Vigenere usoudil, že již našetřil dost peněz, aby pověsil svou kariéru na hřebík a nadále se věnoval jen studiu. Teprve tehdy prozkoumal do detailů práce Albertiho, Trithemia a Porty, aby spojil jejich příspěvky do návrhu ucelené a silné šifry.
Přes nesporný význam příspěvků Albertiho, Trithemia a Porty se šifra nazývá po Vigenerovi – muži, který ji dopracoval do konečné podoby. Síla Vigenerovy šifry spočívá v tom, že k zašifrování zprávy nepoužívá jednu, ale 26 odlišných šifrových abeced. První šifrovací krok spočívá v tom, že se vypíše tzv. Vigenerův čtverec (viz tabulka 3), což je otevřená abeceda následovaná 26 šifrovými abecedami, z nichž každá je vůči předchozí posunuta o jedno písmeno. První řádek tedy odpovídá šifrové abecedě s Caesarovým posunem 1 a lze jej použít pro šifrování Caesarovou šifrou, v níž je každé písmeno šifrového textu posunuto o jednu abecední pozici oproti otevře­nému textu. Řádek 2 odpovídá šifrové abecedě s Caesarovým posunem 2 a tak dále. Nejvrchnější řádek čtverce reprezentuje otevřený text. Každé jeho písmeno lze zašifrovat kteroukoli z 26 šifrových abeced. Pokud například použijeme abecedu 2, pak písmeno a šifrujeme jako C, použijeme-li abecedu 12, šifrujeme a jako M.
Kdyby odesilatel použil jen jednu šifrovou abecedu, pak půjde o jednoduchou Caesarovu šifru, což je velmi slabý kryptografický prostředek, který lze snadno rozluštit. Podstata Vigenerovy šifry však spočívá v tom, že se pro zakódování každého písmene použije jiný řádek čtverce, tedy jiná šifrová abeceda. Jinými slovy, odesilatel může zašifrovat první písmeno zprávy pomocí řádku 5, druhé podle řádku 14, třetí řádkem 21 a tak dále.
Aby příjemce získal zpět čitelný text, musí vědět, kterým řádkem Vigenerova čtverce šifroval odesilatel každé písmeno zprávy, musí tedy existovat předem dohodnutý systém, podle něhož se řádky střídají. Toho lze dosáhnout pomocí klíčového slova. Pro ilustraci si předvedeme, jak prostřednictvím Vigenerova čtverce zašifrovat krátkou zprávu divert troops to east ridge („odkloňte jednotky k vý­chodnímu hřebenu“) za použití hesla WHITE („bílý“). Jako první krok napíšeme heslo nad text zprávy – opakovaně, tolikrát, kolikrát je třeba, abychom ji pokryli celou. Pak šifrujeme následujícím způsobem: k zašifrování prvního písmene, jímž je d, se nejprve podíváme, jaké písmeno klíče se u něj nachází. Je to W, čímž je dán řádek Vigenerova čtverce, v daném případě řádek 22, jenž začíná právě písmenem W. V průsečíku sloupce označeného d a řád­ku označeného W najdeme písmeno Z, což je první písmeno hledaného šifrového textu.

Klíčové slovo W H I T E W H I T E W H I T E W H I T E W H I
Otevřený text d i v e r t t r o o p s t o e a s t r i d g e
Šifrový text Z P D X V P A Z H S L Z B H I W Z B K M Z N M

Pro zašifrování druhého písmene zprávy, jímž je i, celý proces zopakujeme. Písmeno klíče nad i je H, takže i šifrujeme pomocí řádku 7, jenž začíná písmenem H. Podíváme se na průsečík sloupce označeného i a řádku označeného H a najdeme v něm písmeno P. To je tedy druhým písmenem šifrového textu. Každé písmeno klíčového slova indikuje konkrétní šifrovou abecedu uvnitř Vigenerova čtverce, a protože naše heslo sestává z pěti písmen, odesilatel šifruje za neustálého střídání pěti šifrových abeced. Páté písmeno zprávy šifrujeme přes páté písmeno klíčového slova, jímž je E, ale u šestého písmene se vracíme k prvnímu písmenu klíčového slova. Delší klíčové slovo nebo fráze znamená, že se používá více šifrových abeced a složitost šifry roste. V tabulce 4 vidíme Vigenerův čtverec, v němž je zvýrazněno pět řádků (tedy pět šifrových abeced) definovaných klíčovým slovem WHITE .
Velkou výhodou Vigenerovy šifry je odolnost vůči frekvenční analýze popsané v první kapitole. Kryptoanalytik používající frekvenční analýzu začne zpravidla tím, že si stanoví, které písmeno v šifrovém textu je nejčetnější. V tomto příkladu je to písmeno Z. Pak učiní předpoklad, že toto písmeno odpovídá nejběžnějšímu písmenu anglické abecedy, jímž je e, což však není pravda. U popsané šifry písmeno Z reprezentuje postupně (na daném vzorku textu, pozn. překl.) písmena d, r a s, v žádném případě e. To je z hlediska kryptoanalytika vážný problém. Skutečnost, že opakované výskyty téhož písmene v šifrovém textu mohou odpovídat různým písmenům v otevřeném textu, představuje obrovskou nejednoznačnost. Stejně matoucí je i opačný princip – totéž písmeno otevřeného textu bude při svých různých výskytech pokaždé šifrováno jinak. Například ve slově troops se o opakuje dvakrát po sobě, v šifrovém textu však toto oo bude zobrazeno jako HS.
Vigenerova šifra je nejen odolná vůči frekvenční analýze, ale také disponuje enormním množstvím klíčů. Odesilatel a příjemce se mohou dohodnout na libovolném slově ze slovníku, na určité kombinaci slov, mohou si dokonce vytvářet umělá slova. Kryptoanalytik nemůže zkoušet všechna myslitelná klíčová slova – je jich příliš mnoho.
Vrcholem Vigenerovy práce byl jeho Traicté des chiffres (Traktát o šifrách), publikovaný roku 1586. Ironií osudu jej vydal téhož roku, kdy Thomas Phelippes prolomil šifru Marie Stuartovny. Kdyby Mariin šifrant četl Vigenerovo pojednání, mohl by Phelippese přelstít – a Marie by možná vyvázla živá.

Tento text je úryvkem z knihy
Simon Singh: Kniha kódů a šifer.
Tajná komunikace od starého Egypta po kvantovou kryptografii

Argo a Dokořán 2017 (1. vydání v češtině 2003)
O knize na stránkách vydavatele

obalka_knihy

Scintilátor – co to vůbec je?

Scintilátor – velmi zvláštní slovo, že? Málokdo by řekl, že označuje něco, s čím se …

Používáme soubory cookies pro přizpůsobení obsahu webu a sledování návštěvnosti. Data o používání webu sdílíme s našimi partnery pro cílení reklamy a analýzu návštěvnosti. Více informací

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close