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

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

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

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

Алгоритм

• Выбирается в качестве системного параметра большое простое число $p$. Абоненты Алиса и Боб выбирают случайные числа $e_A$ и $e_B$ (между 0 и $p-1$), взаимно простые с $p-1=\phi (p)$, где $\phi$ — функция Эйлера.

• С помощью расширенного алгоритма Евклида вычисляются $d_A$ и $d_B$, обратные числам $e_A$ и $e_B$ по модулю $p-1$:

$d_A={e_A}^{-1}mod(p-1)$

$d_B={e_B}^{-1}mod(p-1)$

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

$e_A\cdot d_A\equiv 1mod(p-1)$,

$e_B\cdot d_B\equiv 1mod(p-1)$.

Пары чисел $(e_A,d_A)$, $(e_B,d_B)$ являются секретными ключами абонентов.

$m^{e_A\cdot d_A}=mmodp$, так как

$m^{e_A\cdot d_A}=m^{j\cdot \phi (p)+1}=m^{j\cdot \phi (p)}\cdot m=m$

(Первый сомножитель равен 1 по теореме Эйлера). Аналогично $m^{e_B{d}_B}=mmodp$.

• Абонент Алиса посылает сообщение $m$ ($0<m<p-1$) абоненту Боб. Алиса шифрует своё сообщение первым ключом: $m_1=m^{e_A}modp$ ($0<m_1<p$) и пересылает $m_1$ абоненту Боб.

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

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

$m_3=m_2^{d_A}modp=m^{e_A\cdot e_B\cdot d_A}modp$.

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

$m_4=m_3^{d_B}modp=m^{d_B\cdot e_A\cdot e_B\cdot d_A}modp=m.$

Итак, Бобу доставлено секретное сообщение $m$ от Алисы.

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

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

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

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

$d\equiv e^{-1}(\mathrm{mod}N)$.

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

$e*d=jN+1$

Значит для любой точки $P$ эллиптической кривой $\epsilon$ порядка $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