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

(перенаправлено с «Протокол Шамира»)

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

Алгоритм

править

Используется шифрование на основе функции возведения в степень по модулю[2][3]. Выбирают достаточно большое простое число  , для которого   имеет большой простой множитель. В информационном взаимодействии участвуют два пользователя: Алиса и Боб.

  1. Алиса выбирает число  , взаимно простое с  . Также Алиса использует число   такое, что  , то есть  . Алиса шифрует сообщение   и отправляет шифр Бобу:
     .
  2. Получатель Боб аналогично выбирает целое число  , взаимно простое с  , и число   такое, что  . Боб отправляет обратно следующее сообщение:
     .
  3. Алиса, получив сообщение, вычисляет   (используется коммутативность функции возведения в степень по модулю и свойство   по малой теореме Ферма) и отправляет Бобу:
     .
  4. Боб расшифровывает сообщение:  .

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

 
 
 

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

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

править

В случае, если значения параметр   или   мало, злоумышленник может путем перебора найти значение зашифрованного сообщения[4]. Не нарушая общности, предположим, что параметр   мал. Тогда, последовательно возводя в степень значение   и сравнивая с  , злоумышленник может определить значение  . Зная параметр  , легко находится  , а следовательно и значение  .

Реализация

править

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

править

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

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

править

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

 ,
 ,
 ,

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

 ,

и так как матрицы  ,  ,   и   — унитарные[8], то будет порядка:

 

переменных в уравнении для пиксельного изображения размером  , в то время как имеется только   или   линейных уравнений, поэтому достаточно трудно восстановить   и  . Кроме того, эти матрицы обычно сингулярны (число условий чрезвычайно велико), поскольку они могут иметь много почти нулевых собственных значений. Также трудно восстановить секретное изображение   путём простой инверсии матрицы из-за влияния шума или вычислительной ошибки.

Устойчивость к потере данных

править

Исследователи провели опыт, чтобы проверить переносимость к потере данных. Для этого они закрыли 25 %, 50 % и 75 % пикселей изображения. После всех трех передач и проведения дешифрований все три изображения визуально распознавались. Для дальнейшего улучшения качества этих восстановленных изображений можно выполнить цифровой метод пост-обработки. Данная схема распределяет входное изображение по всей выходной плоскости, тем самым обеспечивая устойчивость к искажениям из-за потери зашифрованных данных.

Примечания

править
  1. 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.
  2. 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 года.
  3. 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 года.
  4. С. М. Владимиров, Э. М. Габидулин, А. И. Колыбельников, А. С. Кшевецкий. Криптографические методы защиты информации / под ред. А. В. Уривского. — M. : МФТИ, 2016. — 266 с. — ISBN 978-5-7417-0615-2.
  5. 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 года.
  6. 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.
  7. 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.
  8. 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.