Matematika IV - Demonstrované cvičení 6 Šifrování
Michal Bulant
Masarykova univerzita Fakulta informatiky
23. 3. 2009
□         S
Obsah přednášky
□         S
Doporučené zdroje
• Menezes, Oorschot, Vanstone - Handbook of Applied Cryptography, CRC Press, 1996 (též na http://www.cacr.math.uwaterloo.ca/hac).
□      s
Ron Rivest, Adi Shamir, Leonard Adieman (1977; C. Cocks,GCHQ - 1973)
• každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý S a
•  každý účastník A potřebuje dvojici klíčů - veřejný V/\ a soukromý Sa
•  generovaní klíčů: zvolí dvě velká prvočísla p, q, vypočte
n = pq, tf (n) = (p — l)(q — 1) [n je veřejné, ale <p(n) nelze snadno spočítat ]
•  každý účastník A potřebuje dvojici klíčů - veřejný V/\ a soukromý Sa
•  generovaní klíčů: zvolí dvě velká prvočísla p, q, vypočte
n = pq, tf (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, tp(n)) = 1
•  každý účastník A potřebuje dvojici klíčů - veřejný V/\ a soukromý Sa
•  generovaní klíčů: zvolí dvě velká prvočísla p, q, vypočte
n = pq, tf (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, tp(n)) = 1
•  např. pomoci Euklidova algoritmu spočíta tajný klíč d tak, aby e • d = 1 (mod <p(n))
•  každý účastník A potřebuje dvojici klíčů - veřejný V/\ a soukromý Sa
•  generovaní klíčů: zvolí dvě velká prvočísla p, q, vypočte
n = pq, tf (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, tp(n)) = 1
•  např. pomoci Euklidova algoritmu spočítá tajný klíč d tak, aby e • d = 1 (mod <p(n))
m zašifrování numerického kódu zprávy M: C = Ce{M) = Me (mod n)
•  každý účastník A potřebuje dvojici klíčů - veřejný V/\ a soukromý Sa
•  generovaní klíčů: zvolí dvě velká prvočísla p, q, vypočte
n = pq, tf (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, tp(n)) = 1
•  např. pomoci Euklidova algoritmu spočítá tajný klíč d tak, aby e • d = 1 (mod <p(n))
m zašifrování numerického kódu zprávy M: C = Ce{M) = Me (mod n)
•  dešifrování šifry C: OT = Dd(C) = Cd (mod n)
•  každý účastník A potřebuje dvojici klíčů - veřejný V/\ a soukromý Sa
•  generovaní klíčů: zvolí dvě velká prvočísla p, q, vypočte
n = pq, tf (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, tp(n)) = 1
•  např. pomoci Euklidova algoritmu spočítá tajný klíč d tak, aby e • d = 1 (mod <p(n))
m zašifrování numerického kódu zprávy M: C = Ce{M) = Me (mod n)
•  dešifrování šifry C: OT = Dd(C) = Cd (mod n)
•  každý účastník A potřebuje dvojici klíčů - veřejný V/\ a soukromý Sa
•  generovaní klíčů: zvolí dvě velká prvočísla p, q, vypočte
n = pq, tf (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, tp(n)) = 1
•  např. pomoci Euklidova algoritmu spočítá tajný klíč d tak, aby e • d = 1 (mod <p(n))
m zašifrování numerického kódu zprávy M: C = Ce{M) = Me (mod n)
•  dešifrování šifry C: OT = Dd(C) = Cd (mod n)
Příklad
Alice si za parametry svého RSA klíče zvolila p = 23, q = 31, e = 17. Dopočítejte její soukromý klíč a pomocí modulárního umocňování na druhou (s možným použitím kalkulačky) zašifrujte (a poté dešifrujte) zprávu m = 12.
□      s
Příklad
Alice si za parametry svého RSA klíče zvolila p = 23, q = 31, e = 17. Dopočítejte její soukromý klíč a pomocí modulárního umocňování na druhou (s možným použitím kalkulačky) zašifrujte (a poté dešifrujte) zprávu m = 12.
Řešení
d = 233, po zašifrování c = 538.
Poznámka
Dosud se bohužel nepodařilo dokázat ani to, že faktorizace (rozklad na prvočísla) čísla n je výpočetně neschůdná, ani to, že prolomit RSA nejde (obecně) snadněji než rozkladem modulu n.
• každý účastník A potřebuje dvojici klíčů - veřejný Va a soukromý S a
Poznámka
Dosud se bohužel nepodařilo dokázat ani to, že faktorizace (rozklad na prvočísla) čísla n je výpočetně neschůdná, ani to, že prolomit RSA nejde (obecně) snadněji než rozkladem modulu n.
•  každý účastník A potřebuje dvojici klíčů - veřejný Va a soukromý S a
•  generování klíčů: zvolí dvě podobně velká prvočísla p, q (mod 4), vypočte n = pq.
Poznámka
Dosud se bohužel nepodařilo dokázat ani to, že faktorizace (rozklad na prvočísla) čísla n je výpočetně neschůdná, ani to, že prolomit RSA nejde (obecně) snadněji než rozkladem modulu n.
•  každý účastník A potřebuje dvojici klíčů - veřejný Va a soukromý S a
•  generování klíčů: zvolí dvě podobně velká prvočísla p, q = 3 (mod 4), vypočte n = pq.
9  VA = n, SA = (p, q)
Poznámka
Dosud se bohužel nepodařilo dokázat ani to, že faktorizace (rozklad na prvočísla) čísla n je výpočetně neschůdná, ani to, že prolomit RSA nejde (obecně) snadněji než rozkladem modulu n.
•  každý účastník A potřebuje dvojici klíčů - veřejný VA a soukromý SA
•  generování klíčů: 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)
Poznámka
Dosud se bohužel nepodařilo dokázat ani to, že faktorizace (rozklad na prvočísla) čísla n je výpočetně neschůdná, ani to, že prolomit RSA nejde (obecně) snadněji než rozkladem modulu n.
•  každý účastník A potřebuje dvojici klíčů - veřejný VA a soukromý SA
•  generování klíčů: 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)
9 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)
•  vypočti a, b tak, že ap + bq = 1
•  vypočti r = C(p+1)/4 (mod p) a s = C^+1)/4 (mod q)
•  polož x = (aps + bqr) (mod n), y = (aps — bqr) (mod n)
•  druhými odmocninami z C modulo n jsou ±x, ±y.
Příklad
V Rabínově kryptosystemu 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.
□     s
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).
Diffie-Hellman key exchange, EIGamal
□         S
Diffie-Hellman key exchange, EIGamal
• Dohoda stran na cyklické grupě G a jejím generátoru g (veřejné)
□     s
Diffie-Hellman key exchange, EIGamal
•  Dohoda stran na cyklické grupě G a jejím generátoru g (veřejné)
•  Alice vybere náhodné a a pošle ga
□     s
Diffie-Hellman key exchange, EIGamal
•  Dohoda stran na cyklické grupě G a jejím generátoru g (veřejné)
•  Alice vybere náhodné a a pošle ga
•  Bob vybere náhodné b a pošle gb
□     s
Diffie-Hellman key exchange, EIGamal
•  Dohoda stran na cyklické grupě G a jejím generátoru g (veřejné)
•  Alice vybere náhodné a a pošle ga
•  Bob vybere náhodné b a pošle gb
•  Společným klíčem pro komunikaci je gab.
□     s
Diffie-Hellman key exchange, EIGamal
•  Dohoda stran na cyklické grupě G a jejím generátoru g (veřejné)
•  Alice vybere náhodné a a pošle ga
•  Bob vybere náhodné b a pošle gb
•  Společným klíčem pro komunikaci je gab.
□     s
Diffie-Hellman key exchange, EIGamal
•   Dohoda stran na cyklické grupě G a jejím generátoru g (veřejné)
•  Alice vybere náhodné a a pošle ga
•   Bob vybere náhodné b a pošle gb
•  Společným klíčem pro komunikaci je gab.
Poznámka
•   Původní (a nejobvyklejší) volba G je multipliktivní grupa invertibilních zbytkových tříd modulo prvočíslo p, její generátor bývá také nazývám primitivní kořen modulo p .
•   Problém diskrétního logaritmu (DLP)
•  Nezbytná autentizace (man in the middle attack)
Příklad
Demonstrujte dohodu Alice a Boba na tajném klíči v DH systému na výměnu klíčů se (všem) známými parametry G = (Z^, •), g = 5.
□       s
Příklad
Demonstrujte dohodu Alice a Boba na tajném klíči v DH systému na výměnu klíčů se (všem) známými parametry G = (Z^, •), g = 5.
Řešení
Možností je mnoho, např. a = 13, b = 20, Alice posílá 513 = 21
(mod 23), Bob posílá 520 = 12 (mod 23), pak klíčem je 2120 = 12i3 = 6 (mod 2)3.
•  Alice zvolí cyklickou grupu G spolu s generátorem g
9 Alice zvolí tajný klíč x, spočítá h = gx a zveřejní veřejný klíč (G,g,h)
•  šifrování zprávy M: Bob zvolí náhodné y a vypočte C\ = gy a C2 = M ■ hy a pošle (Q, C2)
•  dešifrování zprávy: OT = C2/C1
Příklad
Alice zvolila za parametry v kryptosystému EIGamal p = 23, g = 5 za svůj soukromý klíc zvolila x = 13 a zveřejnila veřejný klíc (p, g,gx). Ukažte, jak Bob zašifruje zprávu M = 17 určenou Alici a jak tuto zprávu následně Alice dešifruje.
□     s
Příklad
Alice zvolila za parametry v kryptosystému EIGamal p = 23, g = 5 za svůj soukromý klíc zvolila x = 13 a zveřejnila veřejný klíc (p, g,gx). Ukažte, jak Bob zašifruje zprávu M = 17 určenou Alici a jak tuto zprávu následně Alice dešifruje.
Bob zvolí např. y = 12, dopočte C\ = 512 = 18 (mod 23) a C2 = M ■ (21)12 = 11 (mod 23). Alice (díky znalosti x) spočítá M = C2/Cf = 17 (mod 23).