Š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 položili základy asymetrického šifrování s diskrétním algoritmem. 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íčů. Problém diskrétního algoritmu je 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 i 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, podíváme se tedy i na příklad s čísli. Základem šifrování klíčů je modulární aritmetika. Základní věta aritmetiky je založena na rozkládání čísla na prvočísla, všechna čísla jakkoliv velká se dají rozkládat dokud nenarazíme na prvočíslo. Jinými slovy, všechna čísla se dají vyjádřit několika prvočísli, které představují základní stavební bloky. Alice a Bob se domluví na společném klíči, který je prvočíslem (modulus) 17. Z čísla 17 máme primitivní kořen (prvočíslo) 3, kterému se říká generátor. Alice si vybere svůj tajný klíč 15 a provede výpočet g^x mod p tj. 3¹⁵ mod 17. Výsledkem je číslo 6, které veřejně pošle Bobovi. Bob si vybere také svůj tajný klíč 13 a provede stejný výpočet 3¹³ mod 17. Výsledek je 12 a pošle ho veřejně zpět Alici. Alice vezme Bobův veřejný klíč 12 aumocní ho svým tajným číslem ( 12<sep>15</sep> mod 17 = 10 ). Bob udělá to samé s Aliciným veřejným klíčem ( 6<sep>13</sep> mod 17 = 10 ). Oba získávají sdílený tajný klíč. Pokud další strana nemá privátní klíče Boba a Alice, tak se k výsledku 10 nijak nedostane, tato malá čísla byla pouze na ukázku, ale v praxi dešifrovat modulus se stovkami cifer je prakticky nemožné.

Metoda RSA

Historie RSA

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