Трёхэтапный протокол Шамира — криптографический трёхэтапный протокол, разработанный Ади Шамиром около 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.
- ↑ J. L. Massey. An introduction to contemporary cryptology // Proceedings of the IEEE. — May 1988. — Т. 76, вып. 5. — С. 533–549. — ISSN 0018-9219. — doi:10.1109/5.4440. Архивировано 13 июня 2018 года.
- ↑ U. Carlsen. Cryptographic protocol flaws: know your enemy // Proceedings The Computer Security Foundations Workshop VII. — Franconia, NH, USA: IEEE Comput. Soc. Press, 1994. — С. 192–200. — ISBN 978-0-8186-6230-0. — doi:10.1109/CSFW.1994.315934. Архивировано 16 февраля 2022 года.
- ↑ С. М. Владимиров, Э. М. Габидулин, А. И. Колыбельников, А. С. Кшевецкий. Криптографические методы защиты информации / под ред. А. В. Уривского. — M. : МФТИ, 2016. — 266 с. — ISBN 978-5-7417-0615-2.
- ↑ Jun Lang, Ran Tao, QiWen Ran, Yue Wang. The multiple-parameter fractional Fourier transform (англ.) // Science in China Series F: Information Sciences. — 2008-08-01. — Vol. 51, iss. 8. — P. 1010. — ISSN 1862-2836 1009-2757, 1862-2836. — doi:10.1007/s11432-008-0073-6. Архивировано 22 декабря 2017 года.
- ↑ 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.
- ↑ Ran Tao, Jun Lang, Yue Wang. Optical image encryption based on the multiple-parameter fractional Fourier transform (EN) // Optics Letters. — 2008-03-15. — Т. 33, вып. 6. — С. 581–583. — ISSN 1539-4794. — doi:10.1364/OL.33.000581.
- ↑ 1 2 Jun Lang, Ran Tao, Yue Wang. The discrete multiple-parameter fractional Fourier transform (англ.) // Science China Information Sciences. — 2010-11-01. — Vol. 53, iss. 11. — P. 2287–2299. — ISSN 1869-1919 1674-733X, 1869-1919. — doi:10.1007/s11432-010-4095-5. Архивировано 22 декабря 2017 года.
Литература
править- 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.