RSA (iniciály autorů Rivest, Shamir, Adleman) je šifra s veřejným klíčem, jedná se o první algoritmus, který je vhodný jak pro podepisování, tak šifrování. Používá se i dnes, přičemž při dostatečné délce klíče je považován za bezpečný.

Princip

Bezpečnost RSA je postavena na předpokladu, že rozložit velké číslo na součin prvočísel (faktorizace) je velmi obtížná úloha. Z čísla ${\displaystyle n=pq}$ je tedy v rozumném čase prakticky nemožné zjistit činitele ${\displaystyle p}$ a ${\displaystyle q}$, neboť není znám žádný algoritmus faktorizace, který by pracoval v polynomiálním čase vůči velikosti binárního zápisu čísla ${\displaystyle n}$. Naproti tomu násobení dvou velkých čísel je elementární úloha.

Popis činnosti algoritmu

Alice a Bob chtějí komunikovat prostřednictvím otevřeného (nezabezpečeného) kanálu a Bob by chtěl Alici poslat soukromou zprávu.

Tvorba klíčového páru

Nejprve si bude Alice muset vyrobit pár veřejného a soukromého klíče:

1. Zvolí dvě různá velká náhodná prvočísla ${\displaystyle p}$ a ${\displaystyle q}$.
2. Spočítá jejich součin ${\displaystyle n=pq}$.
3. Spočítá hodnotu Eulerovy funkce ${\displaystyle \varphi (n)=(p-1)(q-1)}$.
4. Zvolí celé číslo ${\displaystyle e}$ menší než ${\displaystyle \varphi (n)}$, které je s ${\displaystyle \varphi (n)}$ nesoudělné.
5. Nalezne číslo ${\displaystyle d}$ tak, aby platilo ${\displaystyle de\equiv 1{\pmod {\varphi (n)}}}$, kde symbol ${\displaystyle \equiv }$ značí kongruenci zbytkových tříd.
6. Jestli ${\displaystyle e}$ je prvočíslo, tak ${\displaystyle d={\frac {1+r\cdot \varphi (n)}{e}}}$, kde ${\displaystyle r=(e-1)\varphi (n)^{e-2}}$

Veřejným klíčem je dvojice ${\displaystyle (n,e)}$, přičemž ${\displaystyle n}$ se označuje jako modul, ${\displaystyle e}$ jako šifrovací či veřejný exponent. Soukromým klíčem je dvojice ${\displaystyle (n,d)}$, kde ${\displaystyle d}$ se označuje jako dešifrovací či soukromý exponent. V praxi se klíče uchovávají v mírně upravené formě, která umožňuje rychlejší zpracování. Veřejný klíč poté Alice uveřejní, respektive zcela otevřeně pošle Bobovi. Soukromý klíč naopak uchová v tajnosti.

V bodě 5 je použit rozšířený Eukleidův algoritmus na ${\displaystyle e}$ a ${\displaystyle \varphi (n)}$, čímž nalezneme ${\displaystyle d}$ a ${\displaystyle c}$ do rovnice ${\displaystyle de+c\varphi (n)=1}$.

Zašifrování zprávy

Bob nyní chce Alici zaslat zprávu ${\displaystyle M}$. Tuto zprávu převede nějakým dohodnutým postupem na číslo ${\displaystyle m}$ (${\displaystyle m<n}$). Šifrovým textem odpovídajícím této zprávě pak je číslo

${\displaystyle c=m^{e}\mod n}$

Tento šifrový text poté zašle nezabezpečeným kanálem Alici.

Dešifrování zprávy

Alice od Boba získá šifrovaný text ${\displaystyle c}$. Původní zprávu ${\displaystyle m}$ získá následujícím výpočtem:

${\displaystyle m=c^{d}\mod n}$

Fakt, že je výsledek tohoto výpočtu původní zprávou, je důsledek následující rovnosti:

${\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m{\pmod {n}}}$

A jelikož ${\displaystyle ed\equiv 1{\pmod {p-1}}}$ a ${\displaystyle ed\equiv 1{\pmod {q-1}}}$, díky malé Fermatově větě platí, že

${\displaystyle (m^{e})^{d}\equiv m^{1+c(p-1)}\equiv m^{1}(m^{p-1})^{c}\equiv m\cdot 1^{c}\equiv m{\pmod {p}}}$

a zároveň

${\displaystyle (m^{e})^{d}\equiv m{\pmod {q}}}$

Jelikož ${\displaystyle p}$ a ${\displaystyle q}$ jsou různá prvočísla, pomocí čínské věty o zbytcích je dáno

${\displaystyle (m^{e})^{d}\equiv m{\pmod {pq}}}$

Tudíž

${\displaystyle c^{d}\equiv m{\pmod {n}}}$

Hodnoty ${\displaystyle m{\pmod {p}}}$ ani $$Zdroj:https://cs.wikipedia.org?pojem=RSA
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.