УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к разделу КРИПТОГРАФИЯ.


Т

Теорема. При числе \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}? Отрицательный ответ на такое предположение дается теоремой Эйлера о числе решений двучленных сравнений.


2017/01/18 21:33 редактировал au