Doplňkový materiál k prezentaci pro podporu výuky matematiky na SŠ na téma
Zajímavosti z kryptologie
Tuto akci podpořil Regionální koordinátor pro popularizaci technických a přírodovědných oborů v Moravskoslezském kraji. IPN Podpora technických a přírodovědných oborů Regionální koordinátor pro Moravskoslezský kraj www.generaceY.cz www.generaceY.cz www.msmt.cz
Úvod do kryptologie Kryptologie je nauka o šífrách. Hledá způsob k nalezení bezpečné komunikace, která by zajistila, že i při zachycení zprávy nebude schopen nepřítel zprávu přečíst. V historii se mnohokrát stalo, že rozluštění tajné komunikace vedlo k zásadním událostem, získání značné výhody ve válkách, či přímo k vítězství. V dnešní době je kryptologie nesmírně důležitá nejenom v oblasti armády a tajných služeb, ale díky informačním technologiím narůstá potřeba chránit i osobní informace, důležitá dat z firem, bank apod.
Steganografie Nejjednodušším způsobem utajení komunikace je, aby se nepřítel ke zprávě jednoduše nedostal. Tato metoda se nazývá steganografie neboli ukrytí zprávy. Dnes je tento způsob ochrany dat zcela nemyslitelný díky snadné možnosti odposlechu. Avšak v minulosti tomu tak vždy nebylo. Například Herodotos ve svých Dějinách líčí konflikt mezi Peršany a Řeky. Perský vládce Xerxes se chytal na překvapivý útok na Řecko a kolem roku 475př.n.l začal sbírat vojsko. To vše sledoval Řek Demaratus a chtěl Řecko varovat. Na samotnou zprávu by Peršané přišli, proto seškrábal vosk z voskových psacích tabulek a zprávu vyryl přímo na dřevo. Poté tabulky opět zakryl voskem. Zprávy prošly kolem Perských hlídek bez povšimnutí a Řekové tak byli včas varováni. Další příklad steganografie je také ze starého Řecka. Zpráva byl ukryta přímo na hlavě otroka, kterému ji vytetovali na oholenou hlavu a poté nechali dorůst vlasy. (V té době bylo možné člověka takto „jednorázově použít“.) V Číně se používaly zprávy napsané na hedvábí, které se následně smotalo do kuličky a zalilo voskem. Takovouto kuličku posel spolkl. (Jakým způsobem se zpráva po několika hodinách až dnech objevila, si již každý určitě domyslí…) Další kapitolou ve steganografii je použití tajných inkoustů. Jeden originální vynalezl v 16. století Italský vědec Giovanni Porta, kdy našel způsob jak ukrýt zprávu ve vejci natvrdo. Pomocí inkoustu z octa a kamence (připrav se na otázku, o jakou sloučeninu se vlastně jedná) se zpráva napsala na skořápku. Čitelná však byla až po oloupání vejce. Tajné inkousty možná znáte sami, některé lze najít i v každé kuchyni např. bramborový škrob, mléko apod. Zpravidla se zpráva ukáže po zahřátí nebo při kontaktu s jinou látkou.
Kryptografie Cílem kryptografie není utajit existenci zprávy resp. zprávu někde šikovně ukrýt , ale upravit samotnou zprávu tak, aby ji nepovolaná osoba nemohla po přečtení rozumět. Kryptografové(šifranti) zprávy šifrují. Takzvaný otevřený text zprávy se pomocí šifrovacího systému a šifrovacího klíče zašifruje na šifrový text. Opačný proces, tedy převedení šifrovaného textu na otevřený se nazývá dešifrování.
Kryptoanalýza Kryptoanalytikové(luštitelé) mají za úkol získat z šifrovaných zpráv otevřený text. Zásadní rozdíl mezi luštiteli a dešifranty je ten, že luštitelé získávají otevřený text bez znalosti šifrovacího klíče a šifrovacího systému. Zásadou kryptografie je najít metodu, která znemožní luštitelům zprávu přečíst.
Kryptografii můžeme dle základního principu při transformaci otevřeného textu na šifru rozdělit na dvě základní části‐transpoziční a substituční šifrování.
Transpozice Princip transpozičních šifer spočívá v tom, že se mezi sebou zamění písmena zprávy. Vytvoří se tedy přesmyčka ‐permutace zprávy. Zásadou kryptografie je najít metodu, která znemožní luštitelům zprávu přečíst. V podstatě jde o to vymyslet šifrovací systém s co možno největším počtem možných šifrovacích klíčů tak, aby při „útoku hrubou silou“ tj. při luštění tak, že vyzkoušíme všechny možnosti, nebylo možné v reálném čase zprávu rozluštit . Např. slovo „les“ můžeme zapsat 6‐ti způsoby(les, lse, sel, esl, els, sle). Proto při luštění takovéto zprávy stačí vyzkoušet šest možností a dostaneme otevřený text. Při delších zprávách ale počet možných permutací prudce roste. Zpráva o 10 písmenech lze zapsat 10!=3628800 možnostmi. Když si kupříkladu vezmeme průměrně dlouhou větu o 40 písmenech dostaneme se rázem na 40!=8*1047 možností. Takovýto počet možných klíčů je nemožné v reálném čase vyzkoušet, proto by se transpoziční šifra mohla jevit jako vhodná volba pro šifrování zpráv. Problémem těchto druhů šifer však není jejich bezpečnost, protože luštitel nemá reálnou šanci na to nalézt otevřený text, ale to, že u takovýchto textů by bylo nemožné i jejich dešifrování. Proto se musí při transpozicích použít nějaký jednoduchý systém šifrování, čímž se ale rapidně sníží bezpečnost. (Ve své podstatě se jedná o problém při předávání tajného klíče, tj. v podstatě klíčová informace o tom, jak byla permutace provedena.) Příkladem transpozičních šifer je Scytala používaná ve Spartě. Jde o dřevěnou tyč o předem stanoveném průměru, kolem ní se navine proužek pergamenu nebo kůže a zapíše se zpráva. Po odvinutí proužku je zpráva nečitelná. Přečíst lze pouze navinutím na tyč o stejném průměru. Takže klíčem je zde tyč daného průměru popřípadě informace o průměru tyče. Dalším příkladem je tzv. „plot“, kdy se zpráva rozdělí do dvou a více řádků pravidelným střídáním písmeno po písmenu. Transpoziční šifra plot T a s o i n š f a l t r n p z č í i r p o Tasoinčfaltrnpzčíirpo Příjemce zná počet řádků plotu a proto může jednoduše text dešifrovat. Klíčem je tedy počet řádků plotu. Tuto informaci si musí šifrant a dešifrant buďto osobně či jinak bezpečně předat.
Substituce Jde o nahrazení písmen otevřeného textu jinými písmeny nebo znaky. První popis substituční šifry je znám ze 4. století kdy byla vydána Kamasútra. V ní je popsáno 64 umění, které by měli ovládat ženy a jedno z nich je umění tajného písma, aby mohly ukrýt informace o svých vztazích. Jedním z principů je spárování písmen abecedy a nahrazení písmene v otevřeném textu jeho partnerem.
O substituční šifře se zmiňuje i Julius Caesar v knize Zápisky o válce galské. Kdy šifroval zprávu tím způsobem, že zaměnil římská písmena v textu za řecká. Jedna z šifer, které Caesar používal, dokonce nese jeho jméno. Tzv. Caesarova šifra je substituce pomocí šifrové abecedy, která vznikne posunutím otevřené abecedy o tři místa 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 ‐ d e f g h i j k l m n o p q r s t u v w x y z a b c Otevřený text‐ abeceda Šifrový text‐ dehfhgd
Šifrovací algoritmus Šifrant má otevřený text a klíč. Pomocí šifrovacího algoritmu zašifruje zprávu do šifrového textu. Příjemce zprávu dešifruje pomocí dešifrovacího algoritmu za použití klíče. Nepřítel není bez klíče schopný šifrovanou zprávu rozluštit. Pro bezpečnost je zcela nezbytné, aby byl utajen klíč. Zároveň čím větší je počet potenciálních klíčů, tím se zvyšuje bezpečnost šifry. U Caesarovy šifry je míra bezpečnosti velmi nízká, neboť potencionálních klíčů je jen 25. Luštiteli stačí vyzkoušet 25 možností. Šifrová abeceda se dá vhodně vytvořit i jinak než posunem písmen v abecedě, např. pomocí nějakého klíčového slova nebo fráze Například pomocí slova „šifry“ vytvoříme šifrovou abecedu. Na začátek napíšeme písmena s,i,f,r,y a zbytek abecedy napíšeme v normálním pořadí. 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‐ s i f r y z a b c d e g h j k l m n o p q t u v w x Možných klíčů k vytvoření abecedy je tolik, že náhodné uhodnutí klíče je téměř nemožné.
Kryptoanalýza Kryptoanalýza, tedy luštění zašifrovaných zpráv bez znalosti klíče a metody šifrování. Její první metody objevili Arabové někdy v 10. století. Arabové používali k šifrování jednoduché šifrovací abecedy, které se v průběhu šifrování nijak neměnily, tento způsob se nazývá monoalfabetická substituční šifra. Islámská civilizace byla tehdy na vysoké úrovni, a tudíž se rozvíjela i věda. Nejpodstatnější pro kryptoanalýzu byly lingvistika a statistika. Islámští teologové začali zkoumat Korán a všímali si nejen počtu opakujících se slov, ale také i četnosti výskytu písmen. Toho si všiml arabský filozof al‐Kindí a vymyslel techniku známou jako frekvenční kryptoanalýza. Ta spočívá v tom, že každý jazyk je specifický v četnosti používaných hlásek a tedy i písmen v textu. Například čeština má nejčastější písmeno E s četností 10,5%. Oproti písmenům Q,W,X, které mají četnost téměř nulovou. Jestliže tedy na dostatečně dlouhém textu, čímž Korán zajisté byl, spočítáme četnost jednotlivých písmen v jazyce a porovnáme tuto četnost s výskytem písmen nebo znaků v šifrované zprávě, můžeme snadno získat šifrovací abecedu, se kterou již zprávu jednoduše vyluštíme. Tato
metoda lze použít pouze na delší texty. Krátké věty o několika slovech zpravidla nejsou dostatečně vypovídající. S objevem frekvenční analýzy přišla na svět i potřeba šifry zdokonalovat, protože díky ní jsou všechny transpoziční a monoalfabetické substituční šifry rozlomitelné. Tak přišli na svět tzv. klamače‐znaky, které nic neznamenají a jen slouží ke ztížení analýzy. V šifrách se používaly také nomenklátory, což jsou nějaká předem stanovená slova, která mají svůj vlastní znak. Nebo byla vymyšlena homofonní substituční šifra, což znamená, že každé písmeno bylo zastoupeno tím počtem znaků, jakou mělo relativní četnost. Například pro písmeno E by bylo 10 znaků, pro P 3 znaky atd. S tím vším si však Luštitelé dokázali po čase taktéž poradit (zejména s využitím lingvistických znalostí ).
Polyalfabetická šifra Zbraní proti frekvenční kryptoanalýze (alespoň na pár set let) se stala polyalfabetická subrtituční šifra. Využívá ne jednu ale více šifrovacích abeced k zašifrování jedné zprávy. Nejznámější polyalfabetickou šifru vymyslel v 16. století Francouz Blaise de Vigenere. Jeho šifra používá dokonce 26 šifrových abeced. Šifruje se pomocí hesla. K zašifrování prvního písmene použijeme abecedu která přísluší prvnímu písmeni hesla. K zašifrování druhého použijeme abecedu u druhého písmene hesla, atd. klíčové heslo se při šifrování neustále opakuje. Takže například chceme zašifrovat text Blaise de Vigenere pomocí hesla „šifra“. První písmeno je B a šifrujeme abecedou u písmen S, takže B se změní na T. Druhé je L šifrované podle I, dostaneme T. Po pěti krocích vyčerpáme všechny písmena hesla, takže začínáme znova od začátku, šesté písmeno podle S, atd.
Klíčové slovo‐heslo
S I F R A S
I
Otevřený text
B L A I
D E V
Šifrový text
T T F Z S W L J M I
S E
F R
A S I
F R A S
I
N E R E
G E
Y M S V R W
Tato šifra byla po dlouhou dobu téměř 300 let neprolomitelná. Až v polovině 19. století přišel Charles Babbage na metodu, jak Vigenerovu šifru rozluštit. Vtip spočíval v tom, že tak jako tak se určité slova nebo fráze budou v šifrovaném textu opakovat. Každý jazyk má speciální slova, dvojce nebo trojice písmen, které se v textech opakují. Na základě těchto lingvistických znalostí dokázal Babbage určit délku hesla, poté už nezbývalo nic jiného, než rozdělit text na části podle příslušného počtu písmen v hesle a použít standardní frekvenční kryptoanalýzu.
Neprolomitelná šifra Vigenerova šifra byla prolomena proto, že heslo použité k zašifrování bylo krátké. Kdyby však bylo heslo stejné dlouhé jako zpráva samotná, nešlo by text rozdělit a použít frekvenční analýzu. Tato metoda se nazývá Vernamova nebo také jednorázová tabulková šifra. Je absolutně bezpečná, což je i matematicky dokázáno (připrav se na případnou otázku, na čem je důkaz založen). Zmiňované heslo se však nesmí použít více než jednou, protože pak by kryptoanalytici mohli být schopni zprávu rozluštit. Tato podmínka zabránila tomu, aby se metoda používala v praxi, neboť má hned několik vad. Pokaždé se musí použít nové a jedinečné heslo, navíc s přesným počtem písmen. Heslo navíc musí být zcela náhodné, nesmí se v něm objevovat žádné fráze.Takový postup je zejména ve válečné komunikaci zcela nemožný. Přesto se šifra používala či používá, na jednorázové velmi důležité komunikace, kterým nevadí časová náročnost distribuce klíče. Takovýmto šifrováním byla například spojena horká linka mezi Washingtonem a Moskvou za studené války.
Polybiova tabulka(čtverec) Jedná se o substituční šifru, kde každé písmeno je vyjádřeno pomocí dvojice čísel
V tabulce se obvykle vynechává písmeno, které se v daném jazyce často nevyskytuje(x). Např. B je šifrováno jako 12, O jako 34, atd. Obvykle se navíc čtverec vytváří podle nějakého hesla, takže např.podle hesla Ostrava by vypadal následovně
1 2
3 4
5
1 O S
T R
A
2 V B
C D
E
3 F G
H I/J K
4 L
M N P
Q
5 U W X Y
Z
Kryptologie 1. poloviny 20. století
ADFGVX Koncem 19. století byla kryptologie v úpadku. S přelomem století však přišel na svět převratný objev rádia, které vymyslel Italský fyzik Guglielmo Marconi. Zrodil se nový způsob komunikace, který však měl jedno úskalí. Snadná komunikace bez nutnosti používání elektrických vodičů a kabelů se dá velice jednoduše odposlouchávat. Z toho důvodu bylo nutné, zejména ve vojenské komunikaci, používat kryptografické metody, které nelze lehce rozluštit. V období až do konce první světové války se kryptografové snažili přijít na nový bezpečný druh šifry, avšak to se nepovedlo. Přes mnohé pokusy nikdo nepřišel na šifru, který by odolala kryptoanalytikům. Jednou z používaných šifer byla německá ADFGX, posléze ADFGVX, kdy do tabulky byla přidána i čísla. Písmena ADFGX byla použita kvůli tomu,aby se při radiovém přenosu předešlo chybám. V Morseově abecedě totiž mají tato písmena významný rozdíl. A D F
A A F L
D B G M
F C H N
G D I/J O
X E K P
G Q R S T X V W X Y A D F G V X
A A G M S Y 5
D B H N T Z 6
F C I O U 1 7
G D J P V 2 8
U Z
V E K Q W 3 9
X F L R X 4 0
Šifrování pomocí šifry ADFGVX spočívá v kombinaci dvou šifrovacích metod‐substituci a transpozici. Zpráva se nejprve zašifruje analogicky jako u Polybiova čtverce, tedy substitucí jednoho znaku za dvojici písmen. K tomuto kroku se použije substituční klíč (buďto celá tabulka nebo heslo, podle něhož se tabulka vytvoří). Chceme zašifrovat zprávu „Letní škola “ a použijeme substituční klíč „Je 22. srpna “. Postupujeme tak, že vytvoříme tabulku, kdy vždy první písmeno řádku/sloupce je postupně jedno z písmen ADFGVX. Následně do tabulky vepíšeme klíč, přičemž opakující se písmena nebo číslice vepíšeme pouze jednou a to na pozici, kde se vyskytly poprvé. Poté tabulku doplníme o zbývající písmena abecedy a číslice, které se v klíči nevyskytovaly. A D F G V X
A J N G O X 4
D E A H Q Y 5
F 2 B I T Z 6
G S C K U 0 7
V X R P D F L M V W 1 3 8 9
Potom tedy zpráva LETNÍ ŠKOLA bude zašifrována následující sekvencí znaků (viz 2. řádek tabulky): L E T N Í Š K O L A FV AD GF DA FF AG FG GA FV DA V druhém kroku se použije permutační klíč, pomocí něhož se zpráva (již po substituci) zapíše do tabulky pod tento klíč tak, že počet písmen klíče odpovídá počtu sloupců tabulky. Pomocí permutačního klíče „LÉTO“ sepíšeme substituovanou zprávu do tabulky L 2 F G F
E 1 V F F
T 4 A D A
O 3 D A G
F G G A F V D A Sloupce v tabulce se následně seřadí podle abecedního pořadí písmen v klíči. E 1 V F F G V
L 2 F G F F F
O 3 D A G A A
T 4 A D A G D
Nakonec se zapíší zašifrované znaky z tabulky v pořadí odshora dolů, vzestupně od prvního sloupce. Tím dostaneme zašifrovaný text.
VFFGVFGFFFDAGAAADAGD Němci začali tuto šifru používat před zahájením ofenzívy v březnu 1918. Tuto šifru rozluštil Francouz Georges‐Jean Painvin, který mimochodem při jejím intenzivním luštění zhubl 15kg. Při luštení se využívalo zpráv stejné délky a k tomu opakující se slova, jako například osloveních na začátních zpráv nebo podpisy na koncích zpráv. Počátkem června 1918 se podařilo rozluštit vylepšenou verzi šifry ADFGVX. Němci při svých útocích ztratili moment překvapení a jejich útok byl poražen.
Kódové knihy V první světové válce bylo také velice obvyklé šifrování pomocí kódových knih. Zhruba měsíc poté, co Německo vyhlásilo Rusku válku ztroskotal u Ruského pobřeží německý křižník Magdeburg. Posádka při spěchu přehlédla dvě kopie německé kódovací knihy Signalbuch. Rusové se o Signalbuch podělili se Velkou Británií, což později přispělo k tomu, že se do války zapojily Spojené státy americké. Stalo se tak v důsledku rozluštění Zimmermannovi depeše. Zimmermann byl za první světové války německý státní tajemník a na počátku roku 1917, kdy Němci plánovali ponorkovou válku proti Velké Británii, chtěl vtáhnout Mexiko do války proti USA, aby USA nemohly zasáhnout do bojů v Evropě. Jeho depeši směřovanou do Mexika, kde vybízí Mexiko ke vstupu do války však dostali do rukou i Spojené státy, které poté podpořili Brity a vyhlásili Německu válku.
Šifrovací stroje Po první světové válce, kdy se ukázala důležitost šifrování, se začali rozvíjet složitější šifrovací metody. Ruční transpoziční a substituční metody neměli v boji s kryptoanalyticky šanci a tak muselo nutně dojít k mechanizaci šifrování. Za první šifrovací stroj by se dal považovat šifrovací disk, vynalezený v 15. Století Italem Albertim. Skládal se ze dvou disků(menšího a většího), které měli po obvodu napsanou abecedu. Během šifrování se podle určitého hesla měnilo nastavení disku, čímž se měnila i šifrovací abeceda.
Nejednalo se však o nic jiného, než o mechanickou pomůcku k Vigenerově šifře (popřípadě i Caesarově šifře). Šifrovací disky používala například i Konfederace za americké občanské války.
V roce 1918 vyrobil Američan E.H.Hebern první šifrovací stroj, který k šifrování používal rotor. Ten se při zašifrování každého písmene otáčel a měnil tak šifrovací abecedy. Tento stroj měl periodu 26, tedy podle počtu písmen abecedy. Hebern svůj stroj zdokonaloval a jeho pětirotorový stroj(s možností 265=11881376 různých šifrovacích abeced) používalo na přelomu 30.let 20.století americké námořnictvo. Roku 1919 si nechal Nizozemec H.A.Koch patentovat šifrovací stroj na principu rotoru. Žádný stroj však nevyrobil a v roce 1927 prodal svůj patent německému inženýrovi Arthuru Scherbiusovi. Ten dal stroji název Enigma (řecky záhada). Několikrát vylepšenou verzi Enigmy používala v důležitých okamžicích 2.sv.války německá armáda. Enigma
Šifrovací vojenská enigma se skládala ze tří částí‐klávesnice pro zadávání otevřeného textu, šifrovací jednotky a signalizačních lampiček, které zobrazovali zašifrovaný text. Nejdůležitější součástí stroje jsou disky(rotory). Příklad disku, pro jednoduchost se šesti písmeny.
a b c d e f
C A D B E F
Podstata šifrování spočívá v tom, že disk se po zadání každého písmene posune o 1/6(1/26) periody, čímž vytvoří jinou šifrovací abecedu.
a b c d e f
A D B E C F
Napíšeme‐li šestkrát za sebou B dostaneme šifrový text ADBBFC. Po 26 znacích se o jeden zub pootočí druhý disk. Po 262 = 676 znaků se o pootočí i třetí disk. 263=17576 je tedy celkový počet možných nastavení stroje. Šifrant i dešifrát tedy musí základní nastavení znát, jinak nejsou schopni správně zprávu zašifrovat a dešifrovat. Nastavení se měnilo každý den pomocí denních klíčů. Jediná možnost jak zprávu rozluštit, byla v získání klíče. Scherbius ke stroji přidal ještě část zvanou reflektor. Ten odráží signál, který projde přes tři disky a vrací ho přes ně zase zpátky, avšak ne na klávesnici, nýbrž na signální desku. Šifrování a dešifrování jsou zrcadlové postupy a reflektor zajistil jednoduchost dešifrování.
Napíšeme‐li při šifrování písmeno E, dostaneme F. Díky reflektoru se při stejném nastavení a zadání písmene F objeví E.
Scherbius zvýšil bezpečnost stroje ještě dvěma prvky. Mohl použít větší množství disků, to by zvýšilo počet možných klíčů vždy 26krát, avšak zároveň by se museli zvětšit i rozměry přístroje. Scherbius na místo toho vyrobil disky, které se daly vyměňovat. Před šifrováním bylo nutné znát i pořadí disků nejen jejich nastavení. Tím se zvýšil celkový čet 6 krát. Neboť počet možných pořadí je 3!. Druhým vylepšením bylo přidání propojovací desky, zařazené mezi klávesnici a disky. Pomocí ní se dají prohodit některá písmena předtím, než se se dostanou na šifrovací disky. Když se propojí a a b, tak a se šifruje jako b a naopak. Propojovacích kabelů bylo šest‐tudíž šest možností přehození písmen.
Celkový počet možných nastavení Enigmy byl tedy závislý na: 1)nastavení disků‐263=17 576 2)Uspořádání disků‐3!=6 3)Nastavení propojovací desky‐100 391 791 500 17 657 x 6 x 100 391 791 500 = 1,06 x 1016 Bezpečnost navíc zvyšovali ještě další součástky, např. prstenec. Odolnost stroje spočívá v kombinaci propojovací desky s otáčivými disky. Samotná propojovací deska zajišťuje velký počet možných klíčů, avšak nedělá nic jiného než monoalfabetickou substituci. Tudíž snadno podlehne frekvenční kryptoanalýze. Na druhou stranu disky produkují jen 17 576 možných kombinací, které lze teoreticky v relativně krátkém čase vyzkoušet. Avšak díky pravidelnému otáčení odolá šifra právě frekvenční analýze. Díky těmto vlastnostem měli němci zato, že jsou zprávy šifrované Enigmou nerozluštitelné.
Luštění Enigmy Roku 1926 začali Němci posílat depeše šifrované Enigmou. Američané, Francouzi ani Angličané nebyli schopni tuto šifru vyluštit. Navíc nehrozilo přímé vojenské nebezpečí tudíž nebyla luštění kladena vysoká priorita. Ve stejné situaci však v té době nebylo Polsko. Z východu bylo ohrožováno Ruskem, šířícím komunismus. Na západě bylo Německo, které chtělo získat zpět území ztracená v 1.sv.válce. To nutilo Poláky, aby založili šifrové oddělení zvané Biura Szyfrow. Ve třicátých letech se Poláci dostali k plánům Enigmy. Dostali je od Francouzů, kterým je prodal neloajální Němec H.T.Schmidt.
Luštění Enigmy mělo ještě jeden háček. Samotné šifrování probíhalo pomocí denních klíčů, které operátoři používali k nastavení stroje. Tento způsob komunikace by však moc bezpečný nebyl. Ve větším počtu zpráv zašifrovaných stejným klíčem by se dalo nalézt zprávy se stejným počtem znaků. To by ale kryptoanalytikům umožnilo tyto zprávy porovnávat a pomocí vhodných metod nalézt klíč. Proto se denním klíčem šifroval pouze třímístný unikátní klíč, který určoval nastavení disků pro každou konkrétní zprávu zvlášť. Aby se předešlo chybám, způsobenými překlepy a radiovým spojením, psal se třímístní klíč dvakrát za sebou. Při zachycení 1000 depeší by měli kryptoanalytici k dispozici jen 6000 náhodných písmen zašifrovaných stejným klíčem, což by k vyluštění porovnáváním nevedlo. Opakování unikátního klíče však nevedlo jen ke snížení počtu chyb v dešifrování, nýbrž vedlo taky k rozluštění šifry. Do Biuro Szyfrow se dostal mladý Polský matematik Marian Rejewski. Ten se při luštění Enigmy soustředil na zmiňované opakování unikátního klíče. Všiml si zákonitostí, které z opakování plynou. Například byl‐li denní klíč UKLUKL a zašifrován byl jako HRJZND, dokázal Rejewski určit, že písmena H,Z vznikla zašifrováním stejného písmene, akorát posunutého o tři kroky na prvním disku. Z velkého množství zpráv, které Rejewski zkoumal, pak dokázal sestavit tabulku závislostí jednotlivých písmen. Ta mohla vypadat například takto: 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 F Q H P L W O G B M V R X U Y C Z I T N J E A S D K Nyní uspořádal písmena do cyklů podle závislostí. A→F→W→A B→Q→Z→K→V→E→L→R→I→B C→H→G→O→Y→D→P→C J→M→X→S→T→N→U→J Délka cyklů 4,9,7,7 Všiml si toho , že se každý den tyto cykly mění. Měnila se i jejich délka. Jedna věc ale byla podstatná. Při změně písmen na propojovací desce se délka cyklů nezmění. Vyměníme‐li např.K s L dostáváme A→F→W→A B→Q→Z→L→V→E→K→R→I→B C→H→G→O→Y→D→P→C J→M→X→S→T→N→U→J Délka cyklů je opět 4,9,7,7 Tím Rejewski přišel na zcela klíčovou metodu při luštění Enigmy. Díky tomu, že se délka cyklů nemění, zúžil počet možných denních klíčů z 1,06 x 1016 na „pouhých“ 105 456(17 576 x 6) tím, že v podstatě
oddělil šifrování propojovací desky od šifrování disků. Stále ještě zbývalo vyřešit problém které ze 100 000 možných nastavení disků je to správné. Rejewski postupoval tím to způsobem. Na základě ukradených plánů Enigmy odzkoušel všech 105 000 možných nastavení a sestavil z nich katalog. Do katalogu zahrnul i cykly pro 2.s 5. a 3.s 6. písmenem. Tvorba katalogu zabrala celý rok. Poté však mohl Enigmu začít luštit. Když dostal do rukou denní zprávy, sestavil z prvních 6 písmen každé z nich tabulku závislostí. Z té vytvořil cykly (1.a 4.,2.a 5.,3.a 6), nahlédl do katalogu a věděl jaké nastavení disků má smysl zkoušet. Teď už stačilo vyluštit část zašifrovanou spojovací deskou. To už bylo vcelku jednoduché, neboť propojovací deska mohla zaměnit jen 6 dvojic písmen. Na základě logické úvahy dokázal Rejewski tyto dvojice postupně eliminovat a získat tak otevřený text. Němci čase změnili způsob vysílání zpráv a starý katalog byl Rejewskému k ničemu. Proto vytvořil mechanický stroj zvaný „bomba“. Bomb bylo 6 (každá s jedním možným nastavením disků) . Bomba prověřovala všech 17576 možných nastavení Enigmy dokud nenarazila na to správné. Hledání klíče zabralo asi 2 hodiny. Na konci roku 1938 Němci zvýšili bezpečnost Enigmy tím, že přidali další dva disky. Z šesti možných uspořádání jich rázem bylo 60. Na rozluštění klíče bylo potřeba 10krát více bomb než dosud. Díky omezenému rozpočtu ale neměli Poláci prostředky na jejich vybudování a ztratili tak schopnost číst Německé zprávy. Polákům se naštěstí podařilo podělit se o úspěchy v luštění Enigmy s Francouzi a Angličany, když těsně před zahájením 2.sv.války propašovali do Paříže a Londýna plány bomb a repliky Enigmy. Během války Angličané luštili německé zprávy v Bletchy park, kde zdokonalili polské metody. V anglickém Bletchy luštili Enigmu v síti Luftwaffe. Při hledání denních klíčů se nespoléhali jen na výsledky bomb, ale také využívali chyb, které šifréři nevědomky dělali. Šifréři často používali k nastavení stroje písmena, která byla vedle sebe na klávesnici(NBV, ASD) nebo dokonce tři stejná písmena. Zároveň Německé velení ve snaze zvýšit bezpečnost šifrování zavedlo pravidlo pro denní výměnu disků. Dva dny po sobě se tak jeden disk nesměl nacházet na stejném místě. Chtěli tím docílit toho, že dva dny po sobě nebudou zprávy zašifrované stejným způsobem, což by mohlo vést k rozluštění. Paradoxně to luštění naopak pomohlo. Jestliže byla rozluštěna nastavení předchozího dne, nebylo nutné zkoumat všech 60 možných nastavení, ale pouze 12. Neboť každá část německého vojska měla svoje kryptologické oddělení a tato oddělení spolu nespolupracovala , měli pozemní, námořní i letecké jednotky svůj vlastní způsob a pravidla šifrování. Námořníci nepoužívali 5, ale dokonce 8 výměnných disků, čímž zvedli počet možností na 336. V pozdější fázi války začalo námořnictvo používat dokonce čtyřdiskovou verzi Enigmy. Námořní Enigmu se s většími úspěchy luštit nepodařilo.Tak jedinou možností jak číst nepřátelské zprávy bylo krást Němcům jejich denní klíče, ale tato kapitola už nepatří do oblasti kryptologie. Enigma nebyla jediným šifrovacím strojem používaným za války. Němci například používali stroje s názvy SZ‐40, SZ‐42 založené na binárním šifrování. Japonci používali stroj zvaný Purpur(Purple), úspěšně vyluštěný Američany. Šifrovacími stroji nebyly šifrovány všechny zprávy, ale jen ty nejdůležitější. U jednotek od pluků níže se používala ruční dvojitá transpozice.
Šifrování za 2.sv.války USA‐ Navaho Američané využili při šifrování ve válce jeden z Amerických indiánských kmenů‐ kmen Navaho. Dialekt Navaho lze jen těžko rozeznat, pro neznalé posluchače úplně nesrozumitelný. Navahům dokonce nerozuměli ani jiné indiánské kmeny. Komunikace pak probíhala tak, že se zpráva sdělila Navahovi, ten ji přeložil a odvysílal vysílačkou. Na druhé straně byl další příslušník kmene a zpětně zprávu přeložil. Japonci nikdy zprávy nerozluštili. V navažském jazyce ale neexistovala pojmenování pro moderní vojenskou techniku. Proto byl vytvořen kód Navaho, který popisoval letadla a lodě pomocí kódových slov v Navažštině. Například Bojové letadlo bylo Kolibřík(da‐he‐tih‐hi) nebo Ponorka se řekla jako železná ryba(Bush‐lo)
SSSR‐jednorázové klíče V Rusku se za války používaly pro důležitou korespondenci jednorázové klíče‐jediná 100% bezpečná metoda šifrování. Po válce však sovětští šifréři udělali obrovskou chybu. Zašifrovali zprávy pomocí klíčů, které byly už jednou použity za války. Této chyby si všiml Američan Meredith Gardner. Podařilo se mu zprávy rozluštit a Američane se např. dozvěděli krycí jména zhruba 200 sovětských agentů.
Británie‐Naval cypher, Playfair Britské námořnictvo používalo ke komunikaci kódy Naval cypher. Ty se němcům úspěšně dařilo luštit a tak mohli téměř po celou dobu války číst Britské korespondence. Až verze Naval cipher no.5, která byla používána od června 1943 nebyla rozluštěna.
Playfair‐šifra Playfair byla pojmenována po anglickém baronovi Lyonu Playfairovi. Britská armáda ji používala v búrských válkách a v první světové válce. Ve druhé tuto šifru používala britská SOE‐special operations executice‐správa pro zvláštní operace. V upravené podobě šifro používala i německá armáda. Princip‐zvláštností je, že Playfair nešifruje jednotlivá písmena, ale dvojice písmen. Vytvoří se čtverec 5x5 pomocí klíčového slova. Např. pomocí hesla „příklad playfair“ by čtverec vypadal následovně.(díky tomu, že je písmen 25, tak se písmena I a J píší do stejné buňky nebo se vynechá písmeno, které se v daném jazyce téměř nevyskytuje‐pro češtinu X,Q) Vepíšeme do tabulky 5x5 postupně po řádcích heslo (opakující se písmena opět vynecháváme) a tabulku doplníme o další písmena dle abecedy, která v heslu nejsou obsažena. P A C N U Chceme zašifrovat
R D E O V
I/J Y G Q W
K F H S X
L B M T Z
Ostravská univerzita Nejprve text určený k šifrování rozdělíme do dvojic. OS TR AV SK AU NI VE RZ IT AX Písmeno X se doplní v případě lichého počtu písmen. Zároveň v případě, že by se v textu vyskytla dvě stejná písmena , druhé by se nahradilo X(SS by se psalo jako SX) Nyní nastanou tři možnosti: 1. Dvojice písmen leží obě v jiném řádku a sloupci. Jako šifru se berou písmena, která doplňují tato dvě na obdélník. Pro TR by šifra byla OL. (Nikoli LO)‐jako první se šifruje písmeno, které je dřív i v šifrovaném textu. P A C N U
R D E O V
I/J Y G Q W
K F H S X
L B M T Z
2. písmena jsou ve stejném řádku. Bereme písmena, která ve čtverci leží vpravo vedle písmen šifrovaného textu OS‐QT 3.písmena jsou ve stejném sloupci Vybírají se písmena pod SK‐XF Výsledný text tedy vypadá: QT OL DU XF CP QP RO LV LQ FU Zpráva se ještě rozdělí např. Do pětic: QTOLD UXFCP QPROL VLQFU Dešifrování probíhá přesně obráceně. Text se zardělí do dvojic písmen a v jiných řádcích a sloupcích se doplňují na obdélník. Ve stejných řádcích se berou písmena vlevo a ve stejných sloupcích nad danými písmeny.
Československé šifrování Za 2. sv. války bylo potřeba komunikace mezi domácím odbojem v Praze a zejména Londýnem. Ale také spojení mezi ostatními městy, kde působili Čechoslováci, Paříž, Istanbul, Veršava, Moskva. V Londýně se ujalo šifrování TTS(transpozice, transpozice, substituce). Dvojitá transpozice se dělala pomocí hesel, na kterých byly obě strany dohodnuty. Sady hesel se po nějaké době měnily. Hesla byla očíslovaná čísly 0‐9 a R. Pro šifrování daný den se použila hesla podle data. Např. 15. v měsíci se pořadě použila hesla 1 a 5. Následná substituce probíhala tak, že každý znak se nahrazoval jednoduše pomocí substituční abecedy(ta měla 45 znaků; a‐ž,.,?,‐,/ ,0‐9). Substituční abeceda se
navíc tvořila také podle data v měsíci‐15.února byla abeceda A‐15, B‐16,…,9‐13,0‐14. Chceme zašifrovat zprávu Ostravská univerzita. Je 22.srpna, takže použijeme klíč 2 a R. 2 je Beneš, R je Masaryk.
1.transpozice
B 1 O V N Z
E 2 S S I I
N 4 T K V T
E 3 R Á E A
Š 5 A U R
Výsledný text‐OVNZSSIIRÁEATKVTAUR
2.transpozice M 4 O I V
A 1 V R T
S 6 N Á A
A 2 Z E U
R 5 S A R
Y 7 S T
K 3 I K
Dostáváme text VRTZEUIKOIVSARNÁAST
3. substituce‐substituční tabulku číslujeme od 22 A 22 N 37 Ž 07
B 23 O 38 . 08
C 24 P 39 ? 09
Č 25 Q 40 ‐ 10
D 26 R 41 / 11
E 27 Ř 42 1 12
Ě 28 S 43 2 13
F 29 Š 44 3 14
G 30 T 45 4 15
H 31 U 01 5 16
I 32 V 02 6 17
J 33 W 03 7 18
K 34 X 04 8 19
L 35 Y 05 9 20
M 36 Z 06 0 21
Výsledná šifra bude vypadat: 02414506270132343832024322413722224345 Šifra se ještě rozdělila do bloků po pěti. V případě, že nebyl počet čísel dělitelný pěti, dopsala se nakonec libovolně čísla 5‐9
02414 50627 01323 43832 02432 24137 22224 34598 Československé šifrování bylo za války na velmi špatné úrovni. Představa, že dvojitá transpozice je nenapadnutelná frekvenční analýzou a tudíž nevylučitelná byla mylná. Čeští šifréři chybovali, protože posílali stejně dlouhé zprávy zašifrované týmž klíčem. Jejich porovnáváním pak byli Němci schopni vyluštit denní klíče a tím pádem i zprávy. Další chyba se stávala při výměně starých klíčů za nové. Nové klíče se zasílali vzduchem zašifrované pomocí starých hesel, nikoli ,jak by se správně mělo dělat, pomocí kurýrů. Němci, kteří znali stará hesla už v podstatě nemuseli zprávy luštit, jednoduše je dešifrovali, protože znali klíče.
Šifrování veřejným klíčem S příchodem elektroniky a výpočetní techniky byla stále větší potřeba nutnosti šifrování. Proto byly vytvořeny šifrovací systémy založené na binárních kódech. Jejich složitost zaručovala téměř 100% bezpečí, protože počet možných šifrovacích klíčů byl u daných systémů natolik vysoký, že nebylo možné v reálném čase nalézt správný klíč ani s nemodernější výpočetní technikou. Nastal však jeden problém a tím byla distribuce klíčů. Pokud by chtěl např.banka bezpečně komunikovat s klientem, musela by s ním mít domluvený nejenom šifrovací systém, ale taky bezpečnostní klíč. Tento klíč by však musela bezpečně ke klientovi dopravit. Klíče se posílaly pomocí kurýrů. Tento způsob distribuce klíčů však byl neúnosný jak z ekonomického tak z bezpečnostního hlediska.
Veřejný klíč Cílem bylo vytvořit systém, který by nevyžadoval výměnu klíčů. Pro ilustraci budeme používat osoby A(Alice) a B(Bob), kteří se snaží o komunikaci. Představme si situaci, kdy Alice pošle Bobovi informaci ve schránce s mechanickým zámkem. Klíč od něj má jen Alice. Bob však schránku neotevře, protože nemá klíč, ale dá na schránku další, svůj zámek a pošle schránku zpět Alici. Ta na schránce následně odemkne svůj zámek a když znovu pošle informace Bobovi, je na ní už jen jeho zámek, který je schopný otevřít. Takto si oba vyměnili zprávu, bez nutnosti vyměnit si klíče. Problém byl v tom nalézt nějakou matematickou interpretaci této myšlenky. V roce 1976 přišli s revoluční myšlenkou dva kryptografové Whitfield Diffie a Martin Hellman. Jejich metoda je založena na takzvaných jednosměrných funkcích. Jednosměrná funkce je taková fce, která lze jednouše vypočítat, avšak její inverze, tedy obrácená funkce je mnohonásobně časově náročnější. Pro příklad obousměrné funkce můžeme uvažovat trojnásobek nebo druhou mocninu. Máme‐li číslo 6, tak trojnásobek je 18. Inverzní funkce k násobení je dělení, takže jednoduše můžeme opačně vypočítat 18/3=6. Jako jednosměrnou funkci můžeme uvažovat například násobení ve zbytkových třídách modulo N. Když si vezmeme funkci trojnásobku ve zbytkových třídách modulo 7, tak 3*6=18(mod7)=4. Jestliže však máme vypočítat rovnici 3*x(mod7)=4, nelze výsledek určit stejně rychle. Výsledek můžeme odhadnout nebo můžeme prověřit všechny možné varianty. Časová náročnost inverzní operace je však mnohem delší než vlastní operace.
x 0 1 2 3 4 5 6 3x 0 3 6 9 12 15 18 3x(mod7) 0 3 6 2 5 1 4 Diffie a Hellman přišli na jednosměrnou funkci , která umožňovala výměnu klíče bez přímého kontaktu mezi Alicí a Bobem. Funkcí byla αx mod p a princip výměny klíče vypadal následovně. Na začátku se veřejně Alice a Bob domluví na dvou hodnotách α a p, kde p je prvočíslo a α náleží Zp(2<=α<=p‐2). Poté si Alice i Bob zvolí své vlastní tajné číslo(z,y) a vypočítají hodnotu funkce pro toto číslo(A=αz mod p, B=αy mod p). Tuto hodnotu následně pošlou, opět veřejně, druhé straně. Oba dva potom na základě přijaté hodnoty vypočítají šifrovací heslo K podle rovnice K= Ay mod p[resp. K= Bz mod p]. Tak Alice a Bob získali tajné heslo, aniž by si ho mezi sebou přímo vyměnili. Příklad: α=5, p=7. Alice si zvolí z=4 Bob y=3. Alice vypočítá hodnotu A= αz mod p= 54 mod 7= 625 mod 7=2. Bob vypočítá hodnotu B= αy mod p= 53 mod 7= 125 mod 7=6. Nyní oba dva vypočítají klíčové heslo K. K= Ay mod p= 23 mod 7=8mod7=1. K= Az mod p = 64 mod 7=1296 mod 7= 1. Alice a Bob dospěli ke stejné hodnotě 1. Z pohledu někoho kdo tuto komunikaci odposlouchá je téměř nemožné přijít na šifrovací heslo. Veřejně jsou známá čísla α,p,A,B, avšak k výpočtu hesla je nutné znát z a y. Jde o úkol vypočítat logαA mod p=z(logαB mod p=y). Výpočet této inverzní funkce, obzvláště při velkých číslech je nesmírně obtížný. Tento úkol se nazývá „discrete logarithm problem“. Ačkoliv tento princip mohl vyřešit problém distribuce klíčů, nestalo se tak. Komunikace například nemůže běžně probíhat mezi lidmi na druhém konci světa, protože pro komunikaci je nutné aby obě strany byly online a mohli si tak vyměňovat informace bez čekání na odpověď.
Asymetrické klíče Diffie později přišel s myšlenkou takzvané asymetrické šifry, nedokázal ji však realizovat. Symetrická šifra je taková, že dešifrování je přesným opakem šifrování. U asymetrické šifry nelze ani při znalosti šifrovacího klíče zprávu dešifrovat. K tomu je zapotřebí zvláštní dešifrovací klíč. Při komunikaci Alice vystaví veřejně svůj šifrovací klíč‐veřejný klíč. Sama však uchová v tajnosti svůj soukromý klíč‐ dešifrovací. Bob může zprávu určenou Alici zašifrovat pomocí jejího veřejného klíče, avšak sám již nebude schopen zprávu dešifrovat, protože nezná dešifrovací klíč. Vroce 1977 pánové Rivest, Shamir a Adleman vymysleli asymetrickou šifru známou jako RSA. Rsa je založená na jednosměrné funkci součinu dvou prvočísel. Vynásobení dvou prvočísel je časově nenáročná operace. Naopak faktorizace, nalezení prvočinitelů ze součinu dvou prvočísel je velice těžká a hlavně časově náročná úloha. RSA funguje na tomto principu. Alice si zvolí dvě náhodná hodně velká prvočísla p a q. Pro ilustraci zvolíme čísla menší, např.p=11 a q=13. V reálu se používají čísla daleko větší, v řádech 10150. Alice si poté vypočítá součin svých čísel n=p*q, v našem případě n = 11*13=143. Číslo n bude sloužit jako Alicin veřejný klíč, který veřejně publikuje. Podstata šifry je
v tom, že, i když někdo zná n, není v reálném čase možné zjistit z něj hodnoty p a q nutné k dešifrování zprávy. Dále vypočítá hodnotu Ф=(p‐1)*(q‐1)=n+1‐p‐q. Ф=10*12=120. Poté si zvolí náhodné číslo e(1<e<Ф), takové, že gcd(e,Ф)=1‐nesoudělné s Ф. Zvolíme e=7.Jako Alicin veřejný klíč bude sloužit dvojice čísel (n,e)‐(143,7). Kdokoliv bude chtít poslat Alici zprávu zašifruje jí následovně. Chceme zašifrovat písmeno F. V Ascii kódu je F reprezentováno jako 1000110 tedy 70 v desítkové soustavě. Označíme si otevřený text jako m=70. Zprávu zašifrujeme pomocí funkce f: c=me mod n. c=707 mod 143=60. Kdokoliv chce Alici poslat zašifrované písmeno F, pošle jí číslo 60. Alice může zprávu dešifrovat, protože od začátku zná čísla p a q. Nejdříve si musí vypočítat hodnotu d, takovou, že ed=1 modФ. Výpočet se provede pomocí Euklidova algoritmu. d se tedy rovná 103. Nyní může Alice provést inverzní operaci f‐1=m= cd mod n= 60103 mod 143=70. Což představuje původní písmeno F. Metoda veřejného klíče RSA umožňuje zároveň jednu důležitou věc a tím je identifikace. Představme si situaci, kdy Alice chce poslat Bobovi zprávu. Zašifruje ji Bobovým veřejným klíčem a odešle. Jakou má však Bob jistotu, že jde právě o zprávu od Alice? Jednosměrná funkce umožní Alici svou zprávu podepsat. Alice zná Bobův veřejný šifrovací klíč fB (nB,eB) a také svůj dešifrovací klíč fA‐1 (nA,dA). K zašifrování podpisu P použije Alice funkci fBfA‐1(P). Bob použije k dešifrování nejdříve svůj dešifrovací klíč fB‐1. Dostává fB‐1 fBfA‐1(P)= fA‐1(P). Nyní aplikuje Alicin veřejný klíč fA fA‐1(P)=P. Jelikož fA‐1 nemá nikdo jiný než Alice, může si být Bob jistý, že zpráva není podvrh.
Budoucnost Úkolem pro kryptoanalytiky nyní zůstává nalézt vhodné metody pro faktorizaci velkých čísel, či nalezení diskrétního logaritmu. Je možné, že už nějaký kryptoanalytik přišel na metodu k luštění například RSA ale nemohl svůj objev zveřejnit, jak už se tomu v historii několikrát stalo. Pokroky v oblasti kryptografie jsou většinou státními tajemstvími, která se zveřejňují s odstupem i desetiletí nebo nikdy. Další pomocí kryptoanalytiků by mohly být kvantové počítače, které by byly schopny vyluštit v současnosti nejpoužívanější šifrování. S nimi by však přišlo i kvantové šifrování a boj mezi kryptografy a kryptoanalytiky tak bude pokračovat vždy.
