RSA kryptografie veřejného klíče

Kryptosystém RSA (který v roce 1978 vymysleli Ronald Rivest, Adi Shamir a Leonard Adlemann) je založen na problému faktorizace velkých čísel. Podívejme se na to, jak tento systém řeší přenos zprávy mezi dvěma místy. Nejprve musí přijímající strana (v tomto případě Bob) vygenerovat pár klíčů, z nichž jeden je tzv. veřejný klíč, který je k dispozici všem a Bob jej sdělí veřejným kanálem Alici. Alice tímto klíčem zprávu zašifruje (tuto část komunikace může provést kdokoliv). V této chvíli přichází na řadu druhý klíč - privátní, který Bob nikomu nesdělil. Alice pošle zašifrovanou zprávu Bobovi, který si ji svým privátním klíčem dešifruje. Aby to však bylo možné, je nutné, aby byly oba klíčem určitým způsobem propojeny. Pojďme se teď na toto spojení podívat podrobněji. Aby byl RSA systém bezpečný, musí být těžké na základě znalosti veřejného klíče a zašifrované zprávy od Alice zjistit otevřenou hodnotu zprávy (to také znamená, že ze znalosti těchto hodnot musí být těžké zjistit klíč privátní). Toho RSA dociluje tím, že spoléhá na neschůdnost faktorizace velkých celých čísel. Řekněme, že Bob chce komunikovat s Alicí. Konkrétní postup při komunikaci se skládá jednak z části generování klíče (první tři body) a části komunikační:

• Bob si nejdříve vybere dvě dostatečně velká prvočísla $p$ a $q$, která vynásobí a získá číslo $n = p\cdot q$.
• Poté začne počítat dvě celá čísla $d$ a $e$ tak, že za $e$ si zvolí náhodné číslo, které je nesoudělné s číslem $(p - 1)(q - 1)$. Dále musí vypočítat $d$ z výrazu $e d \equiv 1\ \mathrm {mod}\ (p - 1)(q - 1)$.
• Následuje zaslání veřejného klíče Alici jako páru čísel {$e, n$}.
• Vytvoření zprávy $M \in {\mathbb{Z}}_n$.
• Nyní Alice zašifruje zprávu pomocí veřejného klíče jako $C = M^e\ \mathrm {mod}\ n$.
• Tu pak zašle Bobovi, který na základě znalosti svého utajeného privátního klíče dešifruje jako $M = C^d\ \mathrm {mod}\ n$ a potom převede zpět do textové podoby.

Ukažme si celou proceduru na vysvětlujícím příkladu:
Bob si například zvolí $p = 11$ a $q = 13$, dále je $n = p\cdot q = 143$. Jestliže si za $e$ zvolí například číslo 7 (nesoudělné s $(p - 1)(q - 1)$ a zároveň menší než toto číslo), pak z rovnice $d\cdot 7 \equiv 1\ \mathrm {mod}\ 120$ je $d = 103$. Tím má Bob k zaslání připraven veřejný klíč (7, 143) a k uschování privátní klíč (103, 143). Veřejným klíčem Alice zašifruje třeba písmeno x, které je v našem číselném kódu rovno řekněme 16. Takže je pak $C_p = 16^7\mathrm {mod}\ 143 = 3$. To si Bob dešifruje jako $M = 3^{103}\mathrm {mod}\ 143 = 16$, tj. kód písmene x. Pro velká čísla nepřipadá prolomení hrubou silou v úvahu, protože k tomu by bylo potřeba zjistit $p$ a $q$. Pak by byl již výpočet $d$ jednoduchý. Jako bezpečné se dnes obvykle uvažuje použití $n$ v délce 1024 bitů, sestavené ze dvou prvočísel přibližně poloviční délky.