Криптосистема Мэсси — Омуры

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

Первоначальный вариант

Изначально протокол Мэсси-Омуры был описан применительно к мультипликативной группе $Z_{p}^{*}$ , где $p$ — простое число, и представлял собой аналог передачи секрета с помощью запираемых на один или два замка ящиков. Суть схемы заключается в следующем: абонент Alice запирает ящик с письмом своим ключом и пересылает ящик абоненту Bob. Абонент Bob, в свою очередь, запирает его своим ключом, и отправляет обратно к Alice. Alice снимает свой замок и направляет ящик к Bob, который снимает свой замок.

Алгоритм

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

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

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

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

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

,

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

.

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

m^{e_{A}\cdot {d_{A}}}=m{\bmod {p}}

, так как

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

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

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

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

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

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

.

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

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

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

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

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

Эллиптический вариант

Эллиптический вариант данного протокола предоставляет возможность передавать сообщение от Alice к Bob по открытому каналу без предварительной передачи какой-либо ключевой информации. Системные параметры здесь: уравнение эллиптической кривой $\varepsilon$ и поле $F$ , задающееся неприводимым многочленом. Пусть порядок эллиптической кривой $\varepsilon$ равен $N$ , $e$ — целое число, взаимно простое с $N$ ( $1<e<N$ ). По алгоритму Евклида можно найти

d\equiv {e^{-1}}{\pmod {N}}

.

По определению сравнимости по модулю:

e*d=jN+1

Значит для любой точки $P$ эллиптической кривой $\varepsilon$ порядка $N$ выполняется:

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

, то есть

e\cdot (d\cdot P)=P

.

Теперь, используя $e$ и $d$ и любую точку $P$ эллиптической кривой, можно вычислить

Q=d\cdot {P}

R=e\cdot {Q}

Где $P=R$ . Вычисление точки $P$ по $eP$ эквивалентно решению задачи дискретного логарифма для эллиптической кривой.

Алгоритм

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

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

Литература

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.