Система Orphus

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.

Система Orphus

Комментарии