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

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

Алгоритм

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

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

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

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

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

3. Алиса, получив сообщение, вычисляет $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}\mod p=1$ по малой теореме Ферма) и отправляет Бобу:

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

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

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

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

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

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

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

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

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

Реализация

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

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

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

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

$\mathbf {A} \to \mathbf {B} :C_{1}=A\cdot X\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 \mathbf {B} :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.
• С. М. Владимиров, Э. М. Габидулин, А. И. Колыбельников, А. С. Кшевецкий. Криптографические методы защиты информации / под ред. А. В. Уривского. — M. : МФТИ, 2016. — 266 с. — ISBN 978-5-7417-0615-2.