Просмотр кода страницы Криптосистема Мэсси — Омуры

'''Криптосистема Мэсси — Омуры''' была предложена в 1978 году [[Мэсси, Джеймс|Джеймсом Мэсси]] и Джимом К. Омурой изначально в качестве улучшения протокола [[Шамир, Ади|Шамира]]. Имеется два варианта реализации данного протокола: классический и эллиптический. Первый построен на сложности задачи [[Дискретное логарифмирование|дискретного логарифмирования]], второй на свойствах [[Эллиптическая кривая|эллиптической кривой]]. Обычно сгенерированное в результате сообщение <math>m</math> используется в качестве ключа традиционной криптосистемы.

== Первоначальный вариант ==
Изначально протокол Мэсси — Омуры был описан применительно к [[Мультипликативная группа кольца вычетов|мультипликативной группе]] <math>Z^*_p</math>, где <math>p</math> — простое число, и представлял собой аналог передачи [[Секрет (криптография)|секрета]] с помощью запираемых на один или два замка ящиков.
Суть схемы можно описать следующим образом: 
Алиса запирает ящик с письмом своим ключом и пересылает ящик абоненту Бобу. Боб, в свою очередь, запирает его своим ключом, и отправляет обратно к Алиса. Алиса снимает свой замок и направляет ящик обратно к Бобу, который снимает свой замок и читает письмо.

=== Алгоритм ===

* Выбирается в качестве системного параметра большое [[простое число]] <math>p</math>. Абоненты Алиса и Боб выбирают [[случайное простое число|случайные числа]] <math>e_A</math> и <math>e_B</math> (между 0 и <math>p-1</math>), [[взаимно простые числа|взаимно простые]] с <math>p-1=\varphi(p)</math>, где <math>\varphi</math> — [[функция Эйлера]].

* С помощью [[Расширенный алгоритм Евклида|расширенного алгоритма Евклида]] вычисляются <math>d_A</math> и <math>d_B</math>, обратные числам <math>e_A</math> и <math>e_B</math> по модулю <math>p-1</math>:
:: <math>d_A = {e_A}^{-1} \bmod (p-1) </math>
:: <math>d_B = {e_B}^{-1} \bmod (p-1) </math>
: Иначе говоря, должны выполняться условия:
:: <math>e_{A}\cdot{d_A\equiv1\bmod (p-1)}</math>,
:: <math>e_B\cdot{d_B}\equiv1\bmod (p-1)</math>.
Пары чисел <math>(e_A, d_A)</math>, <math>(e_B, d_B)</math> являются [[Ключ (криптография)|секретными ключами]] абонентов.
:: <math>m^{e_A\cdot{d_A}}=m\bmod p</math>, так как
:: <math>m^{e_A\cdot{d_A}}=m^{j\cdot{\varphi(p)+1}}=m^{j\cdot{\varphi(p)}}\cdot{m}=m</math>
(Первый сомножитель равен 1 по [[теорема Эйлера (теория чисел)|теореме Эйлера]]).
Аналогично <math>m^{e_{B}d_{B}}=m\bmod p</math>.

* Абонент Алиса посылает сообщение <math>m</math> (<math>0<m<{p-1}</math>) абоненту Боб. Алиса [[шифрование|шифрует]] своё сообщение первым ключом: <math>m_1=m^{e_A}\bmod p</math> (<math>0<m_1<p</math>) и пересылает <math>m_1</math> абоненту Боб.

* Боб шифрует вторым ключом: <math>m_2=m_1^{e_B}\bmod p</math> (<math>0<m_2<p</math>) и пересылает обратно к Алисе.

* Алиса «снимает первый замок» с помощью второго секретного ключа:
:: <math>m_3=m_2^{d_A}\bmod p=m^{e_A\cdot{e_B}\cdot{d_A}}\bmod p</math>.

* Боб «снимает свой первый замок» с помощью второго секретного ключа:
:: <math>m_4=m_3^{d_B}\bmod p=m^{d_B\cdot{e_A}\cdot{e_B}\cdot{d_A}} \bmod p=m.</math>
Итак, Бобу доставлено секретное сообщение <math>m</math> от Алисы.

=== Проблемы в использовании ===
Данный вариант системы может быть реализован и без использования процедуры возведения в степень в конечных полях, но задача дискретного логарифмирования достаточно сложна для Боба, чтобы тот по <math>m_1=m^{e_A}</math> не смог определить ключ <math>m^{e_A}</math> и впредь читать сообщения, ему не предназначавшиеся.
Обязательным условием надежности является хорошая система подписи сообщений. Без использования подписей любое постороннее лицо Ева может представиться Бобу и вернуть Алисе сообщение вида <math>m_\tilde{2}=m_1^{e_E}\bmod p</math>.
Алиса продолжит процедуру и, «сняв свой замок», откроет самозванке Еве путь к расшифрованию сообщения.
В связи с этим, <math>m_2=m_1^{e_B}\bmod p</math> должно сопровождаться [[аутентификация|аутентификацией]].

== Эллиптический вариант ==
Эллиптический вариант данного протокола предоставляет возможность передавать сообщение от Alice к Bob по [[Канал связи|открытому каналу]] без предварительной передачи какой-либо ключевой информации. Системные параметры здесь: уравнение [[Эллиптическая кривая|эллиптической кривой]] <math>\varepsilon</math> и [[Поле (алгебра)|поле]] <math>F</math>, задающееся [[Неприводимый многочлен|неприводимым многочленом]].
Пусть порядок эллиптической кривой <math>\varepsilon</math> равен <math>N</math>, <math>e</math> — целое число, взаимно простое с <math>N</math>(<math>1<e<N</math>).
По [[Алгоритм Евклида|алгоритму Евклида]] можно найти
:: <math>d\equiv{e^{-1}}\pmod N</math>.
По определению [[Сравнение по модулю|сравнимости по модулю]]:
:: <math>e*d=jN+1</math>
Значит для любой точки <math>P</math> эллиптической кривой <math>\varepsilon</math> порядка <math>N</math> выполняется:
:: <math>e\cdot{(d\cdot P)}=(e\cdot{d})P=(j\cdot{N}+1)P=(j\cdot{N})P+P=j\cdot{0}+P=0+P=P</math>, то есть
:: <math>e\cdot(d\cdot P)=P</math>.
Теперь, используя <math>e</math> и <math>d</math> и любую точку <math>P</math> эллиптической кривой, можно вычислить
:: <math>Q=d\cdot{P}</math>
:: <math>R=e\cdot{Q}</math>
Где <math>P=R</math>.
Вычисление точки <math>P</math> по <math>eP</math> эквивалентно решению задачи дискретного логарифма для эллиптической кривой.

=== Алгоритм ===
* Абонент Alice помещает своё сообщение <math>m</math> в некоторую точку <math>M(m)</math> эллиптической кривой и умножает её на своё секретное значение <math>e_A</math>, получает точку <math>P_1=e_A\cdot{M(m)}</math>. Эта точка отправляется абоненту Bob.
* Bob вычисляет <math>P_2=e_B\cdot{P_1}</math> и отправляет результат Alice.
* Alice «снимает замок», вычисляя <math>P_3=d_A\cdot{P_2}</math>. Возвращает полученный результат абоненту Bob.
* Bob расшифровывает сообщение, используя свой секретный ключ шифрования <math>d_B</math>:
:: <math>M(m)=d_B\cdot{P_3}</math>

== Литература ==
* Н. Коблиц «Курс теории чисел и криптографии». Москва, 2001
* А. А. Болотов, С. Б. Гашков, А. Б. Фролов, А. А. Часовских "Алгоритмические основы эллиптической криптографии. Москва, 2004
* Б. Н. Воронков, А. С. Щеголеватых «Элементы теории чисел и криптозащита». Воронеж, 2008
[[Категория:Криптография]]