Pár slov o šifrách Matematika IV – 6. přednáška Poznámky o šifrách Masarykova univerzita Fakulta informatiky 26. 3. 2012 Pár slov o šifrách Obsah přednášky 1 Pár slov o šifrách Pár slov o šifrách Doporučené zdroje Martin Panák, Jan Slovák, Drsná matematika, e-text. Předmětové záložky v IS MU R. B. Ash, Abstract algebra, http://www.math.uiuc.edu/~r-ash/Algebra.html. Jiří Rosický, Algebra, PřF MU, 2002. Peter J. Cameron. Introduction to algebra, Oxford University Press, 2001, 295 s. (Dostupné v knihovně PřF). Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone , Handbook of Applied Cryptography, CRC Press, 2001, 780 p., http://www.cacr.math.uwaterloo.ca/hac/ Jan Paseka, Kódování, elektronický text, MU – http://www. math.muni.cz/~paseka/ftp/lectures/kodovani.ps. Pár slov o šifrách Plán přednášky 1 Pár slov o šifrách Pár slov o šifrách RSA 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ý SA Pár slov o šifrách RSA 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ý SA generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, ϕ(n) = (p − 1)(q − 1) [n je veřejné, ale ϕ(n) nelze snadno spočítat ] Pár slov o šifrách RSA 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ý SA generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, ϕ(n) = (p − 1)(q − 1) [n je veřejné, ale ϕ(n) nelze snadno spočítat ] zvolí veřejný klíč e a ověří, že (e, ϕ(n)) = 1 Pár slov o šifrách RSA 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ý SA generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, ϕ(n) = (p − 1)(q − 1) [n je veřejné, ale ϕ(n) nelze snadno spočítat ] zvolí veřejný klíč e a ověří, že (e, ϕ(n)) = 1 např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e · d ≡ 1 (mod ϕ(n)) Pár slov o šifrách RSA 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ý SA generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, ϕ(n) = (p − 1)(q − 1) [n je veřejné, ale ϕ(n) nelze snadno spočítat ] zvolí veřejný klíč e a ověří, že (e, ϕ(n)) = 1 např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e · d ≡ 1 (mod ϕ(n)) zašifrování numerického kódu zprávy M: C = Ce(M) ≡ Me (mod n) Pár slov o šifrách RSA 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ý SA generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, ϕ(n) = (p − 1)(q − 1) [n je veřejné, ale ϕ(n) nelze snadno spočítat ] zvolí veřejný klíč e a ověří, že (e, ϕ(n)) = 1 např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e · d ≡ 1 (mod ϕ(n)) 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ár slov o šifrách RSA 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ý SA generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, ϕ(n) = (p − 1)(q − 1) [n je veřejné, ale ϕ(n) nelze snadno spočítat ] zvolí veřejný klíč e a ověří, že (e, ϕ(n)) = 1 např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e · d ≡ 1 (mod ϕ(n)) 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ár slov o šifrách RSA 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ý SA generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, ϕ(n) = (p − 1)(q − 1) [n je veřejné, ale ϕ(n) nelze snadno spočítat ] zvolí veřejný klíč e a ověří, že (e, ϕ(n)) = 1 např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e · d ≡ 1 (mod ϕ(n)) 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) Důkaz. Fermatova, resp. Eulerova věta. Pár slov o šifrách Korektní naprogramování bez postranních kanálů není triviální (viz např. PKCS#1, RFC 3447). Analogicky podepisování (hashů) zpráv (viz např. DSA) Viz RSA factoring challenge (např. rozklad 212 ciferného čísla RSA-704 vynese 30 000 USD). Pár slov o šifrách Example Generování klíče. Alice vybere prvočísla p = 2357, q = 2551, and vypočte n = p · q = 6012707 a ϕ(n) = (p − 1)(q − 1) = 6007800. Alice zvolí e = 3674911 a pomocí Euklidova algoritmu vypočte d = 422191 (e · d ≡ 1 (mod ϕ(n))). Soukromý klíč Alice je d, veřejný pak (n, e). Pár slov o šifrách Example Generování klíče. Alice vybere prvočísla p = 2357, q = 2551, and vypočte n = p · q = 6012707 a ϕ(n) = (p − 1)(q − 1) = 6007800. Alice zvolí e = 3674911 a pomocí Euklidova algoritmu vypočte d = 422191 (e · d ≡ 1 (mod ϕ(n))). Soukromý klíč Alice je d, veřejný pak (n, e). Chce-li Bob poslat Alici zprávu m = 5234673, pomocí modulárního umocňování vypočte c ≡ me ≡ 52346733674911 ≡ 3650502 (mod n), a tu odešle Alici. Pár slov o šifrách Example Generování klíče. Alice vybere prvočísla p = 2357, q = 2551, and vypočte n = p · q = 6012707 a ϕ(n) = (p − 1)(q − 1) = 6007800. Alice zvolí e = 3674911 a pomocí Euklidova algoritmu vypočte d = 422191 (e · d ≡ 1 (mod ϕ(n))). Soukromý klíč Alice je d, veřejný pak (n, e). Chce-li Bob poslat Alici zprávu m = 5234673, pomocí modulárního umocňování vypočte c ≡ me ≡ 52346733674911 ≡ 3650502 (mod n), a tu odešle Alici. Alice zprávu dešifruje díky výpočtu cd ≡ 3650502422191 ≡ 5234673. Pár slov o šifrách Diffie-Hellman key exchange, ElGamal 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, . . . ). Pár slov o šifrách Diffie-Hellman key exchange, ElGamal 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 cyklické grupě G a jejím generátoru g (veřejné) Pár slov o šifrách Diffie-Hellman key exchange, ElGamal 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 cyklické grupě G a jejím generátoru g (veřejné) Alice vybere náhodné a a pošle ga Pár slov o šifrách Diffie-Hellman key exchange, ElGamal 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 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 Pár slov o šifrách Diffie-Hellman key exchange, ElGamal 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 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. Pár slov o šifrách Diffie-Hellman key exchange, ElGamal 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 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. Pár slov o šifrách Diffie-Hellman key exchange, ElGamal 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 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. Problém diskrétního logaritmu (DLP) Nezbytná autentizace (man in the middle attack) Pár slov o šifrách Z protokolu DH na výměnu klíčů odvozen šifrovací algoritmus ElGamal: Alice zvolí cyklickou grupu G spolu s generátorem g 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 C1 = gy a C2 = M · hy a pošle (C1, C2) dešifrování zprávy: OT = C2/Cx 1 Pár slov o šifrách Z protokolu DH na výměnu klíčů odvozen šifrovací algoritmus ElGamal: Alice zvolí cyklickou grupu G spolu s generátorem g 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 C1 = gy a C2 = M · hy a pošle (C1, C2) dešifrování zprávy: OT = C2/Cx 1 Opět lze odvodit podepisování. Pár slov o šifrách 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 . Pár slov o šifrách 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řívce (jen místo generátoru se vybere vhodný bod na křivce) ECDSA - digitální podpis pomocí eliptických křivek. Pár slov o šifrách 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řívce (jen místo generátoru se vybere vhodný bod na křivce) ECDSA - digitální podpis pomocí eliptických křivek. 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.