Algoritmus RSA

Algoritmus RSA publikovali v roce 1978 Ronald Rivest, Adi Shamir a Leonard Adleman. Jedná se o asymetrickou šifru, která je založena na Eulerově větě, a která je použitelná jak pro šifrování, tak pro podepisování dokumentů.

Princip asymetrické kryptografie

Symetrické šifry, jako je například Caesarova šifra nebo exponenciální šifra, mají pouze jeden klíč, pomocí kterého se přenášená zpráva šifruje a inverzním postupem dešifruje. Asymetrické šifry mají klíče dva – soukromý a veřejný. Zatímco veřejný klíč jeho držitel oznámí celému světu, ten soukromý si pečlivě uschová.

Zároveň platí, že cokoliv, co je zašifrováno veřejným klíčem, lze rozšifrovat pouze odpovídajícím klíčem soukromým. Z opačné strany lze zprávy zašifrované soukromým klíčem rozšifrovat pouze příslušným veřejným klíčem.

Šifrování

Pokud tedy chceme poslat uživateli zprávu takovým způsobem, aby ji nikdo kromě nemohl přečíst, tak si seženeme jeho veřejný klíč $A_{vk}$ . Pomocí něj zprávu zašifrujeme a nakonec ji odešleme přes (nezabezpečenou) síť. Obsah zprávy zůstane všem případným útočníkům utajen, protože ji je schopen rozšifrovat pouze držitel odpovídajícího soukromého klíče – uživatel .

Digitální podpis

Druhým případem užití asymetrické kryptografie je digitální podpis. Představme si, že chceme vydat důležité prohlášení, ale nepřejeme si, aby s ním kdokoliv manipuloval a zároveň chceme, aby si každý mohl ověřit, že jsme jej skutečně napsali my (tzn. že se za nás nikdo nevydává).

V případě asymetrické kryptografie pouze zhotovíme hash (otisk zprávy), zašifrujeme jej svým soukromým klíčem a výsledný řetězec přiložíme ke zprávě. Tuto dvojici poté odešleme (samotná zpráva není nijak šifrována, aby si ji mohl kdokoliv přečíst). Každý, kdo si bude chtít ověřit, že je zpráva autentická, může dešifrovat otisk pomocí našeho veřejného klíče a porovnat jej s vlastnoručně vytvořeným otiskem příchozí zprávy. Pokud jsou otisky totožné, tak příjemce ví, že jsme zprávu napsali my, a že s ní nebylo nijak manipulováno.

Komunikace pomocí RSA

Mějme dva uživatele, říkejme jim a . Ukažme si, jakým způsobem musí postupovat, pokud spolu chtějí komunikovat pomocí RSA.

Výpočet klíčů

si zvolí dvě náhodná velká prvočísla $p_{a}$ a $q_{a}$ a jejich součin $p_{a} \\cdot q_{a}$ označí jako $n_{a}$ . Následně si zvolí číslo $e_{a}$ takové, že je nesoudělné s $\\varphi(n_{a}) = \\varphi(p_{a} \\cdot q_{a}) = (p_{a} - 1) \\cdot (q_{a} - 1)$ , kde $\\varphi(n)$ je hodnota Eulerovy funkce pro n (zároveň platí $e_{a} \\lt \\varphi(n_{a})$ ). Nakonec vypočítá číslo $d_{a}$ , které je multiplikativní inverzí čísla $e_{a}$ . Dvojici $(n_{a}, e_{a})$ zveřejní jakožto svůj veřejný klíč, dvojici $(n_{a}, d_{a})$ si ponechá – jedná se o soukromý klíč.

postupuje analogicky a vytvoří si také veřejný a soukromý klíč.

Šifrování a dešifrování

Pokud nyní bude chtít a poslat přirozené číslo (zprávu), tak jej zašifruje pomocí veřejného klíče $B_{vk}$ jako $x = z^{e_{b}} \\bmod (n_{b})$ . B přijatou zprávu dešifruje pomocí vzorce $z = x^{d_{b}} \\bmod (n_{b})$ .

Příklad

Monika a Karel spolu chtějí utajeně komunikovat a volí protokol RSA. Pro společnou komunikaci budou postupovat následujícím způsobem.

Výpočet klíčů

Monika

Monika volí náhodně dvě prvočísla, vypočte modulo a hodnotu Eulerovy funkce.

$p_{m} = 17$
$q_{m} = 19$

$n_{m} = 17 \\cdot 19 = 323$
$\\varphi(323) = \\varphi(17 \\cdot 19) = (17-1) \\cdot (19-1) = 288$

Nyní zvolí číslo $e_{m} = 37$ a pomocí rozšířeného Euklidova algoritmu spočítá jeho inverzi v $Z_{\\varphi(n_{m})}$ .

$d_{m} = 37^{-1} \\bmod (288) = 109 \\bmod (288)$

Monika nyní zveřejní svůj veřejný klíč (323, 37) . Soukromý klíč (323, 109) si ponechá.

Karel

Karel volí náhodně dvě prvočísla, vypočte modulo a hodnotu Eulerovy funkce.

$p_{k} = 7$
$q_{k} = 11$

$n_{k} = 7 \\cdot 11 = 77$
$\\varphi(77) = \\varphi(7 \\cdot 11) = (7-1) \\cdot (11-1) = 60$

Nyní zvolí číslo $e_{k} = 23$ a pomocí rozšířeného Euklidova algoritmu spočítá jeho inverzi v $Z_{\\varphi(n_{k})}$ .

$d_{k} = 23^{-1} \\bmod(60) = 47 \\bmod(60)$

Karel nyní zveřejní svůj veřejný klíč (77, 23) . Soukromý klíč (77, 47) si ponechá.

Komunikace

Karel chce nyní poslat Monice zprávu. Zprávou bude pro jednoduchost číslo 15.

Karel má přístup k veřejnému klíčí Moniky a zašifruje zprávu jako:

$x = 15^{37} \\bmod (323)$
x = 53

Zašifrovanou zprávu pošle Monice a ta ji rozšifruje pomocí svého soukromého klíče jako:

$z = 53^{109} \\bmod (323)$
z = 15

Útok na RSA hrubou silou

Nejjednodušším a nejméně efektivním útokem na RSA je útok hrubou silou, při kterém se útočník snaží prolomit pomocí faktorizace veřejný klíč uživatele.

Příklad

Prolomte veřejný klíč Moniky z předchozího příkladu tj. (323, 37) .

Víme, že se první část klíče dá rozložit na prvočísla.

323 % 3 = 2
323 % 5 = 3
323 % 7 = 1
323 % 11 = 4
323 % 13 = 11
323 % 17 = 0 => 323 = 19*17

Nyní již známe obě prvočísla, která Monika použila pro vytvoření svých klíčů, nyní již můžeme vypočítat soukromý klíč (viz výpočet klíče Moniky).

Poučení z útoku

Z tohoto útoku plyne poučení, že se nikdy nesmí volit velmi krátká prvočísla pro výpočet klíčů. V reálném světě se obvykle používají klíče dlouhé 1024-2048 bitů, které se již nedají žádnými prostředky faktorizovat (faktorizace čísla je velmi obtížný problém).

Literatura

VELEBIL, Jiří. Diskrétní matematika : Text k přednášce. Praha : [s.n.], 2007. 193 s.

Princip asymetrické kryptografie

Šifrování

Digitální podpis

Komunikace pomocí RSA

Výpočet klíčů

Šifrování a dešifrování

Příklad

Výpočet klíčů

Monika

Karel

Komunikace

Útok na RSA hrubou silou

Příklad

Poučení z útoku

Literatura

Doporučujeme