Diskrétní matematika - 5. týden Aplikace teorie čísel - Počítání s velkými čísly, kryptografie klíčem Lukáš Vokřínek Masarykova univerzita Fakulta informatiky podzim 2020 Výpočetní aspekty teorie čísel oooooooo Obsah přednášky Diofanticke rovnice O Kryptografie s veřejným klíčem ooooooooo O Diofanticke rovnice ""^ — fy* Ti***** fTrrnnřktii l.....i i .i1 —^ Q Kryptografie s veřejným klíčem * . [ ( Výpočetní aspekty teorie čísel oooooooo Doporučené zdroje Diofanticke rovnice O Kryptografie s veřejným klíčem ooooooooo • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. Výpočetní aspekty teorie čísel oooooooo Doporučené zdroje Diofanticke rovnice O Kryptografie s veřejným klíčem ooooooooo • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. o V. Švábenský, Sbírka příkladů (a další zdroje), https://is.muni.cz/auth/th/395868/f i_b/ • Jiří Herman, Radan Kučera, Jaromír Šimša, Metody řešení matematických úloh. MU Brno, 2001. • William Stein, Elementary Number Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupné na http://wstein.org/ent/ent.pdf Výpočetní aspekty teorie čísel oooooooo Plán přednášky Diofanticke rovnice O Kryptografie s veřejným klíčem ooooooooo Q Diofanticke rovnice rvnt.oprafie s veřeinvm klíčpm Výpočetní aspekty teorie čísel oooooooo Diofantické rovnice Diofanticke rovnice Kryptografie s veřejným klíčem ooooooooo Příklad Vyřešte diofantickou rovnici 72x + 100y = 16. . nFK? jL L to i©*\A_ I fjĹíu* r c r—K -pŕ —p. y -ŕ fa?* » 7^ (^od. tel l/ 0^ -a s-o ^2X 10ÔU (4V -ttx ~ -2/16- SSM* 3 - r re i Výpočetní aspekty teorie čísel oooooooo Diofantické rovnice Diofanticke rovnice Kryptografie s veřejným klíčem ooooooooo Příklad Vyřešte diofantickou rovnici 72x + 100y = 16 Příklad Vyřešte diofantickou rovnici 72x + 100y + 45z = 1 dulo ujV *fol &-t1M)=>*r 100* + =1 (t) V-5 "7 M —t> ^-ŕ^ŕ ttx-t 4ôú*\ = -kli'AlH (U) n, ^-t9 < /íl - 1 y u/ 00«) -t^St =1 \ = - 1<-tL>) - tola h - 4%o0 i Výpočetní aspekty teorie čísel oooooooo Plán přednášky Diofanticke rovnice O Kryptografie s veřejným klíčem ooooooooo Q Výpočetní aspekty teorie čísel rvnt.oprafie s veřeinvm klíčpm Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O «0000000 ooooooooo 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, Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O «0000000 ooooooooo 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. Diofanticke rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O «0000000 ooooooooo 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 £ N, Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O «0000000 ooooooooo 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. Q inverzi celého čísla a modulo m £ N, O největší společný dělitel dvou celých čísel (a případně koeficienty do Bezoutovy rovnosti), Diofanticke rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O «0000000 ooooooooo 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. Q inverzi celého čísla a modulo m £ 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é, Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O «0000000 ooooooooo 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. Q inverzi celého čísla a modulo m £ 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. Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O O0OOOOOO ooooooooo 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í škol kdy umíme sčítat v lineárním, násobit a dělit se zbytkem v kvadratickém čase. Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O O0OOOOOO ooooooooo 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í škol 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 Q(n}o^3) Diofanticke rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O O0OOOOOO ooooooooo 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(r?log23) nebo algoritmus Schónhage-Strassenův (1971) časové náročnosti 0(r? 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). Diofanticke rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O O0OOOOOO ooooooooo 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(r?log23) nebo algoritmus Schónhage-Strassenův (1971) časové náročnosti 0(r? 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 Diofantické rovnice O Výpočetní aspekty teorie čísel oo«ooooo Kryptografie s veřejným klíčem ooooooooo 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ů /c, / do Bezoutovy rovnosti k • a + / • m = 1 (nalezené k je pak onou hledanou inverzí a modulo m). Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem 0 oo«ooooo ooooooooo GCD a modu lá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ů /c, / do Bezoutovy rovnosti k • a + I • m = 1 (nalezené k je pak onou hledanou inverzí a modulo m). function extended _gcd(a, m) if m — 0 return (1 - 0) else (q, r) := divide (a, m) (k, 1) := extended_gcd(m, r) return (1 , k - q * 1 ) Podrobná analýza (viz např. [Knuth] nebo [Wiki]) ukazuje, že tento algoritmus je kvadratické časové složitosti. <□► -íŕ^J^ < >■ -E O Q, O Diofantické rovnice O Výpočetní aspekty teorie čísel ooo«oooo Kryptografie s veřejným klíčem ooooooooo 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: Diofanticke rovnice O Výpočetní aspekty teorie čísel ooo«oooo Kryptografie s veřejným klíčem ooooooooo 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 , modu lus) result := 1 while exponent > 0 if (exponent mod 2 1): result := (result * base) mod mod u 1 us exponent := exponent » 1 base = (base * base) mod modulus return result Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem 0 oooo»ooo ooooooooo 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, Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem 0 oooo»ooo ooooooooo 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, Diofantické rovnice O Výpočetní aspekty teorie čísel OOOOO0OO Kryptografie s veřejným klíčem ooooooooo Příklad (Ukázka průběhu algoritmu) Vypočtěme 2560 (mod 561). •O ^ O Diofantické rovnice O Výpočetní aspekty teorie čísel OOOOO0OO Kryptografie s veřejným klíčem ooooooooo Příklad (Ukázka průběhu algoritmu) Vypočtěme 2560 (mod 561). Protože 560 = (1000110000)2, dostaneme uvedeným algoritmem no feny) 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 Diofantické rovnice O Výpočetní aspekty teorie čísel OOOOO0OO Kryptografie s veřejným klíčem ooooooooo 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). Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O OOOOOO0O ooooooooo 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. Diofanticke rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O 0000000« ooooooooo Testování prvočíselnosti, rozklad složených čísel Toto je téma na samostatnou přednášku, nebudeme zde uvádět, učebnici lze mnohé najít v odstavcích 10.38-47. Výpočetní aspekty teorie čísel oooooooo Plán přednášky Diofanticke rovnice O Kryptografie s veřejným klíčem ooooooooo Q Kryptografie s veřejným klíčem Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O OOOOOOOO «00000000 Kryptografie s veřejným klíčem (PKC) Dva hlavní úkoly pro PKC jsou zajistit rr & A • šifrování, kdy zprávu zašifrovanou veřejným klíčem příjemce K 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 ti <- řf í 4 Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O OOOOOOOO «00000000 Kryptografie s veřejným klíčem (PKC) Dva hlavní úkoly pro PKC jsou zajistit 9 š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 Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O OOOOOOOO «00000000 Kryptografie s veřejným klíčem (PKC) Dva hlavní úkoly pro PKC jsou zajistit 9 š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 o Digital signature algorithm (DSA) a varianta založená na eliptických křivkách (ECDSA) Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O OOOOOOOO «00000000 Kryptografie s veřejným klíčem (PKC) Dva hlavní úkoly pro PKC jsou zajistit 9 š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 o Digital signature algorithm (DSA) a varianta založená na eliptických křivkách (ECDSA) • Rabínův kryptosystém (a podepisování) Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O OOOOOOOO «00000000 Kryptografie s veřejným klíčem (PKC) Dva hlavní úkoly pro PKC jsou zajistit 9 š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 o Digital signature algorithm (DSA) a varianta založená na eliptických křivkách (ECDSA) • Rabínův kryptosystém (a podepisování) 9 EIGamal kryptosystém (a podepisování) Dva hlavní úkoly pro PKC jsou zajistit 9 š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 o Digital signature algorithm (DSA) a varianta založená na eliptických křivkách (ECDSA) • Rabínů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 9 š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 o Digital signature algorithm (DSA) a varianta založená na eliptických křivkách (ECDSA) • Rabínův kryptosystém (a podepisování) EIGamal kryptosystém (a podepisování) • Kryptografie eliptických křivek (ECC) • Diffie-Hellmanův protokol 4 = Výpočetní aspekty teorie čísel oooooooo RSA Diofanticke rovnice O Kryptografie s veřejným klíčem O0OOOOOOO Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973) o každý účastník A potřebuje dvojici klíčů - veřejný Va a soukromý Sa Výpočetní aspekty teorie čísel oooooooo RSA Diofanticke rovnice O Kryptografie s veřejným klíčem O0OOOOOOO Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973) » každý účastník A potřebuje dvojici klíčů - veřejný Va a soukromý S a • generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, (p(n) = (p — l)(q — 1) [n je veřejné, ale y(n) nelze ^éTiadno spočítat ] . pjT&i^d 0«^ --v poc^re^i .--- r \ I f i '— r u M Výpočetní aspekty teorie čísel oooooooo RSA Diofanticke rovnice O Kryptografie s veřejným klíčem O0OOOOOOO Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973) o každý účastník A potřebuje dvojici klíčů - veřejný Va a soukromý Sa • generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, (p(n) = (p — l)(q — 1) [n je veřejné, ale (p(n) nelze snadno spočítat ] • zvolí veřejný klíč e a ověří, že (e, (p(n)) = 1 Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973) o každý účastník A potřebuje dvojici klíčů - veřejný Va a soukromý Sa • generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, (p(n) = (p — l)(q — 1) [n je veřejné, ale (p(n) nelze snadno spočítat ] • zvolí veřejný klíč e a ověří, že (e, (p(n)) = 1 « např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e • d = 1 (mod v?(r?)) / ; Výpočetní aspekty teorie čísel oooooooo RSA Diofanticke rovnice O Kryptografie s veřejným klíčem O0OOOOOOO Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973) o každý účastník A potřebuje dvojici klíčů - veřejný Va a soukromý Sa • generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, (p(n) = (p — l)(q — 1) [n je veřejné, ale (p(n) nelze snadno spočítat ] • zvolí veřejný klíč e a ověří, že (e, (p(n)) = 1 o např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e • d = 1 (mod (p(n)) 9 zašifrování numerického kódu zprávy M\ C — Ce(M) = Me (mod r?) Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973) o každý účastník A potřebuje dvojici klíčů - veřejný Va a soukromý Sa • generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, (p(n) = (p — l)(q — 1) [n je veřejné, ale (p(n) nelze snadno spočítat ] • zvolí veřejný klíč e a ověří, že (e, (p(n)) = 1 o např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e • d = 1 (mod v?(r?)) • zašifrování numerického kódu zprávy M\ C — Ce(M) = Me • dešifrování šifry C: 07" = Dcy(C) = C (mod r?) (mod r?) Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O OOOOOOOO OO0OOOOOO Rabínův kryptosystém Prvním veřejným kryptosysternem, k jehož prolomení je prokazatelně potřeba faktorizovat modul, je Rabínův kryptosystém, který si uvedeme ve zjednodušené verzi: o každý účastník A potřebuje dvojici klíčů - veřejný Va a soukromý Sa M I- t >0 Q,o Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O OOOOOOOO OO0OOOOOO Rabínův kryptosystém Prvním veřejným kryptosysternem, k jehož prolomení je prokazatelně potřeba faktorizovat modul, je Rabínův kryptosystém, který si uvedeme ve zjednodušené verzi: o 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. Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O OOOOOOOO OO0OOOOOO Rabínův kryptosystém Prvním veřejným kryptosysternem, k jehož prolomení je prokazatelně potřeba faktorizovat modul, je Rabínův kryptosystém, který si uvedeme ve zjednodušené verzi: o 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) Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O OOOOOOOO OO0OOOOOO Rabínův kryptosystém Prvním veřejným kryptosysternem, k jehož prolomení je prokazatelně potřeba faktorizovat modul, je Rabínův kryptosystém, který si uvedeme ve zjednodušené verzi: o 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) 9 zašifrování numerického kódu zprávy M\ C = Ce(M) = M2 (mod n) Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O OOOOOOOO OO0OOOOOO Rabínův kryptosystém Prvním veřejným kryptosysternem, k jehož prolomení je prokazatelně potřeba faktorizovat modul, je Rabínův kryptosystém, který si uvedeme ve zjednodušené verzi: o každý účastník A potřebuje dvojici klíčů - veřejný V a 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) 9 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. <□► -ír^J^ < > -E O Q, O im'1-g- c r?j n1- s i C?) l p • Bob vybere náhodné b a pošle gb (mod p) . i « i Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem 0 oooooooo OOOOOO0OO Diffie-Hel Iman 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 modul p (veřejné) o 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). Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem 0 oooooooo OOOOOO0OO Diffie-Hel Iman 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 modul p (veřejné) o 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). Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O OOOOOOOO OOOOOO0OO 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, ...). 9 Dohoda stran na prvočísle p a primitivním kořenu g modulo p (veřejné) ^ 1 *r*^U3r °< o Alice vybere náhodné a a pošle ga (mod p) renu g moauio, k • 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) 9 Nezbytná autentizace (man in the middle attack) «f- _ u A- «=>a--- M .--/(-- Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem O OOOOOOOO OOOOOOO0O 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 o 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) o dešifrování zprávy: OT — C2/C* ^ obojí W)^^ ^ □ ► < g ► < i ► < i ► Diofantické rovnice Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem 0 oooooooo OOOOOOO0O 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 o 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: OT — C2/C* Poznámka Analogicky jako v případě RSA lze odvodit podepisování. Výpočetní aspekty teorie čísel oooooooo Eliptické křivky Diofanticke rovnice O Kryptografie s veřejným klíčem OOOOOOOO* Eliptické křivky jsou rovinné křivky o rovnici tvaru y = xó + 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 . Výpočetní aspekty teorie čísel oooooooo Eliptické křivky Diofanticke rovnice O Kryptografie s veřejným klíčem OOOOOOOO* Eliptické křivky jsou rovinné křivky o rovnici tvaru y = xó + 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: 9 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. Výpočetní aspekty teorie čísel oooooooo Eliptické křivky Diofanticke rovnice O Kryptografie s veřejným klíčem OOOOOOOO* 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 . C7 #y Protokoly: u Vl