Šifrování s veřejným klíčem (metoda RSA)

Kryptografie je nauka o metodách utajování významu přenášených zpráv. Tato nauka je někdy nazývána jako šifrování jelikož používá tzv. šifrování dat, což je proces, během kterého se nezabezpečená data převádí na data šifrovaná (zabezpečená), která dokáže dešifrovat jen majitel dešifrovacího klíče. Výsledný nesrozumitelný text, vzniklý pomocí šifrovacího algoritmu se nazývá šifra. Kryptografie patří společně s kryptoanalýzou (luštění šifrovaných zpráv) pod obor kryptologie.

Symetrické vs. asymetrické šifrování

Pod pojmem šifrování si mohou lidé po celém světě představit takovou komunikaci, kdy si dva nebo více osob posílají tajné zprávy, které lze přečíst jen pomocí zvláštního klíče, který všichni zúčastnění znají a nikdo zvenčí jej nezná (nemůže jej ani uhodnout). Takto funguje symetrická kryptografie, která k zašifrování i rozluštění zprávy používá tentýž klíč. Jak si ale účastníci tajný klíč předají? Distribuce klíčů se musí provádět na jiném principu. Šifrování zpráv navíc nemusí mít za cíl pouze udržet nějakou informaci v tajnosti, může také zajišťovat ověření totožnosti osob, např. u digitálních podpisů. Těmto účelům slouží asymetrická kryptografie, ve které se pro zašifrování používá jiný klíč než pro luštění.

Symetrické šifrování

Princip asymetrické metody šifrování zpráv tkví v jednom jediném klíči, který slouží k šifrování i dešifrování zpráv. Tzn. že se šifra dešifruje stejným postupem (akorát zpětným) jako byla zašifrována. Tento způsob šifrování se objevil již v dobách Julia Caesara, který používal jako princip šifrování posun o 3 písmena v abecedě. Dnes je tato metoda známá jako Caesarova šifra a je velice jednoduché ji prolomit, jelikož je zde pouze 26 možností (jako je písmen v abecedě, abychom se nedostali zpět na písmenko, které chceme šifrovat). Další symetrická šifra je tzv. Polyalfabetická šifra, která pochází z 15. století, nebo Vernamova šifra z 19. století, která jako první obsahuje princip náhody, stejně jako kdybychom házeli kostkou a hozená čísla bychom si zapisovali jako seznam náhodných posunů, který by byl následně zaslán protistraně jako společný klíč. Tato šifra se považuje za bezpečnou, jelikož se v ní posuny neopakují, nedají se předvídat a výskyt písmen je rovnoměrný.

Asymetrické šifrování

až do 70. let 20. století bylo šifrování založeno na symetrických klíčích. Ovšem postupem času vznikla potřeba komunikovat s více lidmi (např. bankovní účty) a po zavedení internetové sítě také potřeba šifrování dvou stran, které se dohodnou na společném klíči aniž by klíč mohl uniknout jakoukoliv cestou k nějaké třetí nezúčastněné straně. Nad tímto problémem se zamysleli W. Diffie a M. Hellman v roce 1976 a přišli na způsob asymetrického šifrování s diskrétním algoritmem. Bezpečnost algoritmu tkví v tom, že je jednoduché zprávu zašifrovat, ale dešifrovat ji zpět je velice náročné, neplatí zde princip dešifrování stejným klíčem, kterým je zpráva zašifrována. Metoda, která obsahuje princip asymetrického šifrování se nazývá Šifrování s veřejným klíčem.

Šifrování s veřejným klíčem

Diffieho-Hellmanova výměna klíčů znázorněna pomocí míchání barev

Příklad pomocí barev

Na jedné straně stojí Alice a na druhé Bob. Veřejně se dohodnou na počáteční barvě, např. žluté (tuhle barvu zná tudíž i třetí strana, která chce získat jejich komunikaci). Pak si oba náhodně zvolí svoji vlastní utajenou barvu, kterou přimíchají do žluté. Tím zamaskují jejich soukromé zprávy. Alice si nechá svoji tajnou barvu a směs pošle Bobovi (směs se dostane do rukou třetí strany). Bob si také nechá svojí tajnou barvu a směs pošle Alici (i tato směs se dostane ke třetí straně). Nyní Alice a Bob přidají své soukromé barvy do směsi toho druhého. Vznikne společná tajná barva. Třetí strana nemůže určit barvu, protože k tomu potřebuje jednu ze soukromých barev. Aby se toto dalo udělat s čísly, potřebujeme takovou číselnou operaci, která se dělá snadno v jednom směru, ale obtížně v druhém.

S barvami to zní jednoduše, pokud chceme šifrování veřejným klíčem pochopit do hloubky, je lepší se podívat i na příklad s čísli.

Metoda RSA

Historie RSA

Až do 70.let minulého století bylo šifrování založeno na symetrických klíčích. V roce 1976 Whitfield Diffie a Martin Hellman položili základy asymetrického šifrování. V článku New Directions in Cryptography řešili problém distribuce klíčů a protokol, který v článku popisují se jmenuje Diffieho-Helllmanova výměna klíčů.

V roce 1970 britský matematik a technik James Ellis pracoval s myšlenkou neutajené šifry. Je založena na jednoduchém, a přesto chytrém konceptu. Uzamknutí a odemčení jsou inverzní operace. Jānis by mohl koupit zámek, ponechat si klíč a otevřený zámek poslat Ilze. Ona svoji zprávu poté uzamkne a pošle jí zpět majiteli. Vše probíhá bez výměny klíčů. To znamená, že by zámek mohl veřejně nabídnou komukoliv, aby mu díky zámku mohl poslat zprávu. Nicméně James Ellis nikdy nepřišel na matematické řešení. Jeho myšlenka je dále rozdělena na klíče dešifrovací a šifrovací. Dešifrovací klíč provádí inverzní operaci (vrací zpět operaci provedenou šifrovacím klíčem). Řešení nalezl jiný britský matematik Clifford Cocks, který objevil algoritmus, který byl okamžitě utajen po jeho zveřejnění.

Nicméně byl znovu objeven v roce 1977 Ronem Rivestem, Adi Shamirem a Leonardem Adlemanem. Vznikl tak algoritmus RSA pojmenovanný podle jmen jeho tvůrců. RSA je jedním z nejrozšířenějších algoritmů na světě využívající veřejný klíč. Každý uživatel internetu používá RSA nebo jeho variantu, aniž by jsi to uvědomoval. Jeho síla spočívá hlavně v obtížnosti prvočíselného rozpadu.

Tvorba klíčového páru RSA

1. Zvolíme dvě různá náhodná prvočísla p a q
2. Spočítá jejich součin n = p*q
3. Spočítá hodnotu Eulerovy funkce φ(n) = (p − 1)(q − 1)
4. Zvolíme celé liché číslo e menší než φ(n), které je s φ(n) nesoudělné
5. Nalezne číslo d tak, aby platilo de ≡ 1 (mod φ(n)), kde symbol ≡ značí kongruenci zbytkových tříd
6. Jestli e je prvočíslo, tak d = (1+r*φ(n))/e, kde r = [(e-1)φ(n)^(e-2)]
   

Příklad

Ilze vytvoří zprávu, kterou přemění na číslo m. Určí mu hodnotu m = 89

Jānis vytvoří náhodně dvě čísla: p = 53 a q = 59. Spočítá jejich součin n = 3127 a hodnotu Eulerovy věty φ(n) = 3016.

Nyní zvolí jakékoliv liché celé číslo, které nesmí mít společného dělitele s φ(n) a vybere e = 3. Nakonec musí najít hodnotu soukromého exponentu d, který vypočítá následovně [(2*3016+1)/3] = 2011. Hodnoty n a e, které jsou veřejné, odešle Ilze.

Ta vypočítá hodnotu c a zašifruje zprávu m. Šifruj(89) = 89³ mod 3127 = 1394. Výsledek odešle zpět Jānisovi.

Ten jí dešifruje následovně: Dešifruj (1394) = 1394²⁰¹¹ mod 3127 = 89.

Odkazy

Doporučená literatura

• KINSKÝ, Jindřich. Kódování jako ochrana přenášených informací = Cryptology as a method of data protection. Praha, 2010-05-20. 56 s., 6 s. příl. Bakalářská práce (Bc.). Univerzita Karlova v Praze, Filozofická fakulta, Ústav informačních studií a knihovnictví. Vedoucí bakalářské práce Vladimír Smetáček
  

Související články

• Symetrická kryptografie
  
• Asymetrická kryptografie
  
• Asymetrické šifrování
  
• Historický vývoj kryptografie v období světových válek
  
• Informační bezpečnost - její klíčové aspekty, hrozby a minimalizace rizika
  

Klíčová slova

šifrování, RSA, Public Key