Algoritmus RSA publikovali v roce 1977 Ronald Rivest, Adi Shamir a Leonard Adleman.
Problém faktorizace čísel
Máme dvě velká prvočísla p a q, pro které snadno vypočítáme jejich součin n = pq. Pokud však známe pouze složené číslo n, pak je výpočetně náročné nalézt oba jeho faktory p a q, pokud jsou vhodně zvoleny.
Konstrukce RSA
Konstrukce RSA se provádí následujícím algoritmem:
- Zvolíme si dvě prvočísla p a q, které budou dostatečně velké a spočítáme z nich modul m = (pq) a číslo v = φ(p·q) = (p - 1)(q - 1) (φ je eulerova funkce).
- Zvolíme celé číslo e ∈ (0, m), sloužící jako veřejný exponent. Toto číslo musí být nesoudělné s číslem v.
- Vypočítá soukromý exponent d ≡ e-1 mod v.
- Dvojice VK = (e, m) je veřejný klíč adresáta a dvojice SK = (d, m) je soukromý klíč adresáta.
Šifrování zprávy M, která se převede na číslo m poté probíhá jako: c ≡ me mod m kde c je výsledná šifrovaná zpráva. Dešifrování poté probíhá obdobně: m ≡ cd mod m.
Bezpečnost
V srpnu 1977 časopis Scientific American1 vyzval své čtenáře. Pro výhru sta dolarů stačilo rozluštit tajnou zprávu. Znělo to bezpečně: podle odhadu, nemohl ani nejrychlejší možný počítač s pomocí nejúčinnějšího známého algoritmu získat výhru, i přesto, že by běžel bez přerušení milionkrát delší dobou než je stáří vesmíru. Navzdory tomu, by o šestnáct let později stači osm měsíců výpočtu.
--