Literatura Výpočetní aspekty teorie číše Testování prvočíselnosti a složenost Šifry ooooooo ooooooooooooooooooooo ooooo Aplikace teorie čísel - Počítání s velkými čísly, kryptografie Michal Bulant Masarykova univerzita Přírodovědecká fakulta podzim 2013 Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo ooooooooooooooooooooo ooooo 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 Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry ooooo • Jan Slovák, Martin Panák, Michal Bulant, Matematika drsně a svižně, MU Brno, 2013, 774 s. (též jako e-text). Literatura Výpočetní aspekty teorie číše ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry ooooo • Jan Slovák, Martin Panák, Michal Bulant, Matematika drsně a svižně, MU Brno, 2013, 774 s. (též jako e-text). • 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 Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo ooooooooooooooooooooo ooooo 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). • 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 ooooooo ooooooooooooooooooooo ooooo Plán přednášky Q Výpočetní aspekty teorie čísel Q Testování prvočíselnosti a složenosti • Testy na složenost • Testy na prvočíselnost • Hledání dělitele Q Kryptografie s veřejným klíčem Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry •oooooo ooooooooooooooooooooo ooooo 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, Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry •oooooo ooooooooooooooooooooo ooooo Zakladl ní úlohy výpočetní teo rie čí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. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry •oooooo ooooooooooooooooooooo ooooo Zakladl ní úlohy výpočetní teo rie čí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, Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry •oooooo ooooooooooooooooooooo ooooo Zakladl ní úlohy výpočetní teo rie čí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), Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry •oooooo ooooooooooooooooooooo ooooo Zakladl ní úlohy výpočetní teo rie čí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é, Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry •oooooo ooooooooooooooooooooo ooooo Zakladl ní úlohy výpočetní teo rie čí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. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry o»ooooo ooooooooooooooooooooo ooooo Zakladl ní 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. 4Ľ3*4l3*4 = k4 = * -š -O^O Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry o»ooooo ooooooooooooooooooooo ooooo Zakladl ní 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(nlo§23) Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry o»ooooo ooooooooooooooooooooo ooooo Zakladl ní 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). Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry o»ooooo ooooooooooooooooooooo ooooo Zakladl ní 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 Literatura Výpočetní aspekty teorie čísel oo»oooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry ooooo GCD a modulární inverze 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). Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenost Šifry oo»oooo ooooooooooooooooooooo ooooo ŕ~* /— modulární inverze GCD a 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). fu n ct i o n exte n ded _gcd (a , m) i f m = 0 retu rn (1 . o) e 1 s e (q, r) := d i v i d e (a , m) (k, 1) := exten ded_gcd(m, r) retu rn (1 , k — q * 1 ) Podrobná analýza (viz např. [Knuth] nebo [Wiki]) ukazuje, že tento algoritmus je kvadratické časové složitosti. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenost Šifry ooosooo ooooooooooooooooooooo ooooo k n i i • Module irni umocňovaní 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: Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenost Šifry ooosooo ooooooooooooooooooooo ooooo k n ii Module irni umocňovaní 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ženost Šifry OOOO0OO ooooooooooooooooooooo ooooo 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, Literatura Výpočetní aspekty teorie čísel OOOO0OO Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry ooooo 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ženost Šifry ooooo»o ooooooooooooooooooooo ooooo Příklad (Ukázka průběhu algoritmu) Vypočtěme 2560 (mod 561). Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenost Šifry ooooo»o ooooooooooooooooooooo ooooo 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 Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenost Šifry ooooo»o ooooooooooooooooooooo ooooo 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). Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenost Šifry oooooo* ooooooooooooooooooooo ooooo Efektiv ita 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 ooooooo ooooooooooooooooooooo ooooo Plán přednášky Q Výpočetní aspekty teorie čísel Q| Testování prvočíselnosti a složenosti • Testy na složenost • Testy na prvočíselnost • Hledání dělitele Q Kryptografie s veřejným klíčem Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti •oooooooooooooooooooo Šifry ooooo Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti o»ooooooooooooooooooo Šifry ooooo 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) 4Ľ3k4l3*4 = k4 = * -š -O^O Literatura Výpočetní aspekty teorie číse Testování prvočíselnosti a složenosti Šifry ooooooo o»ooooooooooooooooooo ooooo 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) Literatura Výpočetní aspekty teorie číse Testování prvočíselnosti a složenosti Šifry ooooooo o»ooooooooooooooooooo ooooo 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. Literatura Výpočetní aspekty teorie číše Testování prvočíselnosti a složenosti Šifry ooooooo o»ooooooooooooooooooo ooooo 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. Literatura Výpočetní aspekty teorie číse Testování prvočíselnosti a složenosti Šifry ooooooo o»ooooooooooooooooooo ooooo 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. Literatura Výpočetní aspekty teorie číse Testování prvočíselnosti a složenosti Šifry ooooooo o»ooooooooooooooooooo ooooo 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ý postúpi a Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti OO0OOOOOOOOOOOOOOOOOO Šifry ooooo 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. Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti OO0OOOOOOOOOOOOOOOOOO Šifry ooooo 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 ^ O (mod N) takové, že aN 1 ^ 1 (mod /V), pak N není prvočíslo. 4Ľ3k4l3*4 = k4 = * -š -O^O Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti OO0OOOOOOOOOOOOOOOOOO Šifry ooooo 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 ^ O (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. Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti ooo»ooooooooooooooooo Šifry ooooo 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,.. .)■ Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti ooo»ooooooooooooooooo Šifry ooooo 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). Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti ooo»ooooooooooooooooo Šifry ooooo 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 číse OOOOOOO Testování prvočíselnosti a složenosti 0000*0000000000000000 Šifry ooooo 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. Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti OOOO0OOOOOOOOOOOOOOOO Šifry ooooo 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 číse ooooooo Testování prvočíselnosti a složenosti ooooo»ooooooooooooooo Šifry ooooo 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 neodst Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti ooooo»ooooooooooooooo Šifry ooooo 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). Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti ooooo»ooooooooooooooo Šifry ooooo 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). Literatura Výpočetní aspekty teorie číse OOOOOOO Testování prvočíselnosti a složenosti ooooo»ooooooooooooooo Šifry ooooo 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 ucnot i K07 n^lo7oní íHolitolo Literatura Výpočetní aspekty teorie číse OOOOOOO Testování prvočíselnosti a složenosti 000000*00000000000000 Šifry ooooo 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). Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti OOOOOO0OOOOOOOOOOOOOO Šifry ooooo 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í. 4Ľ3k4l3*4 = k4 = * -š -O^O Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti OOOOOO0OOOOOOOOOOOOOO Šifry ooooo 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ämoľt (.2.) Sílu* (2) Z 01? 1 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 číse ooooooo Testování prvočíselnosti a složenosti oooooooooo»oooooooooo Šifry ooooo 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. 4Ľ3k4l3*4 = k4 = * -š -O^O Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti oooooooooo»oooooooooo Šifry ooooo 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 ooooooo oooooooooooo»oooooooo ooooo 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ů. Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo oooooooooooo»oooooooo ooooo 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 Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo oooooooooooo»oooooooo ooooo 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 Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo oooooooooooo»oooooooo ooooo 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 Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo oooooooooooo»oooooooo ooooo 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 Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo oooooooooooo»oooooooo ooooo 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 Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti ooooooooooooo»ooooooo Šifry ooooo 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- Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo ooooooooooooo»ooooooo ooooo 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 Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo ooooooooooooo»ooooooo ooooo 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) var 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 ooooooo oooooooooooooo^oooooo ooooo 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 číse ooooooo Testování prvočíselnosti a složenosti ooooooooooooooo»ooooo Šifry ooooo 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). 4 n * < & > 4 = * 4 = > ^ -O^O Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti ooooooooooooooo»ooooo Šifry ooooo 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. Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti ooooooooooooooo»ooooo Šifry ooooo 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 "2 = —1 (mod Fn), je nutně Fn — 1 řádem čísla 3 modulo Fn, proto je Fn prvočíslo. Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti ooooooooooooooo»ooooo Šifry ooooo 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 ■0 0.0 Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti oooooooooooooooo»oooo Šifry ooooo 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). Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenosti oooooooooooooooo»oooo Šifry ooooo 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 číse ooooooo Testování prvočíselnosti a složenosti OOOOOOOOOOOOOOOOO0OOO Šifry ooooo 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 1. Předpokládejme, že můžeme psát N — 1 = F ■ U, kde (F, U) = 1 a F > VŇ, přičemž známe rozklad čísla F na prvočinitele. Pak platí: Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo oooooooooooooooooo»oo ooooo Užití věty Pocklingtona a Lehmera 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. Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo oooooooooooooooooo»oo ooooo Užití věty Pocklingtona a Lehmera 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 c/ = í 1 (mod p°p) pro všechny prvočíselné faktory F, proto je c/ = 1 (mod F), a tedy d > y/Ň. Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo oooooooooooooooooo»oo ooooo Užití věty Pocklingtona a Lehmera 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 c/ = 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 číse ooooooo Testování prvočíselnosti a složenosti OOOOOOOOOOOOOOOOOOO0O Šifry ooooo Příklad Předchozí test v sobě zahrnuje Papinův test (totiž pro N = Fn máme p = 2, kterému vyhovuje svědek prvočíselnosti ap = 3). Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry OOOOOOO OOOOOOOOOOOOOOOOOOOO* ooooo Hledání dělitele 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. 4Ľ3k4l3*4 = k4 = * -š -O^O Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry OOOOOOO OOOOOOOOOOOOOOOOOOOO* ooooo Hledání dělitele 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í Podrobnosti viz M8190 Algoritmy teorie čísel. Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry OOOOOOO OOOOOOOOOOOOOOOOOOOO* ooooo Hledání dělitele 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 Podrobnosti viz M8190 Algoritmy teorie čísel. Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry OOOOOOO OOOOOOOOOOOOOOOOOOOO* ooooo Hledání dělitele 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 Podrobnosti viz M8190 Algoritmy teorie čísel. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo 00000000000000000000» ooooo III 1 ' f 1v 1 ■ J_ 1 Hledaní dělitele 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 Podrobnosti viz M8190 Algoritmy teorie čísel. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo 00000000000000000000» ooooo III 1 ' f 1v 1 ■ J_ 1 Hledaní dělitele 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) Podrobnosti viz M8190 Algoritmy teorie čísel. Literatura Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo 00000000000000000000» ooooo III 1 ' f 1v 1 ■ J_ 1 Hledaní dělitele 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 čísel Testování prvočíselnosti a složenosti Šifry ooooooo ooooooooooooooooooooo ooooo Plán přednášky Q Výpočetní aspekty teorie čísel Q Testování prvočíselnosti a složenosti • Testy na složenost • Testy na prvočíselnost • Hledání dělitele Q Kryptografie s veřejným klíčem Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry •oooo 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 Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry •oooo 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 Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry •oooo 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) Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry •oooo 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í) Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry •oooo 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í) Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry •oooo 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) 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íčů j^DhQ ^ Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry o»ooo Princip digitálního podpisu Podepisování o Vygeneruje se otisk (hash) Hm zprávy pevně stanovené délky (např. 160 nebo 256 bitů). & 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. Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry o»ooo Princip digitálního podpisu Podepisování o Vygeneruje se otisk (hash) Hm zprávy pevně stanovené délky (např. 160 nebo 256 bitů). & 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 ooooooo ooooooooooooooooooooo oo»oo 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ý Sa Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo ooooooooooooooooooooo oo»oo 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 ] Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo ooooooooooooooooooooo oo»oo 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 Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo ooooooooooooooooooooo oo»oo 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)) Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo ooooooooooooooooooooo oo»oo 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) Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo ooooooooooooooooooooo oo»oo 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 ooooooo ooooooooooooooooooooo ooo»o yptosysté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 Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo ooooooooooooooooooooo ooo»o yptosysté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. Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo ooooooooooooooooooooo ooo»o yptosysté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) Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo ooooooooooooooooooooo ooo»o yptosysté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) Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo ooooooooooooooooooooo ooo»o yptosysté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 číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry OOOO* 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(q+l)/4 (mod g) aUvědomte si, že jde vlastně 0 aplikaci Čínské zbytkové věty! Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry OOOO* 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(q+l)/4 (mod g) « vypočti a, b tak, že ap + bq = 1 aUvědomte si, že jde vlastně 0 aplikaci Čínské zbytkové věty! Výpočet druhé odmocniny z C modulo n = pq, kde p = q = 3 (mod 4) Šifry OOOO* • vypočti r = C(p+1)/4 (mod p) a s = C^1)/4 (mod q) • vypočti a, b tak, že ap + bq = 1 • položa x = (aps + faqr) (mod n), y = (aps — bqr) (mod n) aUvědomte si, že jde vlastně o aplikaci Čínské zbytkové věty! 1Ľ3k4l3*1 = k4 = * -š -00.0 Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry OOOO* 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 + bqr) (mod n), y = (aps — faqr) (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 číse Testování prvočíselnosti a složenost Šifry ooooooo ooooooooooooooooooooo ooooo 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. Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry ooooo 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). Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry ooooo 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, .. .). Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry ooooo 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é) Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry ooooo 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) Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry ooooo 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) Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry ooooo 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). Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry ooooo 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). Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry ooooo 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 ooooooo ooooooooooooooooooooo ooooo 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 Výpočetní aspekty teorie čísel Testování prvočíselnosti a složenosti Šifry ooooooo ooooooooooooooooooooo ooooo 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í. Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry ooooo 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 . Literatura Výpočetní aspekty teorie číse ooooooo Testování prvočíselnosti a složenost ooooooooooooooooooooo Šifry ooooo 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. Eliptické krivky jsou rovinné krivky 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.