Preview

Математика и математическое моделирование

Расширенный поиск

Атаки на шифр случайного гаммирования

https://doi.org/10.24108/mathm.0619.0000210

Полный текст:

Аннотация

В 1917 году Гильберт Вернам запатентовал совершенно секретную схему шифрования, которая называлась одноразовым блокнотом, а позднее шифром Вернама. В то время, когда Вернам предложил эту схему, не было никаких доказательств того, что она была совершенно секретной, так как, на самом деле, в то время ещё не было понятия о том, что такое совершенная секретность шифра. Однако, примерно 25 лет спустя Клод Шеннон ввёл определение идеальной секретности (совершенности шифра) и продемонстрировал, что шифр случайного гаммирования достигает такого уровня безопасности. Криптографы считают, что для шифра случайного гаммирования не существует эффективных атак. В частности, не существует эффективных атак для шифра Вернама.

Цель: обосновать ошибочность этого суждения построить эффективные атаки.

Методы: анализ связей ключа шифра с полученным зашифрованным текстом.

Результаты: разработана атака на открытый текст шифра случайного гаммирования по заданному зашифрованному тексту. Кроме того, предложена ещё одна атака на содержимое открытого текста по зашифрованному тексту. Для всех атак проводится расчёт параметров их сложности. Эти результаты являются новыми. До этого не существовало ни одной атаки на шифр случайного гаммирования. Результаты опровергают мнение об отсутствии атак на данный шифр.

Практическая значимость: во-первых, появилась возможность проведения атак на шифр случайного гаммирования. Во-вторых, при использовании этого шифра необходимо строго ограничить длину сообщения.

Обсуждение: мысль о существовании эффективной атаки на шифр случайного гаммирования возникла в 2002 году, в связи с возможностью введения аналогичного понятия, заменяя в определении совершенности шифра открытый текст на ключ. Первая идея создания атак состоит в том, что при длинном ключе его части повторяются. Вторая идея – имеются атаки на два открытых текста, зашифрованных одним ключом. А основной идеей явились мысль о необходимости совершенствовании математической модели шифра К. Шеннона. Именно, при трактовке понятия совершенности шифра следует говорить о совершенности модели шифра.

Место данной публикации: в поисковой системе Яндекс по запросу «Совершенные шифры» нашлось 22 млн. ссылок, по запросу «schemes perfectly secret» нашлось 43 млн. ссылок. Яндекс на запрос «шифр случайного гаммирования» дает 13 млн. результатов.

Об авторе

А. В. Бабаш
Национальный исследовательский университет «Высшая школа экономики», Москва; Российский экономический университет имени Г.В. Плеханова, Москва
Россия
Бабаш Александр Владимирович


Список литературы

1. Shannon C.E. Communication theory of secrecy systems // Bell Systems Technical J. 1949. Vol. 28. No. 4. Pp. 656-715; Claude E. Shannon: Collected papers / ed. by N.J.A. Sloane, A.D. Wyner. N.Y.: Wiley-IEEE Press, 1993. Ch. 2. Pp. 84-143. DOI: 10.1109/9780470544242.ch2

2. Шеннон К.Э. Работы по теории информации и кибернетике: пер. с англ. М.: Изд-во иностр. лит, 1963. 829 с.

3. Katz J., Lindell Y. Introduction to modern cryptography. Boca Raton: Chapman & Hall: CRC Press, 2008. 534 p.

4. Sсhneier B. Applied cryptography: Protocols, algorithms and source code in C. 2nd ed. N.Y.: Wiley, 1996. 758 р.

5. Шнайер Б. Секреты и ложь: Безопасность данных в цифровом мире: пер с англ. М. и др.: Питер, 2003. 367 с. [Sсhneier B. Secrets and lies: Digital security in a networked world. N.Y.: Wiley, 2000. 412 p.].

6. Запечников С. В., Казарин О.В., Тарасов А.А. Криптографические методы защиты информации: учеб. М.: Юрайт, 2017. 309 с.

7. Основы криптографии: учеб. пособие / А.П. Алферов, А.Ю. Зубков, А.С. Кузьмин и др. 2-е изд. М.: Гелиос АРВ, 2002. 480 с.

8. Diffie W., Hellman M.E. Privacy and authentication: An introduction to cryptography // Proc. of the IEEE. 1979. Vol. 67. No. 3. Pp. 397-427. DOI: 10.1109/PROC.1979.11256

9. Авдошин С.М., Савельева А.А. Криптоанализ: современное состояние и перспективы развития // Информационные технологии. 2007. Прил. к журн. № 3. С. 1-32.

10. Зубов А.Ю. Совершенные шифры. М.: Гелиос АРВ, 2003. 160 c.

11. Жданов О.Н, Золотарев В.В. Методы и средства криптографической защиты информации: учеб. пособие. Красноярск: Изд-во Сибир. гос. аэрокосмич. ун-та (СибГАУ), 2007. 217 с.

12. Golomb S.W., Berlekamp E., Cover T.M., Gallager R.G., Massey J.L., Viterbi A.J. Claude Elwood Shannon (1916 – 2001) // Notices of the Amer. Math. Soc. 2002. Vol. 49. No. 1. Pp. 8-16.

13. Фомичев В.М. Дискретная математика и криптология: Курс лекций. М.: Диалог-МИФИ, 2003. 400 c.

14. Ferguson N., Schneier B. Practical cryptography. N.Y.: Wiley, 2003. 410 p.

15. Encyclopedia of cryptography and security / Ed. by C.A. Henk van Tilborg, Sushil Jajodia. 2nd ed. N.Y.: Springer, 2011. Vol. 1-2. 1475 p.

16. Mohamed Barakat, Eder Ch., Hanke T. An introduction to cryptography. 2nd ed. Technische Univ. Kaiserlautern, 2018. 138 p.

17. Buchmann J. Introduction to cryptography. N.Y.: Springer, 2012. 281 p.

18. Stinson D.R. Cryptography: Theory and practice. 3rd ed. Boca Raton : Chapman & Hall/CRC, 2006. 593 p.

19. Trappe W., Washington L.C. Introduction to cryptography: with coding theory. 2nd ed. Upper Saddle River: Pearson Prentice-Hall, 2006. 577 p.

20. Carroll J.M, Martin S. The automated cryptanalysis of substitution ciphers // Cryptologia. 1986. Vol. 10. No. 4. Pp. 193-209. DOI: 10.1080/0161-118691861001

21. Aumasson J.-P. Serious cryptography: a practical introduction to modern encryption. San Francisco: No Starch Press, [2017]. 282 p.

22. Бабаш А.В., Баранова Е.К. Совершенные шифры и как к ним относиться // Методы и технические средства обеспечения безопасности информации: 27-я науч.-техн. конф. (С.-Петербург, Россия, 24-27 сентября 2018 года): Материалы. СПб.: Изд-во С.-Петербург. политехн. ун-та, 2018. С. 77-81.

23. Babash A.V., Sizov V.A., Baranova E.K., Mikrukov A.A. Theoretically unbreakable ciphers as they should be understood // Современные информационные технологии и ИТ-образование. 2018. Т. 14. № 3. С. 573-577. DOI: 10.25559/SITITO.14.201803

24. Бабаш А.В., Баранова Е.К. Новый совершенный шифр тук-тук // Методы и технические средства обеспечения безопасности информации: 27-я науч.-техн. конф. (С.-Петербург, Россия, 24-27 сентября 2018 года): Материалы. СПб.: Изд-во С.-Петербург. Политехн. ун-та, 2018. C. 70-72.

25. Бабаш А.В., Шанкин Г.П. Криптография: учеб. пособие. М.: СОЛОН-ПРЕСС, 2007. 512 с.

26. Бабаш А.В., Баранова Е.К. Избранные вопросы криптоанализа шифра случайного гаммирования // Методы и технические средства обеспечения безопасности информации: 28-я науч.-техн. конф. (С.-Петербург, Россия, 24-27 июня 2019 г.): Материалы. СПб.: Изд-во С.-Петербург. Политехн. ун-та, 2019. С. 76-77.

27. Friedman W. F. The index of coincidence and its applications in cryptography. Geneva, Ill.: Riverbank Laboratories, 1922. 87 p.

28. Carroll J.M., Robbins L.E. Computer cryptanalysis of product ciphers // Cryptologia. 1989. Vol. 13. No. 4. Pp. 303-326. DOI: 10.1080/0161-118991863989

29. Denning D.E.R. Cryptography and data security. Reading, Mass.: Addison-Wesley, 1982. 400 p.

30. Gaines H.F. Cryptanalysis: A study of ciphers and their solution. [2nd ed.]. N.Y.: Dover Publ., 1956. 244 p.

31. Kahn D. The codebreakers: The story of secret writing. N.Y.: McMillan Publ. Co., 1967. 1164 p.

32. King J.C., Bahler D.R. An implementation of probabilistic relaxation in the cryptanalysis of simple substitution ciphers // Cryptologia. 1992. Vol. 16. No. 3. Pp. 215-225. DOI: 10.1080/0161-119291866892

33. Matthews R. An empirical method for finding the keylength of periodic ciphers // Cryptologia. 1988. Vol. 12. No. 4. Pp. 220-224. DOI: 10.1080/0161-118891862963

34. King J.C. An algorithm for the complete automated cryptanalysis of periodic polyalphabetic substitution ciphers // Cryptologia. 1994. Vol. 18. No. 4. Pp. 332-355. DOI: 10.1080/0161-119491882928

35. Kasiski F.W. Die Geheimschriften und die Dechiffrir-Kunst. B.: Mittler & Sohn, 1863. 95 p.

36. Васильева И.Н. Криптографические методы защиты информации: учеб. М.: Юрайт, 2016. 349 c.

37. Салий В.Н. Криптографические методы и средства защиты информации: учеб. пособие. Саратов, 2017. 43 с.

38. Цыганов А.В. Криптография и криптоанализ. СПб.: Изд-во С.-Петербург. гос. ун-та, 2009. 60 с.

39. Реализация и криптоанализ шифра гаммирования / Чертоги разума: личный блог Кузьминых Кирилла. Режим доступа: http://mindhalls.ru/gamma-code/ (дата обращения 12.08.2019).

40. Banks M.J. A search-based tool for the automated cryptanalysis of classical ciphers. The Univ. of York; Dep. of Computer Science, 2008. 76 p.

41. Бабаш А.В. Криптографические методы защиты информации: учебно-метод. пособие. 2-е изд. Т. 1. М.: РИОР: ИНФРА-М, 2013. 412 с.

42. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2002. 955 с. [Cormen T., Leiserson Ch., Rivest R. Introduction to algorithms. Camb.: MIT Press; N.Y.: McGraw-Hill, 1990. 1028 p.].

43. Kullback S. Statistical methods in cryptanalysis / War Dep.; Office of the Chief Signal Officer; Signal Intelligence Service. Revised ed. Wash.: U.S. Government Printing Office, 1959. 206 p.

44. Omolara A.E., Oludare I.A., Aman Bin Jantan, Humaira Arshad. An enhanced practical difficulty of one-time pad algorithm resolving the key management and distribution problem // Intern. MultiConf. of Engineers and Computer Scientists: IMECS 2018 (Hong Kong, March 14-16, 2018): Proc. Vol. 1. 2018. Pp. 409-415.

45. Lee C.-Y., Wang Z.-H., Harn L., Chang C.-C. Secure key transfer protocol based on secret sharing for group communications // IEICE Trans. on Information and Systems. 2011. Vol. E94-D. No. 11. Pp. 2069–2076. DOI: 10.1587/transinf.E94.D.2069

46. Yingbin Liang, Poor H.V., Shiomo Shamai (Shitz). Information-theoretic security // Foundations and Trends in Communications and Information Theory. 2009. Vol. 5. No. 4-5. Pp. 355-580. DOI: 10.1561/0100000036

47. Maurer U., Wolf S. The intrinsic conditional mutual information and perfect secrecy // IEEE intern. symp. on information theory: ISIT 1997 (Ulm, Germany, June 29–July 4, 1997): Proc. N.Y.: IEEE, 1997. P. 88. DOI: 10.1109/ISIT.1997.613003

48. Stallings W. Cryptography and network security: principles and practice. 5th ed. Boston: Prentice Hall, 2011. 719 p.

49. Godlewsky P., Mitchell C. Key-minimal cryptosystems for unconditional secrecy // J. of Cryptology. 1990. Vol. 3. No. 1. Pp. 1-25. DOI: 10.1007/BF00203966

50. Kessler G.C. An overview of cryptography. 2019. 65 p. Режим доступа: http://works.bepress.com/gary_kessler/67 (дата обращения 6.02.20).

51. Poonam Jindal, Brahmjit Singh. RC4 encryption - a literature survey // Procedia Computer Science. 2015. Vol. 46. Pp. 697-705. DOI: 10.1016/j.procs.2015.02.129

52. Johansson T., Jönsson F. On the complexity of some cryptographic problems based on the general decoding problem // IEEE Trans. on Information Theory. 2002. Vol. 48. No. 10. Pp. 2669–2678. DOI: 10.1109/TIT.2002.802608


Для цитирования:


Бабаш А.В. Атаки на шифр случайного гаммирования. Математика и математическое моделирование. 2019;(6):35-58. https://doi.org/10.24108/mathm.0619.0000210

For citation:


Babash A.V. Attacks on the Random Gamming Code. Mathematics and Mathematical Modeling. 2019;(6):35-58. (In Russ.) https://doi.org/10.24108/mathm.0619.0000210

Просмотров: 553


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2412-5911 (Online)