Рассуждения, приводимые ниже, рассказывают о том, почему алгоритм шифрования 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».