Трёхэтапный протокол Шамира

Трёхэтапный протокол Шамира — криптографический трёхэтапный протокол, разработанный Ади Шамиром около 1980 года. Протокол позволяет двум сторонам безопасно обмениваться сообщениями без необходимости распространения ключей шифрования. Обмен сообщением между пользователями происходит в три прохода.

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

Используется шифрование на основе функции возведения в степень по модулю. Выбирают достаточно большое простое число $p\sim <!--\; \sim \; -->2^{1024}$$p\sim 2^{1024}$ , для которого $p-<!--\; -\; -->1$$p-1$  имеет большой простой множитель. В информационном взаимодействии участвуют два пользователя: Алиса и Боб.

1. Алиса выбирает число $a$$a$ , взаимно простое с $p-<!--\; -\; -->1$$p-1$ . Также Алиса использует число $a^{\prime }$$a'$  такое, что $a{a}^{\prime }\mathrm{mod}(p-<!--\; -\; -->1)=1$$aa'\mod (p-1)=1$ , то есть $a{a}^{\prime }=1+n(p-<!--\; -\; -->1),n\in <!--\; \in \; -->\mathbb{Z}$$aa'=1+n(p-1),n\in \mathbb {Z}$ . Алиса шифрует сообщение $M$$M$  и отправляет шифр Бобу:

   $Alice\to <!--\; \to \; -->\{E_A(M)=M^a\mathrm{mod}p\}\to <!--\; \to \; -->Bob$$Alice\rightarrow \{E_{A}(M)=M^{a}\mod p\}\rightarrow Bob$ .

2. Получатель Боб аналогично выбирает целое число $b$$b$ , взаимно простое с $p-<!--\; -\; -->1$$p-1$ , и число $b^{\prime }$$b'$  такое, что $b{b}^{\prime }\mathrm{mod}(p-<!--\; -\; -->1)=1$$bb'\mod (p-1)=1$ . Боб отправляет обратно следующее сообщение:

   $Bob\to <!--\; \to \; -->\{E_B(E_A(M))=M^{ab}\mathrm{mod}p\}\to <!--\; \to \; -->Alice$$Bob\rightarrow \{E_{B}(E_{A}(M))=M^{ab}\mod p\}\rightarrow Alice$ .

3. Алиса, получив сообщение, вычисляет $D_A(M^{ab})=(M^{ab}{)}^{a^{\prime }}=M^{b(1+n(p-<!--\; -\; -->1))}=M^b{M}^{n(p-<!--\; -\; -->1)b}=M^b(M^{p-<!--\; -\; -->1}{)}^{nb}=M^b\mathrm{mod}p$$D_{A}(M^{ab})=(M^{ab})^{a'}=M^{b(1+n(p-1))}=M^{b}M^{n(p-1)b}=M^{b}(M^{p-1})^{nb}=M^{b}\mod p$  (используется коммутативность функции возведения в степень по модулю и свойство $M^{p-<!--\; -\; -->1}\mathrm{mod}p=1$$M^{p-1}\mod p=1$  по малой теореме Ферма) и отправляет Бобу:

   $Alice\to <!--\; \to \; -->\{E_B(M)=M^b\}\to <!--\; \to \; -->Bob$$Alice\rightarrow \{E_{B}(M)=M^{b}\}\rightarrow Bob$ .

4. Боб расшифровывает сообщение: $D_B(M^b)=(M^b{)}^{b^{\prime }}\mathrm{mod}p=M$$D_{B}(M^{b})=(M^{b})^{b'}\mod p=M$ .

Если третья сторона перехватила все три сообщения:

$M_1=M^a\mathrm{mod}p$$M_{1}=M^{a}\mod p$ 

$M_2=M^{ab}\mathrm{mod}p$$M_{2}=M^{ab}\mod p$ 

$M_3=M^b\mathrm{mod}p$$M_{3}=M^{b}\mod p$ 

Чтобы вычислить $M$$M$  при корректно выбранных параметрах $a$$a$  и $b$$b$ , нужно решить систему из этих трех уравнений, что имеет очень большую вычислительную сложность, так как нужно решать задачу дискретного логарифма.

Атака на протокол ШамираПравить

В случае, если значения параметр $a$$a$  или $b$$b$  мало, злоумышленник может путем перебора найти значение зашифрованного сообщения. Не нарушая общности, предположим, что параметр $a$$a$  мал. Тогда, последовательно возводя в степень значение $M_3$$M_{3}$  и сравнивая с $M_2$$M_{2}$ , злоумышленник может определить значение $a$$a$ . Зная параметр $a$$a$ , легко находится $a^{\prime }=a^{-<!--\; -\; -->1}\mathrm{mod}p-<!--\; -\; -->1$$a'=a^{-1}\mod p-1$ , а следовательно и значение $M=M_1^{a^{\prime }}\mathrm{mod}p$$M=M_{1}^{a'}\mod p$ .

РеализацияПравить

Схема безопасного обмена изображениямиПравить

В 2008 году предложено обобщенное дробное преобразование Фурье — многопараметрическое дробное преобразование Фурье (MPFRFT), которое сохраняет все желаемые свойства дробного преобразования Фурье^[en] без использования фазовых ключей. Для оптического кодирования изображений непосредственно по спектру MPFRFT было предложено использовать свою функцию с несколькими параметрами. Дальнейший обмен изображениями между пользователями должен происходить по протоколу Шамира.

Стойкость к атакам посредникаПравить

Если злоумышленник соберет все три сообщения:

$\mathbf{A}\to <!--\; \to \; -->\mathbf{B}:C_1=A\cdot <!--\; \cdot \; -->X\cdot <!--\; \cdot \; -->B$$\mathbf {A} \to \mathbf {B} :C_{1}=A\cdot X\cdot B$ ,

$\mathbf{B}\to <!--\; \to \; -->\mathbf{A}:C_2=C\cdot <!--\; \cdot \; -->A\cdot <!--\; \cdot \; -->X\cdot <!--\; \cdot \; -->B\cdot <!--\; \cdot \; -->D=A\cdot <!--\; \cdot \; -->C\cdot <!--\; \cdot \; -->X\cdot <!--\; \cdot \; -->D\cdot <!--\; \cdot \; -->B$$\mathbf {B} \to \mathbf {A} :C_{2}=C\cdot A\cdot X\cdot B\cdot D=A\cdot C\cdot X\cdot D\cdot B$ ,

$\mathbf{A}\to <!--\; \to \; -->\mathbf{B}:C_3=C\cdot <!--\; \cdot \; -->X\cdot <!--\; \cdot \; -->D$$\mathbf {A} \to \mathbf {B} :C_{3}=C\cdot X\cdot D$ ,

где $A$$A$ , $B$$B$ , $C$$C$  и $D$$D$  — дискретные многопараметрические дробные матрицы преобразования Фурье (DMPFRFT). Из зашифрованной информации третья сторона может получить следующее уравнение:

$A\cdot <!--\; \cdot \; -->C_3\cdot <!--\; \cdot \; -->B=C_2$$A\cdot C_{3}\cdot B=C_{2}$ ,

и так как матрицы $A$$A$ , $B$$B$ , $C$$C$  и $D$$D$  — унитарные, то будет порядка:

$\frac{N(N+1)}{2}+\frac{M(M+1)}{2}$${\frac {N(N+1)}{2}}+{\frac {M(M+1)}{2}}$ 

переменных в уравнении для пиксельного изображения размером $N\times <!--\; \times \; -->M$$N\times M$ , в то время как имеется только $N$$N$  или $M$$M$  линейных уравнений, поэтому достаточно трудно восстановить $A$$A$  и $B$$B$ . Кроме того, эти матрицы обычно сингулярны (число условий чрезвычайно велико), поскольку они могут иметь много почти нулевых собственных значений. Также трудно восстановить секретное изображение $X$$X$  путём простой инверсии матрицы из-за влияния шума или вычислительной ошибки.

Устойчивость к потере данныхПравить

Исследователи провели опыт, чтобы проверить переносимость к потере данных. Для этого они закрыли 25 %, 50 % и 75 % пикселей изображения. После всех трех передач и проведения дешифрований все три изображения визуально распознавались. Для дальнейшего улучшения качества этих восстановленных изображений можно выполнить цифровой метод пост-обработки. Данная схема распределяет входное изображение по всей выходной плоскости, тем самым обеспечивая устойчивость к искажениям из-за потери зашифрованных данных.

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

• J. Massey, An introduction to contemporary cryptology, Proc. IEEE 76(5), 533—549 (1988)
• U. Carlsen, Cryptographic protocol flaws: know your enemy, Proceedings The Computer Security Foundations Workshop VII, 1994, pp. 192—200, doi: 10.1109/CSFW.1994.315934.
• Oktaviana B., Siahaan A. P. U. Three-Pass Protocol Implementation on Caesar Cipher in Classic Cryptography //IOSR Journal of Computer Engineering (IOSR-JCE). — 2016. — Т. 18. — №. 4.
• Lang J. A no-key-exchange secure image sharing scheme based on Shamir’s three-pass cryptography protocol and the multiple-parameter fractional Fourier transform //Optics express. — 2012. — Т. 20. — №. 3. — С. 2386—2398.
• С. М. Владимиров, Э. М. Габидулин, А. И. Колыбельников, А. С. Кшевецкий. Криптографические методы защиты информации / под ред. А. В. Уривского. — M. : МФТИ, 2016. — 266 с. — ISBN 978-5-7417-0615-2.