Трёхэтапный протокол Шамира — криптографический трёхэтапный протокол, разработанный Ади Шамиром около 1980 года[1]. Протокол позволяет двум сторонам безопасно обмениваться сообщениями без необходимости распространения ключей шифрования. Обмен сообщением между пользователями происходит в три прохода.
Используется шифрование на основе функции возведения в степень по модулю[2][3]. Выбирают достаточно большое простое число , для которого имеет большой простой множитель. В информационном взаимодействии участвуют два пользователя: Алиса и Боб.
Алиса выбирает число , взаимно простое с . Также Алиса использует число такое, что , то есть . Алиса шифрует сообщение и отправляет шифр Бобу:
.
Получатель Боб аналогично выбирает целое число , взаимно простое с , и число такое, что . Боб отправляет обратно следующее сообщение:
.
Алиса, получив сообщение, вычисляет (используется коммутативность функции возведения в степень по модулю и свойство по малой теореме Ферма) и отправляет Бобу:
.
Боб расшифровывает сообщение: .
Если третья сторона перехватила все три сообщения:
Чтобы вычислить при корректно выбранных параметрах и , нужно решить систему из этих трех уравнений, что имеет очень большую вычислительную сложность, так как нужно решать задачу дискретного логарифма.
Атака на протокол Шамира
В случае, если значения параметр или мало, злоумышленник может путем перебора найти значение зашифрованного сообщения[4]. Не нарушая общности, предположим, что параметр мал. Тогда, последовательно возводя в степень значение и сравнивая с , злоумышленник может определить значение . Зная параметр , легко находится , а следовательно и значение .
Реализация
Схема безопасного обмена изображениями
В 2008 году[5][6] предложено обобщенное дробное преобразование Фурье — многопараметрическое дробное преобразование Фурье (MPFRFT[7]), которое сохраняет все желаемые свойства дробного преобразования Фурье[англ.] без использования фазовых ключей. Для оптического кодирования изображений непосредственно по спектру MPFRFT было предложено использовать свою функцию с несколькими параметрами. Дальнейший обмен изображениями между пользователями должен происходить по протоколу Шамира.
Стойкость к атакам посредника
Если злоумышленник соберет все три сообщения:
,
,
,
где , , и — дискретные многопараметрические дробные матрицы преобразования Фурье (DMPFRFT[8]). Из зашифрованной информации третья сторона может получить следующее уравнение:
,
и так как матрицы , , и — унитарные[8], то будет порядка:
переменных в уравнении для пиксельного изображения размером , в то время как имеется только или линейных уравнений, поэтому достаточно трудно восстановить и . Кроме того, эти матрицы обычно сингулярны (число условий чрезвычайно велико), поскольку они могут иметь много почти нулевых собственных значений. Также трудно восстановить секретное изображение путём простой инверсии матрицы из-за влияния шума или вычислительной ошибки.
Устойчивость к потере данных
Исследователи провели опыт, чтобы проверить переносимость к потере данных. Для этого они закрыли 25 %, 50 % и 75 % пикселей изображения. После всех трех передач и проведения дешифрований все три изображения визуально распознавались. Для дальнейшего улучшения качества этих восстановленных изображений можно выполнить цифровой метод пост-обработки. Данная схема распределяет входное изображение по всей выходной плоскости, тем самым обеспечивая устойчивость к искажениям из-за потери зашифрованных данных.
Примечания
↑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.
↑С. М. Владимиров, Э. М. Габидулин, А. И. Колыбельников, А. С. Кшевецкий. Криптографические методы защиты информации / под ред. А. В. Уривского. — M. : МФТИ, 2016. — 266 с. — ISBN 978-5-7417-0615-2.
↑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.
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.