1. Steganografie a kryptologie

Steganografie a kryptologie

První zmínky o kryptografii, kryptoanalýze či steganografii najdeme již ve starověku. Nyní se blíže podíváme na jejich historii a význam jednotlivých vědních oborů.

Steganografie

Slovo steganografie pochází z řeckého steganós - schovaný a gráphein - psát. Steganografie je věda zabývající se utajením existence komunikace či ukrýváním existujících zpráv - spadá do kryptologie.

Do steganografie můžeme zahrnout například neviditelné inkousty, či modernější mikrotečky. Díky steganografickým postupům, které ukrývají existenci zprávy, dosáhneme jistého stupně utajení. Ovšem již zde je patrná Achillova pata tohoto způsobu utajení - pokud se ukrytou zprávu podaří odhalit, dostane se nepřítel i k celému jejímu obsahu.

V pozdější době se utajení stupňovalo kombinací steganografického a kryptografického postupu. Zpráva se zašifrovala pomocí šifrovacího algoritmu a rozluštit se dala pouze za pomoci příslušného klíče. Takto upravená zpráva se poté nějakým steganografickým postupem uschovala.

První známý případ použití steganografie byl zaznamenán v 5. stol. př. n. l. Jednalo se o zprávu, která pomohla Řekům v boji proti Peršanům. Tajné zprávy se podle záznamů ukrývaly například v žebráckých berlách, dutých holích, částech oděvu, v dámských doplňcích, keramice či dalších nejrůznějších věcech, které by nás dnes ani nenapadly. Známé jsou také steganografické pomůcky, jako neviditelný inkoust z mléčné šťávy pampelišky nebo citronové šťávy, který se po zahřátí zviditelní, nebo inkousty ze složitějších

sloučenin, které jsou viditelné pod speciálním zdrojem světla (UV záření), či po styku s jinou synteticky vyrobenou sloučeninou.

Kryptologie

Kryptologie je věda, která v sobě zahrnuje jak kryptoanalýzu, tak kryptografii a její součástí je i steganografie obr. 1.

Obr. 1 Kryptologie a odvětví

• Kryptografie

Kryptografie je věda o šifrování, o zatajování obsahu zprávy. Cílem kryptografie není utajit existenci zprávy, ale její význam.

• Kryptoanalýza

Je věda, která dokáže bez znalosti klíče dešifrovat šifrovaný text. Kryptoanalytikové se snaží prolomit každý možný kryptografický systém. Odvětvím kryptoanalýzy může být chápáno klasické dešifrování - zpráva se zašifruje a odešle adresátovi - adresát je vlastníkem klíče a zprávu dešifruje.

Souhrn

Dozvěděli jsme se hlavní rozdíly mezi steganografickými a kryptologickými postupy. Pochopení tohoto rozdílu je důležité v návaznosti na další studijní články v tomto kurzu.

Zdroje

SINGH, Simon. Kniha kódů a šifer: tajná komunikace od starého Egypta po kvantovou kryptografii. 2. vyd. v českém jazyce. Praha: Dokořán, 2009. ISBN 978-807-3632-687.

2. Od Caesara k Vigenérovi

Od Caesara k Vigenérovi

Postupně se seznámíme s mnoha typy šifer, v průběhu vývoje lidstva a příslušných věd bylo nutné zdokonalovat iutajování zpráv. Jsou zde jmenovány postupně za sebou, jak byly vynalézány, využívány a některé i prolomeny.

Důležité ovšem je si připomenout a uvědomit, že šifry, které vznikají dnes, jsou založeny na kombinaci dvou základních algoritmů - substituce a transpozice. Všimněte si tedy i jednotlivých rozdílů mezi historickými šiframi, jak byla která vytvářena a na jakém principu byly založeny - napomohou vám k tomu i jednotlivá připravená cvičení.

Caesarova šifra

Caesarova posunová substituční šifra z 1. stol. př. n. l. je základem pro většinu dalších šifer, její posun je o 3 písmena (A = D, B = E, C = F...). Je ovšem zřejmé, že kombinací může být až 26 a můžeme měnit i pořadí, čím získáme 4*10^26 možností. Caesar sám tuto šifru zaměňoval, ovšem do povědomí všech vešla v podobě, jakou jí známe - tedy posun o 3 písmena ve zvolené abecedě daného jazyka obr. 1.

Obr. 1 Caesarova šifra

Šifra „podle plotu“

Jednou z prvních šifer, jež není založená na substituci, ale na transpozičním algoritmu, je „šifra podle plotu“ obr. 2. Algoritmus této šifry je jednoduchý, ale účinný, na obrázku vidíme plot „pouze dvouřádkový“, dotyčný musel vědět klíč, kterým zde je do kolika řádek má „plot“ postavit, kde se láme text a samozřejmě, že se jedná o šifru podle plotu. V tomto příkladu by to bylo do dvou řádek a po 15 písmenku.

Obr. 2 šifrování "podle plotu"

Scytale

Když před vámi bude pojem kryptografický stroj - co se vám vybaví?

Enigma

Jenže dávno dávno před legendární Enigmou tady bylo první vojenské zařízení, které můžeme nazývat zařízením tzv. scytale obr. 3. Princip byl jednoduchý, na proužek kůže, který byl navinutý na tyči, se vyryl text. Kůže se odvinula a dostali jsme do rukou posloupnost nicneříkajících znaků vyrytých na kůži. Až poté, co se navinula zpět na tyč o správném průměru, se text přečíst. Klíčem tedy zde byl průměr tyče, na kterou se pruh musel navinout, pokud chtěl adresát zprávu dešifrovat.

Obr. 3 Scytale

Umění tajného písma

Překvapení v podobě návodu, jak šifrovat, můžeme najít i v knize bráhmana Vátsjájany ze 4. stol. n. l., známé jako Kámasútra. Vedle šedesáti čtyř umění, jimž se má žena naučit, je zde popsáno i umění tajného písma - údajně, aby ukryla své další vztahy s muži. Šifrování bylo snadné. Otevřená abeceda se jednoduše přiřadila k šifrované, každé písmenko mělo svůj protějšek. Nevýhodou bylo, že adresát i odesilatel museli přesně znát šifrovanou abecedu, která fungovala současně i jako klíč. Bez toho je zprávu relativně nemožné rozluštit obr. 4.

 Obr. 4 Transpoziční šifra

Postupem času bylo ale nutné zkracovat klíče. Pokud byla klíčem celá šifrovaná abeceda, bylo velmi těžké si klíč nejen zapamatovat, ale znovu používat. Proto byl vymyšlen klíč, kterým bylo slovo, či sousloví, které všichni znali (CAESAR), odstranily se dublované hlásky (CAESR), poslední písmenko současně určovalo i další pořadí písmenv šifrované abecedě (CAESRTUVW...). Tento inovovaný systém si můžete vyzkoušet ve cvičení s názvem Substituční šifra.

Polybiova matice

Známé jsou i tzv. „tabulkové“ šifry například Polybiova metoda. Písmena abecedy jsou umístěny do matice 5x5, zapisují se po sloupcích a šifrovaný text má tedy podobu souřadnic jednotlivých písmen v matici. Polybiova šifra má význam až tehdy, kdy zpřeházíme abecedu; v češtině písmeno I a J zaujímá stejnou pozici. Polybiova šifra je rovněž připravena v následujícím cvičení.

Kardanova mřížka (Cardanova mřížka)

Nyní se podíváme do doby renesance. Hieronymus Cardanus (Jeroným Cardan) byl jeden z nejvzdělanějšíchrenesančních učenců 16. století. Jak víme, v renesanci se každý snažil proniknout do tajů vědy a snažil se být prospěšný společnosti po všech stránkách. Dnes známe přirovnání renesanční člověk, a právě takový byl i Hieronymus Cardanus. Fyzik, matematik, lékař, filosof a astrolog, jenž vynalezl inovovaný způsob šifrování.

Šifrovací mřížka byla destička tvaru čtverce, do které byly vyřezány otvory. Do průřezů se pak napsal zvolený text. Mřížka byla následně odstraněna a ostatní místa doplněna náhodnými písmeny či symboly. Dostali jsme tedy tabulku nic neříkajících písmen, která dávala smysl pouze po přiložení identické mřížky, kterou ideálně vlastnil pouze adresát.

Původní verze mřížky byla stabilní - rozumíme neotočná, její zdokonalenou formou je mřížka otočná.

Verze mřížek si rovněž můžete vyzkoušet na připravených cvičeních.

A v našem přehledu historických šifer pokračujeme dále.

Morseova abeceda

Pro někoho může být šifrou, pro jiného již vzpomínkou, ale.

Samuel Finley Breese Morse byl na svou dobu velmi pokrokový, v roce 1835 vynalezl první telegraf a 24. května 1844 se mezi Washingtonem a Baltimorem nesla první telegrafní zpráva v jeho abecedě. „Šifra“, kterou jsme se na dětských táborech učili všichni. Akát, blýskavice, cílovníci, dálava... dokážete pokračovat? V 18. století znamenala převratný objev a společně s rozvojem telekomunikace a telegrafních drátů i nový způsob komunikace - Morseova abeceda. Její používání bylo před více než deseti lety zrušeno, stále se ale s ní můžeme setkat na již zmíněných dětských táborech, kde je vítaným doplněním různých „bojových“ her v lesích.

Obr. 5 Morseova abeceda

Dokázali byste říci, jakými způsoby lze Morseovu abecedu interpretovat?

• textem (čárka/tečka)
• akustickým signálem (skrz pískání, dlouhý/krátký)
• elektronickým signálem (pomocí Morseova telegrafu, dlouhý/krátký)
• vizuálním signálem (baterka, dlouhý/krátký)

Šifra Vigenérova

Poslední zde jmenovanou šifrou je Vigenérova šifra, jež představuje složitější problém - šifra je totiž polyalfabetická - to znamená, že k šifrování je použito několik abeced. Vychází z principů Caesarovy šifry, ovšem je daleko bezpečnější a pro kryptoanalytiky těžší. Navíc čím delší klíčové slovo, tím více je použitých abeced pro šifrování.

Je založená na použití tzv. Vigenérova čtverce obr. 6, který je využíván jak pro zašifrování, tak dešifrování.

Obr. 6 Vigenérova matice

Použití Vigenérova čtverce je potom následující:

• v levém sloupci jsou modře napsána písmena klíče (řádky tedy určují abecedy dle písmena v klíči)
• v horním řádku jsou postupně vypsána červeně písmena abecedy (sloupce tedy určují písmena abecedy)
• průsečík mezi sloupcem a řádkem dá výsledné písmeno (čili písmeno klíče s písmenem textu dá výsledné písmeno)
• použití této metody si můžete vyzkoušet na cvičeních

Prolomení Vigenérovy šifry koncem 19. století ovšem pomohlo i jejímu zdokonalení. Pokud je totiž klíčové slovo relativně krátké, dochází k opakování v zašifrovaném textu (totéž písmeno je šifrované toutéž abecedou - takže je zašifrováno stejně) a šikovný kryptoanalytik si toho všimne. Zde to byli nezávisle na sobě Charles Babbage patrně v roce 1854, který prolomení nepublikoval a Friedrich Wilhelm Kasiski v roce 1863, který ovšem publikoval a od té doby je kryptoanalýza Vigenérovy šifry známá jako Kasiského test.

Vernamova šifra

Shrnutí

Zdroje

3. Cvičení: Substituční šifra

4. Cvičení: Polybiův čtverec

5. Cvičení: Cardanova mřížka

6. Cvičení: Vigenérova šifra

Zadání

                                  Obrázek 1. Vigenérova šifra - cvičení

7. Cvičení: Vigenérova šifra - bezpečnost

Zadání

Toto cvičení je zaměřeno spíše na pochopení principu, jak je možné šifru prolomit. Na krátkém textu máte možnost si vyzkoušet šifrování třemi různými abecedami.

Text zní:

"ŠIFROVÁNÍ DAT NENÍ JEN PRO PROFÍKY"

1. odstraňte z textu diakritická znaménka a mezery

2. použijte Vigenérovu matici pro zašifrování, klíč je slovo DEN

3. použijte Vigenérovu matici pro zašifrování, klíč je slovo SPOZLNMK

4. použijte Vigenérovu matici pro zašifrování, klíč je slovo APLIKACE

Porovnejte šifrované texty.

Tipy pro řešení

pomocí Vigenérova čtverce si vytvořte abecedy pro klíče DEN a SPOZLNMK

• pro POSLEDNÍ bod použijte abecedu z Vigenérova čtverce z minulého cvičení - text i klíč jsou totiž stejné
• podívejte se na zašifrované texty, porovnejte je, popřemýšlejte, kde má každý z nich slabinu

Návrh řešení

8. Enigma a jazyk kmene Navajo

Enigma a jazyk kmene Navajo

V roce 1918 založil německý vynálezce Arthur Scherbius spolu se svým přítelem Richardem Ritterem firmu Scherbius & Ritter. Scherbius studoval poznatky svých předchůdců, kteří se kryptografií zabývali, a postupem času vynalezl stroj, který uměl šifrovat obr. 1.

Obr. 1 Enigma

Pro usnadnění pochopení je na obrázcích zjednodušená verze - abeceda má „jenom“ šest znaků.

Hlavní části enigmy jsou principielně tři. Klávesnice, kterou je písmeno po písmenu zadáván otevřený text.Scrambler, jehož vnitřní zapojení přesně definovalo, které písmeno se bude jak šifrovat. Důležité zde je, že scramblery rotovaly. Principielně je to zachyceno na obrázku. V konečné verzi Enigmy byly použity tři scramblery vzájemně propojeny, všechny se stejnou funkcí. To znásobilo možnost kombinací písmen. 

Reflektor, který zadaná písmena z klávesnice, která prošla přes scramblery, poslal zpět na signalizační desku již zašifrovaná. Díky reflektoru taky nikdy nemohlo dojít k tomu, že by písmeno otevřeného textu bylo v šifrované podobě totožné (A nikdy nemohlo být v šifrované abecedě A). Další částí byla propojovací deska. Každá Enigma měla k dispozici šest kabelů, takže mohla propojit až šest písmen a prohodit je mezi sebou. A denní klíče, které byly pečlivě tvořeny a zapisovány do kódových knih se, již podle názvu, měnily každých 24 hodin.

Klíč k Enigmě

Pro zajímavost si vypočteme počet možných klíčů:

• rotující scrambler má 26 poloh, do kterých se může dostat. Scramblery jsou v původní Enigmě tři (26 x 26 x 26).
• Scramblery, protože se dají měnit, mají 6 možností, jak mohou být uspořádány (pro pochopení si je označíme a, b, c - možnosti jsou tedy: abc, acb, bac, bca, cab, cba)
• Propojovací deska umožňuje až 100 391 791 500 prohození.
• Když všechna čísla mezi sebou vynásobíme, dostaneme 1*10^15 možných klíčů.

Enigma se dostala do rukou německých vojáků v roce 1925. Během svého „života“ byla neustále zdokonalována a odolávala útokům kryptoanalytiků. V roce 1939 jí byly přidány další dva scramblery, počet kabelů se ze šesti zvýšil na deset - počet klíčů se zvýšil na 159*10^17.

Jak je ale možné, že takto silná šifra mohla být kdy prolomena...

• dvojí zakódování klíče na počátku každé šifrované zprávy
• příliš jednoduché klíče, popřípadě jejich opakování (únava kryptografů)
• cilky (z angl. cillies) - iniciály přítelkyň, zkratky jmen
• Alan Turing a jeho taháky
• a především sami tvůrci, když eliminovali možnosti zašifrování písmen

Rejewského bomby a Turingovy taháky

O prolomení Enigmy se pokoušelo několik týmů matematiků, lingvistů či kryptoanalytiků. Povedlo se to polskému kryptoanalytickému oddělení Biura Szyfrow. Klíčovou postavou zde byl Marian Rejewski, kterému trvalo „pouhý rok“ než zjistil všechna možná schémata denních klíčů a postavil tzv. Rejewského stroje přezdívané bomby. Bomby byly prototypy stroje Enigma, generovaly denní klíče a byly schopny dešifrovat přijaté depeše. Rejewski tohoto úspěchu dosáhl tím, že rozdělil problém scramblerů a propojovací desky.

Po porušení paktu Ribentrop-Molotov a napadení Ruska Německem byla Enigma obrněna proti útokům a všechno, co dokázali v Polsku, bylo najednou málo. Bylo potřeba dešifrovat pět scramblerů a propojovací deska měla deset kabelů. Zde přichází na scénu Alan Turing.

Alan Turing si byl vědom pokroku, kterého dosáhli polští kryptoanalytici, nicméně byl si také vědom toho, že x tisíc zadržených depeší leží v archivech. Věděl, že Němci posílají ve stejný čas stejnou informaci každý den. Našel si tedy všechny šifrované texty a hledal. Výsledkem toho byly jakési taháky, díky nimž se dalo částečně dešifrovat nové zprávy. Enigma se prozradila sama.

Spojenci a „mládě jestřába“

Na druhé straně světa se ale rovněž vedla kryptografická válka.

Kódem pro komunikaci, který Spojenci využívali, se zde považoval jazyk kmene Navajo, původních obyvatel Ameriky. Pro každé písmeno měli svůj navažský ekvivalent. V době 2. světové války byl součástí každé americké divize jeden radista, domluva probíhala přes vysílačky. Kryptoanalytici při pokusu o rozluštění nazvali jazyk:

„...podivnou posloupností hrdelních, nosových a jazykolomných zvuků, nemohli jsme je ani přepsat, natož rozlomit kód.“ [1]

Velitel diktoval zprávu, radista hlásku po hlásce diktoval na druhou stranu dalšímu radistovi ze svého kmene, a ten potém překládal do angličtiny. Každý voják, který se chtěl stát radistou, musel umět anglicky a projít několika testy - poté byl vybrán jako člen divize. Navažští členové divizí měli i své „bodyguardy“, kteří se starali o jejich bezpečnost. A kromě abecedy pro hlásky měli i speciální označení pro bojová vozidla.Navajové, kteří se stali členy divizí, však byli pod přísahou a nikdo se nesměl o jejich působení v armádě dozvědět. Navenek měli působit jako řadoví vojáci. První zmínky o jejich „kryptografickém přínosu“ jsou až ze 70. let, kdy bylo dávno po válce, a jedinou odměnou pro ně může být to, že jejich jazyk byl tak silnou šifrou, že nikdy nebyl rozluštěn.

Shrnutí

Zdroje