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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

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

Алгоритм

[math]\displaystyle{ d_A = {e_A}^{-1} \bmod (p-1) }[/math]
[math]\displaystyle{ d_B = {e_B}^{-1} \bmod (p-1) }[/math]
Иначе говоря, должны выполняться условия:
[math]\displaystyle{ e_{A}\cdot{d_A\equiv1\bmod (p-1)} }[/math],
[math]\displaystyle{ e_B\cdot{d_B}\equiv1\bmod (p-1) }[/math].

Пары чисел [math]\displaystyle{ (e_A, d_A) }[/math], [math]\displaystyle{ (e_B, d_B) }[/math] являются секретными ключами абонентов.

[math]\displaystyle{ m^{e_A\cdot{d_A}}=m\bmod p }[/math], так как
[math]\displaystyle{ m^{e_A\cdot{d_A}}=m^{j\cdot{\varphi(p)+1}}=m^{j\cdot{\varphi(p)}}\cdot{m}=m }[/math]

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

  • Абонент Alice посылает сообщение [math]\displaystyle{ m }[/math] ([math]\displaystyle{ 0\lt m\lt {p-1} }[/math]) абоненту Bob.

Alice шифрует своё сообщение первым ключом: [math]\displaystyle{ m_1=m^{e_A}\bmod p }[/math] ([math]\displaystyle{ 0\lt m_1\lt p }[/math]) и пересылает [math]\displaystyle{ m_1 }[/math] абоненту Bob.

  • Bob шифрует вторым ключом: [math]\displaystyle{ m_2=m_1^{e_B}\bmod p }[/math] ([math]\displaystyle{ 0\lt m_2\lt p }[/math]) и пересылает обратно к Аlice.
  • Alice «снимает первый замок» с помощью второго секретного ключа:
[math]\displaystyle{ m_3=m_2^{d_A}\bmod p=m^{e_A\cdot{e_B}\cdot{d_A}}\bmod p }[/math].
  • Bob «снимает свой первый замок» с помощью второго секретного ключа:
[math]\displaystyle{ m_4=m_3^{d_B}\bmod p=m^{d_B\cdot{e_A}\cdot{e_B}\cdot{d_A}} mod p=m }[/math]

Итого: абоненту Bob доставлено секретное сообщение [math]\displaystyle{ m }[/math] от Аlice.

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

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

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

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

[math]\displaystyle{ d\equiv{e^{-1}}\pmod N }[/math].

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

[math]\displaystyle{ e*d=jN+1 }[/math]

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

[math]\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 }[/math], то есть
[math]\displaystyle{ e\cdot(d\cdot P)=P }[/math].

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

[math]\displaystyle{ Q=d\cdot{P} }[/math]
[math]\displaystyle{ R=e\cdot{Q} }[/math]

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

Алгоритм

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

Литература

  • Н. Коблиц «Курс теории чисел и криптографии». Москва, 2001
  • А. А. Болотов, С. Б. Гашков, А. Б. Фролов, А. А. Часовских "Алгоритмические основы эллиптической криптографии. Москва, 2004
  • Б. Н. Воронков, А. С. Щеголеватых «Элементы теории чисел и криптозащита». Воронеж, 2008
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Криптосистема_Мэсси_—_Омуры&oldid=5825014