Пусть «n» и «e» — натуральные числа. Функция «f», реализующая RSA, устроена следующим образом:
f: x → xe(mod n) (1)
Для расшифровки сообщения достаточно решить сравнение:
xe = a(mod n) (2)
При некоторых условиях на «n» и «e» это сравнение имеет единственное решение «x». Для этого воспользуемся функцией Эйлера. Эта функция натурального аргумента «n» обозначается φ(n) и равняется количеству целых чисел на отрезке от 1 до «n», взаимно простых с «n». Так φ(1) = 1 и φ(pr) = pr-1(p-1) для любого простого числа «p» и натурального числа «r». Кроме того, φ(ab) = φ(a)φ(b) для любых натуральных взаимно простых чисел «a» и «b». Эти свойства позволяют легко вычислять значения φ(n), если известно разложение числа «n» на простые сомножители.
Если показатель степени «e» в (2) взаимно прост с φ(n), то (2) имеет единственное решение. Для того, чтобы его найти, определим целое число «d», удовлетворяющее условию:
de ≡ 1(mod φ(m)), 1 ≤ d ≤ φ(n) (3)
Такое число существует и оно единственное, т.к. (e, φ(n)) = 1. Классическая теорема Эйлера утверждает, что для каждого числа «x», взаимно простого с «n», выполняется сравнение: xφ(n) ≡ 1(mod n) и следовательно ad ≡ xed ≡ x(mod n).
Таким образом, единственное решение сравнения (2) может быть найдено в виде:
x ≡ ad(mod n) (4)
В RSA n = p*q, т.к. φ(n) = φ(p*q) = (p-1)(q-1) (5), то единственное условие на выбор показателя степени «e» в отображении (1) есть (e, p-1) = (e, q-1) = 1 (6).
В итоге: выбирается число «e», удовлетворяющее условиям (6), вычисляется с помощью (5) число φ(n) и с помощью (3) — число «d». Любой может зашифровать сообщение через (1), а расшифровать через (4).