Еще одно доказательство работы RSA

Пусть "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).