Preview

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

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

Исследование практической возможности решения связанных с криптоанализом задач на обобщенных клеточных автоматах алгебраическими методами

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

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

Аннотация

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

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

Криптоанализ основанный на построении системы полиномиальных уравнений, которая связывает открытый текст, шифртекст и ключ, и решении ее алгебраическими методами, обычно называется алгебраическим криптоанализом. Одними из основных методов решения систем полиномиальных уравнений являются методы, связанные с построением базисов Грёбнера.

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

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

 С помощью программы, написанной на языке Python, генерировались случайные 6-регулярные графы Рамануджана с необходимым числом вершин. Для каждого графа генерировалась система уравнений, описывающая k шагов соответствующего обобщенного клеточного автомата. Для полученных систем строились базисы Гребнера с помощью алгоритма Фужера F4, посредством системы Magma v2.21-5 и посредством библиотеки Polybori 0.8.3.  Эксперименты проводились как для задачи обращения, так и для задачи восстановления ключа. Использовался компьютер с 16-ю ядрами Intel Xeon E5-2690 и 16 ГБ ОЗУ, работающем под управлением OS Linux.

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

Об авторе

П. Г. Ключарёв
МГТУ им. Н.Э. Баумана
Россия


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

1. Аржанцев И.В. Базисы Грёбнера и системы алгебраических уравнений. М.: МЦНМО, 2003. 68 с.

2. Компьютерная алгебра: Символические и алгебраические вычисления / Бухбергер Б., Калме Ж., Калтофен Э. и др.; под ред. Н.Н. Говоруна. М.: Мир, 1986. 391 с. [Computer algebra: symbolic and algebraic computation / Ed. by B. Buchberger. W.; N.Y.: Springer, 1982. 283 p.].

3. Ключарёв П.Г. Блочные шифры, основанные на обобщённых клеточных автоматах // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 12. С. 361-374. DOI: 10.7463/0113.0517543

4. Ключарёв П.Г. Построение псевдослучайных функций на основе обобщённых клеточных автоматов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 10. С. 263-274. DOI: 10.7463/1112.0496381

5. Ключарёв П.Г. Криптографические хэш-функции, основанные на обобщённых клеточных автоматах // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2013. № 1. С. 161-172. DOI: 10.7463/0113.0534640

6. Ключарёв П.Г. Построение случайных графов, предназначенных для применения в криптографических алгоритмах, основанных на обобщенных клеточных автоматах // Математика и математическое моделирование. Электрон. журн. 2017. № 3. С. 77-90. DOI: 10.24108/mathm.0317.0000076

7. Кокс Д., Литтл Дж., О’Ши Д. Идеалы, многообразия и алгоритмы. Введение в вычислительные аспекты алгебраической геометрии и коммутативной алгебры. М.: Мир, 2000. 687 с. [Cox D., Little J., O’Shea D. Ideals, varieties and algorithms: An introduction to computational algebraic geometry and commutative algebra. 2nd ed. N.Y.: Springer, 1998. 536 p.].

8. Bard G.V. Algebraic cryptanalysis. Dordrecht; N.Y.: Springer, 2009. 356 p.

9. Becker Th., Kredel H., Weispfenning V. Gröbner bases: A computational approach to commutative algebra. N.Y.: Springer, 2012. 576 p.

10. Bosma W., Cannon J., Playoust C. The Magma algebra system. I: The user language // J. of Symbolic Computation. 1997. Vol. 24. No. 3-4. Pp. 235-265. DOI: 10.1006/jsco.1996.0125

11. Brickenstein M., Dreyer A. POLYBoRI: A framework for Gröbner-basis computations with Boolean polynomials // J. of Symbolic Computation. 2009. Vol. 44. No. 9. Pp. 1326-1345. DOI: 10.1016/j.jsc.2008.02.017

12. Buchberger B. An algorithm for finding a basis for the residue class ring of a zero-dimensional polynomial ideal. Ph.D. thesis. Innsbruck, 1965. 58 s.

13. Gröbner bases and applications / Ed. by B. Buchberger, F. Winkler. Camb.; N.Y.: Camb. Univ. Press, 1998. 552 p.

14. Buchmann J., Pyshkin A., Weinmann R.-P. Block ciphers sensitive to Gröbner basis attacks // Topics in Cryptology–CT-RSA 2006. B.; Hdbl.: Springer, 2006. Pp. 313-331. DOI: 10.1007/11605805_20

15. Cid C., Weinmann R.-Ph. Block ciphers: algebraic cryptanalysis and Gröbner bases // Gröbner bases, coding, and cryptography. B.; Hdbl.: Springer, 2009. Pp. 307-327. DOI: 10.1007/978-3-540-93806-4_17

16. Courtois N.T. General principles of algebraic attacks and new design criteria for cipher components // Advanced encryption standard – AES. B.; Hdbl.: Springer, 2005. Pp. 67-83. DOI: 10.1007/11506447_7

17. Courtois N.T. How fast can be algebraic attacks on block ciphers? // Symmetric Cryptography: Dagstuhl Seminar (Schloss Dagstuhl, Germany, January 7-12, 2007): Proceedings no. 07021. 2007. Режим доступа: http://drops.dagstuhl.de/opus/volltexte/2007/1013/pdf/07021.CourtoisNicolas.Paper.1013.pdf (дата обращения 13.10.2017).

18. Davidoff G., Sarnak P., Valette A. Elementary number theory, group theory and Ramanujan graphs. N.Y.: Camb. Univ. Press, 2003. 144 p.

19. Ene V., Herzog J. Gröbner bases in commutative algebra. Providence: Amer. Math. Soc. 2012. 164 p.

20. Faugere J.-C. A new efficient algorithm for computing Gröbner bases (F4) // J. of Pure and Applied Algebra. 1999. Vol. 139. No. 1-3. Pp. 61-88. DOI: 10.1016/S0022-4049(99)00005-5

21. Faugere J.-C. A new efficient algorithm for computing Gröbner bases without reduction to zero (F5) // 2002 Intern. Symp. on symbolic and algebraic computation: ISSAC’02 (Lille, France, July 7-10, 2002): Proc. N.Y.: ACM Press, 2002. Pp. 75-83. DOI: 10.1145/780506.780516

22. Fröberg R. An introduction to Gröbner bases. Chichester; N.Y.: Wiley, 1997. 177 p.

23. Handbook of Magma functions (Provisional). Version 2.20 / Ed. by W. Bosma, J. Cannon, C. Fieker, A. Steel. Sydney, 2014. 5583 p.

24. Hoory S., Linial N., Wigderson A. Expander graphs and their applications // Bull. of the Amer. Math. Soc. 2006. Vol. 43. No. 4. Pp. 439-562.

25. Joux A. Algorithmic cryptanalysis. Boca Raton: CRC Press, 2009. 501 p.

26. Lazard D. Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations // Computer algebra: EUROCAL’83: European computer algebra conf. (London, England, March 28-30, 1983): Proc. B.; Hdbl.: Springer, 1983. Pp. 146-156. DOI: 10.1007/3-540-12868-9_99

27. Li H. Gröbner bases in ring theory. Singapore: World Scientific, 2012. 284 p.

28. Lubotzky A., Phillips R., Sarnak P. Ramanujan graphs // Combinatorica. 1988. Vol. 8. No. 3. Pp. 261-277. DOI: 10.1007/BF02126799

29. Minato Sh. Zero-suppressed BDDs for set manipulation in combinatorial problems // 30th Intern. design automation conf.: DAC’98 (Dallas, Texas, USA, June 14-18, 1993): Proc. N.Y.: ACM, 1993. Pp. 272-277. DOI: 10.1145/157485.164890

30. Minato Sh. Zero-suppressed BDDs and their applications // Intern. J. on Software Tools for Technology Transfer (STTT). 2001. Vol. 3. No. 2. Pp. 156-170. DOI: 10.1007/s100090100038

31. Mishchenko A. An introduction to zero-suppressed binary decision diagrams. Режим доступа: https://people.eecs.berkeley.edu/~alanmi/publications/2001/tech01_zdd_.pdf (дата обращения 13.10.2017).

32. Steger A., Wormald N.C. Generating random regular graphs quickly // Combinatorics, Probability and Computing. 1999. Vol. 8. No. 4. Pp. 377-396.

33. Sturmfels B. What is... a Gröbner basis? // Notices of the Amer. Math. Soc. 2005. Vol. 52. No. 10. Pp. 1199-1200.


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


Ключарёв П.Г. Исследование практической возможности решения связанных с криптоанализом задач на обобщенных клеточных автоматах алгебраическими методами. Математика и математическое моделирование. 2017;(5):29-44. https://doi.org/10.24108/mathm.0517.0000080

For citation:


Klyucharev P.G. Investigation of the Practical Possibility of Solving Problems on Generalized Cellular Automata Associated with Cryptanalysis by Mean Algebraic Methods. Mathematics and Mathematical Modeling. 2017;(5):29-44. (In Russ.) https://doi.org/10.24108/mathm.0517.0000080

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


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


ISSN 2412-5911 (Online)