Алгоритм RSA

Ади Шамиром и Леном Адлеманом и опубликован в 1978 году;
представляет

собой блочный алгоритм шифрования, где зашифрованные и незашифрованные данные являются целыми между 0 и n -1 для некоторого n;
основан на использовании того факта, что задача факторизации является трудной, т.е. легко перемножить два числа, в то время как не существует полиномиального алгоритма нахождения простых сомножителей большого числа.

и q;
вычислить n = p · q;
выбрать d gcd

(Φ(n), d) = 1; 1 < d < Φ(n);
вычислить е = d-1 mod Φ(n);
открытый ключ KU = {e, n};
закрытый ключ KR = {d, n};

n
зашифрованный текст: С = М е (mod n)

дешифрование:
зашифрованный текст: С

незашифрованный текст: М = Сd (mod n)

q = 17.
вычислить n = p · q = 7

· 17 = 119.
вычислить Φ(n) = (p - 1) · (q - 1) = 96.
выбрать е так, чтобы е было взаимно простым с Φ(n) = 96 и меньше, чем Φ(n): е = 5.
определить d так, чтобы d · e = 1 mod 96 и d < 96.
d = 77, так как 77 · 5 = 385 = 4 · 96 + 1.
результирующие ключи открытый KU = {5, 119} и закрытый KR = {77, 119}.
например, требуется зашифровать сообщение М = 19.
195 = 66 (mod 119); С = 66.
для дешифрования вычисляется 6677 (mod 119) = 19.