Основное
Вспомогательная страница к разделу ☞ КРИПТОГРАФИЯ.
Теорема. При числе $ \mathbf E $, выбранном по алгоритму RSA, сравнение
$$ x^{\mathbf E} \equiv c \pmod{M} $$ имеет единственное решение, которое может быть найдено по формуле $$ x=c^{\mathbf D} \pmod{M} \, .$$
Доказательство. Покажем, что пара $ \mathbf E $ и $ \mathbf D $, построенная по алгоритму RSA, обладает свойством обратимости: $$ \left(x^{\mathbf E} \right)^{\mathbf D}=x^{\mathbf{E D}} \equiv x \pmod{M} \quad npu \ \forall x\in \{0,1,\dots,M-1 \} \ . $$ Сравнение $ \mathbf E \cdot \mathbf D \equiv 1 \pmod{\phi(M)} $ эквивалентно: $ {\mathbf{E D}}=1+k\phi(M) $ при $ k\in \mathbb Z $. Если $ \operatorname{HOD}(x,M)=1 $, то, на основании теоремы Эйлера, имеем $$ x^{\mathbf{E D}}=x^{1+k\phi(M)}=x\left(x^{\phi(M)} \right)^k \equiv x \pmod{M} \ . $$ Исключительный случай $ \operatorname{HOD}(x,M)>1 $ требует более кропотливого исследования. При $ x=0 $ сравнение очевидно. Пусть $ x\ne 0 $. Поскольку число $ M_{} $ является произведением двух различных простых чисел $ p_{1} $ и $ p_{2} $, то, на основании теоремы 4, приведенной ☞ ЗДЕСЬ, $ \operatorname{HOD}(x,M) $ должен совпадать с одним из них. Пусть для определенности $ \operatorname{HOD}(x,M)=p_1 $, т.е. $ x \equiv 0 \pmod{p_1} $. Тогда при любом числе $ Q\in \mathbb N $ будет справедливо $$x^{Q} \equiv x \pmod{p_1} \ ,$$ и, в частности, это будет справедливо при $ Q= {\mathbf{E D}} $. Далее, поскольку $ x_{} $ не может делиться еще и на $ p_{2} $, то на основании теоремы Ферма $$x^{p_2-1} \equiv 1 \pmod{p_2} \ .$$ Возводим это сравнение в степень (см. ☞ ЗДЕСЬ ): $$x^{k(p_1-1)(p_2-1)} \equiv 1 \pmod{p_2} \iff x^{k\phi(M)} \equiv 1 \pmod{p_2} \ , $$ и домножаем на $ x_{} $: $$x^{k\phi(M) +1} \equiv x \pmod{p_2} \iff x^{\mathbf{E D}} \equiv x \pmod{p_2} \ .$$ Итак, сравнение $ x^{\mathbf{E D}} \equiv x $ имеет место для обоих модулей $ p_{1} $ и $ p_{2} $. На основании теоремы 4, приведенной ☞ ЗДЕСЬ, оно имеет место и для их произведения, что и завершает доказательство справедливости формулы $ \left(x^{\mathbf E} \right)^{\mathbf D} \equiv x \pmod{M} $.
Мы установили, что если сообщение $ x_{} $ зашифровано с помощью ключа $ {\mathbf E } $: $ c=x^{\mathbf E} \pmod{M} $, то ключ $ {\mathbf D} $ правильно дешифрует: $ x=c^{\mathbf D} \pmod{M} $. Остается открытым вопрос однозначности дешифрования: что если существует $ \tilde x \ne x $ такое, что $ c={\tilde x}^{\mathbf E} \pmod{M} $? Отрицательный ответ на такое предположение дается теоремой Эйлера о числе решений двучленных сравнений. ♦