302
правки
Изменения
RSA
,→Реализация
* Взять открытый текст <tex>m</tex>
* Зашифровать сообщение с использованием открытого ключа Алисы:
*: <tex>c = E(m) = m^e \mod n ~~~~ (1)</tex>
[[Файл:Gg1.png|800px|center]]
* Взять свой закрытый ключ <tex>(d,n)</tex>
* Применить закрытый ключ для расшифрования сообщения:
*: <tex>m = D(c) = c^d \mod n ~~~~ (2)</tex> ===Корректность схемы <tex>\mathtt{RSA}</tex>==={{Теорема|statement=Уравнения <tex>(1)</tex> и <tex>(2)</tex>, на которых основана схема <tex>\mathtt{RSA}</tex>, определяют взаимно обратные преобразования множества <tex>\mathbb{Z}_n</tex>|proof=Действительно, для <math>\forall m \in \mathbb{Z}_{n}</math>: <math>D\left( {E\left( m \right)} \right) = E\left( {D\left( m \right)} \right) = m^{ed} \mod n</math> Покажем, что:: <math>\forall m \in \mathbb{Z}_{n}: m^{ed} \equiv m \mod p</math>. Возможны два случая:* <math>m \not\equiv 0 \mod p</math>. Поскольку числа <math>e</math> и <math>d</math> являются взаимно обратными относительно умножения по модулю <math>\varphi(n)=(p-1)(q-1)</math>, т.e : <math>ed=1+k(p-1)(q-1)</math> для некоторого целого <math>k</math>, тогда: : <math>\begin{align}m^{ed} & \equiv m^{1 + k\left( {p - 1} \right)\left( {q - 1} \right)} & \equiv & \mod p \\ & \equiv m\left( {m^{p - 1} } \right)^{k\left( {q - 1} \right)} & \equiv & \mod p \\ & \equiv m\left( 1 \right)^{k\left( {q - 1} \right)} & \equiv m & \mod p\end{align}</math> где второе тождество следует из [[Теорема_Ферма|теоремы Ферма]]. * Рассмотрим второй случай:: <math>m \equiv 0 \mod p</math>,тогда: <math>m^{ed} \equiv 0 \equiv m \mod p</math> Таким образом, при всех <math>m</math> выполняется равенство ::: <math>m^{ed} \equiv m \mod p</math> Аналогично можно показать, что:: <math>\forall m \in \mathbb{Z}_{n}: m^{ed} \equiv m \mod q</math>. Тогда, из [[китайская теорема об остатках|китайской теоремы об остатках]]: <math>\forall m \in \mathbb{Z}_{n}: m^{ed} \equiv m \mod n</math>}} ===Криптографическая стойкость===
==Применение==
