RSA:Доказательство корректности, использование для шифрования и электронной подписи

Уравнения:

$c=E(m)=m^e~\bmod~n$ ,

$m=D(c)=c^d~\bmod~n$

определяют взаимно обратные преобразования множества $\mathbb{Z}_n$

Доказательство

Действительно

$\forall n\in\mathbb{Z}_m~~D(E(m))=E(D(m))=m^{ed}~\bmod~n$

Покажем что

$\forall n\in\mathbb{Z}_m~~m^{ed}=m~\bmod~p$ .

Пусть $m\ne 0~\bmod~p$ .

Поскольку числа $e$ и $d$ являются взаимно обратными относительно умножения по модулю $\varphi(n)=(p-1)(q-1)$ :

$\exist k\in\mathbb{Z}: ed=1+k(p-1)(q-1)$ .

Тогда

$m^{ed}=m^{1 + k(p - 1)(q - 1)}~\bmod~p =$

$= m\left( m^{p - 1}~\bmod~p\right)^{k (q - 1)}~\bmod~p=$

$=m \cdot 1^{k(q - 1)}= m$

Аналогично

$m^{ed}~\bmod~q=m~\bmod~q$ .

Из китайской теоремы об остатках следует

$m^{ed}~\bmod~n=m~\bmod~n$ .

Сказать "Спасибо"