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, O 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: ,n _(fry)* n •_ 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 2560 (mod 561]. Protože 560 = (1000110000)2 dostaneme uvedeným algoritmem 2 • 1 exponent 560 280 140 70 35 17 8 4 2 G> o base 2 4 16 256 460 TÜ5 511, 256 460 103 result 460 256 256" 256 256 1 exp's last digit 0 0 0 0 1 T o. "ô" 0 1 o A tedy 2560 = 1 (mod 561). ff O " 4 fan * • «í 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. /yj& 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. ^^^ ^^^^^^^^^^^^^ A, & JO 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) 12. přednáška RSA Rivest, Shamir, Adleman (1977); Cocks(1973) • Jsou dva typy klíčů - veřejný a soukrom; • Generování klíčů: zvolí se dvě velká prvočísla p, q, vypočte se/ni= pj, \p{rí) = (p - 1 )(q - 1). Přitom pouze n je fit veřejné, 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)^ = 18 (mod 23) a C8 = 108 = 14 (mod 31). Dále -4 • 23T3 -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 I / 23 31 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-Q Oba otisky se porovnají HM = HřM?. 12. přednáška Výměna klíčů podle Diffie-Hellmana -y /Qfl.6 - f/l *\ I__^„A. _ , . x /&- Mi D/'ff/e, 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). i 12. přednáška Kryptosystém EIGamal C t.- T- Z protokolu Diffie-Hellman na výměnu klíčů je odvozen šifrovací algoritmus EIGamal: S H • 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, g, h)* *k~ = (.1) I-if C~sf (-3)$ = -31 S ^ **"*u1