!!§!! Вспомогательная страница к разделу
☞
((:crypto#алгоритм_rsa КРИПТОГРАФИЯ)).
----
!!Т!! **Теорема.** //При числе// $ \mathbf E $, //выбранном по алгоритму// **RSA**,
//сравнение//
$$ x^{\mathbf E} \equiv c \pmod{M} $$
//имеет единственное решение, которое может быть найдено по формуле//
$$ x=c^{\mathbf D} \pmod{M} \, .$$
**Доказательство.** Покажем, что пара $ \mathbf E $ и $ \mathbf D $, построенная
по **((:crypto#алгоритм_rsa алгоритму 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 $, то, на основании ((:modular#теорема_эйлера теоремы Эйлера)), имеем
$$
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, приведенной
☞
((:numtheory#каноническое_разложение_числа ЗДЕСЬ)), $ \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} $, то на основании ((:modular#теорема_ферма теоремы Ферма))
$$x^{p_2-1} \equiv 1 \pmod{p_2} \ .$$
Возводим это сравнение в степень (см.
☞
((:modular#сравнения ЗДЕСЬ)) ):
$$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, приведенной
☞
((:numtheory#взаимно_простые_числа ЗДЕСЬ)), оно имеет место и для их
произведения, что и завершает доказательство справедливости формулы $ \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} $?
Отрицательный ответ на такое предположение дается ((:modular#двучленные_сравнения теоремой Эйлера о числе решений двучленных сравнений)).
♦