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

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

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

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

Алгоритм

• Выбирается в качестве системного параметра большое простое число p {displaystyle p} . Абоненты Alice и Bob выбирают случайные числа e A {displaystyle e_{A}} и e B {displaystyle e_{B}} (между 0 и p − 1 {displaystyle p-1} ), взаимно простые с p − 1 = φ ( p ) {displaystyle p-1=varphi (p)} , где φ {displaystyle varphi } — функция Эйлера.
• С помощью расширенного алгоритма Евклида вычисляются d A {displaystyle d_{A}} и d B {displaystyle d_{B}} , обратные числам e A {displaystyle e_{A}} и e B {displaystyle e_{B}} по модулю p − 1 {displaystyle p-1} :

d A = e A − 1 mod ( p − 1 ) {displaystyle d_{A}={e_{A}}^{-1}{mod {(}}p-1)} d B = e B − 1 mod ( p − 1 ) {displaystyle d_{B}={e_{B}}^{-1}{mod {(}}p-1)} Иначе говоря, должны выполняться условия: e A ⋅ d A ≡ 1 mod ( p − 1 ) {displaystyle e_{A}cdot {d_{A}equiv 1{mod {(}}p-1)}} , e B ⋅ d B ≡ 1 mod ( p − 1 ) {displaystyle e_{B}cdot {d_{B}}equiv 1{mod {(}}p-1)} .

Пары чисел ( e A , d A ) {displaystyle (e_{A},d_{A})} , ( e B , d B ) {displaystyle (e_{B},d_{B})} являются секретными ключами абонентов.

m e A ⋅ d A = m mod p {displaystyle m^{e_{A}cdot {d_{A}}}=m{mod {p}}} , так как m e A ⋅ d A = m j ⋅ φ ( p ) + 1 = m j ⋅ φ ( p ) ⋅ m = m {displaystyle m^{e_{A}cdot {d_{A}}}=m^{jcdot {varphi (p)+1}}=m^{jcdot {varphi (p)}}cdot {m}=m}

(Первый сомножитель равен 1 по теореме Эйлера). Аналогично m e B d B = m mod p {displaystyle m^{e_{B}d_{B}}=m{mod {p}}} .

• Абонент Alice посылает сообщение m {displaystyle m} ( 0 < m < p − 1 {displaystyle 0<m<{p-1}} ) абоненту Bob.

Alice шифрует своё сообщение первым ключом: m 1 = m e A mod p {displaystyle m_{1}=m^{e_{A}}{mod {p}}} ( 0 < m 1 < p {displaystyle 0<m_{1}<p} ) и пересылает m 1 {displaystyle m_{1}} абоненту Bob.

• Bob шифрует вторым ключом: m 2 = m 1 e B mod p {displaystyle m_{2}=m_{1}^{e_{B}}{mod {p}}} ( 0 < m 2 < p {displaystyle 0<m_{2}<p} ) и пересылает обратно к Аlice.
• Alice «снимает первый замок» с помощью второго секретного ключа:

m 3 = m 2 d A mod p = m e A ⋅ e B ⋅ d A mod p {displaystyle m_{3}=m_{2}^{d_{A}}{mod {p}}=m^{e_{A}cdot {e_{B}}cdot {d_{A}}}{mod {p}}} .

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

m 4 = m 3 d B mod p = m d B ⋅ e A ⋅ e B ⋅ d A m o d p = m {displaystyle m_{4}=m_{3}^{d_{B}}{mod {p}}=m^{d_{B}cdot {e_{A}}cdot {e_{B}}cdot {d_{A}}}modp=m}

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

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

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

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

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

d ≡ e − 1 ( mod N ) {displaystyle dequiv {e^{-1}}{pmod {N}}} .

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

e ∗ d = j N + 1 {displaystyle e*d=jN+1}

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

e ⋅ ( d ⋅ P ) = ( e ⋅ d ) P = ( j ⋅ N + 1 ) P = ( j ⋅ N ) P + P = j ⋅ 0 + P = 0 + P = P {displaystyle ecdot {(dcdot P)}=(ecdot {d})P=(jcdot {N}+1)P=(jcdot {N})P+P=jcdot {0}+P=0+P=P} , то есть e ⋅ ( d ⋅ P ) = P {displaystyle ecdot (dcdot P)=P} .

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

Q = d ⋅ P {displaystyle Q=dcdot {P}} R = e ⋅ Q {displaystyle R=ecdot {Q}}

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

Алгоритм

• Абонент Alice помещает своё сообщение m {displaystyle m} в некоторую точку M ( m ) {displaystyle M(m)} эллиптической кривой и умножает её на своё секретное значение e A {displaystyle e_{A}} , получает точку P 1 = e A ⋅ M ( m ) {displaystyle P_{1}=e_{A}cdot {M(m)}} . Эта точка отправляется абоненту Bob.
• Bob вычисляет P 2 = e B ⋅ P 1 {displaystyle P_{2}=e_{B}cdot {P_{1}}} и отправляет результат Alice.
• Alice «снимает замок», вычисляя P 3 = d A ⋅ P 2 {displaystyle P_{3}=d_{A}cdot {P_{2}}} . Возвращает полученный результат абоненту Bob.
• Bob расшифровывает сообщение, используя свой секретный ключ шифрования d B {displaystyle d_{B}} :

M ( m ) = d B ⋅ P 3 {displaystyle M(m)=d_{B}cdot {P_{3}}}