Popíšeme stručně, na čem je založen algoritmus RSA, který se používá pro bezpečné elektronické podepisování dokumentů.
Nejprve se zvolí dvě dosti velká (např. 1024 bitů dlouhá) prvočísla p a q, navzájem různá. Vypočte se jejich součin N = pq a hodnota Eulerovy funkce φ(N) = (p−1)(q−1).
Multiplikativní cyklická grupa ZN je řádu φ(N), tzn. má tolik prvků. Jejími prvky jsou všechna čísla od 1 do N−1 nesoudělná s N. Protože je ZN cyklická, má generátor g. Jinými slovy libovolný prvek této grupy lze zapsat ve tvaru gkpro vhodné celé číslo k. Také platí, že umocněním libovolného prvku této grupy na její řád dostaneme jedničku, tedy xφ(N) = 1.
Dále se volí soukromý exponent d nesoudělný s hodnotou φ(N) a pomocí Euklidova algoritmu se dopočítá veřejný exponent e, splňující de ≡ 1 mod φ(N), tzn. de = 1 + kφ(N) pro nějaké celé číslo k. Tím máme vše připraveno. Prvočísla p, q můžeme zapomenout. Dvojici (d, N) nazveme soukromým klíčem a dvojici (e, N) klíčem veřejným, který vystavíme na internetu.
Nyní nám chce Alice poslat zprávu zakódovanou jako číslo m < N. Protože jde o důvěrné psaní, zašifruje pomocí našeho veřejného klíče; vypočte me mod N a výsledek nám pošle. Tuto zprávu jsme schopni dešifrovat pouze my, neboť známe soukromý exponent d. Umocněním přijatého čísla dostaneme (me)d mod N = mde mod N = m1 + kφ(N) = m⋅(mφ(N))k = m⋅1k = m.
Druhou situací je, když chceme Alici poslat dopis a potřebujeme zajistit, aby nám uvěřila, že jsme to byli skutečně my, a ne někdo jiný, kdo dopis psal. Zprávu m tentokrát umocníme naším soukromým exponentem, získáme md mod Na výsledek jí pošleme. Alice vezme zprávu a náš veřejný exponent e a umocní (md)e mod N. Výpočet probíhá úplně stejně, čili na konci dostane opět m. Nikdo jiný zprávu napsat nemohl, neboť nikdo jiný nemá k dispozici číslo d.
Bezpečnost této procedury visí na faktu, že není znám rychlý algoritmus, který by dokázal faktorizovat velká čísla. Nikdo tedy není schopen z čísla N získat zpětně prvočísla p, q a dále dopočítat φ(N) a konečně i soukromý exponentd. To je důvod, proč jsme na začátku celé procedury volili prvočísla tak velká. Malá čísla se totiž faktorizují o poznání rychleji.
Ve skutečnosti vstupuje do hry ještě certifikační autorita, která svým soukromým klíčem podepíše náš veřejný klíč, a tím potvrdí, že je to skutečně náš klíč, ke kterému máme soukromý klíč.
Algoritmus vymysleli pánové Rivest, Shamir, Adleman (odtud RSA) v roce 1977 a registrován je jako americký patent #4405829.
