Výpočetní aspekty teorie čísel	Kryptografie s veřejným klíčem
oooooooo	ooooooooo
Diskrétní matematika - 5. týden Aplikace teorie čísel - Počítání s velkými čísly, kryptografie
Jan Slovák (výběr z podkladů M. Bulanta)
Masarykova univerzita Fakulta informatiky
jaro 2015
LU33J|>| WÄUÍ3J3A S 3l}ej3o}dÄJ>] ^
psj3 3U031 Äi^adse JU1330dÄ/\ Q
		JI
ooooooooo		oooooooo
		|3sjp 3uo3q. Äq.>|3dse iu}3DodÄ/\
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
oooooooo ooooooooo
Doporučené zdroje
• 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	Kryptografie s veřejným klíčem
oooooooo	ooooooooo
Doporučené zdroje	
• Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne.
• V. Švábenský, Sbírka příkladů (a další zdroje), https://is.muni.cz/auth/th/395868/fi_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 Kryptografie s veřejným klíčem
oooooooo ooooooooo
Plán přednášky
O Výpočetní aspekty teorie čísel
Q Kryptografie s veřejným
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
•ooooooo 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,
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
•ooooooo 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.
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
•ooooooo 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 G N,
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
•ooooooo 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 G N,
O největší společný dělitel dvou celých čísel (a případně koeficienty do Bezoutovy rovnosti),
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
•ooooooo 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 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é,
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
•ooooooo 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 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.
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.
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)
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).
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
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ů k, I do Bezoutovy rovnosti k ■ a + / • m = 1 (nalezené k je pak onou hledanou inverzí a modulo m).
Výpočetní aspekty teorie čísel
oo»ooooo
Kryptografie s veřejným klíčem
ooooooooo
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 extendedgcd(a, b) a  := 0; old a   := 1
t
= 1
old t
= 0
r
= b
old r
while r # 0
quotient   := old r div r
[old r, r) := (r, old r - quotient * r) (old_s,  s) (3,  olds - quotient * s)
(old_t,   t)   :=  (t,  old_t - quotient * t)
output "Bezout coefficients:",   (olds, old t)
output "greatest common divisor:",   old r output  "quotients by the gcd:",   (t, s}
Podrobná analýza (viz např. [Knuth] nebo [Wiki]) ukazuje, že tento algoritmus je kvadratické časové složitosti.
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
ooo»oooo 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:
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
ooo»oooo 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 ,   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	
Výpočetní aspekty teorie čísel	Kryptografie s veřejným klíčem
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,
Výpočetní aspekty teorie čísel
oooo^ooo
Kryptografie s veřejným klíčem
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-
Výpočetní aspekty teorie čísel	Kryptografie s veřejným klíčem
ooooo»oo	ooooooooo
Příklad (Ukázka průběhu algoritmu)
Vypočtěme 2560 (mod 561).
Výpočetní aspekty teorie čísel	Kryptografie s veřejným klíčem
ooooo»oo	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
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
ooooo»oo 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).
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
oooooo»o 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.
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
ooooooo* ooooooooo
Testování prvočíselnosti, rozklad složených čísel
Toto je téma na samostatnou přednášku, nebudeme zde uvádět, v učebnici lze mnohé najít v odstavcích 10.38-47.
Výpočetní aspekty teorie čísel
oooooooo
Kryptografie s veřejným klíčem
ooooooooo
Q Výpočetní aspekty teorie čísel
Q Kryptografie s veřejným klíčem
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
OOOOOOOO »00000000
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
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
OOOOOOOO »00000000
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
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
OOOOOOOO »00000000
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)
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
OOOOOOOO »00000000
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í)
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
OOOOOOOO »00000000
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í)
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
OOOOOOOO »00000000
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)
Kryptografie s veřejným klíčf
•oooooooo
Dva hlavní úkoly pro PKC jsou zajistit
• šifrovaní, 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 ^
1 -00.0
Výpočetní aspekty teorie čísel
oooooooo
Kryptografie s veřejným klíčem
o»ooooooo
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
oooooooo
Kryptografie s veřejným klíčem
o»ooooooo
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
oooooooo
Kryptografie s veřejným klíčem
o»ooooooo
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
oooooooo
Kryptografie s veřejným klíčem
o»ooooooo
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
oooooooo
Kryptografie s veřejným klíčem
o»ooooooo
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
oooooooo
Kryptografie s veřejným klíčem
o»ooooooo
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
oooooooo
Kryptografie s veřejným klíčem
oo»oooooo
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
oooooooo
Kryptografie s veřejným klíčem
oo»oooooo
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
oooooooo
Kryptografie s veřejným klíčem
oo»oooooo
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
oooooooo
Kryptografie s veřejným klíčem
oo»oooooo
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
oooooooo
Kryptografie s veřejným klíčem
oo»oooooo
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.
Výpočetní aspekty teorie čísel
oooooooo
Kryptografie s veřejným klíčem
ooo^ooooo
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ě o aplikaci Čínské	zbytkové věty!
Výpočetní aspekty teorie čísel
oooooooo
Kryptografie s veřejným klíčem
ooo^ooooo
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ě o aplikaci Čínské	zbytkové věty!
Výpočetní aspekty teorie čísel
oooooooo
Kryptografie s veřejným klíčem
ooo^ooooo
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	
• položa x = (aps + bqr) (mod n), y =	= (aps — bqr) (mod n)
aUvědomte si, že jde vlastně o aplikaci Čínské	zbytkové věty!
Výpočetní aspekty teorie číse
oooooooo
Kryptografie s veřejným klíčem
ooo»ooooo
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 — faqr) (mod n) 9 druhými odmocninami z C modulo n jsou ±x, ±y.
aUvědomte si, že jde vlastně o aplikaci Čínské zbytkové věty!
Výpočetní aspekty teorie čísel	Kryptografie s veřejným klíčem
oooooooo	oooo»oooo
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.
Výpočetní aspekty teorie čísel
oooooooo
Kryptografie s veřejným klíčem
oooo»oooo
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 Kryptografie s veřejným klíčem
oooooooo ooooosooo
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.
4 n * < & > 4 = * 4 = >     -š -O^O
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
oooooooo ooooosooo
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
oooooooo
Kryptografie s veřejným klíčem
oooooo»oo
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, .. .).
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
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, .. .).
• Dohoda stran na prvočísle p a primitivním kořenu g modulo p (veřejné)
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
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, .. .).
• 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)
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
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, .. .).
• 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)
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
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, .. .).
• 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).
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
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, .. .).
• 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).
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
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, .. .).
• 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 Kryptografie s veřejným klíčem
oooooooo ooooooo»o
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 Kryptografie s veřejným klíčem
oooooooo ooooooo»o
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	Kryptografie s veřejným klíčem
oooooooo	OOOOOOOO*
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 .
4 n * < & > 4 = * 4 = >     -š -O^O
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
oooooooo oooooooo*
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.
Výpočetní aspekty teorie čísel Kryptografie s veřejným klíčem
oooooooo oooooooo*
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.