Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo OOOOOOOOQDOOODODOOOOOOOOOO 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 2013 Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooamraooooooooooo 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 ooooooooaoraatrooooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, průběžně připravovaný e-text. • Předmětové záložky v IS MU • 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/ • 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. Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování •oooooo ooooooooooooooooooooo ooooooooamraooooooooooo 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 ooooooooamraooooooooooo 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 ooooooooamraooooooooooo 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 ooooooooaoraatrooooooooooo 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 OOOOOOOOQDOOODODOOOOOOOOOO 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 ooooooooamraooooooooooo 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 ooooooooarasBaDoooooooooo 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) O otestování zbylého faktoru na složenosti (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 ooooooooaoraatrooooooooooo 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 ooooooooamraooooooooooo 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 ooooooooamraooooooooooo 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 ooooooooamraooooooooooo 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 10), 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 ooooooooaoraatrooooooooooo 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. Výpočetní aspekty teorie ooooooo Testování prvočíselnosti a složenosti oooooo»oooooooooooooo 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 o Eulerova pseudoprvočísla O silná (strong) pseudoprvočísla o základu a, pokud projdou následujícím testem na složenost. P&cudoprines to base 2 Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooo»ooooooooooooo ooooooooamraooooooooooo 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 ooooooooamraooooooooooo 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 ooooooooaoraatrooooooooooo 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 ooooooooamraooooooooooo 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 ooooooooamraooooooooooo 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 ooooooooaoraatrooooooooooo 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 ooooooooamraooooooooooo Pépinův test Označme Fn = 22" + 1 tzv. n-té Fermatovo číslo. Pak Fn je prvočíslo, právě když 3~^~ = — 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~n?~ = — 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~n?~ = (jr) (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 ooooooooamraooooooooooo 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 ooooooooamraooooooooooo 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 OOOOOOOOCBOOODODOOOOOOOOOO 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 ooooooooaoraatrooooooooooo 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 ooooooooaoraatrooooooooooo 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 OOOOOOOOCBOOODODOOOOOOOOOO 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* ooooooooarasBaDoooooooooo 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 •oooooooamraooooooooooo 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«oooooooooooooooo (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 • RIPEMD-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 ooosooooaoraatrooooooooooo 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) Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo oooo»ooooooooooooo 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/ň], t = |~V"1 + 1, t = |~V"1 + 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 oooooo»ooooooooooo 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 ooooooo»oooooooooo 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 oooooooo«raatrooooooooooo 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. Řešení c = 692, kandidáti původní zprávy jsou ±4 • 23 • 14 ± 3 • 31 • 18 (mod 713). Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo oooooooodowraooooooooooo 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) Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooamamooooooooooo Kryptosystém EIGamal 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 ooooooooamraDoooooooooo Eliptické křivky Eliptické křivky jsou rovinné křivky o rovnici tvaru y2 = x3 + ax + b a zajímavé jsou tím, že na jejich bodech lze definovat operace tak, že výslednou strukturou bude komutativní grupa. Přitom uvedené operace lze efektivně provádět a navíc se ukazuje, že mají (nejen) pro kryprografii zajímavé vlastnosti - srovnatelné bezpečnosti jako RSA lze dosáhnout již s podstatně kratšími klíči. Výhodou je rovněž velké množství použitelných eliptických křivek (a tedy grup různé struktury) podle volby parametru a, b . Protokoly: • ECDH - přímá varianta DH na eliptické křivce (jen místo generátoru se vybere vhodný bod na křivce) • ECDSA - digitální podpis pomocí eliptických křivek. Poznámka Problém diskrétního logaritmu (ECDLP). Navíc se ukazuje, že eliptické křivky jsou velmi dobře použitelné při faktorizaci prvočísel. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooaoaraooooooooooo 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 ooooooooatnraoDoooooooooo Úplně jednoduchým příkladem je kód kontrolující paritu. Kódové slovo o k + 1 bitech je určené tak, aby přidáním prvního bitu byl zaručen sudý počet jedniček ve slově. Pokud při přenosu dojde k lichému počtu chyb, přijdeme na to. Dvě různá kódová slova se při tomto kódu vždy liší alespoň ve dvou pozicích, chybové slovo se ale od dvou různých (vhodných) kódových slov liší pouze v pozici jedné. Nemůžeme proto umět chyby opravovat, ani kdybychom věděli, že došlo k právě jedné chybě. Navíc neumíme detekovat tak obvyklé chyby, jako je záměna dvou sousedních bitů ve slově. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooaraaaDoooooooooo 011 010 ^^001 á 110 000 |101 100 Definice Hammingova vzdálenost dvou slov je rovna počtu bitů, ve kterých se liší. O Kód odhaluje r a méně chyb právě, když je minimální Hammingova vzdálenost kódových slov právě r + 1. O Kód opravuje r a méně chyb právě, když je minimální Hammingova vzdálenost kódových slov právě 2 r + 1. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooaoraaOTOooooooooo Jak konstruovat kódová slova, abychom je snadno rozpoznali? Kontrolu parity jsme už viděli, další triviální možnost je prosté opakování bitů - např. (3, l)-kód bere jednotlivé bity a posílá je třikrát po sobě. Systematickou cestou je pak využití dělitelnosti polynomů. Zpráva fao^i • • • bk-i Je reprezentována jako polynom m(x) = bQ + bix H-----h bk^xk^. Definice Nechť p(x) = ao + a\x + • • • + an-kxn~k G 2^[x] je polynom s ao = 1, an-k = 1. Polynomiální kód generovaný polynomem p(x) je (n, k)-kóá jehož slova jsou polynomy stupně menšího než n dělitelné p(x). Zpráva m(x) je zakódována jako v(x) = r(x) + xn~km(x), kde r(x) je zbytek po dělení polynomu xn~km(x) polynomem p(x). Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo ooooooooaoraatro^ooooooooo Z definice víme, že v(x) = xn~km(x) + r(x) = q(x)p(x) + r(x) + r(x) = q(x)p(x). Budou tedy všechna kódová slova dělitelná p(x). Původní zpráva je obsažena přímo v polynomu v(x), takže dekódování správného slova je snadné. ' Příklad ^ Q Polynom p(x) = 1 +x generuje (n, n — l)-kód kontroly parity pro všechna n > 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 OOOOOOOOQDOOODODO^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) £ Z2[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 ooooooooaoraatrooo^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 OOOOOOOOQDOOODODOOO^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 ooooooooairaii>oooo»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 ooooooooanfflatroooooosoooo Věta Každý polynomiální (n, k)-kód je lineární kód. Generující matice (7,4) kódu příslušná k polynomu p(x) = 1 + x2 + x3 je 1 1 o\ 0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 \o 0 0 1/ Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry Úvod do kódování ooooooo ooooooooooooooooooooo OOOOOOOO<3D0!30OS>OOOOOO»OOO Věta Je-li g lineární kódování s maticí potom zobrazení h : (Z2)" —> {^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 ooooooooaoraatroooooooosoo 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 ooooooooairaii>oooooooo»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 ooooooooaoraatroooooooooo* 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 oooooooooraomooooooooooo' Ř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 V resp. (010011 ,0 0 1 0 0 1, 1 1\ 0 1 1 1 1 0 1 0 0 0 1 0 \o 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 ooooooooaoraatroooooooooooi 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 oooooooooraomooooooooooo' Ř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 . Odeslaná zpráva tedy byla 101.