Masarykova univerzita v Brně Přírodovědecká fakulta Diplomová práce Kryptografie v systému Maple Vedoucí diplomové práce: Mgr. Michal Bulant, Ph.D. Vypracoval: Jiří Pospíšil Prohlašuji, že jsem předloženou diplomovou práci vypracoval samostatně, pod vedením Mgr. Michala Bulanta, Ph.D., a veškeré zdroje, ze kterých jsem při vypracování práce čerpal, řádně cituji. V Brně, 15. května 2009 . . . . . . . . . . . . . . . . . Děkuji vedoucímu diplomové práce Mgr. Michalovi Bulantovi, Ph.D. za cenné připomínky a čas, který věnoval konzultacím, a také za poskytnutou odbornou literaturu. Obsah 1 Úvod 1 2 Historie kryptografie a její vývoj 2 2.1 Úvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Vymezení kryptografie . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3 Historie kryptologie . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.4 Historie využití strojů k šifrování a dešifrování zpráv . . . . . . . 8 3 Algebra v Maple 10 3.1 Dělitelnost v oboru celých čísel . . . . . . . . . . . . . . . . . . . 10 3.2 Generování náhodných čísel . . . . . . . . . . . . . . . . . . . . . 11 3.3 Práce s prvočísly . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.4 Diofantické rovnice . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.5 Modulární aritmetika . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.6 Kongruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.7 Vybrané úlohy z teorie čísel . . . . . . . . . . . . . . . . . . . . . 16 3.7.1 Eulerova funkce (n) . . . . . . . . . . . . . . . . . . . . . 17 3.7.2 Primitivní kořeny . . . . . . . . . . . . . . . . . . . . . . . 18 3.7.3 Výpočet diskrétního logaritmu . . . . . . . . . . . . . . . 19 4 Problém distribuce klíčů 21 4.1 Historie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 Algoritmus Diffie-Hellman-Merkle . . . . . . . . . . . . . . . . . . 23 4.2.1 Idea algoritmu . . . . . . . . . . . . . . . . . . . . . . . . 29 4.2.2 Implementace . . . . . . . . . . . . . . . . . . . . . . . . . 30 5 Kryptografie s veřejným klíčem 33 i Obsah ii 6 Šifrování RSA 35 6.1 Historie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6.2 Idea algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.3 Postup při šifrování RSA . . . . . . . . . . . . . . . . . . . . . . 37 6.4 Implementace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.5 Útoky na RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 6.5.1 Útok hrubou silou, faktorizace velkých čísel . . . . . . . . 43 6.5.2 Man-in-the-middle attack . . . . . . . . . . . . . . . . . . 44 7 Digitální podpis 50 7.1 Postup při digitálním podepisování zprávy pomocí RSA . . . . . 51 7.2 Implementace digitálního podpisu pomocí RSA . . . . . . . . . . 51 8 Programování mapletů 55 9 Závěr 57 Literatura 58 Příloha 59 10 Příklady mapletů 60 10.1 Diffie-Hellman-Merkle . . . . . . . . . . . . . . . . . . . . . . . . 60 10.2 RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 10.3 RSA ­ Man-in-the-middle-attack . . . . . . . . . . . . . . . . . . 64 10.4 RSA ­ Digital signature . . . . . . . . . . . . . . . . . . . . . . . 67 Kapitola 1 Úvod Cílem této práce je objasnit čtenáři se středoškolskými znalostmi matematiky základní principy kryptografie s veřejným klíčem. Proto je také v práci kladen velký důraz na poutavé podání vysvětlované problematiky s cílem vzbudit zájem o kryptografii a teorii čísel. Z tohoto důvodu jsou v práci popsány historické souvislosti vzniku a využívání jednotlivých šifer, algoritmů a postupů i stručná historie kryptologie jako celku. Aby si čtenář mohl nově získané vědomosti empiricky ověřit, jsou součástí práce interaktivní maplety, na nichž si může ověřit funkčnost probraných algoritmů a postupů. V práci jsou též uvedeny použité procedury a činnost mapletů je rozebrána a krok za krokem popsána. Z důvodu usnadnění pochopení v mapletech použitých příkazů, je v práci zařazena kapitola věnující se řešení základních algebraických úloh a vybraných úloh z teorie čísel. Součástí práce jsou též mapleovské worksheety, které obsahují veškeré výpočty uvedené v práci, takže čtenář si výpočty může projít a ověřit bez zdlouhavého opisování hodnot. 1 Kapitola 2 Historie kryptografie a její vývoj 2.1 Úvod Kryptografie je vědou, kterou halí už od pradávna jisté mysterium. Toto mysterium má dvojí původ. První je historický a tím druhým je fakt, že používala a používá matematické či logické principy, které byly často na samé hranici lidského chápání. Je tedy atraktivní a její motivy jsou často použity v historických knihách nebo románech. Kryptografie totiž od počátku svých věků sloužila jak mocným, tak i utlačovaným. Během válek byla součástí vojenských strategií a použití šifry či její prolomení často významně ovlivnilo světové dějiny. V dnešní době známe kryptografii jako vědu, která slouží například k zabezpečení citlivých elektronických dat, elektronickým podpisům bankovních převodů nebo jako hráz mezi útočníkem a informacemi, bez které by bylo možno tyto informace zneužít. Takřka stejnou rychlostí, jakou se vyvíjely kryptografické algoritmy, kterými se zprávy šifrovaly, se pochopitelně rozvíjela i kryptoanalýza, díky níž bylo možné zachycenou zprávu neautorizovaně dešifrovat. To vedlo ke stále většímu využití matematiky v kryptografii a k důkazům kdy a za jakých okolností je možné či nemožné šifru určitého typu prolomit. S nástupem počítačů bylo nutno vymýšlet stále sofistikovanější algoritmy, což vyústilo v jakousi skrytou válku mezi matematikou a výpočetní technikou na poli kryptografie a kryptoanalýzy. Tak se stalo, že od primitivní kombinatoriky ve starověku jsme se dostali přes moderní algebru a teorii čísel až k teorii eliptických křivek. Zatím vítězí matematika, která krom lidské inteligence nezná hranic. Nejsme však ještě zdaleka u konce vývoje. Očekávaný nástup kvantových počítačů by mohl přinést nárůst výpočetního výkonu strojů do té míry, že by bylo možno faktorizovat i opravdu velká čísla. To by v praxi mohlo znamenat, že při použití současné asymetrické kryptografie by dešifrování hrubou výpočetní silou představovalo jen ,,o něco delší výpočet než samotné šifrování. Tento hypotetický výkon kvantového počítače motivuje vědce, kteří v současné 2 Kapitola 2. Historie kryptografie a její vývoj 3 době rozvíjejí algoritmy šifrování za pomocí nástrojů kvantové fyziky a přenosu šifrovaných informací na základě Heisenbergova principu neurčitosti. V následující kapitole se budeme dále věnovat zařazení kryptografie do kontextu okolních věd a uvedeme její historický vývoj od starověku až do současnosti. Dále provedeme diskuzi o prolomitelnosti současných šifer a uvedeme historii výpočetních strojů, které se k tomuto účelu používaly a používají. 2.2 Vymezení kryptografie Kryptografie jako obor je součástí obecnější kryptologie (řecky kryptós ­ skrytý, lógos ­ smysl, nauka), což je věda zkoumající utajení a zabezpečení komunikace. Zahrnuje kryptografii, kryptoanalýzu a často i steganografii. Kryptografie (řecky: kryptós ­ skrytý, gráphein ­ psát) zkoumá, jak zašifrovat a následně rozšifrovat zprávu. Jednotlivé strany jsou schopny takto mezi sebou komunikovat pouze pomocí speciální znalosti. Nejčastěji se využívá znalost hesla nebo klíče, pomocí něhož lze zprávu zašifrovat/dešifrovat. Kryptoanalýza (řecky: kryptós ­ skrytý, analýein ­ uvolnit) se zabývá rozšifrováním zprávy ze zašifrovaného stavu bez znalosti klíče. Využívá slabin použité šifry a je jakýmsi opakem kryptografie. Steganografie (řecky: steganós ­ schovaný, gráphein ­ psát) se věnuje utajení komunikace prostřednictvím ukrytí zprávy1. Zpráva je ukryta tak, aby si pozorovatel neuvědomil, že komunikace vůbec probíhá. Zachycení zprávy se rovná prolomení steganografie. Aby ani v takovém případě nedošlo k prozrazení obsahu zprávy, zpravidla se steganografie kombinuje s kryptografií (šifrováním). V dnešní době, kdy se těžiště všeho lidského konání přesouvá pozvolna do elektronického kybersvěta, zajišťuje kryptografie čtyři nejdůležitější služby, které při práci s citlivými daty musíme mít na paměti. 1. Důvěrnost, která umožňuje, aby zpráva (obecně informace) byla čitelná pouze autorizovaným stranám. 2. Integrita dat, která zajišťuje možnost ověření, zda nebyla informace pozměněna třetí stranou. 3. Autentizace, díky které jsme schopni ověřit identitu proklamované entity dat. Využívá službu integrity dat. 4. Nepopiratelnost, která věrohodným způsobem dokazuje akce komunikujících stran, aniž by ji tyto strany mohly vyvrátit (např. u soudu). 1 Je otázkou, zda-li vůbec steganografii řadit do kryptologie, jelikož její základ je spíše sociální a psychologický. Jelikož však využívá i principy teorie informace a fyziky a uvádíme-li kryptologii jako vědu zkoumající utajení a zabezpečení komunikace, je toto zařazení korektní. Kapitola 2. Historie kryptografie a její vývoj 4 2.3 Historie kryptologie Nejstarší zmínka o použití kryptologie je zřejmě v Herodotových Dějinách. Je uvedeno, že v 5. století př. n. l. věznil král Darius řeckého tyrana2 Histiaea. Histiaeus potřeboval odeslat tajně zprávu svému zeti Aristagorovi do Anatolianu. Histiaeus nechal vyholit hlavu svému otrokovi (zřejmě to bylo vězení na úrovni) a na ni nechal zprávu vytetovat. Otrok se vydal na cestu teprve až mu vlasy dorostly natolik, že zprávu nebylo možno rozeznat. Díky této zprávě bylo započato v Milétu povstání proti Peršanům. Je-li pověst pravdivá, můžeme dnes říci, že Histiaeus byl prvním, kdo steganografii použil. Steganografie je zcela jistě věda využívající lidskou důmyslnost a proto bývá často pokládána za umění. Jedním z dalších oblíbených steganografických postupů bylo použití neviditelného inkoustu. Tuto metodu uvádí například Alexander Dumas starší ve svém románu Hrabě Monte Christo (1844­1845)3. Jeden z hrdinů jeho románu, Abbé Faria, našel závěť rodu Spadů jako záložku v knize, cenném breviáři, až několik set let poté, co bylo sídlo rodu Spadů roku 1498 prohledáno vrahy kardinála Cesara Spady. Poté ležela závěť 309 let nenalezena právoplatnými dědici. Až teprve roku 1807, kdy chtěl Abbé Faria použít záložku k zapálení svíce od krbu, všiml si tento knihovník posledního hraběte Spady, že se na papíru zjevují neobvyklé symboly. Objevil tak na závěti tajné písmo, které ztmavlo až při zahřátí listu a které udávalo polohu pokladu na ostrově Monte Christo. Tento poklad pak přinesl bohatství hlavnímu hrdinovi románu Edmondu Dant`esovi po jeho útěku z vězení. Dnešní steganografické metody jsou poněkud prozaičtější. Jedná se zejména o kódování zprávy do šumu nějakého zvukového souboru, zprávy ukryté do obrázku, případně o modulaci zprávy do nevyužitých bitů v počítačových datech. Jelikož se jedná o digitální data, mluvíme zde o tzv. digitální steganografii. Rovněž nejstarší doložená kryptografická metoda má svůj původ v antickém Řecku. V 7. století př. n. l. používali ve Spartě první známou mechanickou pomůcku na šifrování ­ skytalé. Doslovně to znamená palici, kterou byli vyzbrojeni sparťanští stratégové na vojenských výpravách. Skytalé se používala na doručování tajných zpráv takovým způsobem, že se na palici navinul kožený proužek, na který se později napsala zpráva. Po napsání se proužek svinul a napsaná zpráva se dala přečíst zase jen po navinutí na palici o stejném průměru. Roku 360 př. n. l. napsal řecký stratég Aineiás ze Stymfálu v Arkadii, zvaný Taktikos, dílo Taktika o vojenském umění. V části Poliorketika uvádí 16 různých šifrovacích metod. Jedna z těchto uvedených metod je založena na podobném principu jako dnešní Morseova abeceda, jiná zase používá nahrazení znaků řecké 2 Tyran (řecky tyrannos) je hlavou státního zřízení tyrannis, typického pro období 600­200 př. n. l. v antickém Řecku. Tyranida bývá chybně zaměňována s tyranií, ale termín sám znamená ,,vládu jednoho člověka , zatímco ,,tyranie je krutovláda. Označení tyran je dnes obecně chápáno pouze ve svém negativním významu, zatímco v dobách antického Řecka to bylo běžné označení vládce. 3 Zásluhu na tomto románu měl i profesor historie August Maquet. Kapitola 2. Historie kryptografie a její vývoj 5 Obrázek 2.1: Skytalé abecedy čísly. Obě tyto myšlenky byly o několik set let později dále úspěšně rozvíjeny. Z dalších antických metod uveďme Polybiův loučový dalekopis. Byl to asi první prakticky používaný ,,telegrafický kód . Byl založený na tabulce písmen, kde mělo každé písmeno své souřadnice. Vysílání probíhalo po písmenech tak, že na viditelném místě stáli za dvěma neprůhlednými panely loučonosiči, kteří po úvodním pohotovostním signálu strany ,,na příjmu začali vysílat signály tak, že nejprve se nad levým panelem objevil počet loučí odpovídající pořadovému číslu sloupce, ve kterém se nacházelo vysílané písmeno, a následně se nad pravým panelem objevil počet loučí odpovídající číslu jeho řádku. Tímto způsobem byla zpráva po písmenech odeslána. V antickém Římě nebyly podmínky pro šifrování právě příznivé. Římané preferovali ochranu listin pečetěním. Samotné slovo šifra k nám přišlo od Arabů (as-sifr), kteří jej přeložili od starověkých Indů z jejich sanskrtského označení sunya neboli prázdný, používaného též pro nulu. Francouzština přejala toto slovo jako chiffre. Od těch dob slovo cifra zdomácnělo i u nás a je používáno pro označení všech číslic při zápisu čísla. První a na dlouhou dobu i poslední výraznější zápis Říma do dějin kryptologie byl prostřednictvím Gaia Julia Caesara. Caesar v korespondenci při některých příležitostech používal jednoduchou substituční šifru, ve které každé písmeno nahradil písmenem, které v abecedním pořadí leží o tři písmena za ním. Na tehdejší poměry se jednalo o poměrně silnou šifru. Caesar svou šifru popisuje ve své knize Commentarii de bello Gallico (Zápisky o válce galské). Nebyl však prvním, kdo na tento způsob šifrování přišel. Myšlenka záměny písmen se už o něco dříve objevila v hebrejské metodě zvané ,,atbaš . Touto metodou jsou dokonce šifrovány některé texty v samotné Bibli, konkrétně ve Starém zákoně. Například překladatelé dlouho nemohli pochopit některé nesmyslné úryvky textu ve verši 51:1 z prorocké knihy Jeremjáš. Kapitola 2. Historie kryptografie a její vývoj 6 Teprve po dešifrování nesmyslného textu tak, že byla provedena symetrická náhrada prvního písmene hebrejské abecedy za poslední, druhého za předposlední atd., mohl být verš doplněn správným textem. Zatímco arabský svět znal využití frekvenční analýzy pro luštění jednoduché substituční šifry již v devátém století (viz např. práce Abú-Yusuf Ya'qub ibn Ishaq al-Kindiho (801­873)), západní Evropa tuto metodu objevila pravděpodobně až na začátku století čtrnáctého. Učenci proto tehdy začali hledat vylepšení v té době dominantního šifrovacího systému ­ jednoduché záměny. Tato mnohá zlepšení monoalfabetické šifry (jednoduché záměny) se soustředila na zakrytí statistických závislostí v šifrovaném textu, které prozrazují informace o otevřeném textu. Díky tomu se však proces šifrování a dešifrování stal velmi pracnou záležitostí. Zásadní objev v této oblasti přivedl na svět otec evropské kryptologie, všestranně vzdělaný člověk, stavitel, nadaný varhaník, filozof a básník Leon Battista Alberti (1404 ­ 1472). Alberti se na podnět papežského sekretáře Leonarda Data začal věnovat otázkám šifrování. Albertiho stručná práce napsaná v roce 1466 je první prací v západní Evropě věnovaná kryptoanalýze. Poznatek, že statistická analýza frekvence výskytu písmen v textu vede k rozluštění monoalfabetických šifer (prostá záměna písmen 1 : 1) ho vedl k objevu polyalfabetických šifer (záměna písmene za jiné, které se ale mění dle kontextu). Alberti doporučoval posunout abecedy vždy po 3 až 4 slovech. První tištěná kniha s kryptologickým obsahem vyšla roku 1606 a napsal ji roku 1499 benediktínský opat Johannes Trittheim (1452 ­ 1518). Trittheim zavedl a doporučoval vkládání klamačů do šifrovaného textu. Také v páté knize jeho šestisvazkového cyklu ,,Polygraphiace libri sex je zavedena tzv. ,,tabula recta , která je základem pro polyalfabetické šifry. Tato čtvercová tabulka v naší latince (26 písmen) vznikla tak, že každý následující řádek se zaměněnou abecedou vznikl posunutím abecedy o jedno písmeno. Šifrování se provádělo tak, že první slovo se zašifrovalo substitucí podle druhého řádku, druhé podle třetího řádku atd., až po posledním řádku se začalo opět od druhého. Pomocí prvního řádku se písmena šifrovala. V knize byl navržen i šifrovací systém Ave Maria, u kterého se text pomocí důmyslné záměny písmen za slova převedl na nevinnou modlitbu. Kniha však obsahovala příliš mnoho tajných informací a panovnické rody byly znepokojeny, že vyzrazuje choulostivé informace. Proto následně obvinily Trittheima z čarodějnictví a jeho dílo bylo roku 1609 umístěno na Index Librorum Prohibitorum (seznam zakázaných knih). Podobným způsobem postavila před soud církev i francouzského právníka a matematika Francoise Vi`eta (1540 ­ 1610), který luštil zašifrované depeše španělského krále a předával je francouzskému panovníkovi Jindřichu IV. Navarrskému. Trvalo několik let, než na to Španělé přišli. Nevěřili, že je možné jejich složitou záměnu rozluštit a žádali Svatou stolici, aby postavila Vi`eta před soud, protože musí být spojen s ďáblem. Roku 1553 zveřejnil Giovan Bastista Belaso rozšíření možnosti použití polyalfabetické šifry na základě principu ,,tabula recta tak, že navrhnul používání Kapitola 2. Historie kryptografie a její vývoj 7 klíčového slova nebo fráze. Při tomto postupu se řádky z tabulky neberou postupně, ale berou se jen řádky, které jsou určeny písmenem hesla. Právě v tomto místě začíná úloha a význam klíče v šifrovacích systémech. Výhoda klíče je zřejmá. Jeden a ten jistý systém můžeme podle potřeby variabilně měnit. Odtud už je jen pár kroků k myšlence vytvořit takový systém, ve kterém by byla klíčem samotná zpráva. Takový autoklíč navrhl Blaise de Vigenére ve své knize Traicté des Chiffres (Pojednání o šifrách), která vyšla roku 1586. Vigenérova myšlenka byla, že obě komunikující strany mají dohodnuto jedno jediné písmeno (případně slovo). Do vrchního řádku se pak napíše toto písmeno následované textem, který je třeba zašifrovat. Pod něj se do druhého řádku zapíše šifrovaný text a dále se postupuje Belasovým způsobem. Vigenér touto úvahou prakticky dokončil myšlenku Girolama Cardana (1501 ­ 1576), milánského fyzika, astronoma a matematika, který ve svém bohatém díle navrhuje mimo jiné použití autoklíče, avšak svou myšlenku neformuluje použitelným způsobem. Dnes je s Vigenérovým jménem spojena (kryptologicky) mnohem jednodušší šifra, kterou dostaneme z Belasova systému použitím jednoslovného periodického klíče. Girolamo Cardano se své slávy dočkal díky jiné publikované šifrovací metodě známé pod názvem Cardanova mřížka, která pracuje na principu utajení zprávy pomocí mřížky, do jejíchž otvorů je vepisován tajný text do čtvercové matice mezi nesouvisející (matoucí) znaky. Další z variant Cardanovy mřížky, respektive jeden z modelů transpozičních šifer, který z Cardanovy mřížky vychází, je tzv. otočná mřížka. Otočná mřížka je použita i v románu Julese Vernea Matyáš Sandorf (Nový Hrabě Monte Christo). Na téma polyalfabetických šifer by bylo možno sepsat celou knihu, avšak zastavme se nyní u jejího prolomení. Důstojník pruské armády Friedrich Wilhelm Kasiski zveřejnil roku 1863 v knize Die Geheimschrifften und die Dechiffrirkunst (Tajné šifry a umění je dešifrovat) obecnou metodu na řešení Vigenérovy polyalfabetické šifry (s periodickým heslem) pomocí vyhledání periody hesla a následným zredukováním na řešení řady monoalfabetických šifer. Šifry Vigenérova typu vzkřísil roku 1917 Gilbert S. Vernam, zaměstnanec americké firmy AT&T, který vymyslel polyalfabetický šifrovací stroj schopný používat jako klíč náhodný neopakující se kód. Do zařízení se vkládala děrná páska s otevřeným textem a současně i děrná páska, na které byl náhodně vyděrovaný klíč. Šifrovaný text vznikl sečtením příslušných bitů obou pásek modulo 2 následovně: 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0. Tento systém je bezpečný, pokud je klíč náhodný, je stejně dlouhý jako otevřená zpráva a použije se pouze jednou (tzv. systém One Time Pad). Tvrzení, že se jedná o absolutně bezpečný šifrovací systém za daných podmínek bylo dokázáno díky poznatkům Teorie informace, jejímž zakladatelem byl v polovině 20. století Claud Elwood Shannon. Kapitola 2. Historie kryptografie a její vývoj 8 Nejrůznější modifikace uvedených šifer pak byly používány během válek a krizí státními tajnými službami. S nástupem mechanických a posléze i elektronických počítačů však ani jeden způsob šifrování nevydržel dlouho neprolomen. Historie využití strojů viz 2.4. Problémem totiž zůstává fakt, že pokud je zkompromitován šifrovací klíč, lze rozšifrovat libovolnou symetrickou šifru (používá stejný klíč k šifrování i dešifrování). O tom se přesvědčila např. Marie Stuartovna, která skončila na popravišti, protože dopis, který zašifrovala, byl modifikován použitím stejné šifry a po dešifrování druhá strana prozradila jména spiklenců, kteří měli Marii Stuartovně pomoci na anglický trůn. Zde je také patrné, že moderní šifrovací systém by měl umožňit jednoznačně identifikovat stranu, která zprávu zašifrovala. Tento princip spolu s vyřešením problému kompromitace sdíleného klíče vyřešil až nástup asymetrické kryptografie, které se věnuje tato diplomová práce. 2.4 Historie využití strojů k šifrování a dešifrování zpráv K prvnímu opravdu významnému použití stroje k automatickému šifrování a dešifrování zpráv došlo ve 20. letech 20. století pomocí šifrovacího přístroje Enigma, který byl později využíván k šifrování komunikace německé armády během II. světové války. Ve snaze dešifrovat zprávy zašifrované pomocí stroje Enigma zkonstruoval Alan Turing jednoúčelová zařízení, takzvané Turingovy bomby, která hrubou výpočetní silou dekódovala zprávy zašifrované pomocí stroje Enigma. K šifrování velmi důležitých zpráv mezi Hitlerem a jeho generály používala německá armáda šifru Lorenz, což byla složitější verze šifry Enigma. Její prolomení bylo nad technické možnosti jednoúčelových Turingových bomb a zprávy zašifrované šifrou Lorenz musely být prolomeny ručně, což zabralo týdny usilovné práce. Až matematik Max Newman přišel s návrhem konceptu stroje vycházejícího do značné míry z konceptu Turingova univerzálního stroje, který byl schopen adaptace na různé problémy. Dnes bychom jej nazvali programovatelným počítačem. Přestože se uskutečnění Newmanova plánu zdálo být technicky nemožné, zkonstruoval k tomuto účelu inženýr Tommy Flowers v roce 1943 přístroj Colosus, který se skládal z 1500 elektronek. Po skončení druhé světové války byly nicméně Colosus i jeho výkresová dokumentace zničeny a tak díky utajení byl první veřejnosti představený počítač zkonstruován až v roce 1945 J. Presperem Eckertem a Johnem W. Mauchlym na Pensylvánské univerzitě. Ten již nesl proslulý název ENIAC (Electronic Numerical Integrator and Calculator), skládal se z 18000 elektronek a byl schopen vykonávat až 5000 operací za jednu vteřinu. Historii šifrovacích strojů se podrobně věnuje [11]. Kapitola 2. Historie kryptografie a její vývoj 9 Obrázek 2.2: Enigma Obrázek 2.3: Turingova bomba Kapitola 3 Algebra v Maple V této kapitole si ukážeme, jak lze za pomocí programu Maple řešit základní algebraické úlohy. Zaměříme se na dělitelnost čísel a rozklad čísel na prvočísla, generování náhodných čísel, práci s prvočísly, hledání celočíselných řešení rovnic, výpočty v modulární aritmetice, řešení kongruencí a v závěru se podíváme na vybrané problémy z teorie čísel. Cílem této kapitoly není vysvětlit matematickou podstatu problému, ale ukázat, jak užitečným nástrojem je program Maple při řešení algebraických úloh. 3.1 Dělitelnost v oboru celých čísel Podíl dvou celých čísel se zbytkem vypočítáme pomocí příkazu iquo nebo irem. Příkaz iquo má v základní variantě dva celočíselné parametry: dělenec a dělitel. Návratovou hodnotou je celočíselný podíl. 1 > iquo(11,4); 2 V rozšířené variantě je pak třetím parametrem příkazu iquo název proměnné, do které se má přiřadit hodnota zbytku po dělení. Aby nedocházelo k vyhodnocení názvu této proměnné, uzavíráme třetí parametr do apostrofů. 2 > iquo(11, 4, 'r'); 3 r; 2 3 Příkaz irem má v základní variantě dva celočíselné parametry: dělenec a dělitel. Návratovou hodnotou je zbytek po dělení. 4 > irem(11,4); 3 V rozšířené variantě je pak třetím parametrem příkazu irem název proměnné, do které se má přiřadit hodnota celočíselného podílu. Aby nedocházelo k vy- 10 Kapitola 3. Algebra v Maple 11 hodnocení názvu této proměnné, uzavíráme třetí parametr do apostrofů. 5 > irem(11, 4, 'q'); 6 > q; 3 2 Nejmenší společný celočíselný násobek nalezneme pomocí příkazu ilcm. Parametry příkazu jsou celá čísla oddělená čárkou. 7 > ilcm(-15, 12, 18); 180 Největšího společného celočíselného dělitele nalezneme pomocí příkazu igcd. Parametry příkazu jsou celá čísla oddělená čárkou. 8 > igcd(-15, 12, 18); 3 Pokud chceme vypsat všechna přirozená čísla nesoudělná s číslem n, použijeme následující příkaz: 9 > n:=15; 10 > select(x->evalb(gcd(x,n)=1), [seq(i, i=1..n-1)]); n := 15 [1, 2, 4, 7, 8, 11, 13, 14] Pro výpis všech dělitelů čísla n použijeme příkaz divisors z balíčku numtheory. Parametrem je celé číslo, jehož dělitele chceme vypsat, návratovou hodnotou je pak množina jeho celočíselných dělitelů. 11 > with(numtheory): 12 > divisors(24); {1, 2, 3, 4, 6, 8, 12, 24} Dělitelnosti se mimo jiné věnuje [10], kde je vysvětlena matematická podstata problému a také je zde ukázáno, jak tyto úlohy řešit bez pomoci programu Maple. 3.2 Generování náhodných čísel Před samotným generováním musíme inicializovat generátor náhodných čísel pomocí příkazu randomize. 13 > randomize: Následně můžeme generovat náhodná čísla pomocí příkazu rand. Pokud příkaz rand zadáme bez parametru, vrací náhodné dvanáctimístné číslo. 14 > rand(); Kapitola 3. Algebra v Maple 12 Pokud zavoláme příkaz rand s jedním celočíselným parametrem, je návratovou hodnotou definice procedury generující náhodná čísla z uzavřeného intervalu 0, n . 15 > Generuj_0_5 := rand(5); 16 Generuj_0_5(); Generuj 0 5 := proc() (proc() option builtin = RandNumberInterface; end proc)(6, 5, 3) end proc 1 Pokud nechceme definici procedury ukládat a stačí nám jednorázově vygenerovat náhodné číslo, stačí za volání příkazu rand připojit ještě jeden pár prázdných závorek. 17 > rand(5)(); 4 Jako parametr příkazu rand lze též zadat rozsah, z něhož mají být náhodná čísla generována. Návratovou hodnotou je pak opět definice procedury, která generuje náhodná čísla v požadovaném rozsahu. 18 > Generuj_10_20 := rand(10..20); 19 Generuj_10_20(); 20 rand(10..20)(); Generuj 10 20 := proc() (proc() option builtin = RandNumberInterface; end proc)(6, 11, 4) + 10 end proc 20 13 3.3 Práce s prvočísly Ověření, zda-li je číslo prvočíslem, se provadí pomocí příkazu isprime. Parametrem příkazu je celé číslo n, které chceme ověřit. 21 > isprime(19); 22 isprime(18); true false Největší prvočíslo menší než zadané celé číslo n obdržíme jako návratovou hodnotu příkazu prevprime. Parametrem příkazu je celé číslo n. 23 > prevprime(32); 31 Nejmenší prvočíslo větší než zadané celé číslo n obdržíme jako návratovou hodnotu příkazu nextprime. Parametrem příkazu je celé číslo n. 24 > nextprime(50); Kapitola 3. Algebra v Maple 13 53 Celé číslo n rozdělíme na součin prvočísel pomocí příkazu ifactor. Parametrem příkazu je celé číslo n. 25 > ifactor(1050); (2)(3)(5)2 (7) Náhodné prvočíslo generujeme složením příkazů rand a nextprime. 26 > nextprime(rand(1..10^3)()); 257 Pro zjištění n-tého prvočísla slouží příkaz ithprime z balíčku numtheory. Parametrem příkazu je přirozené číslo n, které určuje kolikáté prvočíslo chceme vypsat. 27 > with(numtheory): 28 ithprime(1); 29 ithprime(7); 2 17 Počet prvočísel menších nebo rovných přirozenému číslu n zjistíme pomocí přikazu pi z balíčku numtheory. Parametrem příkazu je libovolné celé číslo n. 30 > with(numtheory): 31 pi(100); 25 Pro výpočet bezpečných prvočísel slouží příkaz safeprime z balíčku numtheory. Parametrem příkazu je celé číslo n. Návratovou hodnotou je pak nejmenší bezpečné prvočíslo větší než n. Ještě připomeňme, že bezpečné prvočíslo je takové prvočíslo p, pro nějž platí, že p-1 2 je také prvočíslo. 32 > n:= 20; 33 p := safeprime(n); 34 isprime((p-1)/2); n := 20 p := 23 true 3.4 Diofantické rovnice Diofantické rovnice, jejichž řešení hledáme pouze v oboru celých čísel, řešíme pomocí příkazu isolve. Parametrem příkazu je rovnice, případně množina rovnic oddělených čárkou tvořících soustavu rovnic, jejichž celočíselné řešení hledáme. Pro lepší pochopení práce s příkazem isolve uvedeme několik příkladů. Řešení diofantické rovnice s jednou neznámou Kapitola 3. Algebra v Maple 14 35 > isolve(7*x-19=9); 36 isolve(x^3-1=7); 37 isolve(3^x=27); {x = 4} {x = 2} {x = 3} Řešení soustavy diofantických rovnic 38 > isolve({3*x-7*z=4, y+z=7, x+y+z=-1}); {x = -8, y = 11, z = -4} Příkaz isolve umožňuje řešit soustavy diofantických rovnic s větším počtem neznámych, než je počet rovnic v soustavě. V takovém případě je výsledek vyjádřen parametricky a konkrétní řešení soustavy rovnic obdržíme, pokud za parametry dosadíme libovolná celá čísla. Názvy, které isolve volí pro parametry (implicitně Zi) můžeme ovlivnit zadáním množiny názvů jako druhý nepovinný parametr příkazu isolve. 39 > isolve(5*x-6*y=7); 40 isolve(x^3-y=19); 41 isolve({w+x+y+z=24, w+y=12}); 42 isolve({w+x+y+z=24, w+y=12}, {a,b,c,d}); {x = 5 + 6 Z1, y = 3 + 5 Z1} {x = Z1, y = Z13 - 19} {w = 12 - Z1, x = 12 - Z2, y = Z1, z = Z2} {w = 12 - a, x = 12 - b, y = a, z = b} V případě, že se příkazu isolve nepodaří nalézt řešení diofantické rovnice, neznamená to, že rovnice nemá řešení. Například řešením rovnice x3 - y3 = 19 jsou celá čísla x = 3, y = 2. Přesto isolve řešení nenalezne. 43 > isolve(x^3-y^3=19); Někdy též isolve vrátí parametrické vyjádření řešení, které ovšem vrací celočíselné řešení nikoliv pro všechny, ale pouze pro vyhovující celočíselné parametry. Jinými slovy isolve nebyl schopen řešení nalézt a rovnici pouze převedl do jejího parametrického vyjádření. Řešením následující rovnice jsou čísla x = 3, y = 5. 44 > isolve(2^x+2^y=40); 45 2^3+2^5; x = Z1, y = ln -eln(2) Z1 + 40 ln (2) 40 Kapitola 3. Algebra v Maple 15 Volbou nevhodného parametru neobdržíme celočíselné řešení. 46 > _Z1:=2; 47 ln(-exp(_Z1*ln(2))+40)/ln(2); Z1 := 2 2ln(6) ln(2) Volbou vhodného parametru obdržíme celočíselné řešení. 48 > _Z1:=3; 49 ln(-exp(_Z1*ln(2))+40)/ln(2); Z1 := 3 5 Řešení diofantických rovnic se mimo jiné zabývá [10], kde je vysvětlena matematická podstata problému a je zde také ukázáno, jak tyto úlohy řešit bez pomoci programu Maple. 3.5 Modulární aritmetika Maple umožňuje zapisovat výrazy modulární aritmetiky dvěma navzájem ekvivalentními způsoby. Pomocí operátoru mod 50 > 17^3 mod 9; 8 Pomocí funkce modp. Prvním parametrem je počítaný výraz, druhým je nenulový celočíselný parametr modul n. Návratovou hodnotou je celé číslo z uzavřeného intervalu 0, |n - 1| . 51 > modp(17^3, 9); 8 Při počítání mocnin modulo n Maple umožňuje počítat i s tak velkými čísly, která by za normálních okolností vyvolala výjimku přetečení číselného registru. Bohužel skutečnost, že výsledek bude nad standardní možnosti Maple, musíme vědět předem a k výpočtu použít funkci Power mod pro počítání mocnin velkých čísel v modulární aritmetice. 52 > 2^rand(10^80)(); Error, numeric exception: overflow 53 > 2^rand(10^80)() mod 19; Error, numeric exception: overflow Kapitola 3. Algebra v Maple 16 54 > Power(2,rand(10^80)()) mod 19; 17 3.6 Kongruence Kongruence řešíme v programu Maple pomocí příkazu msolve. Parametrem příkazu je kongruence, případně množina kongruencí oddělených čárkou tvořících soustavu kongruencí, jejichž řešení hledáme. Rozdíl mezi msolve a isolve (sekce 3.4, strana 13) je, že isolve počítá v x Z a msolve počítá v x Zn. Pro lepší pochopení práce s příkazem msolve uvedu několik příkladů. 55 > msolve(4*x+3=2,7); {x = 5} 56 > msolve(2*x^2-16=2, 11); {x = 3}, {x = 8} 57 > msolve(3^(x+2)-7=2, 13); {x = 0}, {x = 3}, {x = 6}, {x = 9}, {x = 12} 58 > msolve(2^x-1=1, 7); {x = 1 + 3 Z2} 59 > msolve(x+2*y+z=10, 11); {x = 9y + 10z + 10, y = y, z = z}, {x = x, y = 5x + 5z + 5, z = z}, {x = x, y = y, z = 10x + 9y + 10} 60 > msolve({x+4*y-z=18, 18*y-x=1, 4*z+3*y=17}, 19); {x = 8, y = 10, z = 11} 61 > msolve({x^3-y^3=19, 7*x+y=2}, 21); {x = 3, y = 2}, {x = 6, y = 2}, {x = 12, y = 2} Řešení kongruencí se mimo jiné věnuje [10], kde je vysvětlena matematická podstata problému a je zde také ukázáno, jak tyto úlohy řešit bez pomoci programu Maple. 3.7 Vybrané úlohy z teorie čísel V této kapitole si ukážeme výpočet Eulerovy funkce (n), nalezení primitivních kořenů modulo n a výpočet diskrétního logaritmu. Kapitola 3. Algebra v Maple 17 Při řešení vybraných úloh budeme používat příkazy z balíčku numtheory. Balíček obsahuje tyto příkazy: 62 > with(numtheory); [GIgcd, bigomega, cfrac, cfracpol, cyclotomic, divisors, factorEQ, factorset, fermat, imagunit, index, integral basis, invcfrac, invphi, iscyclotomic, issqrfree, jacobi, kronecker, , legendre, mcombine, mersenne, migcdex, minkowski, mipolys, mlog, mobius, mroot, msqrt, nearestp, nthconver, nthdenom, nthnumer, nthpow, order, pdexpand, , , pprimroot, primroot, quadres, rootsunity, safeprime, , sq2factor, sum2sqr, , thue] Příkazy divisors (odkaz), ithprime (odkaz), pi (odkaz) a safeprime (odkaz) již byly popsány v předchozích kapitolách a nyní se jim již věnovat nebu- deme. 3.7.1 Eulerova funkce (n) Z teorie čísel je známá Eulerova funkce (n), která pro dané přirozené číslo n vrací počet čísel menších než n, která jsou s n nesoudělná. Pro výpočet hodnoty Eulerovy funkce (n) použijeme příkaz phi z balíčku numtheory. 63 > phi(10); 64 phi(11); 4 10 Naopak seznam čísel, která jsou nesoudělná právě s n menšími přirozenými čísly, vrací příkaz invphi z balíčku numtheory. 65 > invphi(4); 66 Nesoudelna := n->select(x->evalb(gcd(x,n)=1), 67 [seq(i, i=1..n-1)]): 68 Nesoudelna(5), phi(5); 69 Nesoudelna(8), phi(8); 70 Nesoudelna(10), phi(10); 71 Nesoudelna(12), phi(12); [5, 8, 10, 12] [1, 2, 3, 4] , 4 [1, 3, 5, 7] , 4 [1, 3, 7, 9] , 4 [1, 5, 7, 11] , 4 Eulerově funkci (n) se mimo jiné věnuje [10], kde je vysvětlena matematická podstata problému a je zde také ukázáno, jak tyto úlohy řešit bez pomoci Kapitola 3. Algebra v Maple 18 programu Maple. 3.7.2 Primitivní kořeny Pro výpočet primitivního kořene modulo n slouží příkaz primroot. Prvním nepovinným parametrem je celé nezáporné číslo x určující spodní mez pro vyhledání primitivního kořene modulo n. Druhým parametrem je přirozené číslo n větší než 1, které určuje modul. Návratovou hodnotou příkazu je nejmenší z primitivních kořenů a : x < a < n nebo FAIL v případě, že primitivní kořen a : x < a < n neexistuje. 72 > primroot(7); 73 primroot(%,7); 74 primroot(%,7); 3 5 FAIL Příkaz pro vypsání všech primitivních kořenů modulo n Maple neposkytuje. Můžeme si jej ale snadno vytvořit pomocí předcházejícího příkazu primroot a následujících vědomostí: * Primitivní kořen je řádu (n). * Pokud je řád čísla a roven r, pak řád čísla as je roven číslu r (r,s) . Z výše uvedeného vyplývá, že pokud a je primitivní kořen modulo n, pak také as je primitivní kořen modulo n pokud ((n), s) = 1 75 > primroots:= proc(n::integer) 76 local firstPrimitiveRoot, listOfRoots::set, 77 indivisebledExponentWithPhiN::list, i::integer: 78 79 use numtheory in 80 firstPrimitiveRoot:= primroot(n): 81 if firstPrimitiveRoot = FAIL then 82 return FAIL: 83 else 84 indivisebledExponentWithPhiN := 85 select(x->evalb(gcd(x,phi(n))=1), 86 [seq(i, i=1..n-2)]): 87 listOfRoots := convert( 88 map(x->Power(firstPrimitiveRoot,x) mod n, 89 indivisebledExponentWithPhiN), set): 90 return listOfRoots: 91 end if: 92 end use: Kapitola 3. Algebra v Maple 19 93 end proc: Parametrem procedury primroots je přirozené číslo n větší než jedna určující modul, pro něhož chceme vypsat primitivní kořeny modulo n. Návratovou hodnotou je množina všech primitivních kořenů modulo n. 94 > primroots(19); {2, 3, 10, 13, 14, 15} Problematice výpočtu primitivních kořenů se mimo jiné věnuje [10], kde je vysvětlena matematická podstata problému a je zde také ukázáno, jak tyto úlohy řešit bez pomoci programu Maple. 3.7.3 Výpočet diskrétního logaritmu Příkazem mlog z balíčku numtheory vypočteme diskrétní logaritmus x o základu a modulo n. První parametr je logaritmovaná hodnota x, druhým parametrem je základ logaritmu a a třetím parametrem je modul n. Parametry x, a, n jsou celočíselné. Návratovou hodnotou je hodnota diskrétního logaritmu. 95 > 5^3 mod 7; 96 mlog(6, 5, 7); 6 3 Zatímco operace umocnění je časově poměrně nenáročným úkonem, výpočet inverzní operace, tedy diskrétního logaritmu, trvá nepoměrně déle. 97 > p:= nextprime(rand(10^20)()); 98 x:= rand(p)(); 99 a:= primroot(p); p := 47326865160473042737 x := 22175023910090287620 a := 7 Změříme čas výpočtu operace umocnění 100 ts := time(): 101 y:= Power(a,x) mod p; 102 time()-ts; y := 2466318645087628652 0. Změříme čas výpočtu diskrétního logaritmu 103 ts:= time(): 104 mlog(y, a, p); 105 time()-ts; Kapitola 3. Algebra v Maple 20 22175023910090287620 176.531 Pro přibližnou orientaci v tomto případě na běžném PC Intel Core2Duo 1,5GHz trval výpočet 176, 531 vteřin. Kapitola 4 Problém distribuce klíčů V této kapitole se seznámíme s nejslavnějším problémem v historii kryptografie, jehož řešením se kryptografové zabývali několik staletí. 4.1 Historie V druhé polovině 20. století došlo k výraznému zrychlení ve vývoji počítačů, růstu jejich výkonu a poklesu jejich cen, především díky objevu tranzistoru1 a integrovaného obvodu2. Dalšími významnými kroky, které umožnily komerční využití počítačů jakožto kryptografických strojů, byla standardizace protokolu převodu znaků na binární čísla ASCII (American Standard Code for Information Interchange)3 a vytvoření prvního imperativního jazyka FORTRAN4 firmou IBM, který konečně umožnil širší veřejnosti psát počítačové programy. V 70. letech 20. století pak byly počítače dostupné řadě komerčních subjektů, které je mimo jiné využívaly právě pro šifrování. Spolu s přibývajícím množstvím firem, které si kupovaly počítače, se však zvyšoval i objem šifrovaných dat a kryptografové tak stáli před zcela novými problémy, které v době, kdy byla kryptografie výlučnou oblastí vlády a armády, nebyly vnímány jako podstatné. Jedním z hlavních problémů byla otázka standardizace šifrovacího systému. Podnik sice pro zabezpečení své interní komunikace mohl využívat určitý kryptografický systém, poslat však šifrovanou zprávu jiné organizaci nebylo možné v případě, že příjemce používal jiný šifrovací systém. Proto dne 15. května 1973 Národní standardizační úřad Spojených států (National Bureau for Standards) vyzval výrobce kryptografických systémů k předložení návrhů na standardní šifrovací systém. Tím se nakonec stala 56bi- 1 Tranzistorový efekt byl objeven a tranzistor vynalezen 16. prosince 1947 v Bellových laboratořích týmem ve složení William Shockley, John Bardeen a Walter Brattain. 2 První integrovaný obvod zkonstruoval Jack St. Clair Kilby z firmy Texas Instruments již v roce 1958. Obvod byl na destičce z germania o velikosti 11 × 1, 6 mm a obsahoval jediný tranzistor pouze s několika pasivními součástkami navíc. 3 ASA X3.4-1963, American Standards Association, June 17, 1963 4 Název je odvozen z The IBM Mathematical Formula Translating System. 21 Kapitola 4. Problém distribuce klíčů 22 tová5 verze šifry Lucifer, kterou vyvinul Horst Feistel v laboratořích firmy IBM. Nový šifrovací standard byl přijat 23. listopadu 1976 pod názvem DES (Data Encryption Standard). Vyřešení problému standardizace tak motivovalo firmy, aby k zajištění bezpečné komunikace používaly právě metod kryptografie. Bez ohledu na standardizaci a sílu DES se podniky musely potýkat ještě s jedním závažným problémem, kterým byla distribuce klíčů. Banka chtěla například poslat klientovi telefonní linkou důvěrná data, ale z obavy, že je telefonní linka odposlouchávána, zvolila šifrovací klíč a zašifrovala zprávu pomocí algoritmu DES. Klient pak, chtěl-li zprávu dešifrovat, musel mít na svém počítači kopii algoritmu DES a současně musel znát klíč, který byl použit bankou k zašifrování zprávy. Nabízí se otázka: ,,Jakým způsobem klienta o použitém klíči informovat? Nebylo možno jej poslat potenciálně odposlouchávanou telefonní linkou, takže jediný zaručeně bezpečný, avšak časově velmi náročný způsob, bylo předat klíč klientovi osobně. Méně bezpečné, ale praktičtější řešení bylo poslat klíč kurýrní službou. S rostoucím objemem přepravovaných klíčů se však tento způsob stával logisticky i finančně příliš náročný, a to i pro takové organizace, jakými byly banky. Malé organizace si šifrovanou komunikaci vzhledem k vynaloženým nákladům dovolit nemohly vůbec. Abychom si udělali obrázek o množství klíčů, které bylo potřeba distribuovat, představme si následují situaci: na burze obchoduje n firem. Pokud chceme zajistit, aby každá firma měla možnost libovolnému obchodnímu partnerovi poslat zprávu zašifrovanou symetrickou šifrou DES, musíme distribuovat n(n - 1)/2 klíčů. Což pro n = 100 je 4950 klíčů, pro n = 200 je to ale už 19900 klíčů, pro n = 500 124750 klíčů a pro n = 1000 už neúnosných 499500 klíčů. Neudržitelnost tehdejší situace je patrná i ze skutečnosti, že agentura COMSEC (Communications Security), která spravovala a distribuovala klíče používané k šifrování zpráv americkou vládou, v 70. letech přepravovala denně několik tun médií (děrných štítků, pásků, disket), na nichž byly klíče uloženy. Přestože se distribuce klíčů na první pohled zdá jako banální záležitost, stala se nejvýznamnějším problémem poválečné kryptografie. Jestliže spolu chtěly dvě strany bezpečně komunikovat, musely spoléhat na třetí stranu, která doručila klíč, což byl v celém systému nejslabší článek řetězu, a tedy i nejlépe napadnutelné místo. Problém distribuce klíčů navzdory tehdejšímu všeobecnému mínění, že jde o neřešitelný problém, vyřešil tým Whitfield Diffie, Martin Hellman a Ralph Merkle. 5 Původní verze šifry Lucifer byla 128 bitová. Jako standard byla přijata oslabená 56 bitová verze po intervenci NSA (National Security Agency); NSA se zřejmě domnívala, že 56 bitový klíč poskytne dostatečnou ochranu šifrovaných zpráv, protože žádná civilní organizace neměla tehdy dostatečně výkonný počítač, aby mohla v rozumném čase prověřit každý možný klíč. Sama NSA by však díky přístupu k nejvýkonnější výpočetní technice byla takové zprávy ještě schopna dešifrovat. Kapitola 4. Problém distribuce klíčů 23 4.2 Algoritmus Diffie-Hellman-Merkle Po dva tisíce let se kryptografové domnívali, že pro dešifrování zašifrované zprávy je nutné znát klíč, kterým byla zpráva zašifrována. Existuje však myšlenkový experiment, který jakoby tuto skutečnost popíral. Představme si situaci, kdy Alice a Bob žijí v zemi, kde je poštovní systém naprosto nemravný a poštovní zaměstnanci čtou veškerou nechráněnou korespondenci. Alice chce Bobovi poslat soukromou zprávu. Vloží ji tedy do kovové skříňky a zamkne. Bob skříňku nemůže otevřít, protože nemá klíč, kterým Alice skříňku zamkla, přidá na ni tedy svůj zámek a skříňku opatřenou dvěma zámky odešle zpět Alici. Když Alice skříňku s Bobovým zámkem obdrží, odstraní svůj zámek a skříňku zamčenou pouze Bobovým zámkem odešle zpět k Bobovi. Nyní Bob může otevřít skříňku se zprávou. Komunikační schéma znázorňuje obrázek 4.1. Obrázek 4.1: Schéma myšlenkového experimentu se zámky. Kapitola 4. Problém distribuce klíčů 24 Zásadní překážkou v implementaci tohoto protokolu komunikace je fakt, že při vícenásobném šifrování zprávy běžnou symetrickou šifrou záleží na pořadí, v jakém byly jednotlivé šifry na zprávu aplikovány. Dešifrovat zprávu je u většiny šifer nutné provádět v opačném pořadí, než v jakém byla zpráva šifrována. O pravdivosti tohoto tvrzení se přesvědčíme experimentálně na jednoduché substituční šifře. Nechť pro x (A..Z) { } je definována funkce f(x), g(x) tabulkami: x A B C D E F G H I J K L M N f(x) C A J K H O L B M I F G W D g(x) O L P S Z X B Q T E U Y I x O P Q R S T U V W X Y Z f(x) P R N E U Y S Z V Q T X g(x) F G C A J M R N V K H W D Nechť funkce f-1(x) je inverzní funkcí k f(x) a g-1(x) je inverzní funkcí k g(x), pak g(f("M")) = "V " , f-1(g-1("V ")) = "M", ale g(f("M")) = "V " , g-1(f-1("V ")) = "G" Předchozí příklad jasně ukázal, že u monoalfabetické substituční šifry záleží na pořadí šifrování a dešifrování. Nyní pro názornost uveďme implementaci jednoduché substituční šifry v Ma- ple: Nejprve definujeme abecedu jako uspořádanou množinu znaků, nad kterou bude substituční šifra pracovat: 106 > restart; 107 > Abeceda := "ABCDEFGHIJKLMNOPQRSTUVWXYZ_"; Abeceda := "ABCDEFGHIJKLMNOPQRSTUV WXY Z " Následně definujeme klíč Alice a Boba jako libovolnou permutaci písmen abecedy. Například: 108 > AliceKey := "CAJKHOLBMIFGWDP_RNEUYSZVQTX"; AliceKey := "CAJKHOLBMIFGWDP RNEUY SZV QTX" 109 > BobKey := "OLPS_ZXBQTEUYIFGCAJMRNVKHWD"; BobKey := "OLPS ZXBQTEUY IFGCAJMRNV KHWD" Šifrování a dešifrování zajistí funkce EncodeSimpleSubstitution a DecodeSimpleSubstitution definované níže: 110 > EncodeSimpleSubstitution := proc (msg::string, 111 alphabet::string, key::string) Kapitola 4. Problém distribuce klíčů 25 112 113 local res::string, i::integer, j::integer; 114 with(StringTools): 115 res := ""; 116 117 # procházíme zprávu po znacích 118 for i from 1 to length(msg) do 119 120 # hledáme znak abecedy shodný 121 # s~aktuálním znakem zprávy 122 for j from 1 to length(alphabet) do 123 if UpperCase(alphabet[j]) = UpperCase(msg[i]) then 124 125 # do výstupního řetězce předáme znak klíče, 126 # který je na stejné pozici jako znak v~abecedě 127 res := cat(res, key[j]); 128 end if; 129 end do; 130 end do; 131 return res; 132 end: Funkce EncodeSimpleSubstitution v cyklu prochází po znacích zprávu určenou k zašifrování a ke každému znaku ve zprávě najde jeho index v abecedě. Do výstupní zašifrované zprávy zřetězí znak klíče nacházející se na pozici se stejným indexem. 133 > DecodeSimpleSubstitution := proc (msg::string, 134 alphabet::string, key::string) 135 136 # dešifrovní je stejné jako šifrování pouze 137 # zaměníme abecedu a klíč 138 return EncodeSimpleSubstitution(msg, key, alphabet); 139 end: Při dešifrování postupujeme inverzně: v cyklu procházíme po znacích zprávu určenou k dešifrování a ke každému znaku ve zprávě najdeme jeho index v klíči. Do výstupní dešifrované zprávy zřetězíme znak abecedy nacházející se na pozici se stejným indexem. Pokud pomocí EncodeSimpleSubstitution zašifrujeme zprávu nejdřív klíčem Alice a pak klíčem Boba a následně ji dešifrujeme klíčem Boba a poté klíčem Alice, výsledkem je dešifrovaná zpráva. 140 > EncodeSimpleSubstitution("AHOJ_BOBE", Abeceda, AliceKey); "CBPIXAPAH" Kapitola 4. Problém distribuce klíčů 26 141 > EncodeSimpleSubstitution(%, Abeceda, BobKey); "PLGQKOGOB" 142 > DecodeSimpleSubstitution(%, Abeceda, BobKey); "CBPIXAPAH" 143 > DecodeSimpleSubstitution(%, Abeceda, AliceKey); "AHOJ BOBE" Pokud ale zašifrovanou zprávu dešifrujeme v opačném pořadí, tj. nejdřív klíčem Alice a pak klíčem Boba, výsledkem je nesmyslný text. 144 > EncodeSimpleSubstitution("AHOJ_BOBE", Abeceda, AliceKey); "CBPIXAPAH" 145 > EncodeSimpleSubstitution(%, Abeceda, BobKey); "PLGQKOGOB" 146 > DecodeSimpleSubstitution(%, Abeceda, AliceKey); "OGLY DFLFH" 147 > DecodeSimpleSubstitution(%, Abeceda, BobKey); "APBM OBOY " U skříňky zamčené visacími zámky nezáleží na pořadí, v jakém je zamykáme, případně odemykáme. Šifrovací systémy jsou bohužel na pořadí citlivější. Tým Diffie, Hellman a Merkle proto pátral po funkci, u které by na pořadí šifrování a dešifrování nezáleželo. Nezajímaly jej obousměrné funkce, tj. funkce, ke kterým existuje inverze, protože ze znalosti zašifrované zprávy a inverzní funkce snadno zprávu dešifrujeme. Pokud bychom jako šifrovací funkci zvolili funkci f(x) = x2, zašifrovali bychom písmeno A převedené na číslo podle ASCII takto: 148 > f := x->x^2; f := x x2 149 > g:= x->sqrt(x); g := x x Kapitola 4. Problém distribuce klíčů 27 Zvolíme znak, který chceme zašifrovat, pomocí funkce f 150 > Chr := "M"; Chr := "M" Převedeme znak na jeho číselnou hodnotu 151 > OrdChr := Ord(Chr); OrdChr := 77 Zašífrujeme pomocí funkce f 152 > EncodedOrdChr := f(OrdChr); EncodedOrdChr := 5929 A protože známe zašifrovanou zprávu i inverzní funkci, jsme schopni původní zprávu snadno dešifrovat 153 > DecodedOrdChr := g(EncodedOrdChr); DecodedOrdChr := 77 Převedeme číselnou hodnotu znaku zpět na znak 154 > Char(DecodedOrdChr); "M" Použitá funkce k šifrování však nesmí podat útočníkovi žádnou informaci o tom, zda je jím aktuálně zvolený klíč k dešifrování více vhodný než ten předchozí, případně jak ho má upravit, aby se pravděpodobnost dešifrování zvýšila. Zvolme jako šifrovací funkci opět funkci f(x) = x2 a předpokládejme, že útočník není schopen zjistit jak je funkce implementovaná a nedokáže k ní najít inverzní funkci, pomocí níž by zprávu dešifroval. Je to sice komplikace, ale útočník si poradí i bez této informace a zprávu dešifruje pomocí hádání klíčů. Zakódujme písmeno M pomocí funkce f 155 > f(Ord("M")); 5929 Útočník odchytil zašifrovanou zprávu, tedy číslo 5929 a má též k dispozici funkci f, přestože neví jak je implementovaná a bude se snažit uhodnout, jaké písmeno se na tuto hodnotu zašifruje. Zkusí například písmena E a U 156 > f(Ord("E")); Kapitola 4. Problém distribuce klíčů 28 4761 157 > f(Ord("U")); 7225 Protože výsledek f(E) je menší než požadované číslo 5929 a výsledek f(U) je větší než požadované číslo, útočník se může správně domnívat, že musí jít o některé z písmen mezi písmeny E a U, proto interval zmenší. 158 > f(Ord("K")); 5625 159 > f(Ord("O")); 6241 A takto postupuje, dokud neuhodne, že 160 > f(Ord("M")); 5929 Z těchto důvodů se tým Diffie, Hellman a Merkle zaměřil na funkce z oblasti modulární aritmetiky, které jsou často jednosměrné a jejichž výsledky poskytují minimální informace o vstupních parametrech. Pokud předchozí příklad zopakujeme v modulární aritmetice, zjistíme, že útočník má šance na uhodnutí výsledku daleko menší. 161 > f(Ord("E")) mod 29; 5 162 > f(Ord("U")) mod 29; 4 163 > f(Ord("K")) mod 29; 28 164 > f(Ord("O")) mod 29; 6 Kapitola 4. Problém distribuce klíčů 29 Po dvou letech zkoumání jednocestných funkcí v modulární aritmetice se snaha Martina Hellmana vyplatila a na jaře roku 1976 vyřešil problém distribuce klíčů. Protože si však byl vědom toho, že úspěchu dosáhl jen díky společnému úsilí, nese algoritmus název složený ze jmen všech, kteří s ním na vyřešení problému distribuce klíčů spolupracovali. 4.2.1 Idea algoritmu Násobení je komutativní operací, tudíž a b = b a. Totež platí i v modulární aritmetice a b mod p = b a mod p Z komutativnosti násobení plyne ax by = a a . . . a x-krát b b . . . b y-krát = b b . . . b y-krát a a . . . a x-krát = by ax speciálně pak axy = ax ay = ay ax = ayx Můžeme bezpečně říct, že funkce f(x) = ax je rostoucí v Z pro všechna a Z : 1 < a, avšak průběh funkce g(x) = ax mod p lze popsat jen velmi obtížně. Abychom si udělali lepší představu o nepředvídatelném chování funkce g(x), srovnejme průběhy funkcí f(x), g(x) na intervalu -3, 8 pro hodnoty parametrů a = 2 a p = 11 x -3 -2 -1 0 1 2 3 4 5 6 7 8 f(x) 1 8 1 4 1 2 1 2 4 8 16 32 64 128 512 g(x) 7 3 6 1 2 4 8 5 10 9 7 3 Pokud bychom chtěli zjistit chování funkcí f(x), g(x) na jiných intervalech nebo pro jiné hodnoty paramerů a, p, můžeme jejich průběh zkoumat v Maple pomocí následujících příkazů 165 restart: 166 > a := 2: 167 > p := 11: 168 > LBound := -3: 169 > UBound := 8: 170 > f := x->a^x: 171 > g := x->a^x mod p: 172 > map(f, [seq(i, i=LBound..UBound)]); 173 > map(g, [seq(i, i=LBound..UBound)]); 1 8 , 1 4 , 1 2 , 1, 2, 4, 8, 16, 32, 64, 128, 256 [7, 3, 6, 1, 2, 4, 8, 5, 10, 9, 7, 3] Kapitola 4. Problém distribuce klíčů 30 Zatímco spočítat y ze vztahu y = ax mod p je časově poměrně nenáročné (známe-li hodnoty a, x, p), pro výpočet hodnoty x (známe-li hodnoty y, a, p), tj. pro výpočet diskrétního logaritmu y o základu a modulo p, není znám žádný efektivní algoritmus. Na složitosti výpočtu diskrétního logaritmu je založena celá řada kryptografických systémů, včetně algoritmu distribuce klíčů Diffie- Hellman-Merkle. Při výměně klíčů pomocí algoritmu Diffie-Hellman-Merkle postupujeme takto: 1. Uživatel UA zvolí parametry Y, P funkce f(x) = Y x mod P takové, že P je prvočíslo a Y je primitivní kořen modulo P. Tyto parametry odešle uživateli UB přes potenciálně odposlouchávané komunikační médium. 2. Uživatel UA zvolí číslo XA a ponechá si jej v tajnosti. Vypočte hodnotu f(XA) a odešle ji uživateli UB. 3. Uživatel UB zvolí číslo XB a ponechá si jej v tajnosti. Vypočte hodnotu f(XB) a odešle ji uživateli UA. 4. Uživatel UA vypočte hodnotu f(XB)XA mod P. 5. Uživatel UB vypočte hodnotu f(XA)XB mod P. 6. Uživatel UA i UB dospěli ke stejnému číslu, které mohou použít jako klíč pro symetrickou šifru. f(XA)XB = (Y XA mod P)XB mod P = Y XAXB mod P = Y XBXA mod P = (Y XB mod P)XA mod P = f(XB)XA Potencionální útočník není schopen bez znalosti XA vypočítat hodnotu f(XB)XA , případně bez znalosti XA vypočítat hodnotu f(XA)XB . Může se ovšem pokusit XA (resp. XB) vypočítat z hodnoty f(XA) (resp. f(XB)), což mu ale zabere nepoměrně více času a výpočetní kapacity. Popsaný postup si prakticky můžete vyzkoušet v mapletu DiffieHellman- Merkle.maplet 4.2.2 Implementace Alice zvolí parametry Y, P jednocestné funkce f(x) = Y x mod P takové, že P je prvočíslo a Y je primitivní kořen modulo P. Tyto parametry odešle přes Evou odposlouchávanou linku 174 > GenerateModul:= proc() 175 return nextprime(rand(10^20..10^25)()): 176 end proc: 177 > P:= GenerateModul(); Kapitola 4. Problém distribuce klíčů 31 P := 3548256839678504695583929 178 > GetPrimitiveRoot:= proc(x::integer) 179 use numtheory in 180 return primroot(x); 181 end use: 182 end proc: 183 > Y:= GetPrimitiveRoot(P); Y := 11 Nyní Alice náhodně zvolí Xa, uchová jej v tajnosti, a vypočítá f(Xa). Bob náhodně zvolí Xb, které též uchová v tajnosti, a vypočítá f(Xb). K provedení tohoho výpočtu je třeba v mapletu definovat funkci f. Oproti protokolu výměny klíčů Diffie-Hellman-Merkle je v mapletu funkce f definována obecněji jako F(y, x, p) = yx mod p, tj. Y a P nejsou pevně zvoleny, ale vstupují do funkce jako proměnné, což nám umožní funkci f opět využít i v 3. kroku algoritmu při počítání hodnot f(Xa)Xb = F(Xa, Xb, P) a f(Xb)Xa = F(Xb, Xa, P) 184 > F := proc (aY, aXa, aP) 185 return eval(Power(aY,aXa) mod aP): 186 end proc: 187 > GetRandomLargeNumber:= proc() 188 return rand(10^20..10^25)(): 189 end proc: 190 > Xa:= GetRandomLargeNumber(); 191 > Fxa:= F(Y, Xa, P); Xa := 3775505218338988823656415 Fxa := 219753464317952423565523 192 > Xb:= GetRandomLargeNumber(); 193 > Fxb:= F(Y, Xb, P); Xb := 3626973769922677344193466 Fxb := 1919848287237492186921187 Nyní si Alice vypočítá hodnotu f(Xb)Xa mod P, Bob si také vypočítá hodnotu f(Xa)Xb mod P 194 > Fxaxb:= F(Fxa, Xb, P); 195 > Fxbxa:= F(Fxb, Xa, P); 196 > evalb(Fxaxb=Fxbxa); Fxaxb := 1658148615342060726815022 Fxbxa := 1658148615342060726815022 true Kapitola 4. Problém distribuce klíčů 32 Alice i Bob dospěli ke stejnému číslu, které mohou použít jako klíč symetrické šifry. Kapitola 5 Kryptografie s veřejným klíčem V létě 1975 publikoval Whitfield Diffie koncept kryptografie s asymetrickým klíčem. Zatímco v symetrické kryptografii používají odesilatel a příjemce k šifrování a dešifrování stejný klíč, v asymetrické kryptografii je k šifrování zprávy použit klíč jiný než je použit k jejímu dešifrování. Každý účastník U systému má svou dvojici klíčů * veřejný klíč EU určený k šifrování zpráv * soukromý klíč DU určený k dešifrování zpráv Svůj soukromý klíč uchová každý uživatel v tajnosti, protože pouze se znalostí soukromého klíče uživatele lze dešifrovat zprávy zašifrované pomocí jeho veřejného klíče. Veřejné klíče všech uživatelů jsou uloženy v registru veřejných klíčů a má k nim přístup každý uživatel systému. Pokud chce například Alice poslat zašifrovanou zprávu Bobovi, proběhne komunikace podle následujícího schématu: 1. Alice vyhledá Bobův veřejný klíč EB v centrálním registru 2. Zašifruje pomocí EB zprávu M 3. Zašifrovanou zprávu EB(M) odešle Bobovi 4. Jenom Bob může zprávu dešifrovat pomocí svého soukromého klíče DB(EB(M)) = M Na kryptovací systém je tedy kladen požadavek, aby nikdo nebyl v rozumném čase schopen zjistit z EU a EU (M) libovolnou informaci vedoucí k odhalení DU nebo M. Výhody asymetrických šifrovacích systémů: * Není potřeba výměna klíčů. 33 Kapitola 5. Kryptografie s veřejným klíčem 34 * Počet klíčů v systému narůstá lineárně s počtem uživatelů (je roven dvojnásobku počtu uživatelů). Kapitola 6 Šifrování RSA Algoritmus RSA je jednou z nejslavnějších implementací principu asymetrické šifry. V dnešní době se s protokoly, které RSA využívají, setkáváme téměř denně, nejčastěji při zabezpečené komunikaci na internetu. Z protokolů pro bezpečnou komunikaci využívajících RSA zmiňme alespoň SSL ­ Secure Socket Layer, který je využíván ve známých protokolech HTTPS a SSH. V této kapitole se seznámíme s historií vzniku RSA, principem jeho fungování i s možnými útoky na šifrovaný obsah zpráv. 6.1 Historie Přestože Wightfield Diffie popsal princip obecné asymetrické šifry, nevěděl, jak ji realizovat. Výsledky jeho práce, které publikoval, inspirovaly Ronalda Rivesta a jeho kolegy Adi Shamira a Leonarda Adlemana z laboratoře počítačových věd MIT (Massachussets Institute of Technology), kteří uvedli Diffieho myšlenku asymetrické kryptografie do praxe. První asymetrický kryptografický systém je nazván RSA1 podle počátečních písmen příjmení jeho autorů. Širší veřejnost se o RSA dozvěděla v srpnu 1977 z článku Martina Gardnera s názvem ,,Nový druh šifry, jejíž rozlomení by zabralo miliony let , který uveřejnil ve svém sloupku Mathematical Games v časopise Scientific American. Vysvětlil v něm principy obecné asymetrické šifry a vytiskl zašifrovaný text C = 96 869 613 754 622 061 477 140 922 254 355 882 905 759 991 124 574 319 874 695 120 930 816 298 225 145 708 356 931 476 622 883 989 628 013 391 990 551 829 945 157 815 154 a veřejný klíč (E,N), který použil k zašifrování zprávy2 1 Původně se systém měl jmenovat ARS (jména autorů jsou řazena v abecedním pořadí), ale Leonard Adleman se domníval, že jejich objev je velmi malého významu a zpočátku nechtěl být jako autor vůbec jmenován a až po diskusi s kolegy souhlasil s tím, že bude uveden také, ovšem až jako třetí autor v pořadí. 2 Text zprávy nejprve převedl na číslo dle schématu 01=A, 02=B, . . . a následně zašifroval pomocí RSA. Zde bych chtěl podotknout pro čtenáře, který bude zkoušet zprávu dekódovat pomocí přiloženého mapletu, že nebude úspěšný, protože maplet převádí znaky na čísla dle 35 Kapitola 6. Šifrování RSA 36 E = 9007 N = 114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541 a vyhlásil čtenářskou soutěž s odměnou $100 pro toho, kdo první zašifrovanou zprávu dešifruje. Gardner ve svém článku neměl prostor k tomu, aby vysvětlil princip RSA, proto čtenáře odkázal, aby si v případě zájmu napsali o detaily do laboratoře počítačových věd MIT. Rivest, Shamir a Adleman byli překvapeni třemi tisíci žádostí o popis šifry RSA. Neodpověděli na ně však hned, protože se báli, že předčasné zveřejnění RSA by mohlo ohrozit udělení patentu. V případě Gardnerovy výzvy trvalo 17 let, než byla zpráva rozluštěna. Teprve 26. dubna 1994 se díky spojenému úsilí 600 dobrovolníků, kteří věnovali volnou výpočetní kapacitu svých počítačů k dešifrování zprávy, povedlo vypočítat soukromý klíč, kterým jsou prvočísla p = 32 769 132 993 266 709 549 961 988 190 834 461 413 177 642 967 992 942 539 798 288 533 q = 3 490 529 510 847 650 949 147 849 619 903 898 133 417 764 638 493 387 843 990 820 577 D = 106 698 614 368 578 024 442 868 771 328 920 154 780 709 906 633 937 862 801 226 224 496 631 063 125 911 774 470 873 340 168 597 462 306 553 968 544 513 277 109 053 606 095 a dešifrovat obsah zprávy ,,the magic words are squeamish ossifrage (Magická slova jsou orlosup bradatý). Dodejme však, že jejich úspěch byl umožněn jen díky tomu, že Gardner zvolil poměrně malá prvočísla. Dnes se využívají k šifrování prvočísla tak velká, že výpočet soukromého klíče z veřejného, do nějž by se zapojily všechny počítače na Zemi, by trval zhruba 20 × déle než je doposud odhadované stáří vesmíru. 6.2 Idea algoritmu Pro náhodně zvolená velká prvočísla P1, P2 spočteme N = P1 P2. Pro náhodně vybraný invertibilní prvek E spočítáme jeho inverzi D modulo (N). Jako šifrovací klíč použijeme dvojici (E,N) a šifrujeme pomocí funkce Encode(E,N)(M) = ME mod N Jako dešifrovací klíč použijeme dvojici (D,N) a dešifrujeme pomocí funkce Decode(D,N)(C) = CD mod N Nyní si ukážeme, že výše popsaný způsob šifrování a dešifrování je korektní: Víme, že pokud E D 1 mod (N), pak existuje k N, pro něž platí standardu ASCII. Jednoduchou úpravou převodní procedury však lze upravit maplet tak, aby zprávu dekódoval. Upravená převodní procedura je ve worksheetu RSA.mws Kapitola 6. Šifrování RSA 37 E D 1 + k(N). Předpokládejme, že M N. Tedy Decode(Encode(M)) M(E.D) M1+k(N) M (M(N) )k M mod N platí podle Eulerovy věty. Lze snadno ukázat, že M1+k(N) M i v případě, že (M, N) > 1. Úplný důkaz viz [9]. Uvědomme si ale, že tento případ vlastně znamená, že jsme ,,náhodou objevili při kódování zprávy do čísla M dělitele N, tj. rozklad N na prvočísla a jsme tak schopni snadno vypočítat soukromý klíč příjemce. 6.3 Postup při šifrování RSA 1. Každý uživatel U si zvolí dvě velká prvočísla P1 a P2 a vypočte NU = P1 P2. Prvočísla P1 a P2 uchová v tajnosti. 2. Dále zvolí náhodně velké přirozené číslo EU , které je nesoudělné s číslem (P1 - 1)(P2 - 1). 3. Vypočte přirozené číslo DU : 1 DU (P1 - 1)(P2 - 1) dle vztahu: EU DU = 1 mod (P1 - 1)(P2 - 1) 4. Dvojici přirozených čísel (EU , NU ) zveřejní jako svůj veřejný klíč. 5. Pokud chce uživatel V poslat zprávu M uživateli U, převede zprávu M na číslo z intervalu 1, NU . Je-li zpráva příliš dlouhá, rozdělí ji do bloků a každý blok převede zvlášť. Poté vyhledá ve veřejném registru veřejný klíč uživatele U, tj. dvojici čísel (EU , NU ), a každý blok zprávy Mi zašifruje do kryptogramu Ci dle vztahu: Ci = MEU i mod NU Takto zašifrovanou zprávu odešle uživateli U. 6. Uživatel U dešifruje kryptogram Ci pomocí soukromého klíče DU dle vztahu: Mi = CDU i mod NU Popsaný postup si můžeme názorně vyzkoušet na mapletu RSA.maplet 6.4 Implementace Nyní se podívejme na to, jak maplet pracuje uvnitř: Nejprve vyberme dvě náhodně velká prvočísla P1 a P2 ­ v mapletu je za tímto účelem definována procedura GetLargePrime Kapitola 6. Šifrování RSA 38 197 > restart; 198 > GetLargePrime := proc() 199 return nextprime(rand(10^80)()): 200 end proc: 201 202 > P1 := GetLargePrime(); 203 > P2 := GetLargePrime(); P1 := 9959688390946552033561771216646757705 9926068276305009675299763431340064249105379 P2 := 3463312908886101368864334773373197417 6548310874222673528866121995231476726634233 Nyní spočtěme N = P1 P2 a N2 = (P1 - 1)(P2 - 1) ­ v mapletu jsou za tímto účelem definovány procedury ComputeN a ComputeN2 204 > ComputeN := proc(aP1::algebraic, aP2::algebraic) 205 return aP1 * aP2: 206 end proc: 207 > ComputeN2 := proc(aP1::algebraic, aP2::algebraic) 208 return (aP1-1)*(aP2-1): 209 end proc: 210 > N := ComputeN(P1, P2); 211 > N2 := ComputeN2(P1, P2; N := 34493517372848237512608095050034301122 2957354441763581136550586503505578104655863 5106376031343593416741225347027722276355988 981065625958550072769528812005839307 N2 := 3449351737284823751260809505003430112 2295735444176358113655058650350557810465585 0087636303301705939248016544682817103988160 9830537942754384187342957271030099696 Nyní zvolme náhodně veřejný klíč E nesoudělný s N2 a vypočtěme soukromý klíč D ­ v mapletu jsou za tímto účelem definovány procedury IsPublicKeySafe a ComputeSecretKey 212 > E := GetLargePrime(); 213 > IsPublicKeySafe := proc (aE::algebraic, 214 aP1::algebraic, aP2::algebraic) 215 216 if gcd(aE, ComputeN2(aP1, aP2)) = 1 then 217 return true: 218 else 219 return false: Kapitola 6. Šifrování RSA 39 220 end if: 221 end proc: 222 > IsPublicKeySafe(E, P1, P2); 223 > DD:= ComputeSecretKey(E, N2); E := 1356966399556818437035187136318860209105 9585382901640771036052210785004346397873 true DD := 133300500987161049194509253800431382599 5045089468230840839715698845788498188664712507 9471614113403664421853939140558313636006064083 60231662710838488235918947537 Dále zvolme zprávu M, kterou chceme zašifrovat, a zašifrujme ji pomocí procedury EncodeMessage, která ke své činnosti využívá procedury ComputeBlockSize a EncodeBlock 224 > EncodeMessage := proc (aPlaintext::string, 225 aPublicKeyPower::algebraic, aPublicKeyModul::algebraic) 226 227 local xBlockSize, xNumberOfBlock, xPlaintextBlock, 228 xEncodedBlock, xEncodedMessage, i: 229 230 xBlockSize := ComputeBlockSize(aPublicKeyModul): 231 xNumberOfBlock := 232 trunc(length(aPlaintext) / xBlockSize) + 1: 233 xEncodedMessage := "": 234 for i from 1 to xNumberOfBlock do 235 xPlaintextBlock := substring(aPlaintext, 236 ((i-1)*xBlockSize+1)..i*xBlockSize): 237 xEncodedBlock := EncodeBlock(xPlaintextBlock, 238 aPublicKeyPower, aPublicKeyModul): 239 xEncodedMessage := 240 cat(xEncodedMessage, xEncodedBlock, ","): 241 end do: 242 243 return convert(substring(xEncodedMessage, 244 1..length(xEncodedMessage)-1), 'name'): 245 end proc: 246 247 > ComputeBlockSize := proc (aN::algebraic) 248 local 249 xInterval, xRealMin, xIntMin: 250 xInterval := solve (256^x >= aN, x): 251 xRealMin := evalf(op(1, xInterval)): 252 xIntMin := trunc(xRealMin): Kapitola 6. Šifrování RSA 40 253 return xIntMin: 254 end proc: 255 256 > EncodeBlock := proc (aPlaintextBlock::string, 257 aPublicKeyPower::algebraic, 258 aPublicKeyModul::algebraic) 259 260 return Power(TextToNumber(aPlaintextBlock), 261 aPublicKeyPower) mod aPublicKeyModul: 262 end proc: 263 264 > TextToNumber := proc(aMessage::string) 265 local 266 ByteToHex, HexMessageArray, HexMessageNumber: 267 268 ByteToHex:= xByte -> substring(convert(256 + xByte, 269 'hex'), 2..3): 270 HexMessageArray := 271 map(ByteToHex, convert(aMessage, bytes)): 272 HexMessageNumber := 273 cat(seq(HexMessageArray[i], 274 i = 1..nops(HexMessageArray))): 275 276 return convert(HexMessageNumber,decimal,hex): 277 end proc: Pro příklad zašifrování pomocí RSA byl vybrán poněkud delší text závěti kardinála Cesara Spady z románu Hrabě Monte Christo. Je to z důvodu demonstrace rozdělení dlouhé zprávy na jednotlivé bloky, které tak budou zašifrovány samostatně. 278 > M := "Dnes 25. dubna 1498, byv pozván Jeho Svatostí 279 Alexandrem VI. k~obědu a obávaje se, aby, nejsa spokojen tím, 280 co zaplatil jsem za klobouk, nechtěl se stát i mým dědicem 281 a nechystal mi osud kardinálu Caprary a Bentivoglia, kteří 282 byli otráveni, oznamuji svému synovci Quidonu Spadovi, svému 283 universálnímu dědici, že zakopal jsem na jistém místě, o~nemž 284 ví, neboť navštívil je se mnou, to jest v~jeskyních malého 285 ostrůvku Monte-Cristo, vše, co mám raženého zlata, drahokamů, 286 diamantů, klenotů; že jedině já vím o~existenci toho pokladu, 287 jenž páčí se asi na dva miliony římských tolarů a jejž 288 nalezne, pozvedna dvacátý balvan, počítaje od malé východní 289 zátoky v~přímé čáře. Dva otvory jsou utvořeny v~těch 290 jeskyních: poklad je v~nejvzdálenejším úhlu druhé, kterýžto 291 poklad mu odkazuji a postupuji v~úplné vlastnictví jakožto 292 svému jedinému dědici. 25. dubna 1498. Cesar Spada.": 293 > C := EncodeMessage(M, E, N); Kapitola 6. Šifrování RSA 41 C := 268...487, 131...583, 138...095, 805...033, 142...807, 339...656, 178...790, 260...175, 297...269, 344...339, 624...020, 231...059, 723...054, 220...430 Po přepsání zprávy do programu Maple a jejím zašifrování procedurou EncodeMessage bude výsledkem poněkud delší výstup. Z každého bloku byly ponechány tři počáteční a tři koncové číslice a zbytek bloku byl nahrazen třemi tečkami, aby uváděný výstup nebyl zbytečně dlouhý. Na příkladu je ale patrné rozdělení zprávy na bloky oddělené čárkou. Zašifrovanou zprávu C lze opět dešifrovat pomocí procedury DecodeMessage, která, kromě již výše uvedených pomocných procedur, využívá ke své činnosti procedury DecodeBlock, SplitEncodedMessage a NumberToText. 294 > DecodeMessage := proc (aEncodedText::string, 295 aSecretKey::algebraic, aPublicKeyModul::algebraic) 296 297 local 298 xPlaintextBlock, xEncodedBlock, 299 xSpitMessage, xPlaintext: 300 301 xPlaintext := "": 302 xSplitMessage := 303 SplitEncodedMessage(aEncodedText, ","): 304 305 for xEncodedBlock in xSplitMessage do 306 xPlaintextBlock := DecodeBlock(convert(xEncodedBlock, 307 decimal, 10), aSecretKey, aPublicKeyModul): 308 xPlaintext := cat(xPlaintext, xPlaintextBlock): 309 end do: 310 311 return convert(xPlaintext, name): 312 end proc: 313 314 > SplitEncodedMessage:= proc(aEncodedMessage::string, 315 aSplitChar::string := ",") 316 317 local 318 xEncodedBlock, xListOfEncodedBlock, 319 iChar, iListIndex: 320 321 iChar := 0: 322 iListIndex := 0: 323 xEncodedBlock := "": 324 325 while iChar < length(aEncodedMessage) do Kapitola 6. Šifrování RSA 42 326 iChar := iChar + 1: 327 if aEncodedMessage[iChar] <> aSplitChar then 328 xEncodedBlock := cat(xEncodedBlock, 329 aEncodedMessage[iChar]): 330 else 331 iListIndex := iListIndex + 1: 332 xListOfEncodedBlock[iListIndex] := xEncodedBlock: 333 xEncodedBlock := "": 334 end if: 335 end do: 336 337 if xEncodedBlock <> "" then 338 iListIndex := iListIndex + 1: 339 xListOfEncodedBlock[iListIndex] := xEncodedBlock: 340 end if: 341 342 return convert(xListOfEncodedBlock, 'list'): 343 end proc: 344 345 > DecodeBlock := proc (aEncodedTextBlock::algebraic, 346 aSecretKey::algebraic, aPublicKeyModul::algebraic) 347 348 return NumberToText(Power(aEncodedTextBlock, 349 aSecretKey) mod aPublicKeyModul): 350 end proc: 351 352 > NumberToText := proc(aNumber::algebraic) 353 local 354 HexMessageNumber, NumberOfCharacters, ByteArray, i: 355 HexMessageNumber := convert(aNumber, 'hex'): 356 if (length(HexMessageNumber) mod 2) = 1 then 357 HexMessageNumber := cat("0", HexMessageNumber) 358 end if: 359 NumberOfCharacters := length(HexMessageNumber) / 2: 360 ByteArray := linalg[vector](NumberOfCharacters): 361 for i from 1 to NumberOfCharacters do 362 ByteArray[i] := convert(substring(HexMessageNumber, 363 2*i-1..2*i), decimal, hex): 364 end do: 365 return convert( 366 convert(convert(ByteArray,list),bytes),name): 367 end proc: 368 > MM := DecodeMessage(convert(C, string), DD, N); MM := Dnes 25. dubna ... jedinému dědici. 25. dubna 1498. Cesar Spada. Kapitola 6. Šifrování RSA 43 Dešifrovaná zpráva je opět z důvodu její délky a vzhledem ke skutečnosti, že je již v textu uvedena výše, pro účely výpisu krácena. 6.5 Útoky na RSA Ačkoliv je RSA velmi silná šifra založená na pevných matematických základech, neznamená to, že je neprolomitelná. V této kapitole si popíšeme nejzákladnější metody útoků na šifru RSA. 6.5.1 Útok hrubou silou, faktorizace velkých čísel Pokusit se o útok hrubou silou s pomocí Maple je velice snadný úkol, nicméně pokud uživatel systému zvolí dostatečně velká tajná prvočísla, je pravděpodobnost úspěchu minimální. Zvolme nebezpečně malá prvočísla a vypočtěme soukromý a veřejný klíč 369 > P1:= nextprime(rand(10^30)()); 370 > P2:= nextprime(rand(10^30)()); 371 > N := ComputeN(P1, P2); 372 > N2 := ComputeN2(P1, P2); 373 > E := GetLargePrime(); 374 > IsPublicKeySafe(E, P1, P2); 375 > DD := ComputeSecretKey(E, N2); P1 := 961471544286222976468279041941 P2 := 816697134291888070572018935339 N := 7852310549217544545381980167778 11338552552171746657748052999 N2 := 785231054921754454538198016776 033169873974060699617450075720 E := 97377092984191404409 true DD := 892400551819973955894231194098 Nyní zašifrujme zprávu M 376 > M := "Tohle se nesmí nikdo dozvědět..."; 377 > C:= EncodeMessage(M, E, N); C := 16682934572615349236368514453579442257775 0750210195678897837, 74535908526433050875290411 2838354375122270854283397012790755 Veřejný klíč (E,N) je komukoliv volně dostupný. Pokud se útočníkovi povede rozložit modul N na součin prvočísel P1 a P2, je pro něj už snadné vypočítat Kapitola 6. Šifrování RSA 44 DD a dešifrovat zprávu. Pokusme se tedy rozložit modul N na součin prvočísel pomocí funkce ifactor. Čas potřebný k rozkladu modulu N na prvočísla lze změřit pomocí funkce time 378 > ts := time(): 379 > res := ifactor(N); 380 > time()-ts; res := (816697134291888070572018935339)(961471544286222976468279041941) 18.718 381 > xP1 := op(1, op(1,res)); 382 > xP2 := op(1, op(2,res)); xP1 := 816697134291888070572018935339 xP2 := 961471544286222976468279041941 Nyní jsme úspěšně rozložili modul na součin prvočísel xP1 a xP2. S jejich pomocí nyní vypočtěme xN2 a soukromý klíč xDD jakožto inverzní číslo k původnímu E. Následně dešifrujme zprávu. 383 > xN2 := ComputeN2(xP1, xP2); 384 > xDD := ComputeSecretKey(E, xN2); 385 > MM:= DecodeMessage(convert(C, string), xDD, N); xN2 := 785231054921754454538198016776033169873974060699617450075720 xDD := 420225122630508110807217261646327895136594772547061308298529 MM := Tohle se nesmí nikdo dozvědět... 6.5.2 Man-in-the-middle attack Prolomit RSA hrubou silou je sice teoreticky možné, nikoliv však v reálném čase a bez nasazení velkého množství počítačů společně pracujících na prolomení RSA. Existuje ale postup, díky němuž může Eva číst zprávy Alice a Boba, aniž by se o tom kdokoliv z nich dozvěděl. Nutnou podmínkou ale je, aby Eva mohla nejen odposlouchávat linku, přes kterou Alice a Bob komunikují, ale aby mohla zprávy zachytit a změnit jejich obsah. Představme si následující situaci. Alice, Bob (i Eva) využívají pro utajenou komunikaci asymetrickou šifru RSA. Tedy každý z nich má svůj veřejný a soukromý klíč stejně jako v sekci 6.4. * Alice ­ veřejný klíč ­ (EA, NA) ­ soukromý klíč ­ DA * Bob ­ veřejný klíč ­ (EB, NB) Kapitola 6. Šifrování RSA 45 ­ soukromý klíč ­ DB * Eva ­ veřejný klíč ­ (EE, NE) ­ soukromý klíč ­ DE Alice odjela na služební cestu, ale nechce s Bobem ztratit kontakt. Domluví se že si budou psát zprávy šifrované pomocí RSA aby chránili své soukromí. Před odjezdem ale jako vždy zavládl spěch a zmatek, ve kterém si zapomněli předat své veřejné klíče. Toho může Eva využít následujícím způsobem: 1. Alice pošle Bobovi svůj veřejný klíč (EA, NA) a požádá ho, aby udělal totéž. Eva jej však zachytí a místo něj pošle Bobovi svůj veřejný klíč (EE, NE). Totéž udělá, když Bob pošle Alici svůj veřejný klíč. 2. Bob je nyní přesvědčen, že klíč (EE, NE) je veřejným klíčem Alice a stejně tak Alice je nyní přesvědčena, že klíč (EE, NE) je veřejným klíčem Boba 3. Pokud bude Alice chtít poslat Bobovi zašifrovanou zprávu, použije k jejímu zašifrování veřejný klíč Evy. C1 = MEE 1 mod NE 4. Eva takto zašifrovanou zprávu dešifruje pomocí svého soukromého klíče CDE 1 mod NE = MEEDE 1 mod NE = M1 5. Nyní může Eva přečíst i libovolně změnit obsah zprávy M1 (zprávu se změněným obsahem označme M2) a pak ji opět zakóduje Bobovým veřejným klíčem a odešle Bobovi. C2 = MEB 2 mod NB 6. Bob obdržel zprávu M2, o které si myslí, že ji psala Alice a vůbec jej nenapadne, že by zprávu mohl někdo přečíst nebo dokonce změnit. 7. Stejně nepozorovaně jako změnila Eva Alicinu zprávu pro Boba, může měnit i Bobovy zprávy pro Alici Poznamenejme také, že výše popsaný útok by byl úspěšný i v případě, že by Alice a Bob své zprávy digitálně podepisovali. Tento problém je v praxi řešen certifikačními autoritami. Výše uvedený postup si názorně demonstrujme na Mapletu RSA-Sign.maplet: A nyní se opět podívejme, jak maplet funguje uvnitř: Nejprve vypočtěme veřejný a soukromý klíč Alice, Evy a Boba Kapitola 6. Šifrování RSA 46 386 > P1a:= GetLargePrime(); 387 > P2a:= GetLargePrime(); 388 > Na := ComputeN(P1a, P2a); 389 > N2a := ComputeN2(P1a, P2a); 390 > Ea := GetLargePrime(); 391 > IsPublicKeySafe(Ea, P1a, P2a); 392 > Da := ComputeSecretKey(Ea, N2a); P1a := 20367984599189691159381017892700257282167 316971138052373273954187062982296276889 P2a := 28387851992035382710969079256804361065171 851560152239813041506510086204611937519 Na := 578203332177853070276795004727546001181299 021765246075699551683330268030837059714157526113 994941022144822060865546079994409299462959006532 898926063958391698391 N2a := 57820333217785307027679500472754600118129 902176524607569955168333026803083705966540168952 276986715179472491136092773265524076817266682021 7438228914771483483984 Ea := 645992528607231088974414548165300741282653 84158649907016960992132925041944295111 true Da := 633518610234478839677515276686713934241164 122078181402819614854761143829789365603154774337 997720376409075242540618568650941280613214126364 17468916198962674775 393 > P1e:= GetLargePrime(); 394 > P2e:= GetLargePrime(); 395 > Ne := ComputeN(P1e, P2e); 396 > N2e := ComputeN2(P1e, P2e); 397 > Ee := GetLargePrime(); 398 > IsPublicKeySafe(Ee, P1e, P2e); 399 > De := ComputeSecretKey(Ee, N2e); Kapitola 6. Šifrování RSA 47 P1e := 45295935982551265895850422243658713761269 017228463454989661840554010533150502129 P2e := 46302080334453582842310257957225925209298 685981045753713774308909730703714656767 Ne := 209729606668835539517112981813802643440341 617232341930331748405050790929716391597343171971 583477648015784162462965193672631045715451516551 1495123450862937756943 N2e := 20972960666883553951711298181380264344034 161723234193033174840505079092971639158818337033 988299277419971614237450129661586072476453064620 75345659709626072598048 Ee := 420383928562414249994085031219443407762746 43481718240213083087420215206611649789 true De := 124399163421273123612594849233231585194621 868342960234544840228013760891425650079910011592 651673955529836857831563743793773971015861437884 2125530099969591325749 400 > P1b:= GetLargePrime(); 401 > P2b:= GetLargePrime(); 402 > Nb := ComputeN(P1b, P2b); 403 > N2b := ComputeN2(P1b, P2b); 404 > Eb := GetLargePrime(); 405 > IsPublicKeySafe(Eb, P1b, P2b); 406 > Db := ComputeSecretKey(Eb, N2b); Kapitola 6. Šifrování RSA 48 P1b := 83199225988171366877646805278084059968265 650073819389433383171164895738673769359 P2b := 89395594647520098220861726793131619288375 681184557851169886220047738769618459099 Nb := 743764428142598729957955652104399358976080 546261590606642796475287434979940560092609019539 734517411055830660735666898524901887851069369036 8620757697923700947541 N2b := 74376442814259872995795565210439935897608 054626159060664279647528743497994056007534953747 616537090120497745361409897286076876201334530870 99229545063415408719084 Eb := 357200190458069577892020318415817367728441 38652493740196700850443322647608614909 true Db := 633801065251518236031540754347152234570148 877347582460837084396237564993815584860933670078 738122872222289506758149127847930246003130301425 1888986502272165665269 Alice pošle Bobovi šifrovanou zprávu, k jejímuž zašifrování použije podvržený veřejný klíč Evy. 407 > M1 := "Ahoj Bobe, zavolej mi dnes večer, 408 budu mít čas. Alice"; 409 > C1 := EncodeMessage(M1, Ee, Ne); M1 := "Ahoj Bobe, zavolej mi dnes večer, budu mít čas. Alice" C1 := 152166776395441815950997306568437709723661469 611171660483675108937230119910863131961104121877171 820863758612700381232229985669182632589870860418747 9362206965216 Eva zprávu zachytí, dešifruje a změní a následně pošle Bobovi 410 > DecodeMessage(convert(C1, string), De, Ne); 411 > M2 := "Ahoj Bobe, dnes večer mi nevolej, 412 budu na poradě. Alice"; 413 > C2 := EncodeMessage(convert(M2, string), Eb, Nb); Kapitola 6. Šifrování RSA 49 Ahoj Bobe, zavolej mi dnes večer, budu mít čas. Alice M2 := "Ahoj Bobe, dnes večer mi nevolej, budu na poradě. Alice" C2 := 73562143807514464729951163337719840797430641603 82947822765068554476944142839835779494807891599515927 22649213689195544001516472659953516456738175268811007 9974724 Bob dešifruje domnělou zprávu od Alice a odpoví na ni 414 > DecodeMessage(convert(C2, string), Db, Nb); 415 > M3 := "Ahoj Alice, to nevadí, kdy kdy Ti můžu 416 zavolat? Bob"; 417 > C3 := EncodeMessage(M3, Ee, Ne); Ahoj Bobe, dnes večer mi nevolej, budu na poradě. Alice M3 := "Ahoj Alice, to nevadí, kdy kdy Ti můžu zavolat? Bob" C3 := 1537986890423812612745931104073836085345834044106 6445163109371516369917027068077936698806670809146863623 46851002051018859460762342186028550691314333171624601290 Eva Bobovu odpověď opět zachytí, změní a zašifruje a poté pošle Alici 418 > DecodeMessage(convert(C3, string), De, Ne); 419 > M4 := "Ahoj Alice, to je skvělé, určitě Ti 420 zavolám. Bob"; 421 > C4 := EncodeMessage(M4, Ea, Na); Ahoj Alice, to nevadí, kdy kdy Ti můžu zavolat? Bob M4 := "Ahoj Alice, to je skvělé, určitě Ti zavolám. Bob" C4 := 1489738198685088627107150965832769650362895573324 3168840741708602438080247620190653738608905781755771782 3497475273451012015643912661774235844127387804024563432 Alice dešifruje domnělou zprávu od Boba 422 > DecodeMessage(convert(C4, string), Da, Na); Ahoj Alice, to je skvělé, určitě Ti zavolám. Bob Kapitola 7 Digitální podpis Další významnou myšlenkou Diffieho a Hellmana je digitální podpis. Digitální podpis by měl plně nahradit obvyklý podpis rukou, proto by měl mít i totožné vlastnosti. Pokud Alice podepsala dokument D, obyčejný podpis zaručuje následující: * Stejný podpis jako Alice není schopen vytvořit nikdo jiný * Každý je schopen ověřit, že dokument podepsala opravdu Alice * Podpis je pevně svázán s dokumentem D, který Alice podepsala a nelze jej přenést na jiný dokument Na digitální podpis jsou kladeny naprosto stejné nároky; formálně vyjádřeno, digitální podpis musí naplňovat požadavky na: Indentifikaci, tj. podpis musí jednoznačně identifikovat osobu, která jej vy- tvořila; Autentizaci, tj. musí existovat mechanismus, pomocí něhož může kdokoliv ověřit, že je podepisující skutečně tou osobou, za kterou se vydává; Integritu dat, tj. musí být zajištěno, že nikdo není schopen jakkoliv změnit obsah dokumentu, jenž byl podepsán; Nepopiratelnost, tj. skutečnost, že osoba podepsaná pod dokumentem dokument opravdu podepsala, nesmí být jakýmkoliv způsobem zpochybnitelná. Explicitně pak digitální podpis nesmí být možné připojit k dokumentu, který vlastník podpisu nepodepsal, a podpis nemůže vytvořit nikdo jiný, než jeho vlastník; 50 Kapitola 7. Digitální podpis 51 7.1 Postup při digitálním podepisování zprávy pomocí RSA Každý uživatel U šifrovacího systému vlastní svůj veřejný klíč, tj. dvojici čísel (EU , NU ) a svůj soukromý klíč, tj. číslo DU mající stejný význam jako v 6.4 Pokud chce uživatel U podepsat zprávu M, postupuje takto: 1. Pomocí hashovací funkce H vypočte hash H(M) zprávy M. 2. Podepíše hash H(M) svým soukromým klíčem DU , tj. vypočte číslo SH(M) dle vztahu: SH(M) = H(M)DU mod NU a odešle podpis SH(M) spolu se zprávou uživateli V . Zprávu může před odesláním zašifrovat dle postupu v 6.4 pokud je důvěrná, nebo odeslat jako otevřený text, pokud důvěrná není. 3. Uživatel V nejprve zprávu, byla-li zašifrována, dešifruje podle postupu v 6.4 Otevřený text zprávy, který uživatel V obdrží, označme m. Poté vypočte hash H(m). 4. Následně ve veřejném registru vyhledá veřejný klíč (EU , NU ) uživatele U a dešifruje podpis SH(M) dle vztahu: H(M) = SH(M) Obrázek 7.1: Podpis zprávy 5. Pokud se hashe H(M) a H(m) rovnají, pak zpráva, kterou obdržel, je zprávou, jenž podepsal uživatel U. Pokud se ale nerovnají, znamená to, že zpráva byla někým změněna a není totožná se zprávou, kterou podepsal uživatel U. 7.2 Implementace digitálního podpisu pomocí RSA V následující části budeme využívat procedury popsané v 6.4 Kapitola 7. Digitální podpis 52 Obrázek 7.2: Ověření podpisu zprávy Pro získání hashe ze zprávy M použijeme funkci z knihovny StringTool Hash, která z řetězce, jenž je jí zadán jako vstupní parametr, vytvoří MD5 hash. Zde poznamenejme, že hashovací funkce MD5 je dnes již prolomena a je tedy pro praktické použití nevhodná. Více informací o prolomení hashovací funkce MD5 naleznete v [12], kde si můžete též stáhnout program ke generování multikolizních zpráv. K demonstraci principu digitálního podpisu je však hashovací funkce MD5 dostatečná a vedlejším efektem je, že si čtenář této práce může vyzkoušet útok na digitální podpis podvrhem kolizního MD5 hashe. 423 > GetHash := proc(aMessage::string) 424 use StringTools in 425 return convert(Hash(aMessage), 'name'): 426 end use: 427 end proc: Uživatel U vytvoří svůj souromý a veřejný klíč 428 > P1 := GetLargePrime(); 429 > P2 := GetLargePrime(); 430 > N := ComputeN(P1, P2); 431 > N2 := ComputeN2(P1, P2); 432 > E := GetLargePrime(); 433 > IsPublicKeySafe(E, P1, P2); 434 > DD := ComputeSecretKey(E, N2); Kapitola 7. Digitální podpis 53 P1 := 7596688480402267121842644385510609049418 507520172675888232089719702569500424091 P2 := 1850963947408549717972278085114090772031 917152860611143121757789573574800580307 N := 14061196496918437435785790972443111779216 2911104505135577107244267260935628102478194610 6044310555855259113064526282447939275078146924 1532158085909589402975937 N2 := 1406119649691843743578579097244311177921 6291110450513557710724426726093562810238371808 6326322887187376686600205630030289680777481822 10178310576633445101971540 E := 78737583453547871525800433418961373296815 443596460415997796805591310596113349197 true DD := 4417857746694505658329534758781575648771 3666794607620844181765693050636168932359250323 9263180410770372257063879150236108112716752717 3547781157201658845333973 Uživatel zvolí zprávu M: 435 > M := "Toto je zpráva, pod kterou se podepíšu."; M := "Toto je zpráva, pod kterou se podepíšu." Vytvoří hash H zprávy M 436 > H := GetHash(M); H := d03eb63120505d5554861d5661c9cf42 Podepíše hash H pomocí procedury GetSign 437 > GetSign := proc(aHash::string, 438 aD::algebraic, aN::algebraic) 439 440 return EncodeBlock(aHash, aD, aN): 441 end proc: 442 > S := GetSign(convert(H, string), DD, N); S := 9414815475447161917795238747533870934960663212137 292702519814455017736578192545991264608105205752881000 508906551624639227895716975943521163431051402165296937 Kapitola 7. Digitální podpis 54 Ověří podpis S pomocí procedury VerifySign 443 > VerifySign := proc(aSign::string, 444 aE::algebraic, aN::algebraic) 445 446 return DecodeBlock(convert(aSign, decimal, 10), aE, aN): 447 end proc: 448 > h := VerifySign(convert(S, string), E, N); h := d03eb63120505d5554861d5661c9cf42 Porovnáním zjistíme, že hash H vytvořený ze zprávy a hash získaný z podpisu jsou si rovny 449 evalb(H=h); true Kapitola 8 Programování mapletů Využívání mapletů ve výuce má velmi pozitivní efekt. Jejich tvorba je však zatím velmi náročná. Ze začátku mi práci velmi komplikoval fakt, že Maple nemá žádný rozumný editor zdrojového kódu mapletů. Existuje sice nástroj na tvorbu mapletů, tzv. Maplet Builder, ve kterém se jednodušší maplety dají ,,vyklikat , bohužel se ale zdrojový kód navázaný na formulářové prvky zobrazuje v malém editačním okénku jako čistý text. Delší kód je tím pádem nečitelný a nelze ho rozumě v Maplet Builderu editovat. Je též možné psát maplety v klasickém worksheetu, ale ani ten není pro jejich tvorbu nikterak vhodný. Při zmáčknutí klávesy Enter se rozepsaný maplet pokusí zkompilovat, kurzor se přesune z nedokončeného bloku na konec příkazu což nevybíravým způsobem naruší koncentraci programátora. Pro přechod na nový řádek je nutné použít klávesovou zkratku Shift+Enter. Ale ani teď se editor nezachová nejlépe, protože kurzor umístí na první znak nového řádku a nerespektuje odsazení bloku. Tvůrci mapletu pak nezbývá, chce-li mít přehledný kód, než odsazení dorovnat vložením potřebného počtu mezer, což je při několika vnořených blocích velmi nepříjemné. Další nepříjemností je, že přechod na nový řádek je interpretován neviditelným znakem a lze za něj umístit kurzor. Tedy po zmáčknutí klávesy End se přesunete za neviditelný znak přechodu na nový řádek a pokud začnete psát, zjistíte, že nečekaně píšete o řádek níž, než jste původně zamýšleli. Pro tvorbu mapletů, jsem si nakonec vybral multifunkční textový editor pro programátory jEdit. (Případný zájemce si jej může stáhnou na adrese: www.jedit.org/index.php?page=download). Velkou výhodou jEditu bylo, že dovedl zvýrazňovat syntaxi Maplu tak, že kód mapletu v něm zobrazený byl velmi přehledný. Taktéž chování editoru při psaní odpovídalo pokročilejším programovacím editorům a k dokonalosti mi už jen chyběla intellisence, která by mi umožnila automaticky dokončit rozepsaný výraz a vyznačila chyby v kódu, které by neprošly statickou kompilací. Pokud by byl rozumný textový editor zahrnutý v další verzi programu Maple, věřím, že by popularita tvorby mapletů výrazně vzrostla. 55 Kapitola 8. Programování mapletů 56 Syntaxe jazyka mapletů je pouze rozšířením stávajícího jazyka Maple o knihovnu Maplets. Díky tomu se jednoduché maplety naučí psát velmi rychle psát uživatel Maple, který je zběhlým v psaní procedur. Program maplet je tvořený funkcí a spuštění programu je totožné s vyhodnocením funkce maplet. Volba funkcionální syntaxe ale podle mého názoru není příliš šťastná, protože převážná část mapletu je tvořena deklarací formulářových prvků a jejich vzájemných interakcí.Zamýšlená podobnost mapletu s funkcí je zde spíše zavádějící a člověku neznalému programování orientaci neusnadní. Velmi kladně musím hodnotit intuitivní tvorbu jednoduchých formulářů v Maplet Builderu, která, věřím tomu, nebude dělat problém ani naprostým začátečníkům. Pokud budete ale na uživatelské rozhraní klást větší nároky (členitější formuláře ve více okenní aplikaci) zjistíte, že uděláte nejlépe, když si rozhraní oken dobře rozmyslíte a sami vytvoříte v textovém editoru. Pokud Budete chtít vytvořit prezentační maplety, narazíte na dva velmi nepříjemné aspekty tvorby uživatelského rozhraní v Maple: 1. Ve formuláři nelze vytvářet nové elementy (tlačítka, editační pole, ) po spuštění mapletu. 2. Elementu ve formuláři nelze absolutně určit pozici ani pevně nastavit rozměry. První nepříjemný aspekt se dá obejít tím, že si předem definujete veškeré elementy, které budete kdykoli během práce s mapletem potřebovat a ty které aktuálně nemají být viditelné, skryjete pomocí přiřazení hodnoty false do vlastnosti visible požadovaného elementu. To má za následek další, ale již méně podstatnou nepříjemnost. Maple totiž automaticky přepočítává rozmístění prvků uživatelského rozhraní optimálně vzhledem k velikosti formuláře. Z toho důvodu také nelze elementům nastavit absolutní pozici. Takže se Vám po zobrazení nebo naopak skrytí elementu formulář trochu přeuspořádá. Přes veškeré popsané nepříjemnosti lze vytvářet i velmi složité maplety. Mějme ale na paměti také to, že maplet by měl být z didaktického hlediska co nejvíce intuitivní, s jednoduchým ovládáním, a pokud možno co nejnázornější. Pokud se nám tedy bude zdát, že Maple nenabízí pro tvorbu námi navrženého řešení dostatečné prostředky, měli bychom zvážit, zda by nebylo lepší komplexní problém, který chceme řešit, rozdělit na podproblémy a každý z nich realizovat samostatným mapletem. Kapitola 9 Závěr V jednotlivých kapitolách práce jsem se nejprve zabýval historií a postupným vývojem kryptografie až do okamžiku, kdy se začala opírat o modulární aritmetiku. V další kapitole jsem rozebral základní příkazy a funkce modulární aritmetiky v systému Maple takovým způsobem, aby měl čtenář možnost tyto příkazy samostatně vyzkoušet a porozumět tak hlavnímu těžišti práce ­ kryptografii s veřejným klíčem. Než jsem se však pustil do hlavních kapitol, považoval jsem za nezbytné objasnit co nejnázorněji problematiku distribuce klíčů, ze které pak vyplynulo, jak užitečné jsou z tohoto hlediska asymetrické šifry. Podrobná analýza kryptografie s veřejným klíčem, která je probrána v následujících kapitolách, navazuje na předcházející části práce a je jejím logickým vyústěním. Pro názornou představu asymetrického šifrování jsem vybral známou šifru RSA, se kterou se každý čtenář v praxi setkává, aniž by to často vůbec věděl. Vysvětlením principu funkce této šifry a nemožností jejího prolomení, se proto velmi názorně zabývá celá jedna kapitola. Je doplněna ukázkou z Maple a čtenář je motivován k tomu, aby si šifru samostatně vyzkoušel pomocí přiložených mapletů. V další části práce je vysvětlen princip digitálního podpisu. Jeho implementace je realizována pomocí šifry RSA. V poslední kapitole práce upozorňuji na nedostatky, které podle mého názoru programování maletů obnáší. Práce je určena čtenáři se středoškolskými znalostmi matematiky, proto jsem ji psal pokud možno srozumitelným a zábavným způsobem a matematickou notaci jsem uváděl pouze v případech nezbytně nutných. Také maplety, které jsou nedílnou součástí práce, umožňují problematiku šifrování pochopit co nejnázornějším způsobem. Hlavním cílem bylo vysvětlit zvídavému čtenáři princip kryptografických algoritmů a vzbudit v něm zájem o tuto část matematiky. Na přiloženém CD naleznete též hypertextovou elektronickou verzi ve formátu PDF. Součástí CD jsou i veškeré maplety a worksheety, které jsou v práci uvedeny. Práce byla vysázena v systému LATEX2 57 Literatura [1] Introduction to maple [3rd ed.], Heck A., New York: Springer, 2003. [2] Monagan M. B.: Maple V: Programming guide. Edited by J. S. Devitt. New York: Springer-Verlag, 1996. [3] http://www.maplesoft.cz, 2009. [4] http://www.maplesoft.com, 2009. [5] http://www.mapleprimes.com, 2009. [6] Systém Maple 12 s nápovědou, 2009. [7] http://en.wikipedia.org, 2009. [8] http://cs.wikipedia.org, 2009. [9] Handbook of applied cryptography, Edited by A. J. Menezes - Paul van Oorschot - Scott A. Vanstone. Boca Raton, CRC Press, 1997. [10] Algebra 2 ­ Teorie čísel, Michal Bulant, http://is.muni.cz/el/1431/jaro2007/M6520/um/main-print.pdf [11] Kniha kódů a šifer, Simon Singh, Dokořán, 2003. [12] http://cryptography.hyperlink.cz/2004/kolize hash.htm, Vlastimil Klíma [13] Kryptologie, šifrování a tajná písma, Vondruška P., edice OKO, Albatros 2006 http://crypto-world.info/oko/index.php [14] http://www.math.muni.cz/ paseka/ftp/lectures/2stkryptografie.ps, Paseka J. 58 Příloha Součástí diplomové práce je příloha s diskem CD. Tento disk obsahuje hypertextovou verzi této práce ve fotmátu PDF a mapleovské worksheety (Maple 12) a je členěn do těchto částí: 1. Maplety (a) DiffieHellmanMerkle.maplet (b) RSA.maplet (c) RSA-ManInTheMiddleAttack.maplet (d) RSA-Sign.maplet 2. Worksheety (a) Algebra-v-Maple.mws (b) Monoalfabeticka-sifra.mws (c) DiffieHellmanMerkle.mws (d) RSA.mws 59 Kapitola 10 Příklady mapletů 10.1 Diffie-Hellman-Merkle 1. Alice zvolí parametry Y , P a odešle je Bobovi. Viz obrázek 10.1. 2. Alice zvolí Xa, vypočte f(Xa) a výsledek odešle Bobovi. Viz obrázek 10.2. 3. Bob zvolí Xb, vypočte f(Xb) a výsledek odešle Alici. Viz obrázek 10.3. 4. Alice a Bob vypočítají společný klíč. Viz obrázek 10.4. Obrázek 10.1: Krok 1. 60 Kapitola 10. Příklady mapletů 61 Obrázek 10.2: Krok 2. Alice Obrázek 10.3: Krok 2. Bob Obrázek 10.4: Krok 3. Kapitola 10. Příklady mapletů 62 10.2 RSA 1. Vygenerujeme tajná prvočísla P1, P2. Viz obrázek 10.5. 2. Vytvoříme veřejný klíč. Viz obrázek 10.5. 3. Vytvoříme soukromý klíč. Viz obrázek 10.5. 4. Zašifrujeme a dešifrujeme zprávu. Viz obrázek 10.5. Obrázek 10.5: Krok 1. Generování prvočísel. Kapitola 10. Příklady mapletů 63 Obrázek 10.6: Krok 2. Vytvoření veřejného klíče. Obrázek 10.7: Krok 3. Vytvoření soukromého klíče. Kapitola 10. Příklady mapletů 64 Obrázek 10.8: Šifrování a dešifrování zprávy. 10.3 RSA ­ Man-in-the-middle-attack 1. Alice, Bob i Eva si vytvoří veřejný a soukromý klíč. Viz obrázek 10.9. 2. Alice odešle svůj veřejný klíč Bobovi, Eva jej zachytí a místo něj podvrhne Bobovi svůj veřejný klíč. Viz obrázek 10.10. 3. Bob odešle svůj veřejný klíč Alici, Eva jej zachytí a místo něj podvrhne Alici svůj veřejný klíč. Viz obrázek 10.11. 4. Eva zachtí a dešifruje zprávu zaslanou Alicí, změní ji, zašifruje a odešle Bobovi. Viz obrázek 10.12. Viz obrázek 10.13. Kapitola 10. Příklady mapletů 65 Obrázek 10.9: Vytvoření veřejného a soukromého klíče Alice, Boba a Evi. Obrázek 10.10: Eva podvrhne svůj klíč Bobovi. Kapitola 10. Příklady mapletů 66 Obrázek 10.11: Eva podvrhne svůj klíč Alici. Obrázek 10.12: Eva zachytí a dešifruje zprávu od Alice. Obrázek 10.13: Eva změní zprávu, zašifruje ji a odešle Bobovi. Kapitola 10. Příklady mapletů 67 10.4 RSA ­ Digital signature 1. Alice i Bob vypočtou svůj veřejný a soukromý klíč a doručí si ho bezpečným kanálem. Viz obrázek 10.14. 2. Alice digitálně podepíše zprávu a následně Bob její podpis ověří. Viz obrázek 10.15. Obrázek 10.14: Vypočet veřejného a soukromého klíče Alice a Boba. Obrázek 10.15: Podepsání zprávy a ověření podpisu.