302
правки
Изменения
RSA
,→Корректность схемы \mathtt{RSA}
Покажем, что:
: <tex>\forall m \in \mathbb{Z}_{n}: m^{ed} \equiv m \mod pmod{p}</tex>.
Возможны два случая:
* <tex>m \not\equiv 0 \mod pmod{p}</tex>.
Поскольку числа <tex>e</tex> и <tex>d</tex> являются взаимно обратными относительно умножения по модулю <tex>\varphi(n)=(p-1)(q-1)</tex>, то есть
: <tex>\begin{align}
m^{ed} & \equiv m^{1 + k\left( {p - 1} \right)\left( {q - 1} \right)} & \equiv & \mod pmod{p } \\ & \equiv m\left( {m^{p - 1} } \right)^{k\left( {q - 1} \right)} & \equiv & \mod pmod{p } \\ & \equiv m\left( 1 \right)^{k\left( {q - 1} \right)} & \pmod{p} \equiv m & \mod pmod{p}
\end{align}</tex>
* Рассмотрим второй случай:
: <tex>m \equiv 0 \mod pmod{p}</tex>,
тогда
: <tex>m^{ed} \equiv 0 \equiv m \mod pmod{p}</tex>
Таким образом, при всех <tex>m</tex> выполняется равенство
::: <tex>m^{ed} \equiv m \mod pmod{p}</tex>
Аналогично можно показать, что:
: <tex>\forall m \in \mathbb{Z}_{n}: m^{ed} \equiv m \mod pmod{q}</tex>.
Тогда, из [[китайская теорема об остатках|китайской теоремы об остатках]]
: <tex>\forall m \in \mathbb{Z}_{n}: m^{ed} \equiv m \mod pmod{n}</tex>
}}
