Diofantické rovnice OO
Kryptografie s veřejným klíčem ooooooooooo
Diskrétní matematika - 5. týden Aplikace teorie čísel - Počítání s velkými čísly,
kryptografie
Lukáš Vokřínek
Masarykova univerzita Fakulta informatiky
podzim 2024
Diofantické rovnice Kryptografie s veřejným klíčem
oo ooooooooooo
Obsah přednášky
Diofantické rovnice
Q Kryptografie s veřejným klíčem
Diofantické rovnice Kryptografie s veřejným klíčem
oo ooooooooooo
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
• 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.
o William Stein, Elementary Number Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupné na http://wstein.org/ent/ent.pdf
Diofantické rovnice
Diofantické rovnice
Di
c
Kryptografie s veřejným klíčem ooooooooooo
' Příklad_ 1	
Vyřešte diofantickou rovnici	
72x + 100y = 16.	
Diofantické rovnice
Vyřešte diofantickou rovnici
Kryptografie s veřejným klíčem ooooooooooo
72x + 100y = 16
Vyřešte diofantickou rovnici
72x + 100y + 45z = 1.
Diofantické rovnice Kryptografie s veřejným klíčem
OO »0000000000
Q Kryptografie s veřejným klíčem
Diofantické rovnice Kryptografie s veřejným klíčem
OO O0OOOOOOOOO
kryptografie s verejný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
Diofantické rovnice Kryptografie s veřejným klíčem
OO O0OOOOOOOOO
kryptografie s verejný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 Kryptografie s veřejným klíčem
OO O0OOOOOOOOO
Kryptografie s verejný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
9 Digital signature algorithm (DSA) a varianta založená na eliptických křivkách (ECDSA)
Diofantické rovnice Kryptografie s veřejným klíčem
OO O0OOOOOOOOO
Kryptografie s verejný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
9 Digital signature algorithm (DSA) a varianta založená na eliptických křivkách (ECDSA)
• Rabínův 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
9 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í)
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
9 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)
Diofantické rovnice Kryptografie s veřejným klíčem
OO O0OOOOOOOOO
Kryptografie s verejný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
9 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 na výměnu klíčů (DH)
□ v t3
Diofantické rovnice Kryptografie s veřejným klíčem
oo oo«oooooooo
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
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ý S a
9 generování klíčů: zvolí se dvě velká prvočísla p, q, vypočte se n = pq, (p(n) = (p — l)(q — 1), dále se zvolí e a ověří, že (e,(p(n)) = 1, např. pomocí Euklidova algoritmu se spočítá d tak, aby e • d = 1 (mod (f(n))
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ý S a
9 generování klíčů: zvolí se dvě velká prvočísla p, q, vypočte se n = pq, (p(n) = (p — l)(q — 1), dále se zvolí e a ověří, že (e,(p(n)) = 1, např. pomocí Euklidova algoritmu se spočítá d tak, aby e • d = 1 (mod (f(n))
• VA = (n,e)f S/\ = cř
Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973)
o každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý S a
9 generování klíčů: zvolí se dvě velká prvočísla p, q, vypočte se n = pq, (p(n) = (p — l)(q — 1), dále se zvolí e a ověří, že (e,(p(n)) = 1, např. pomocí Euklidova algoritmu se spočítá d tak, aby e • d = 1 (mod (f(n))
• VA = (n,e)f S/\ = cř
• zašifrování numerického kódu zprávy M: C = Va(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
9 generování klíčů: zvolí se dvě velká prvočísla p, q, vypočte se n = pq, (p(n) = (p — l)(q — 1), dále se zvolí e a ověří, že (e,(p(n)) = 1, např. pomocí Euklidova algoritmu se spočítá d tak, aby e • d = 1 (mod (f(n))
• VA = (n,e)f S/\ = cř
• zašifrování numerického kódu zprávy M: C = Va(M) = Me (mod r?)
• dešifrování šifry C: M = SA(C) = Cd (mod n)
Diofantické rovnice	Kryptografie s veřejným klíčem
OO	ooo»ooooooo
Příklad
Demonstrujte RSA protokol se zvolenými prvočísly 23 a 29 s vhodnou volbou veřejného klíče e. Zašifrujte a odšifrujte několik zpráv m pro ne moc velká m.
Diofantické rovnice OO
Kryptografie s veřejným klíčem ooo»ooooooo
Příklad
Demonstrujte RSA protokol se zvolenými prvočísly 23 a 29 s vhodnou volbou veřejného klíče e. Zašifrujte a odšifrujte několik zpráv m pro ne moc velká m.
Řešení
Budeme volit e = 487 a m = 25. Zašifrovaná zpráva vyjde c = 169, dešifrovací exponent d = 191.
Diofantické rovnice Kryptografie s veřejným klíčem
OO OOOO0OOOOOO
Prvním veřejným kryptosystémem, 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ý S a
Diofantické rovnice Kryptografie s veřejným klíčem
OO OOOO0OOOOOO
Prvním veřejným kryptosystémem, 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ý S a
• generování klíčů: A zvolí dvě podobně velká prvočísla p, q = 3 (mod 4), vypočte n = pq.
Diofantické rovnice Kryptografie s veřejným klíčem
OO OOOO0OOOOOO
Prvním veřejným kryptosystémem, 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ý S a
• generování klíčů: A zvolí dvě podobně velká prvočísla p, q = 3 (mod 4), vypočte n = pq.
• VA = n, SA = (p, q)
Prvním veřejným kryptosystémem, 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ý S a
• 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 — Va(M) = M2 (mod n)
Prvním veřejným kryptosystémem, 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ý S a
• 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 — Va(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čet druhé odmocniny z C modulo n = pq, kde p = q = 3 (mod 4)
klíčem
• vypočti odmocniny modulo p a modulo q, konkrétne r = ±c(p+1)/4 (mod p) a s = iC^1)/4 (mod g)
Diofantické rovnice OO
Kryptografie s veřejným klíčem OOOOO0OOOOO
Výpočet druhé odmocniny z C modulo n = pq, kde p = q = 3 (mod 4)
• vypočti odmocniny modulo p a modulo q, konkrétně r = ±C(p+1)/4 (mod p) a s = ±C^+1)/4 (mod q)
• pomocí Čínské zbytkové věty spočti pro každou kombinaci odmocnin modulo p a modulo q odpovídající odmocninu modulo n — pq
Diofantické rovnice	Kryptografie s veřejným klíčem
OO	oooooo»oooo
Příklad
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.
Diofantické rovnice OO
Kryptografie s veřejným klíčem oooooo»oooo
Příklad
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).
Diofantické rovnice Kryptografie s veřejným klíčem
OO OOOOOOO0OOO
Podepisování
O Vygeneruje se otisk (hash) Hm zprávy pevně stanovené délky (např. 160 nebo 256 bitů).
O Podpis zprávy Sa(Hm) je vytvořen (pomocí dešifrování) z tohoto hashe s nutností znalosti soukromého klíče podepisujícího.
O Zpráva M (případně zašifrovaná veřejným klíčem příjemce) je spolu s podpisem odeslána.
Diofantické rovnice Kryptografie s veřejným klíčem
OO OOOOOOO0OOO
Princip digitálního podpisu
Podepisování
O Vygeneruje se otisk (hash) Hm zprávy pevně stanovené délky (např. 160 nebo 256 bitů).
O Podpis zprávy Sa(Hm) je vytvořen (pomocí dešifrování) z tohoto hashe s nutností znalosti soukromého klíče podepisujícího.
O Zpráva M (případně zašifrovaná veřejným klíčem příjemce) je spolu s podpisem odeslána.
Ověření podpisu
O K přijaté zprávě M se (po jejím případném dešifrování) vygeneruje otisk HfM
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'M?.
Diofantické rovnice Kryptografie s veřejným klíčem
oo oooooooo«oo
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, ...).
Diofantické rovnice Kryptografie s veřejným klíčem
oo oooooooo«oo
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é)
Diofantické rovnice Kryptografie s veřejným klíčem
oo oooooooo«oo
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é)
o Alice vybere náhodné a a pošle ga (mod p)
<□►  < rnP ►  < -E ►  < -E ►     -E     O °n O
Diofantické rovnice Kryptografie s veřejným klíčem
oo oooooooo«oo
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é)
o Alice vybere náhodné a a pošle ga (mod p)
• Bob vybere náhodné b a pošle gb (mod p)
Diofantické rovnice Kryptografie s veřejným klíčem
oo oooooooo«oo
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é)
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 Kryptografie s veřejným klíčem
oo oooooooo«oo
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é)
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 Kryptografie s veřejným klíčem
oo oooooooo«oo
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é)
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).
Poznámka
• Problém diskrétního logaritmu (DLP)
• Nezbytná autentizace (man in the middle attack)
Diofantické rovnice OO
ryptosystem
ama
Kryptografie s veřejným klíčem ooooooooo«o
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í a a spočítá h = ga (mod p)
• VA = (p,g,h), SA = a
o šifrování zprávy M\ Bob zvolí náhodné b a vypočte C\ = g (mod p) a C2 = M • hb (mod p) a pošle C = (Ci, C2)
• dešifrování zprávy: M = C2/C* (mod p)
Diofantické rovnice OO
ryptosystem
ama
Kryptografie s veřejným klíčem ooooooooo«o
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í a a spočítá h = ga (mod p)
• VA = (p,g,h), SA = a
o šifrování zprávy M\ Bob zvolí náhodné b a vypočte C\ = g (mod p) a C2 = M • hb (mod p) a pošle C = (Ci, C2)
• dešifrování zprávy: M = C2/C* (mod p)
Poznámka
Analogicky jako v případě RSA lze odvodit podepisování.
Diofantické rovnice OO
Kryptografie s veřejným klíčem oooooooooo*
Příklad
Martin a Honza chtějí komunikovat šifrou EIGamal navrženou egyptským matematikem Taherem Elgamalem podle protokolu Diffieho a Hellmana na výměnu klíčů. Martin si zvolil prvočíslo p = 41 a jemu příslušný primitivní kořen g — 11 a dále si zvolil soukromý klíč - exponent a = 10. Zveřejnil tedy trojici čísel p = 41, g — 11, g3 = 9. Honza mu poslal veřejným kanálem dvojici čísel gb = 22, c = 6. Jakou zprávu Honza poslal?
<□►  < rnP ►  < -E ►  < -E ►     E     O °n O
Diofantické rovnice OO
Kryptografie s veřejným klíčem oooooooooo*
Příklad
Martin a Honza chtějí komunikovat šifrou EIGamal navrženou egyptským matematikem Taherem Elgamalem podle protokolu Diffieho a Hellmana na výměnu klíčů. Martin si zvolil prvočíslo p = 41 a jemu příslušný primitivní kořen g — 11 a dále si zvolil soukromý klíč - exponent a = 10. Zveřejnil tedy trojici čísel p = 41, g — 11, g3 = 9. Honza mu poslal veřejným kanálem dvojici čísel gb = 22, c = 6. Jakou zprávu Honza poslal?
Řešení
Vyjde gab = 32, následně m = 13.
Eliptické krivky 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 .
Eliptické krivky 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) 9 ECDSA - digitální podpis pomocí eliptických křivek.
Diofantické rovnice Kryptografie s veřejným klíčem
oo ooooooooooo
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:
9 ECDH - přímá varianta DH na eliptické křivce (jen místo
generátoru se vybere vhodný bod na křivce) 9 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.