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

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

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

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

   ${\displaystyle Alice\rightarrow \{E_{A}(M)=M^{a}\mod p\}\rightarrow Bob}$.

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

   ${\displaystyle Bob\rightarrow \{E_{B}(E_{A}(M))=M^{ab}\mod p\}\rightarrow Alice}$.

3. Алиса, получив сообщение, вычисляет ${\displaystyle 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}$ (используется коммутативность функции возведения в степень по модулю и свойство ${\displaystyle M^{p-1}\mod p=1}$ по малой теореме Ферма) и отправляет Бобу:

   ${\displaystyle Alice\rightarrow \{E_{B}(M)=M^{b}\}\rightarrow Bob}$.

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

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

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

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

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

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

В случае, если значения параметр ${\displaystyle a}$ или ${\displaystyle b}$ мало, злоумышленник может путем перебора найти значение зашифрованного сообщения^[4]. Не нарушая общности, предположим, что параметр ${\displaystyle a}$ мал. Тогда, последовательно возводя в степень значение ${\displaystyle M_{3}}$ и сравнивая с ${\displaystyle M_{2}}$, злоумышленник может определить значение ${\displaystyle a}$. Зная параметр ${\displaystyle a}$, легко находится ${\displaystyle a'=a^{-1}\mod p-1}$, а следовательно и значение ${\displaystyle M=M_{1}^{a'}\mod p}$.

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

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

${\displaystyle \mathbf {A} \to \mathbf {B} :C_{1}=A\cdot X\cdot B}$,

${\displaystyle \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}$,

${\displaystyle \mathbf {A} \to \mathbf {B} :C_{3}=C\cdot X\cdot D}$,

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

${\displaystyle A\cdot C_{3}\cdot B=C_{2}}$,

и так как матрицы ${\displaystyle A}$, ${\displaystyle B}$, ${\displaystyle C}$ и ${\displaystyle D}$ — унитарные^[8], то будет порядка:

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

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