Asymetrická kryptografie

Asymetrická kryptografie Ing. Jan Přichystal, Ph.D. PEF MZLU v Brně

12. listopadu 2007

Ing. Jan Přichystal, Ph.D.

Asymetrická kryptografie

Problém výměny klíčů

Problém výměny klíčů mezi odesílatelem a příjemcem zprávy trápil kryptografy po několik století. Problém spočívá ve výměně tajné informace tak, aby ji nikdo třetí nebyl schopen odposlechnout. Pro distribuci klíčů se využívaly služby kurýrů ⇒ logistický problém. Neřešitelnou situace začínala být v případě elektronické komunikace, elektronického obchodování. Situaci příliš neřešil ani systém Diffie-Hellman-Merkle



Asymetrická kryptografie V roce 1975 načrtl Whitfield Diffie myšlenku asymetrické kryptografie. Skupina kryptografických metod, ve kterých se pro šifrování a dešifrování používají odlišné klíče. Základem jsou jednosměrné funkce, které umožní původní zprávu zašifrovat pomocí veřejného klíče, ale již nikoliv dešifrovat za pomocí téhož klíče. Pro dešifrování zpráv se použije klíč soukromý, který má uschovaný příjemce zprávy. Každý, kdo chce šifrovat zprávy s použitím asymetrických metod, si vytvoří pár klíčů (soukromý a veřejný). Veřejný klíč distribuuje po mezi všechny osoby, se kterými chce komunikovat a klíč soukromý si uchová u sebe v tajnosti.



Analogie se zámky

Alice navrhne zámek a jeho kopie distribuuje po celém světě, klíč si ponechá. Bob uloží tajnou zprávu do krabice, na které zaklapne Alicin zámek, a pošle ji zpět Alici poštou. Alice si vyzvedne krabici a odemkne ji svým klíčem.



Základní principy

Šifrovací klíč sestává ze dvou částí: Veřejný klíč – používá se pro zašifrování zprávy, je veřejně dostupný. Soukromý klíč – používá se pro dešifrování zprávy, je vlastníkem pečlivě uschován. Tím je vyřešen základní problém distribuce klíčů, není třeba sdílet žádné veřejné tajemství a komunikace může probíhat asynchronně. Používá se nejen pro šifrování zpráv, ale i pro jejich podepisování (ověření původu).



RSA – Rivest, Shamir, Adelman V podstatě první použitelná asymetrická metoda. Založena na myšlence publikované W. Diffiem. Vznik roku 1977, dva roky po uveřejnění základního principu. Tvůrci – výzkumníci laboratoře počítačových věd MIT. Algoritmus byl v USA v roce 1983 patentován jako patent č. 4 405 829. Patent vypršel 21. 9. 2000.



Tvorba klíčového páru Zvolí se dvě velká náhodná prvočísla p, q. Určí se jejich součin n = p × q Spočítá se hodnota Eulerovy funkce φ(n) = (p − 1)(q − 1) Zvolí se číslo e ∈ (max{p + 1, q + 1}; φ(n)), které je s φ(n) nesoudělné. Nalezne se číslo d aby platilo: de ≡ 1( mod φ(n)) Pokud d vyjde příliš malé (tedy menší než asi log2 (n)), zvolíme jinou dvojici e a d. Ing. Jan Přichystal, Ph.D.


Tvorba klíčového páru

Veřejným klíčem je pak dvojice (n, e), kde n je modul a e je šifrovací exponent Soukromým klíčem je dvojice (n, d), kde d se označuje jako dešifrovací či soukromý exponent. V praxi se klíče uchovávají v mírně upravené formě, která umožňují rychlejší zpracování.



Šifrování zprávy

Bob nyní chce Alici zaslat zprávu M. Zpráva je převede na číslo m. Šifrovým textem odpovídajícím této zprávě pak je číslo c = me ( mod n) Tento šifrový text poté zašle nezabezpečeným kanálem Alici.



Dešifrování zprávy

Alice od Boba získá šifrový text c. Původní zprávu m získá následujícím výpočtem: m = c d ( mod n)



Důkaz možnosti dešifrování I.

Vycházíme z následujících předpokladů definovaných Eulerem: i φ(n) Me

d

mod n = 1 mod n = M

Čísla i a n jsou nesoudělné, M a n jsou nesoudělné.



Důkaz možnosti dešifrování II.

f1 : Me

mod n = C

Cd

mod n = M

f2 :

f2 (f1 (M)) = f2 (M e mod n) = (M e mod n)d mod n = d = M e mod n = M k·φ(n)+1 mod n = M × M k·φ(n) mod n = = M × 1 mod n = M



Příklad

p = 61 (první prvočíslo) q = 53 (druhé prvočíslo) n = p × q = 3233 (modul, veřejný) e = 17 (veřejný, šifrovací exponent) d = 2753 (soukromý, dešifrovací exponent)



Příklad – pokračování

Pro zašifrování zprávy 123 probíhá výpočet: šifruj(123) = 12317 ( mod 3233) = 855 Pro dešifrování pak: dešifruj(855) = 8552753 ( mod 3233) = 123



Bezpečnost RSA

Zabezpečení algoritmu RSA závisí na následujících faktorech: Zabezpečení toho, že čísla p a q zůstanou utajena. Pokud tato čísla odhalíme, je odvození dešifrovacího klíče d ze šifrovacího klíče e triviální záležitost. Obtížnost rozkladu součinu n na prvočísla. V případě, že bychom mohli rozložit číslo n, můžeme získat čísla p a q a tím i dešifrovací klíč. Na nedostatku jiných algebraických technik pro odvození dešifrovacího klíče d ze šifrovacího klíče e a čísla n.



Bezpečnost RSA

RSA je bezpečný jestliže n je dostatečně velké. Jestliže n je 256 bitů nebo kratší, může být za pár hodin faktorizován na osobním počítači, za použití volně dostupného software. Jestliže n je 512 bitů nebo kratší, může být faktorizován několika sty počítačů. Běžně se používá klíč o délce 1024–2048 bitů. V roce 1977 uveřejnil Martin Gardner v časopise Scientific American článek o RSA, který obsahoval zprávu zašifrovanou touto metodou. V roce 1994 byla tato zpráva dešifrována spojeným úsilím více než 1600 stanic z celého světa. RSA-129 byla prolomena.



Rychlost

Asymetrická kryptografie je o hodně pomalejší než symetrická. V praxi se typicky zašifruje tajná zpráva symetrickým algoritmem, šifrování a následně se přenese symetrický klíč i symetricky šifrovaná zpráva příjemci. Tento způsob šifrování se označuje jako hybridní.



Útoky na RSA

Narušení bezpečnosti lze realizovat různými technikami: Útok na rozklad – pokusit se faktorizovat číslo n. Útok na prvočísla – pokusit se napodobit chod generátoru prvočísel. Útok matematickou teorií – objevit nové principy matematiky, které by odhalily zásadní trhliny v RSA nebo objevit ultrarychlý způsob rozkladu velkých čísel.



Alternativní historie AK

Podle informací britské vlády byla asymetrická kryptografie objevena v britské tajné instituci GHCQ. Práce na této technologii zahájil v roce 1965 James Ellis, který načrtl základní principy. Roku 1973 byl do GHCQ přijat nový pracovník Clifford Cocks, který navrhl reálný systém AK. Z důvodů utajení nebyl tento objev veřejně publikován a byl odhalen až několik let po uvedení RSA.



PGP – Pretty Good Privacy V době uvedení RSA na trh nebyl pro běžné uživatele k dispozici výpočetní výkon dostačující k běžnému použití asymetrické kryptografie. Phil Zimmerman se rozhodl umožnit použití bezpečné kryptografie širokým masám lidí po celém světě. První verze PGP byla umístěna na veřejnou síť Usenet v roce 1991. Umožňuje i laikům velmi jednoduchým způsobem používat silné a bezpečné šifrování a podepisování zpráv. Je založeno na algoritmech RSA a IDEA. Později bylo PGP standardizováno. V dnešní době existují nekomerční verze (OpenPGP, GnuPG . . . )



Soukromí pro všechny? Za svou činnost se Phil Zimmerman stal podezřelým z nelegálního vývozu zbraní a byl v souvislosti s tím vyšetřován. Podle amerických zákonů platných v 90. letech nemělo být umožněno okolním státům používat metody silného šifrování. Diskutovala se otázka, zda je přípustné aby k těmto moderním technologiím měl přístup opravdu každý. Vlády všech zemí (USA nevyjímaje) prosazují politiku Velkého bratra pro kontrolu komunikace obyvatel z důvodu zajištění jejich bezpečnosti.

Je to ovšem potřeba? Ing. Jan Přichystal, Ph.D.


Závěr

Děkuji za pozornost Dotazy?



Asymetrická kryptografie

Recommend Documents