MB141 -12. přednáška Aplikace teorie čísel Martin Čadek s využitím přednášek pro předmět MB104 Jarní semestr 2021 12. přednáška Osnova 12. přednášky • Výpočetní aspekty teorie čísel • Kryptografie s veřejným klíčem 12. přednáška 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 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 Q(n log n log 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 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 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 znamená, že od exponentu zapsaného v dvojkové soustavě odebereme poslední cifru 1. 12. přednáška 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 = (((((22)2)2)2)2)2. 12. přednáška 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 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 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 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, g, vypočte se n = pg, g = 1 a polož x = (aps + bqr) (mod n), y = (aps - Ďgr) (mod n) • druhými odmocninami z C modulo n jsou ±x, ±y. Zdůvodnění: Z Čínské zbytkové věty vyplývá, že z2 = C (mod pg), právě když současně platí z2 = C (mod p) a z2 = C (mod g). Lze ukázat, že pro každé liché prvočíslo platí, že kvadratická kongruence z2 = C (mod p) má řešení právě když cV = 1 (mod p). Tedy při počítání (mod p) dostáváme x2 = y2 = (bq)2r2 = 12 • ďr1 = C =1 C = C (mod p). Analogický výpočet lze provést (mod q). 12. přednáška Příklad V Rabínově kryptosystému Alice zvolila za svůj soukromý klíč p = 23, q = 31, veřejným klíčem je pak n = pq = 713. Zašifrujte zprávu M = 327 pro Alici a ukažte, jak bude Alice tuto zprávu dešifrovat. C = 3272 = 692. Při dešifrování spočítáme C6 = (2)6 = 18 (mod 23) a C8 = 108 = 14 (mod 31). Dále -4-23 + 3-31 = 1. Proto máme 4 kandidáty na zprávu, a to ±4 • 23 • 14 ± 3 • 31 • 18 (mod 713). To jsou čísla ±38 a ±327 (mod 731). 12. přednáška Princip digitálního podpisu Podepisování O Vygeneruje se otisk (hash) HM zprávy pevně stanovené délky (např. 160 nebo 256 bitů). O Podpis zprávy Sa(Hm) je vytvořen (pomocí dešifrování) z tohoto hashe s nutností znalosti soukromého klíče Sa podepisujícího. O Zpráva M (případně zašifrovaná veřejným klíčem příjemce) je spolu s podpisem odeslána. Ověření podpisu O K přijaté zprávě M se (po jejím případném dešifrování) vygeneruje otisk HřM Q S pomocí veřejného klíče VA (deklarovaného) odesílatele zprávy se rekonstruuje původní otisk zprávy Va(Sa(Hm)) = Hm-O Oba otisky se porovnají HM = HřM?. 12. přednáška Výměna klíčů podle Diffie-Hellmana Diffie, Hellman (1976), Williamson (1974) Výměna klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj. náhrada jednorázových klíčů, kurýrů s kufříky, ...). • Dohoda stran na prvočísle p a primitivním kořenu g modulo p (veřejné). (Zopakujme, že g je primitivní kořen modulo prvočíslo p, jestliže gn = 1 (mod p) pouze pro násobky p - 1.) • Alice vybere náhodné číslo a a pošle Bobovi ga (mod p) • Bob vybere náhodné b a pošle Alici gb (mod p) • Společným klíčem pro komunikaci je gab (mod p). 12. přednáška Kryptosystém EIGamal Z protokolu Diffie-Hellman na výměnu klíčů je odvozen šifrovací algoritmus EIGamal: • Alice zvolí prvočíslo p spolu s primitivním kořenem g. • Alice zvolí tajný klíč a, spočítá h = ga (mod p) a zveřejní veřejný klíč (p, h). • Šifrování zprávy M: Bob zvolí náhodné b a vypočte C-i = gb (mod p) a C2 = M • hb (mod p) a pošle Alici (Ci,c2). • Dešifrování zprávy provede Alice tak, že spočítá inverzi / k Cf = (gb)a = gaĎ (mod p) a vynásobí C2 • l=Mgab' l=M (mod p). Příklad najdete ve cvičení. Analogicky jako pro RSA lze odvodit podepisování. 12. přednáška