Криптосистема RSA была разработана в 1977 году и получила название в честь ее создателей: Рона Ривеста(Ron Rivest), Ади Шамира(Adi Shamir) и Леонарда Адлмана(Leonard Adleman). Они воспользовались тем фактом, что нахождение больших простых чисел в вычислительном отношении осуществляется легко, но разложение на множители произведения двух таких чисел практически невыполнимо. Доказано (теорема Рабина), что раскрытие шифра RSA эквивалентно такому разложению. Поэтому для любой длины ключа можно дать нижнюю оценку числа операций для раскрытия шифра, а с учетом производительности современных компьютеров оценить и необходимое на это время. Возможность гарантированно оценить защищенность алгоритма RSA стала одной из причин популярности этой криптосистемы на фоне десятков других схем. Поэтому алгоритм RSA используется в банковских компьютерных сетях, особенно для работы с удаленными клиентами (обслуживание кредитных карточек).
Безопасность RSA основана на трудности разложения на множители больших чисел. Открытый и закрытый ключи являются функциями двух больших (100-200 разрядов или даже больше) простых чисел. Предполагается, что восстановление открытого текста по шифротексту и открытому ключу эквивалентно разложению на множители двух больших чисел.

Для генерации двух ключей используются два больших случайных простых числа p и q. Для максимальной безопасности выбирайте p и q равной длины. Рассчитывается произведение:

n=p*q

Затем случайным образом выбирается ключ шифрования e, такой что e и (p-1)(q-1) являются взаимно простыми числами. Наконец расширенный алгоритм Евклида используется для вычисления ключа дешифрирования d, такого что

e*d=1mod(p-1)(q-1)

Заметим, что d и n также взаимно простые числа. Числа e и n - это открытый ключ, а число d - закрытый. Два простых числа p и q больше не нужны. Они должны быть отброшены, но не должны быть раскрыты.
Для шифрования сообщения m оно сначала разбивается на цифровые блоки, меньшие n (для двоичных данных выбирается самая большая степень числа 2, меньшая n). То есть, если p и q - 100-разрядные простые числа, то n будет содержать около 200 разрядов, и каждый блок сообщения mi должен быть около 200 разрядов в длину. (Если нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями слева, чтобы гарантировать, что блоки всегда будут меньше n. Зашифрованное сообщение c будет состоять из блоков ci той же самой длины. Формула шифрования выглядит так
.
Для расшифровки сообщения возьмите каждый зашифрованный блок c_i и вычислите

Шифрование RSA

Открытый ключ:
n произведение двух простых чисел p и q (p и q должны храниться в секрете)
e число, взаимно простое с (p-1)(q-1)
Закрытый ключ:
d e^-1 mod ((p-1)(q-1))
Шифрование:
c = m^e mod n
Дешифрирование:
m = c^d mod n

Точно также сообщение может быть зашифровано с помощью d, а расшифровано с помощью e, возможен любой выбор.
Короткий пример возможно поможет пояснить работу алгоритма.
Если p = 47 и q = 71, то n = pq = 3337.
Ключ e не должен иметь общих множителей (p-1)(q-1)= 46*70 =3220.
Выберем (случайно) e равным 79. В этом случае d = 79^-1 mod 3220 = 1019.
При вычислении этого числа использован расширенный алгоритм Эвклида. Опубликуем e и n, сохранив в секрете d. Отбросим p и q.
Для шифрования сообщения m = 6882326879666683 сначала разделим его на маленькие блоки. Для нашего случая подойдут трехбуквенные блоки. Сообщение разбивается на шесть блоков mi:
m_l = 688
m₂ = 232
m₃ = 687
m₄ = 966
m₅ = 668
m₆ = 003
Первый блок шифруется как 688⁷⁹ mod 3337 = 1570 = c_l.
Выполняя те же операции для последующих блоков, создает шифротекст сообщения:
c = 1570 2756 2091 2276 2423 158.
Для дешифрирования нужно выполнить такое же возведение в степень, используя ключ дешифрирования 1019: 1570¹⁰¹⁹ mod 3337 = 688 = m_l.
Аналогично восстанавливается оставшаяся часть сообщения.

Шифрование RSA выполняется намного быстрей, если вы правильно выберете значение e. Тремя наиболее частыми вариантами являются 3, 17 и 65537 (2¹⁶ + 1). (Двоичное представление 65537 содержит только две единицы, поэтому для возведения в степень нужно выполнить только 17 умножений.) Не существует никаких проблем безопасности, связанных с использованием в качестве e любого из этих трех значений (при условии, что вы дополняете сообщения случайными числами), даже если одно и то же значение e используется целой группой пользователей.
Операции с закрытым ключом можно ускорить при помощи китайской теоремы об остатках, если вы сохранили значения p и q, а также дополнительные значения: d mod (p-1), d mod (q-1) и q^-1 mod p. Эти дополнительные числа можно легко вычислить по закрытому и открытому ключам.