Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo OOOOOOOO<3D0!30Offl0t>OOOOOOOOO Diskrétní matematika B - 5. týden Aplikace teorie čísel - Počítání s velkými čísly, kryptografie Michal Bulant Masarykova univerzita Fakulta informatiky jaro 2014 Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooooooooooo Obsah přednášky Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti • Testy na složenost • Testy na prvočíselnost • Hledání dělitele Kryptografie s veřejným klíčem Úvod do kódování • (n, /c)-kódy • Lineární kódy Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooooooooooo Doporučené zdroje • Jan Slovák, Martin Panák, Michal Bulant, Matematika drsně a svižně, MU Brno, 2013, 774 s. (též jako e-text). • Předmětové záložky v IS MU • Michal Bulant, výukový text k přednášce Elementární teorie čísel, http://is.muni.cz/el/1431/podzim2012/M6520/ um/main-print.pdf • William Stein, Elementary Number Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupné na http://wstein.org/ent/ent.pdf a http://wstein.org/edu/2007/spring/ent/ Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooooooooooo Doporučené zdroje - algoritmy • Radan Kučera, výukový text k přednášce Algoritmy teorie čísel, http://www.math.muni.cz/~kucera/texty/ATC10.pdf • Donald E. Knuth, The Art Of Computer Programming. • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, MIT Press, 2009. • Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press, 2001. (též jako e-text). Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování •oooooo ooooooooooooooooooooo ooooooooooooooooo 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 G 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. Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování oaooooo ooooooooooooooooooooo ooooooooooooooooo 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, 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), který využívá tzv. Fast Fourier Transform. Ten je ale přes svou asymptotickou převahu výhodný až pro násobení čísel majících alespoň desítky tisíc cifer (a používá se tak např. v GIMPS). Pěkný přehled je např. na http://en.wikipedia.org/wiki/ Computational_complexity_of_mathematical_operations Jak už jsme ukazovali dříve, výpočet ř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 a a m a na hledání koeficientů k, I do Bezoutovy rovnosti k ■ a + / • m = 1 (nalezené k je pak onou hledanou inverzí a modulo m). function extended_gcd(a, m) i f m = 0 retu rn (1, 0) e I s e (q, r) (k, I) := divide (a, m) := exten ded_gcd(m, r) ( I , k - q * I ) retu rn Podrobná analýza (viz např. [Knuth] nebo [Wiki]) ukazuje, že tento algoritmus je kvadratické časové složitosti. Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooovooo ooooooooooooooooooooo ooooooooooooooooo Modulární umocňování Modulární umocňování je, jak jsme již viděli dříve, velmi využívaná operace mj. 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 mod u la r.pow ( base , exponent , modulus) result := 1 while exponent > 0 if (exponent mod 2 = = 1): result := (result * base) mod modulus exponent := exponent » 1 base = (base * base) mod modulus retu rn result Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování oooo^oo ooooooooooooooooooooo ooooooooooooooooo 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- Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooo»o ooooooooooooooooooooo OOOOOOOOatnOODODODOOOOOOOOO Příklad (Ukázka průběhu algoritmu) Vypočtěme 2560 (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). Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování oooooo* ooooooooooooooooooooo ooooooooooooooooo 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 n (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. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo »00000000000000000000 ooooooooaoraaraBDOoooooooo Přestože platí základní věta aritmetiky, která nám garantuje, že každé přirozené číslo se dá jednoznačným způsobem rozložit na součin prvočísel, praktické nalezení tohoto rozkladu je obvykle velmi výpočetně náročná operace, obvykle prováděná v několika krocích: O nalezení všech dělitelů nepřevyšujících určitou hranici (metodou pokusného dělení všemi prvočísly až do této hranice, typicky je touto hranicí cca 106) Q otestování zbylého faktoru na složenost (tzv. test na složenost, testující některou nutnou podmínku prvočíselnosti) a) pokud test složenosti prohlásil, že zkoumané číslo je asi prvočíslo, pak testem na prvočíselnost ověřit, že je to opravdu prvočíslo. b) pokud test složenosti prohlásil, že zkoumané číslo je složené, pak nalézt netriviálního dělitele. Takto je posloupnost kroků prováděna z toho důvodu, že jednotlivé algoritmy mají postupně (výrazně) rostoucí časovou složitost. V roce 2002 Agrawal, Kayal a Saxena publikovali algoritmus, který testuje prvočíselnost v polynomiálním čase, prakticky je ale zatím stále efektivnější používat výše uvedený postup. Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo o»ooooooooooooooooooo ooooooooooooooooo Jak s jistotou poznat složená čísla Takzvané testy na složenost testují některou nutnou podmínku prvočíselnosti. Nejjednodušší takovou podmínkou je Malá Fermatova věta. Fermatův test Existuje-li pro dané N nějaké a ^ 0 (mod N) takové, že aN 1 ^ 1 (mod /V), pak N není prvočíslo. Bohužel nemusí být pro dané složené N snadné najít takové a, že Fermatův test odhalí složenost N; pro některá výjimečná N dokonce jediná taková a jsou ta soudělná s N; jejich nalezení je tedy ekvivalentní s nalezením dělitele, a tedy i s rozkladem N na prvočísla. Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo oo»oooooooooooooooooo ooooooooooooooooo Carmichaelova čísla Skutečně existují taková nehezká (nebo extrémně hezká?) složená čísla N, která splňují, že pro libovolné a nesoudělné s N platí aN^ = 1 (mod /V). Taková čísla se nazývají Carmichaelova, nejmenší z nich je 561 = 3 • 11 • 17 a teprve v roce 1992 se podařilo dokázat, že jich je dokonce nekonečně mnoho (v OEIS jde o posloupnost A002997: 561,1105,1729, 2465, 2821,.. .)■ Příklad Dokážeme, že 561 je Carmichaelovo, tj. že pro každé a G N, které je nesoudělné s 3 • 11 • 17, platí a560 = 1 (mod 561). Z vlastností kongruencí víme, že stačí dokázat tuto kongruenci modulo 3,11 i 17. To ale dostaneme přímo z Malé Fermatovy věty, protože takové a splňuje a2 = 1 (mod 3), a10 = 1 (mod 11), a16 = 1 (mod 17), přičemž 2,10 i 16 dělí 560 (viz též Korseltovo kritérium). Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooo»ooooooooooooooooo ooooooooooooooooo Věta (Korseltovo kritérium) Složené číslo n je Carmichaelovým číslem, právě když je nedělitelné čtvercem (square-free) a pro všechna prvočísla p dělící n platí p- 1 | n- 1. Příklad Dokažte, že čísla 2465 a 2821 jsou Carmichaelova. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo oooo»oooooooooooooooo ooooooooooooooooo Eulerův test (též Euler-Jacobi, Solovay-Strassen) Fermatův test lze zlepšit s využitím kvadratických zbytků na Eulerův test, ale výše zmíněný problém se ani tak zcela neodstraní. Eulerův test Je-li N prvočíslo a a G Z, N \ a, pak N— 1 a~ = (a/N) (mod N). Příklad Uvažme a = 5: 3 Pak 5280 = 1 (mod 3),5280 = 1 (mod 11), přitom 5280 = -1 (mod 17), proto určitě 5280 ^ ±1 (mod 561). W-l Zde došlo k tomu, že neplatilo a 2 = ±1 (mod N), proto ani nebylo třeba testovat hodnotu Jacobiho symbolu, často ale právě Eulerův test může odhalit složené číslo i v případě, kdy tato mocnina je rovna ±1. aTestování by selhalo už pro a = 3, ale to je dělitel, my chceme ukázat, že toct mM70 ncnot i K07 n^lo7oní íHolitolo Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooo^ooooooooooooooo ooooooooooooooooo Příklad W-l Test, zda a 2 = ±1 (mod N), neodhalí například N = 1729 = 7-13-19, neboť ^ = 864 = 25 • 33 je dělitelné 6, 12 i 18 a tedy z Fermatovy věty plyne, že pro všechna celá čísla a N-l nesoudělná s N platí a 2 =1 (mod N). Přitom ale pro a = 11 dostaneme (j^g) = —1 a Eulerův test tedy složenost čísla 1729 odhalí. Poznamenejme, že hodnotu Legendreova nebo Jacobiho symbolu (£) lze díky zákonu kvadratické reciprocity spočítat v lepším než kubickém čase. Složené číslo n se nazývá pseudoprvočíslo, pokud projde testem na složenost a není jím odhaleno jako složené. Máme tak O Fermatova pseudoprvočísla o základu a Q Eulerova pseudoprvočísla O silná (strong) pseudoprvočísla o základu a, pokud projdou následujícím testem na složenost. ^fämoi-t (.2.) Sílu* (2) Z 01? 1ooooooooo Test na složenost - zesílení Malé Fermatovy věty Nechť p je liché prvočíslo. Pišme p — 1 = 2ř • q, kde t je přirozené číslo a q je liché. Pak pro každé celé číslo a nedělitelné p bud' platí aq = 1 (mod p)) nebo existuje e G {0,1,..., t — 1} splňující a2eq = -1 (mod p)). Ukazuje se, že tento snadný test výrazně zesiluje schopnost rozpoznávat složená čísla. Nejmenší silné pseudoprvočíslo o základu 2 je 2047 (přitom nejmenší Fermatovo o základu 2 bylo již 341) a při otestování základů 2,3 a 5 dostaneme nejmenší pseudoprvočíslo 25326001. Jinými slovy, pokud nám stačí testovat pouze čísla do 2 • 107, pak stačí tento test na složenost provést pouze pro základy 2,3 a 5. Pokud číslo není odhaleno jako složené, pak je určitě prvočíslem. Na druhou stranu, bylo dokázáno, že žádná konečná báze není dostatečná. Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo oooooooo»oooooooooooo ooooooooooooooooo Test Millera a Rabina Test Millera a Rabina je praktickou aplikací předchozího testu, kdy jsme navíc schopni omezit pravděpodobnost neúspěchu. Věta Necht N > 10 je liché složené číslo. Pišme N — 1 = 2ř • q, kde t je přirozené číslo a q je liché. Pak nejvýše čtvrtina z čísel množiny {a G Z; 1 < a < N, (a, N) = 1} splňuje následující podmínku: aq = 1 (mod N) nebo existuje e G {0,1,..., t — 1} splňující a2Sq = -1 (mod N). Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooo«ooooooooooo ooooooooooooooooo V praktických implementacích se obvykle testuje cca 20 náhodných základů (příp. nejmenších prvočíselných základů). V takovém případě dostáváme z předchozí věty, že pravděpodobnost neodhalení složeného čísla je menší než 2~40. Časová náročnost algoritmu je asymptoticky stejná jako složitost modulárního umocňování, tedy nejhůře kubická. Je ale třeba si uvědomit, že test je nedeterministický a spolehlivost jeho deterministické verze závisí na tzv. zobecněné Riemannově hypotéze (GRH). Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo oooooooooo»oooooooooo ooooooooooooooooo Testy na prvočíselnost Testy na prvočísel nost přicházejí na řadu obvykle ve chvíli, kdy testy na složenost prohlásí, že jde pravděpodobně o prvočíslo, případně se provádějí rovnou u speciálních typů čísel. Uveďme nejprve přehled nejznámějších testů. O AKS (2002) - obecný polynomiální test na prvočísla O Pocklington-Lehmerův test - test na prvočíselnost subexponenciální složitosti o Lucas-Lehmerův test - test prvočíselnosti pro Mersenneho čísla O Papinův test (1877) - test prvočíselnosti pro Fermatova čísla o ECPP - test prvočíselnosti založený na tzv. eliptických křivkách Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooo»ooooooooo ooooooooooooooooo Speciální testy - Mersenneho čísla Lucas-Lehmerův test Definujme posloupnost (sn)^L0 rekurzívně předpisem So = 4, sn+i = s2 — 2. Pak je číslo Mp = 2P — 1 prvočíslo, právě tehdy, když Mp dělí sp_2- // Determine if Mp = 2P — 1 is prime Lucas —Lehmer (p) va r s = 4 var M = 2P - 1 repeat p — 2 times: s = s2 - 2 (mod M) if s = 0 return PRIME else return COMPOSITE Časová složitost testu je asymptoticky stejná jako v případě Miller-Rabinova testu, v konkrétních případech je ale efektivnější. Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo oooooooooooo»oooooooo ooooooooooooooooo Speciální testy - Fermatova čísla Fermatova čísla jsou čísla tvaru F„ = 22" + 1. Pierre de Fermat v 17. století vyslovil hypotézu, že všechna čísla tohoto tvaru jsou prvočísly (zřejmě veden snahou zobecnit pozorování pro F0 = 3, Fi = 5, F2 = 17, F3 = 257 a F4 = 65537. V 18. století ale Leonhard Euler zjistil, že F5 = 641 x 6700417 a dodnes se nepodařilo nalézt žádné další Fermatovo prvočíslo. Vzhledem k rychle rostoucí velikosti těchto čísel je počítání s nimi velmi časově náročné (a ani následující test tak není příliš používán). V současné době nejmenší netestované Fermatovo číslo je F33, které má 2 585 827 973 číslic a je tak výrazně větší než největší dosud nalezené prvočíslo. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooo»ooooooo ooooooooooooooooo Pépinův test Označme Fn = 22" + 1 tzv. n-té Fermatovo číslo. Pak Fn je prvočíslo, právě když = — 1 (mod Fn). Vidíme, že jde o velmi jednoduchý test, který je vlastně pouze malou částí Eulerova testu na složenost. Důkaz korektnosti Papinova testu. Platí-li 3~°2~ = — 1 (mod Fn), je nutně Fn — 1 řádem čísla 3 modulo Fn, proto je Fn prvočíslo. Obráceně, nechť je Fn prvočíslo. Z Eulerova kritéria dostáváme, že 3~°2~ = (-p-) (mod Fn), tj. stačí nám určit hodnotu (^-). To je ale snadné, protože Fn = 2 (mod 3) a tedy (^) = —1. Dále Fn = 1 (mod 4), proto díky zákonu kvadratické reciprocity dostáváme Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo oooooooooooooo»oooooo ooooooooooooooooo Pocklington-Lehmerův test Na závěr uveďme i obecný test na prvočíselnost, který použijeme, pokud chceme vysokou pravděpodobnost Miller-Rabinova algoritmu proměnit v jistotu (ta jistota je ale relativní - udává se, že pravděpodobnost selhání Miller-Rabinova algoritmu je nižší než HW chyba během výpočtu). Věta Necht N je přirozené číslo, N > 1. Necht p je prvočíslo dělící N — 1. Předpokládejme dále, že existuje 3pěZ tak, že a^1 = 1 (mod N) a í ap p -1,A/)=1. Necht pap je nejvyšší mocnina p dělící N — 1. Pak pro každý kladný dělitel d čísla N platí d = l (mod pa"). Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooo»ooooo ooooooooooooooooo Důkaz věty Pocklingtona a Lehmera. Každý kladný dělitel d čísla N je součinem prvočíselných dělitelů čísla N, větu dokažme pouze pro d prvočíslo. Podle Fermatovy věty platí 3p_1 = 1 (mod d), neboť (ap, N) = 1. Protože W-l W-l (app - 1, N) = 1, platí app £ 1 (mod d). Označme e řád ap modulo d. Pak platí e \ d — 1, e \ N — la e f Kdyby pa" \ e, z e | N - 1 by plynulo e | spor. Je tedy pap | e, a tedy i pap \ d — 1. □ Literatura Výpočetní aspekty teorie číse Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo oooooooooooooooo»oooo OOOOOOOO<3D0!30Offl0t>OOOOOOOOO Užití věty Pocklington a a Lehmera J o Tvrzení Necht N G N, N > 1. Předpokládejme, že můžeme psát N — 1 = F ■ U, kde (F, U) = 1 a F > y/Ň, přičemž známe rozklad čísla F na prvočinitele. Pak platí: • jestliže pro každé prvočíslo p | F můžeme najít ap G Z z předchozí věty, pak je N prvočíslo; 9 je-li N prvočíslo, pak pro libovolné prvočíslo p | N — 1 existuje ap G Z s požadovanými vlastnostmi. Důkaz. ad 1. Podle Věty je d = 1 (mod p°p) pro všechny prvočíselné faktory F, proto je d = 1 (mod F), a tedy c/ > y/Ň. ad 2. Stačí za ap zvolit primitivní kořen modulo prvočíslo N (nezávisle na p). □ Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooo»ooo ooooooooooooooooo Příklad Předchozí test v sobě zahrnuje Papinův test (totiž pro N máme p = 2, kterému vyhovuje svědek prvočíselnosti ap - = Fn = 3). Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo oooooooooooooooooo»oo ooooooooooooooooo Máme-li testem na složenost potvrzeno, že jde o číslo složené, obvykle chceme najít netriviálního dělitele. Jde ale o výrazně obtížnější úkol (což je na druhé straně výhodné pro RSA a podobné protokoly), proto si k tématu uvedeme jen stručný přehled používaných metod. O Pokusné dělení O Pollardova p-metoda o Pollardova p — 1 metoda O faktorizace pomocí eliptických křivek O Metoda kvadratického síta (QS) O Metoda síta v číselném tělesa (NFS) Podrobnosti viz M8190 Algoritmy teorie čísel. Literatura Výpočetní aspekty teorie číse Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooo»o OOOOOOOOatnOODODODOOOOOOOOO Pollar dova rho-metod< a - ukázka Pollardova p-metoda je algoritmus speciálně vhodný pro hledání relativně malých dělitelů, založená na myšlence, že pro náhodnou funkci f : S —> S, kde S je konečná n-prvková množina, se musí posloupnost (x„)^l0, kde xn+\ = f(xn) zacyklit. Přitom předperioda i perioda má očekávanou délku y/ir ■ n/8. Inputs: n, the integer to be factored; and f(x) , a pseudo—random function Output: a non —trivial factor of n, or failure, x := 2, y := 2; d := 1 While d = 1 do x := f {x) y ■= f (f (y)) d := GCD(\x-y\,n) If d = n, retu rn failure. Else, return d. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo oooooooooooooooooooo* ooooooooaoraaraBDOoooooooo Příklad Nalezněte dělitele čísla 455459. Uvažujme funkci f(x) = x2 + 1 (mlčky předpokládáme, že se tato funkce modulo neznámý prvočíselný dělitel p čísla n chová náhodně a má tak požadované vlastnosti) a v jednotlivých iteracích počítáme a <— f (a) (mod n), b <— f(f(b)) (mod n). a b d 5 26 1 26 2871 1 677 179685 1 2871 155260 1 44380 416250 1 179685 43670 1 121634 164403 1 155260 247944 1 44567 68343 743 Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo •oooooooooooooooo Kryptografie s veřejným klíčem (PKC) Dva hlavní úkoly pro PKC jsou zajistit • šifrování, kdy zprávu zašifrovanou veřejným klíčem příjemce není schopen rozšifrovat nikdo kromě něj (resp. držitele jeho 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 PKC: • 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) • Rabinův kryptosystém (a podepisování) • EIGamal kryptosystém (a podepisování) • Kryptografie eliptických křivek (ECC) • Diffie-Hellmanův protokol na výměnu klíčů (DH) Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo o«ooooooooooooooo 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 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 O S pomocí veřejného klíče (deklarovaného) odesílatele zprávy se rekonstruuje původní otisk zprávy Va(Sa{Hm)) = Hm-o Oba otisky se porovnají Hm = H'M1. Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo oo»oooooooooooooo (Kryptografická) hashovací funkce (Kryptografická) hashovací funkce má mít následující vlastnosti: • Pro libovolnou zprávu je snadné nalézt její hash. • Nelze (v reálném čase) zjistit zprávu s požadovaným hashem. • Nelze (v reálném čase) nalézt dvě zprávy se stejným hashem. • Každá změna zprávy se projeví změnou hashe. Příklady: a MD5 (128 bit, Rivest 1992) - není collision-resistant • SHA-1 (160 bit, NSA 1995) - od roku 2005 považována za nedostatečně odolnou proti kolizím • PJPEMD-320 • SHA-3 Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooo»ooooooooooooo RSA Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973) • každý účastník A potřebuje dvojici klíčů - veřejný a soukromý S a • generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, tp(n) = (p — l)(q — 1) [n je veřejné, ale tp(n) nelze snadno spočítat ] • zvolí veřejný klíč e a ověří, že (e,ip(n)) = 1 • např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e • d = 1 (mod tp(n)) • zašifrování numerického kódu zprávy M: C = Ce(M) = Me (mod n) 9 dešifrování šifry C: OT = Dd(C) = Cd (mod n) Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo oooo»oooooooooooo Poznámka • Korektní naprogramování bez postranních kanálů není triviální (viz např. PKCS#1, RFC 3447). • Analogicky podepisování (hashů) zpráv (viz např. DSA) • Viz RSA factoring challenge (např. rozklad 212 ciferného čísla RSA-704 by býval vynesl 30 000 USD). Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooo»ooooooooooo Bezpečnost RSA Bezpečnost RSA je testována od vzniku šifry v roce 1977 a dosud se (s výjimkou postranních kanálů či některých singulárních klíčů) nepodařilo objevit výraznou slabinu (při použití dostatečně velkého klíče, nyní se doporučuje 2048 bitů). Přesto se dodnes neumí dokázat, že problém RSA skutečně závisí na nesnadnosti faktorizace. Požadavky na bezpečnou volbu klíče: • d je dostatečně velké (viz Wienerův útok) « p a q nejsou příliš blízká (viz následující příklad) • není znám útok proti malému veřejnému klíči e, doporučuje se alespoň e = 65537. Pomocí tzv. Fermatovy faktorizace se můžeme pokusit rozložit n = p ■ q, pokud máme důvod se domnívat, že rozdíl p a q je malý. Pak totiž 'P + <7N kde s = (p — q)/2 je malé a t = (p + q)/2 je pouze o málo větší než y/Ti. Stačí tedy testovat čísla t = \y/h~], t = + 1, t = \yfh~\ + 2, dokud nebude t2 - n druhou mocninou (což lze efektivně testovat). Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooo»ooooooooo Rabínův kryptosystém Prvním veřejným kryptosystémem, k jehož prolomení je prokazatelně potřeba faktorizovat modul, je Rabinův kryptosystém, který si uvedeme ve zjednodušené verzi: • každý účastník A potřebuje dvojici klíčů - veřejný Va a soukromý Sa • generování klíčů: A zvolí dvě podobně velká prvočísla p,q = 3 (mod 4), vypočte n = pq. • VA = n, SA = (p, q) • zašifrování numerického kódu zprávy M: C = Ce(M) = M2 (mod n) • dešifrování šifry C: vypočtou se (čtyři) odmocniny z C modulo n a snadno se otestuje, která z nich byla původní zprávou. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo oooooooomramoDooooooooo Výpočet druhé odmocniny z C modulo n = pq, kde p = q = 3 (mod 4) • vypočti r = C(p+1)/4 (mod p) a s = C^1)/4 (mod q) • vypočti a, fa tak, že ap + bq = 1 • položa x = (aps + faqr) (mod n), y = (aps — bqr) (mod n) • druhými odmocninami z C modulo n jsou ±x, ±y. aUvědomte si, že jde vlastně o aplikaci Čínské zbytkové věty! Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování OOOOOOO OOOOOOOOOOOOOOOOOOOOO OOOOOOOOooooooooo Diffie-Hellman key exchange Whitfield Diffie, Martin Hellman (1976; M. Williamson, GCHQ -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é) • Alice vybere náhodné a a pošle ga (mod p) • Bob vybere náhodné b a pošle gb (mod p) • Společným klíčem pro komunikaci je gab (mod p). Poznámka « Problém diskrétního logaritmu (DLP) « Nezbytná autentizace (man in the middle attack) Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooaraawBDOoooooooo Z protokolu DH na výměnu klíčů odvozen šifrovací algoritmus EIGamal: • Alice zvolí prvočíslo p spolu s primitivním kořenem g • Alice zvolí tajný klíč x, spočítá h = gx (mod p) a zveřejní veřejný klíč (p, g, h) • šifrování zprávy M: Bob zvolí náhodné y a vypočte C\ = gy (mod p) a C2 = M • hy (mod p) a pošle (Ci, C2) • dešifrování zprávy: 07"= C2/'Cf Poznámka Analogicky jako v případě RSA lze odvodit podepisování. Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooooooooooo Kódování Při přenosu informace zpravidla dochází k její deformaci. Budeme pro jednoduchost pracovat s modelem, kdy jednotlivé částečky informace jsou bud' nuly nebo jedničky (tj. prvky v Z2) a přenášíme slova o k bitech. Obdobné postupy jsou možné i nad ostatními konečnými tělesy. Přenosové chyby chceme O rozpoznávat O opravovat a za tím účelem přidáváme dodatečných n — k bitů informace pro pevně zvolené n > k. Všech slov o k bitech je 2k a každé z nich má jednoznačně určovat jedno kódové slovo z 2" možných. Máme tedy ještě 2"_2^_2^(2" k_1) slov, která jsou chybová. Lze tedy tušit, že pro veliké k nám i malý počet přidaných bitů (tj. n — k) dává hodně redundantní informace. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování OOOOOOO OOOOOOOOOOOOOOOOOOOOO OOOOOOOO 3. O Polynom p(x) = 1 + x + x2 generuje (3, l)-kód opakování bitů. První tvrzení plyne z toho, že 1 +x dělí polynom v(x) tehdy a jen tehdy, když v(l) = 0 a to nastane tehdy, když je ve v(x) sudý počet nenulových koeficientů. Druhé je zřejmé. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooanfflanfflQD^oooooooo Přenos slova v G ZÍJ dopadne příjmem polynomu u(x) = v(x) + e(x) kde e(x) je tzv. chybový polynom reprezentující vektor chyby přenosu. Chyba je rozpoznatelná pouze, když generátor kódu p(x) nedělí e(x). Máme proto zájem o polynomy, které nevystupují jako dělitelé zbytečně často. Definice Ireducibilní polynom p(x) £ stupně m se nazývá primitivní, jestliže p(x) dělí polynom (xk — 1) pro k = 2m — 1, ale nedělí jej pro žádná menší k. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooo»ooooooo Věta Je-li p(x) primitivní polynom stupně m, pak pro všechna n < 2m — 1 rozpoznává příslušný (n, n — m)-kód všechny jednoduché a dvojité chyby. Důsledek Je-li q(x) primitivní polynom stupně m, pak pro všechna n < 2m — 1 rozpoznává (n, n — m — l)-kód generovaný polynomem p(x) = q(x)(l + x) všechny dvojité chyby a všechna slova s lichým počtem chyb. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo OOOOOOOO<3D0!30Offl0t>OO»OOOOOO Tabulka dává o informace o výsledcích předchozích dvou vět pro několik polynomů: primitivní polynom kontrolní bity délka slova 1 + X + X2 2 3 1 + X + X3 3 7 1 + X + X4 4 15 1 + x2 + X5 5 31 1 + X + X6 6 63 1 + x3 + x7 7 127 1 + X2 + X3 + X4 + X8 8 255 l+x4+x9 9 511 1 + X3 + X10 10 1023 Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooooo»ooooo< Definice Lineární kód je injektivní lineární zobrazení g : {1>2)k —> (^2)"-Matice G typu k/n reprezentující toto zobrazení v standardních bazích se nazývá generující matice kódu. Pro každé slovo v je u = G ■ v příslušné kódové slovo. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo 00000000 {^2)k s maticí H=(En_k P) má následující vlastnosti O Ker h = Im g, tj. @ přijaté slovo u je kódové slovo právě, když je H ■ u = 0 Matici H z věty se říká matice kontroly parity příslušného (n, /c)-kódu. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo oooooooooooooo«oo Jak jsme viděli, přenos zprávy u dává výsledek v = u + e. To je ale nad Z2 ekvivalentní s e = u + v. Pokud tedy známe podprostor V c (Z2)" správných kódových slov, víme u každého výsledku, že správné slovo (s opravenými případnými chybami) je ve třídě rozkladu v + V v prostoru (Z2)n/V. Zobrazení (homomorfismus grup) h : (Z2)" —> (^2)'lk má V za jádro, proto indukuje injektivní lineární zobrazení h : (7j2)n/V —> [%2)nk- Jeho hodnoty jsou jednoznačně určeny hodnotami H • u. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooooooooo»o< Definice Hodnota H ■ u se nazývá syndrom slova u. Věta Dvě slova jsou ve stejné třídě rozkladu právě tehdy, když mají týž syndrom. Samoopravné kódy lze konstruovat tak, že pro každý syndrom určíme prvek v příslušné třídě, který je nejvhodnějším slovem. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo oooooooooooooooo»i Příklad Bud' dán (6,3) kód nad Z2 generovaný polynomem x3 + x2 + 1. 9 Určete jeho generující matici a matici kontroly parity. O Dekódujte zprávu 111101 předpokládáte-li, že při přenosu došlo k nejmenšímu možnému počtu chyb. Řešení Protože se jedná o lineární kód, stačí určit jak se zakódují bázové vektory 1, x a x2, tedy určit zbytky polynomů x3, x4 a x5 po dělení polynomem x3 + x2 + 1. Máme x3 = x2 + 1 (mod x3 +x2 + 1) x4 = x(x3) = x(x2 + 1) = x2 + x + 1 (mod x3 + x2 + 1) x5 = x(x4) = x(x2 + x + l)=x + l (mod x3 + x2 + 1) Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooooooooooo< Řešení (pokr.) Bázové vektory (zprávy) 100, 010 a 001 se tedy zakódují do vektorů (kódů) 101100, 111010 a 110001, generující matice, resp. matice kontroly parity kódu jsou tedy '1 0 0 1 1 r resp. H = [ 0 1 0 0 1 1 ,0 0 1 1 1 Oj n 1 1\ 0 1 1 1 1 0 1 0 0 0 1 0 Vo 0 1/ Vynásobíme-li přijatou zprávu 111101 maticí kontroly parity, dostáváme syndrom 100 a víme, že při přenosu došlo k chybě. Sestavme tabulku všech syndromů a jim odpovídajících kódových slov. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooooooooooo< Syndrom (Kódová ) slova s daným synd romem 000 000000 110001 111010 101100 010110 001011 011101 100111 001 001000 111001 110010 100100 011110 000011 010101 101111 010 010000 100001 101010 111100 000110 011011 001101 110111 100 100000 010001 011010 001100 110110 101011 111101 000111 011 011000 101001 100010 110100 001110 010011 000101 111111 101 101000 011001 010010 000100 111110 100011 110101 001111 110 110000 000001 001010 011100 100110 111011 101101 010111 111 111000 001001 000010 010100 101110 110011 100101 011111 Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooooooooooo< Řešení (dokončení) Syndrom 000 mají všechna kódová slova. Počínaje druhým řádkem, je každý řádek tabulky afinním prostorem, jehož zaměřením je vektorový prostor daný prvním řádkem. Zejména je tedy rozdíl každých dvou slov ve stejném řádku nějakým kódovým slovem. Všechna slova s daným syndromem dostaneme přičtením syndromu (doplněného nulami na délku kódového slova) ke všem kódovým slovům. Tzv. vedoucím reprezentantem třídy (řádku, afinního prostoru) odpovídající danému syndromu je slovo s nejmenším počtem jedniček v řádku, a tedy i nejmenším počtem bitových změn, jež je třeba provést, abychom dostali kódové slovo -v našem případě jde o slovo 100000 a jeho odečtením od obdrženého slova dostaneme platné kódové slovo 011101. Je to platné kódové slovo s nejmenší Hammingovou vzdáleností od obdrženého slova. Původní zpráva tedy byla 101.