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

Š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á (a nemůže jej ani uhodnout). Pokud účastníci komunikace tento klíč mají, je bezpečnost jejich sdělování zaručena. 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í.

Představme si např. převod peněz. Aby byl zajištěn hladký transfer, potřebujeme šifrování. Obě zainteresované strany si potřebují vyměnit tajné náhodné číslo, takzvaný klíč. Jak se ale dohodnout na tajném klíči, zejména pokud se lidé neznají a nikdy nesetkali? A jak zabránit někomu dalšímu, aby nezískal kopii? Vysvětleme si to na příkladu barev. Obecně platí, že smíchat dvě barvy, aby vytvořily třetí barvu je snadné. Ovšem ze smíchané barvy je poté těžké zjistit, jaké byly barvy původní. Toto je princip zámku, který musí být lehce uzamykatelný, ale bez klíče těžko odemknutelný. V matematice se tomuto principu říká jednosměrná funkce.

Příklad pomocí barev

Na jedné straně stojí Jānis a na druhé Ilze. 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. Jānis si nechá svoji tajnou barvu a směs pošle Ilze (směs se dostane do rukou třetí strany). Ilze si také nechá svojí tajnou barvu a směs pošle Jānisovi (i tato směs se dostane ke třetí straně). Nyní Jānis a Ilze 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.

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

Externí odkazy

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

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í
  

Klíčová slova

šifrování, RSA, Public Key