Русская Википедия:Криптосистема Мэсси — Омуры
Криптосистема Мэсси — Омуры была предложена в 1978 году Джеймсом Мэсси и Джимом К. Омурой изначально в качестве улучшения протокола Шамира. Имеется два варианта реализации данного протокола: классический и эллиптический. Первый построен на сложности задачи дискретного логарифмирования, второй на свойствах эллиптической кривой. Обычно сгенерированное в результате сообщение <math>m</math> используется в качестве ключа традиционной криптосистемы.
Первоначальный вариант
Изначально протокол Мэсси-Омуры был описан применительно к мультипликативной группе <math>Z^*_p</math>, где <math>p</math> — простое число, и представлял собой аналог передачи секрета с помощью запираемых на один или два замка ящиков. Суть схемы заключается в следующем: абонент Alice запирает ящик с письмом своим ключом и пересылает ящик абоненту Bob. Абонент Bob, в свою очередь, запирает его своим ключом, и отправляет обратно к Alice. Alice снимает свой замок и направляет ящик к Bob, который снимает свой замок.
Алгоритм
- Выбирается в качестве системного параметра большое простое число <math>p</math>. Абоненты Alice и Bob выбирают случайные числа <math>e_A</math> и <math>e_B</math> (между 0 и <math>p-1</math>), взаимно простые с <math>p-1=\varphi(p)</math>, где <math>\varphi</math> — функция Эйлера.
- С помощью расширенного алгоритма Евклида вычисляются <math>d_A</math> и <math>d_B</math>, обратные числам <math>e_A</math> и <math>e_B</math> по модулю <math>p-1</math>:
- <math>d_A = {e_A}^{-1} \bmod (p-1) </math>
- <math>d_B = {e_B}^{-1} \bmod (p-1) </math>
- Иначе говоря, должны выполняться условия:
- <math>e_{A}\cdot{d_A\equiv1\bmod (p-1)}</math>,
- <math>e_B\cdot{d_B}\equiv1\bmod (p-1)</math>.
Пары чисел <math>(e_A, d_A)</math>, <math>(e_B, d_B)</math> являются секретными ключами абонентов.
- <math>m^{e_A\cdot{d_A}}=m\bmod p</math>, так как
- <math>m^{e_A\cdot{d_A}}=m^{j\cdot{\varphi(p)+1}}=m^{j\cdot{\varphi(p)}}\cdot{m}=m</math>
(Первый сомножитель равен 1 по теореме Эйлера). Аналогично <math>m^{e_{B}d_{B}}=m\bmod p</math>.
- Абонент Alice посылает сообщение <math>m</math> (<math>0<m<{p-1}</math>) абоненту Bob.
Alice шифрует своё сообщение первым ключом: <math>m_1=m^{e_A}\bmod p</math> (<math>0<m_1<p</math>) и пересылает <math>m_1</math> абоненту Bob.
- Bob шифрует вторым ключом: <math>m_2=m_1^{e_B}\bmod p</math> (<math>0<m_2<p</math>) и пересылает обратно к Аlice.
- Alice «снимает первый замок» с помощью второго секретного ключа:
- <math>m_3=m_2^{d_A}\bmod p=m^{e_A\cdot{e_B}\cdot{d_A}}\bmod p</math>.
- Bob «снимает свой первый замок» с помощью второго секретного ключа:
- <math>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>m</math> от Аlice.
Проблемы в использовании
Данный вариант системы может быть реализован и без использования процедуры возведения в степень в конечных полях, но задача дискретного логарифмирования достаточно сложна для Bob, чтобы тот по <math>m_1=m^{e_A}</math> не смог определить ключ <math>m^{e_A}</math> и впредь читать сообщения, ему не предназначавшиеся. Обязательным условием надежности является хорошая система подписи сообщений. Без использования подписей любое постороннее лицо Eva может представиться абонентом Bob и вернуть Alice сообщение вида <math>m_\tilde{2}=m_1^{e_E}\bmod p</math>. Alice продолжит процедуру и, «сняв свой замок», откроет самозванцу Eva путь к расшифрованию сообщения. В связи с этим, <math>m_2=m_1^{e_B}\bmod p</math> должно сопровождаться аутентификацией.
Эллиптический вариант
Эллиптический вариант данного протокола предоставляет возможность передавать сообщение от Alice к Bob по открытому каналу без предварительной передачи какой-либо ключевой информации. Системные параметры здесь: уравнение эллиптической кривой <math>\varepsilon</math> и поле <math>F</math>, задающееся неприводимым многочленом. Пусть порядок эллиптической кривой <math>\varepsilon</math> равен <math>N</math>, <math>e</math> — целое число, взаимно простое с <math>N</math>(<math>1<e<N</math>). По алгоритму Евклида можно найти
- <math>d\equiv{e^{-1}}\pmod N</math>.
По определению сравнимости по модулю:
- <math>e*d=jN+1</math>
Значит для любой точки <math>P</math> эллиптической кривой <math>\varepsilon</math> порядка <math>N</math> выполняется:
- <math>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>e\cdot(d\cdot P)=P</math>.
Теперь, используя <math>e</math> и <math>d</math> и любую точку <math>P</math> эллиптической кривой, можно вычислить
- <math>Q=d\cdot{P}</math>
- <math>R=e\cdot{Q}</math>
Где <math>P=R</math>. Вычисление точки <math>P</math> по <math>eP</math> эквивалентно решению задачи дискретного логарифма для эллиптической кривой.
Алгоритм
- Абонент Alice помещает своё сообщение <math>m</math> в некоторую точку <math>M(m)</math> эллиптической кривой и умножает её на своё секретное значение <math>e_A</math>, получает точку <math>P_1=e_A\cdot{M(m)}</math>. Эта точка отправляется абоненту Bob.
- Bob вычисляет <math>P_2=e_B\cdot{P_1}</math> и отправляет результат Alice.
- Alice «снимает замок», вычисляя <math>P_3=d_A\cdot{P_2}</math>. Возвращает полученный результат абоненту Bob.
- Bob расшифровывает сообщение, используя свой секретный ключ шифрования <math>d_B</math>:
- <math>M(m)=d_B\cdot{P_3}</math>
Литература
- Н. Коблиц «Курс теории чисел и криптографии». Москва, 2001
- А. А. Болотов, С. Б. Гашков, А. Б. Фролов, А. А. Часовских "Алгоритмические основы эллиптической криптографии. Москва, 2004
- Б. Н. Воронков, А. С. Щеголеватых «Элементы теории чисел и криптозащита». Воронеж, 2008
