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

Криптосистема Мэсси — Омуры была предложена в 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