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

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

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

• Выбирается в качестве системного параметра большое простое число ${\displaystyle p}$. Абоненты Алиса и Боб выбирают случайные числа ${\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}}}$.

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

• Боб шифрует вторым ключом: ${\displaystyle m_{2}=m_{1}^{e_{B}}{\bmod {p}}}$ (${\displaystyle 0<m_{2}<p}$) и пересылает обратно к Алисе.

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

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

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

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

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

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

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

${\displaystyle d\equiv {e^{-1}}{\pmod {N}}}$.

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

${\displaystyle e*d=jN+1}$

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

${\displaystyle 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}$, то есть

${\displaystyle e\cdot (d\cdot P)=P}$.

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

${\displaystyle Q=d\cdot {P}}$

${\displaystyle R=e\cdot {Q}}$

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

• Абонент 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}}}$

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