MB141 -12. přednáška Aplikace teorie čísel Martin Čadek s využitím přednášek pro předmět MB104 Jarní semestr 2020 12. přednáška Aplikace teorie čísel Osnova 12. přednášky Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem 12. přednáška Aplikace teorie čísel Základní úlohy výpočetní teorie čísel V mnoha praktických úlohách využívajících výsledky teorie čísel je zapotřebí umět rychle provést jeden či více z následujících výpočtů: O běžné aritmetické operace (součet, součin, dělení se zbytkem) na celých číslech, Q zbytek mocniny celého čísla a na přirozené číslo n po dělení daným m. O inverzi celého čísla a modulo m e N, O největší společný dělitel dvou celých čísel (a případně koeficienty do Bezoutovy rovnosti), O rozhodnout o daném čísle, je-li prvočíslo nebo složené, O v případě složenosti rozložit dané číslo na součin prvočísel. 12. přednáška Aplikace teorie čísel 3/17 Základní aritmetické operace Základní aritmetické operace se i na velkých číslech obvykle provádějí obdobně jako jsme se to učili na základní a střední škole, kdy umíme sčítat v lineárním čase, násobit a dělit se zbytkem v kvadratickém čase. Pro násobení, které je základem mnoha dalších operací, existují asymptoticky rychlejší algoritmy (typu rozděl a panuj) - např. první takový Karatsubův (1960) časové náročnosti 0(nlog23) nebo algoritmus Schónhage-Strassenův (1971) časové náročnosti 0(nlog nlog log n). Číslo n zde udává celkový počet cifer vstupujících do výpočtu. Pěkný přehled najdete např. na http://en.wikipedia.org/wiki/Computational_ complexity_of_mathematical_operations 12. přednáška Aplikace teorie čísel 4/17 Největší společný dělitel a modulární inverze Jak už jsme ukazovali dříve, výpočet výpočet inverze modulo m, tj. řešení kongruence a • x = 1 (mod m) s neznámou x lze snadno (díky Bezoutově větě) převést na výpočet největšího společného dělitele čísel aa mana hledání koeficientů /c, / do Bezoutovy rovnosti k • a + / • m = 1 (nalezené k je pak onou hledanou inverzí a modulo m). Podrobná analýza ukazuje, že tento algoritmus je kvadratické časové složitosti. 12. přednáška Aplikace teorie čísel Modulární umocňování V kryptografii s veřejným klíčem budeme budeme potřebovat umocňování modulo m. To se také využívá při ověřování, zda je dané číslo prvočíslo nebo číslo složené. Jedním z efektivních algoritmů je tzv. modulární umocňování zprava doleva: function modular_pow(base, exponent, modul) result := 1 while exponent > 0 if (exponent mod 2 = = 1): result := (result * base) mod modul exponent := exponent » 1 base = (base * base) mod modul return result Symbol >> ve třetím řádku zdola zanamená, že od exponentu zapsaného v dvojkové soustavě odebereme poslední cifru 1. 12. přednáška Aplikace teorie čísel 6/17 Idea algoritmu Algoritmus modulárního umocňování je založen na myšlence, že např. při počítání 264 (mod 1000) • není třeba nejprve počítat 264 a poté jej vydělit se zbytkem číslem 1000, ale lépe je postupně násobit „dvojky" a kdykoliv je výsledek větší než 1000, provést redukci modulo 1000, • ale zejména, že není třeba provádět takové množství násobení (v tomto případě 63 naivních násobení je možné nahradit pouze šesti umocněními na druhou, neboť 264 = (((((^YYYYY- 2\2\2\2\2\2 12. přednáška Aplikace teorie čísel Ukázka průběhu algoritmu Vypočtěme 2bb0 (mod 561). Protože 560 = (1000110000)2 dostaneme uvedeným algoritmem exponent base result exp's last digit 560 2 1 0 280 4 1 0 140 16 1 0 70 256 1 0 35 460 1 1 17 103 460 1 8 511 256 0 4 256 256 0 2 460 256 0 1 103 256 1 0 511 1 0 A tedy 2560 = 1 (mod 561). 12. přednáška Aplikace teorie čísel 8/17 Efektivita modulárního umocňování V průběhu algoritmu se pro každou binární číslici exponentu provede umocnění základu na druhou modulo m (což je operace proveditelná v nejhůře kvadratickém čase), a pro každou „jedničku" v binárním zápisu navíc provede jedno násobení. Celkově jsme tedy schopni provést modulární umocňování nejhůře v kubickém čase. Další úlohy výpočetní teorie čísel jsou testování prvočíselnosti a rozklad složených čísel na prvočísla. Tato témata jsou na samostatnou přednášku, nebudeme se jimi zde zabývat. Více lze najít v učebnici Drsná matematika v odstavcích 10.38-47. 12. přednáška Aplikace teorie čísel Kryptografie s veřejným klíčem Dva hlavní úkoly pro „public-key cryptography" jsou zajistit • šifrování, kdy zprávu zašifrovanou veřejným klíčem není schopen rozšifrovat nikdo kromě držitele soukromého klíče, • podepisování, kdy integrita zprávy podepsané soukromým klíčem odesílatele může být ověřena kýmkoliv s přístupem k veřejnému klíči odesílatele. Nejčastěji používané systémy: • RSA (šifrování) a odvozený systém pro podepisování zpráv • Digital signature algorithm (DSA) a varianta založená na eliptických křivkách (ECDSA) a Rabinův kryptosystém (a podepisování) • Diffie-Hellmanův protokol na výměnu klíčů (DH) • EIGamal kryptosystém (a podepisování) • Kryptografie eliptických křivek (ECC) 12. přednáška Aplikace teorie čísel 10/17 RSA Rivest, Shamir, Adleman (1977); Coc/cs(1973) • Jsou dva typy klíčů - veřejný a soukromý. « Generování klíčů: zvolí se dvě velká prvočísla p, q, vypočte se n = pq,