Про RSA c математической точки зрения

Рассуждения, приводимые ниже, рассказывают о том, почему алгоритм шифрования RSA, о котором я недавно писал, работает, и почему закрытый и открытый ключи являются взаимно обратными.

Шифруемый текст можно разбить на блоки "P", так, что 0 < P < n. Это можно сделать, если блоки будут по "k"-бит, где  "k" - максимально целое число, для которого 2^k < n.

Пусть имеется открытый ключ (n,e) и закрытый ключ (n,d). Нужно доказать, что для любого целого числа "b" (0 ≤ b ≤ n) выполняется тождество: D(E(b)) = b. Достаточным будет доказать даже следующее: D(E(b)) ≡ b(mod n).

Действительно, как "b", так и D(E(b)) - неотрицательные целые числа, которые меньше "n", поэтому они сравнимы по модулю "n" тогда и только тогда, когда они равны (это объясняет и то, почему блоки разбиваются на < n). Из "рецептов" шифрования и дешифрования следует, что:

D(E(b)) ≡ (be)d ≡ bed(mod n) (1)

Поскольку элементы "d" и "e" взаимно обратны по модулю φ(n), найдется также натуральное "k", что ed = 1 + kφ(n). Более того, по условию, числа "d" и "e" больше 2 и φ(n) > 0. Следовательно, k > 0. Подставляя  1 + kφ(n) вместо произведения "ed" в уравнение (1), получаем:

bed ≡ b1+kφ(n) ≡ (bφ(n))k b(mod n)

Теперь воспользуемся теоремой Эйлера, которая утверждает, что bφ(n) ≡ 1(mod n). Отсюда bed ≡ b(mod n), т.е.

D(E(b)) ≡ b(mod n)

Еще надо убедится в простоте чисел "b" и "n" (n = p*q). Определим вычеты числа bed по модулям "p" и "q". Мы уже убедились в том, что: ed = 1 + kφ(n) = 1 + k(p-1)(q-1) для некоторого целого k > 0. Следовательно:

bed ≡ b(b(p-1))k(q-1) (mod n)

Тогда по теореме Эйлера: b(p-1) ≡ 1(mod p), и получается bed ≡ b(mod p), и bed ≡ b(mod q). Другими словами, bed - "b" делится и на "p", и на "q", но НОД (p,q) = 1. Т.к. n = p*q, то bed ≡ b(mod n), т.е. D(E(b)) ≡ b(mod n).

Что и следовало доказать.

Источник: С.Коутинхо "Введение в теорию чисел алгоритма RSA".