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

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

Алгоритм

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

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

   $Alice\to \{E_A(M)=M^{a}modp\}\to Bob$.

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

   $Bob\to \{E_B(E_A(M))=M^{ab}modp\}\to 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}modp$ (используется коммутативность функции возведения в степень по модулю и свойство $M^{p-1}modp=1$ по малой теореме Ферма) и отправляет Бобу:

   $Alice\to \{E_B(M)=M^b\}\to Bob$.

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

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

$M_1=M^{a}modp$

$M_2=M^{ab}modp$

$M_3=M^{b}modp$

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

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

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

Реализация

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

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

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

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

$𝐀\to 𝐁:C_1=A\cdot X\cdot B$,

$𝐁\to 𝐀:C_2=C\cdot A\cdot X\cdot B\cdot D=A\cdot C\cdot X\cdot D\cdot B$,

$𝐀\to 𝐁:C_3=C\cdot X\cdot D$,

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

$A\cdot C_3\cdot B=C_2$,

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

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

переменных в уравнении для пиксельного изображения размером $N\times M$, в то время как имеется только $N$ или $M$ линейных уравнений, поэтому достаточно трудно восстановить $A$ и $B$. Кроме того, эти матрицы обычно сингулярны (число условий чрезвычайно велико), поскольку они могут иметь много почти нулевых собственных значений. Также трудно восстановить секретное изображение $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.
• Шаблон:Книга