WikiSort.ru - Не сортированное

Алгоритм

• Выбирается в качестве системного параметра большое простое число ${\displaystyle p}$ . Абоненты Alice и Bob выбирают случайные числа ${\displaystyle e_{A}}$ и ${\displaystyle e_{B}}$ (между 0 и ${\displaystyle p-1}$ ), взаимно простые с ${\displaystyle p-1=\varphi (p)}$ , где ${\displaystyle \varphi }$  — функция Эйлера.
• С помощью расширенного алгоритма Евклида вычисляются ${\displaystyle d_{A}}$ и ${\displaystyle d_{B}}$ , обратные числам ${\displaystyle e_{A}}$ и ${\displaystyle e_{B}}$ по модулю ${\displaystyle p-1}$ :

${\displaystyle d_{A}={e_{A}}^{-1}{\bmod {(}}p-1)}$

${\displaystyle d_{B}={e_{B}}^{-1}{\bmod {(}}p-1)}$

Иначе говоря, должны выполняться условия:

${\displaystyle e_{A}\cdot {d_{A}\equiv 1{\bmod {(}}p-1)}}$ ,

${\displaystyle e_{B}\cdot {d_{B}}\equiv 1{\bmod {(}}p-1)}$ .

Пары чисел ${\displaystyle (e_{A},d_{A})}$ , ${\displaystyle (e_{B},d_{B})}$ являются секретными ключами абонентов.

${\displaystyle m^{e_{A}\cdot {d_{A}}}=m{\bmod {p}}}$ , так как

${\displaystyle m^{e_{A}\cdot {d_{A}}}=m^{j\cdot {\varphi (p)+1}}=m^{j\cdot {\varphi (p)}}\cdot {m}=m}$

(Первый сомножитель равен 1 по теореме Эйлера). Аналогично ${\displaystyle m^{e_{B}d_{B}}=m{\bmod {p}}}$ .

• Абонент Alice посылает сообщение ${\displaystyle m}$ (${\displaystyle 0<m<{p-1}}$ ) абоненту Bob.

Alice шифрует своё сообщение первым ключом: ${\displaystyle m_{1}=m^{e_{A}}{\bmod {p}}}$ (${\displaystyle 0<m_{1}<p}$ ) и пересылает ${\displaystyle m_{1}}$ абоненту Bob.

• Bob шифрует вторым ключом: ${\displaystyle m_{2}=m_{1}^{e_{B}}{\bmod {p}}}$ (${\displaystyle 0<m_{2}<p}$ ) и пересылает обратно к Аlice.
• Alice «снимает первый замок» с помощью второго секретного ключа:

${\displaystyle m_{3}=m_{2}^{d_{A}}{\bmod {p}}=m^{e_{A}\cdot {e_{B}}\cdot {d_{A}}}{\bmod {p}}}$ .

• Bob «снимает свой первый замок» с помощью второго секретного ключа:

${\displaystyle m_{4}=m_{3}^{d_{B}}{\bmod {p}}=m^{d_{B}\cdot {e_{A}}\cdot {e_{B}}\cdot {d_{A}}}modp=m}$

Итого: абоненту Bob доставлено секретное сообщение ${\displaystyle m}$ от Аlice.

Проблемы в использовании

Данный вариант системы может быть реализован и без использования процедуры возведения в степень в конечных полях, но задача дискретного логарифмирования достаточно сложна для Bob, чтобы тот по ${\displaystyle m_{1}=m^{e_{A}}}$ не смог определить ключ ${\displaystyle m^{e_{A}}}$ и впредь читать сообщения, ему не предназначавшиеся. Обязательным условием надежности является хорошая система подписи сообщений. Без использования подписей любое постороннее лицо Eva может представиться абонентом Bob и вернуть Alice сообщение вида ${\displaystyle m_{\tilde {2}}=m_{1}^{e_{E}}{\bmod {p}}}$ . Alice продолжит процедуру и, «сняв свой замок», откроет самозванцу Eva путь к расшифрованию сообщения. В связи с этим, ${\displaystyle m_{2}=m_{1}^{e_{B}}{\bmod {p}}}$ должно сопровождаться аутентификацией.

Алгоритм

• Абонент Alice помещает своё сообщение ${\displaystyle m}$ в некоторую точку ${\displaystyle M(m)}$ эллиптической кривой и умножает её на своё секретное значение ${\displaystyle e_{A}}$ , получает точку ${\displaystyle P_{1}=e_{A}\cdot {M(m)}}$ . Эта точка отправляется абоненту Bob.
• Bob вычисляет ${\displaystyle P_{2}=e_{B}\cdot {P_{1}}}$ и отправляет результат Alice.
• Alice «снимает замок», вычисляя ${\displaystyle P_{3}=d_{A}\cdot {P_{2}}}$ . Возвращает полученный результат абоненту Bob.
• Bob расшифровывает сообщение, используя свой секретный ключ шифрования ${\displaystyle d_{B}}$ :

${\displaystyle M(m)=d_{B}\cdot {P_{3}}}$