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

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

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

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

АлгоритмПравить

• Выбирается в качестве системного параметра большое простое число $p$$p$ . Абоненты Alice и Bob выбирают случайные числа $e_A$$e_{A}$  и $e_B$$e_{B}$  (между 0 и $p-<!--\; -\; -->1$$p-1$ ), взаимно простые с $p-<!--\; -\; -->1=\mathrm{\phi <!--\; \phi \; -->}(p)$$p-1=\varphi (p)$ , где $\mathrm{\phi <!--\; \phi \; -->}$$\varphi$  — функция Эйлера.
• С помощью расширенного алгоритма Евклида вычисляются $d_A$$d_{A}$  и $d_B$$d_{B}$ , обратные числам $e_A$$e_{A}$  и $e_B$$e_{B}$  по модулю $p-<!--\; -\; -->1$$p-1$ :

$d_A={e_A}^{-<!--\; -\; -->1}mod(p-<!--\; -\; -->1)$$d_{A}={e_{A}}^{-1}{\bmod {(}}p-1)$ 

$d_B={e_B}^{-<!--\; -\; -->1}mod(p-<!--\; -\; -->1)$$d_{B}={e_{B}}^{-1}{\bmod {(}}p-1)$ 

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

$e_A\cdot <!--\; \cdot \; -->d_A\equiv <!--\; \equiv \; -->1mod(p-<!--\; -\; -->1)$$e_{A}\cdot {d_{A}\equiv 1{\bmod {(}}p-1)}$ ,

$e_B\cdot <!--\; \cdot \; -->d_B\equiv <!--\; \equiv \; -->1mod(p-<!--\; -\; -->1)$$e_{B}\cdot {d_{B}}\equiv 1{\bmod {(}}p-1)$ .

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

$m^{e_A\cdot <!--\; \cdot \; -->d_A}=mmodp$$m^{e_{A}\cdot {d_{A}}}=m{\bmod {p}}$ , так как

$m^{e_A\cdot <!--\; \cdot \; -->d_A}=m^{j\cdot <!--\; \cdot \; -->\mathrm{\phi <!--\; \phi \; -->}(p)+1}=m^{j\cdot <!--\; \cdot \; -->\mathrm{\phi <!--\; \phi \; -->}(p)}\cdot <!--\; \cdot \; -->m=m$$m^{{e_{A}\cdot {d_{A}}}}=m^{{j\cdot {\varphi (p)+1}}}=m^{{j\cdot {\varphi (p)}}}\cdot {m}=m$ 

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

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

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

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

$m_3=m_2^{d_A}modp=m^{e_A\cdot <!--\; \cdot \; -->e_B\cdot <!--\; \cdot \; -->d_A}modp$$m_{3}=m_{2}^{{d_{A}}}{\bmod p}=m^{{e_{A}\cdot {e_{B}}\cdot {d_{A}}}}{\bmod p}$ .

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

$m_4=m_3^{d_B}modp=m^{d_B\cdot <!--\; \cdot \; -->e_A\cdot <!--\; \cdot \; -->e_B\cdot <!--\; \cdot \; -->d_A}modp=m$$m_{4}=m_{3}^{{d_{B}}}{\bmod p}=m^{{d_{B}\cdot {e_{A}}\cdot {e_{B}}\cdot {d_{A}}}}modp=m$ 

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

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

Данный вариант системы может быть реализован и без использования процедуры возведения в степень в конечных полях, но задача дискретного логарифмирования достаточно сложна для Bob, чтобы тот по $m_1=m^{e_A}$$m_{1}=m^{{e_{A}}}$  не смог определить ключ $m^{e_A}$$m^{{e_{A}}}$  и впредь читать сообщения, ему не предназначавшиеся. Обязательным условием надежности является хорошая система подписи сообщений. Без использования подписей любое постороннее лицо Eva может представиться абонентом Bob и вернуть Alice сообщение вида $m_{\stackrel{~<!--\; ~\; -->}{2}}=m_1^{e_E}modp$$m_{{\tilde {2}}}=m_{1}^{{e_{E}}}{\bmod p}$ . Alice продолжит процедуру и, «сняв свой замок», откроет самозванцу Eva путь к расшифрованию сообщения. В связи с этим, $m_2=m_1^{e_B}modp$$m_{2}=m_{1}^{{e_{B}}}{\bmod p}$  должно сопровождаться аутентификацией.

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

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

$d\equiv <!--\; \equiv \; -->e^{-<!--\; -\; -->1}(\mathrm{mod}N)$$d\equiv {e^{-1}}{\pmod {N}}$ .

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

$e\ast <!--\; \ast \; -->d=jN+1$$e*d=jN+1$ 

Значит для любой точки $P$$P$  эллиптической кривой $\mathrm{\epsilon <!--\; \epsilon \; -->}$$\varepsilon$  порядка $N$$N$  выполняется:

$e\cdot <!--\; \cdot \; -->(d\cdot <!--\; \cdot \; -->P)=(e\cdot <!--\; \cdot \; -->d)P=(j\cdot <!--\; \cdot \; -->N+1)P=(j\cdot <!--\; \cdot \; -->N)P+P=j\cdot <!--\; \cdot \; -->0+P=0+P=P$$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 <!--\; \cdot \; -->(d\cdot <!--\; \cdot \; -->P)=P$$e\cdot (d\cdot P)=P$ .

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

$Q=d\cdot <!--\; \cdot \; -->P$$Q=d\cdot {P}$ 

$R=e\cdot <!--\; \cdot \; -->Q$$R=e\cdot {Q}$ 

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

АлгоритмПравить

• Абонент Alice помещает своё сообщение $m$$m$  в некоторую точку $M(m)$$M(m)$  эллиптической кривой и умножает её на своё секретное значение $e_A$$e_{A}$ , получает точку $P_1=e_A\cdot <!--\; \cdot \; -->M(m)$$P_{1}=e_{A}\cdot {M(m)}$ . Эта точка отправляется абоненту Bob.
• Bob вычисляет $P_2=e_B\cdot <!--\; \cdot \; -->P_1$$P_{2}=e_{B}\cdot {P_{1}}$  и отправляет результат Alice.
• Alice «снимает замок», вычисляя $P_3=d_A\cdot <!--\; \cdot \; -->P_2$$P_{3}=d_{A}\cdot {P_{2}}$ . Возвращает полученный результат абоненту Bob.
• Bob расшифровывает сообщение, используя свой секретный ключ шифрования $d_B$$d_{B}$ :

$M(m)=d_B\cdot <!--\; \cdot \; -->P_3$$M(m)=d_{B}\cdot {P_{3}}$ 

ЛитератураПравить

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