• Если n = p∙q, где р и q — простые числа, то ф(n) = (р — 1)(q — 1).
• Из малой теоремы Ферма мы знаем, что если а — целое число, большее нуля, и р — простое число, то ар-1 
1 (mod р).
• Согласно теореме Эйлера, если НОД (n, а) = 1, то аф(n) 1 (mod n).
Как уже упоминалось, система шифрования называется «с открытым ключом», потому что ключ шифрования доступен любому отправителю, желающему передавать сообщения. Каждый получатель имеет свой открытый ключ. Сообщения всегда передаются в виде цифр, будь то ASCII-коды или какая-либо другая система.
Сначала Джеймс вычисляет значение n путем умножения двух простых чисел р и q (n = pq) и выбирает значение е так, чтобы НОД (ф(n), е) = 1. Напомним, что ф(n) = (р — 1)(q — 1). Данные, которые являются открытыми, — это значение n и значение е (ни при каких обстоятельствах нельзя выдавать значения р и q). Пара (n, е) является открытым ключом системы, а значения р и q называются RSА-числами. Затем Джеймс вычисляет единственное значение d по модулю ф(n), которое удовлетворяет условию d∙е = 1, то естьd является обратным элементом к числу е по модулю ф(n). Мы знаем, что обратный элемент существует, потому что НОД (ф(n), е) = 1. Это число d является закрытым ключом системы. Со своей стороны, Питер использует открытый ключ (n, е) для шифрования сообщения М с помощью функции М = me (mod n). Получив сообщение, Джеймс вычисляет Md = (me)d (mod n), а это выражение эквивалентно Md = (me)d = m (mod n), что свидетельствует о возможности расшифровать сообщение.
Теперь мы применим эту процедуру к конкретным числовым значениям.
Если р = 3 и q = 11, получим n = 33. Тогда ф(33) = (3–1)∙(11—1) = 20.
Джеймс выбирает е, не имеющее общего делителя с 20, например, е = 7. Открытый ключ Джеймса (33,7).
• Джеймс также вычислил закрытый ключ d, который является обратным элементом к числу 7 по модулю 20, а именно число d = 3, так как 7∙3 1 (mod 20).
• Питер, имея открытый ключ, хочет отправить нам сообщение «9». Чтобы зашифровать это сообщение, он использует открытый ключ Джеймса и вычисляет:
97 = 4 782969 15 (mod 33).
Зашифрованное сообщение имеет вид «15». Питер посылает его нам.
Джеймс получает сообщение «15» и расшифровывает его следующим образом:
153 = 3375 9 (mod 33).
Сообщение расшифровано правильно.
Если мы выбираем большие простые числа р, q, то вычисления в алгоритме RSA становятся такими сложными, что нам придется использовать компьютер. Например, если р = 23 и q = 17, то n = 391. Открытым ключом при выбранном е = 3 будет пара (391,3). Тогда d = 235. Для простого сообщения «34» операция расшифровки будет выглядеть так:
204235 34 (mod 391).
Обратите внимание на степень числа и представьте себе гигантское количество расчетов, необходимых для нахождения этого решения.
Почему мы можем доверять алгоритму RSA
Потенциальный шпион располагает значениями n и е, потому что они являются открытыми. Чтобы расшифровать сообщение, ему нужно также значение d, т. е. закрытый ключ. Как мы показали в предыдущем примере, значение d получается из n и е. Чем же обусловлена безопасность? Напомним, что для построениям/ необходимо знать ф(n) = (р — 1)(q — 1), в частности, р и q. Для этого «достаточно» разложить n на простые множители р и q. Проблема для шпиона заключается в том, что разложение большого числа на простые множители является медленным и трудоемким процессом. Если n достаточно большое (состоящее более чем из 100 цифр), не существует известных способов нахождения р и q за разумное количество времени. В настоящее время простые числа, используемые для шифрования чрезвычайно конфиденциальных сообщений, состоят более чем из 200 цифр.
Алгоритм RSA требует много машинного времени и очень мощных процессоров.