Математика и математическое моделирование. 2017; : 29-44
Исследование практической возможности решения связанных с криптоанализом задач на обобщенных клеточных автоматах алгебраическими методами
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.
Mathematics and Mathematical Modeling. 2017; : 29-44
Investigation of the Practical Possibility of Solving Problems on Generalized Cellular Automata Associated with Cryptanalysis by Mean Algebraic Methods
https://doi.org/10.24108/mathm.0517.0000080Abstract
A number of previous author’s papers proposed methods for constructing various cryptographic algorithms, including block ciphers and cryptographic hash functions, based on generalized cellular automata. This one is aimed at studying a possibility to use the algebraic cryptanalysis methods related to the construction of Gröbner bases for the generalized cellular automata to be applied in cryptography, i.e. this paper studies the possibility for using algebraic cryptanalysis methods to solve the problems of inversion of a generalized cellular automaton and recovering the key of such an automaton.
If the cryptographic algorithm is represented as a system of polynomial equations over a certain finite field, then its breach is reduced to solving this system with respect to the key. Although the problem of solving a system of polynomial equations in a finite field is NP-difficult in the general case, the solution of a particular system can have low computational cost.
Cryptanalysis based on the construction of a system of polynomial equations that links plain text, cipher-text and key, and its solution by algebraic methods, is usually called algebraic cryptanalysis. Among the main methods to solve systems of polynomial equations are those to construct Gröbner bases.
Cryptanalysis of ciphers and hash functions based on generalized cellular automata can be reduced to various problems. We will consider two such problems: the problem of inversion of a generalized cellular automaton, which, in case we know the values of the cells after k iterations, enables us to find the initial values. And the task of recovering the key, which is to find the initial values of the remaining cells, using the cell values after k steps and the initial values of a part of the cells.
A computational experiment was carried out to solve the two problems above stated in order to determine the maximum size of a generalized cellular automaton for which the solution of these problems was possible.
Using a Python language program, random 6-regular Ramanujan graphs with the appropriate number of vertices were generated. For each graph, was generated a system of equations that describes the k steps of the corresponding generalized cellular automaton. For the systems obtained, the Grebner bases were constructed using the Fouger algorithm F4, the Magma system v2.21-5, and the Polybori 0.8.3 library. The experiments were carried out both for the inversion task and for the key recovery task. We used a 16-core 16 GB RAM Intel Xeon E5-2690 computer, OS Linux.
The article presents the results of experiments that confirm that the algebraic cryptanalysis of block ciphers and hash functions based on generalized cellular automata with the number of cells used in practice (of the order of several hundred or more) available tool based on the use of Gröbner bases, is impossible.
References
1. Arzhantsev I.V. Bazisy Grebnera i sistemy algebraicheskikh uravnenii. M.: MTsNMO, 2003. 68 s.
2. Komp'yuternaya algebra: Simvolicheskie i algebraicheskie vychisleniya / Bukhberger B., Kalme Zh., Kaltofen E. i dr.; pod red. N.N. Govoruna. M.: Mir, 1986. 391 s. [Computer algebra: symbolic and algebraic computation / Ed. by B. Buchberger. W.; N.Y.: Springer, 1982. 283 p.].
3. Klyucharev P.G. Blochnye shifry, osnovannye na obobshchennykh kletochnykh avtomatakh // Nauka i obrazovanie. MGTU im. N.E. Baumana. Elektron. zhurn. 2012. № 12. S. 361-374. DOI: 10.7463/0113.0517543
4. Klyucharev P.G. Postroenie psevdosluchainykh funktsii na osnove obobshchennykh kletochnykh avtomatov // Nauka i obrazovanie. MGTU im. N.E. Baumana. Elektron. zhurn. 2012. № 10. S. 263-274. DOI: 10.7463/1112.0496381
5. Klyucharev P.G. Kriptograficheskie khesh-funktsii, osnovannye na obobshchennykh kletochnykh avtomatakh // Nauka i obrazovanie. MGTU im. N.E. Baumana. Elektron. zhurn. 2013. № 1. S. 161-172. DOI: 10.7463/0113.0534640
6. Klyucharev P.G. Postroenie sluchainykh grafov, prednaznachennykh dlya primeneniya v kriptograficheskikh algoritmakh, osnovannykh na obobshchennykh kletochnykh avtomatakh // Matematika i matematicheskoe modelirovanie. Elektron. zhurn. 2017. № 3. S. 77-90. DOI: 10.24108/mathm.0317.0000076
7. Koks D., Littl Dzh., O’Shi D. Idealy, mnogoobraziya i algoritmy. Vvedenie v vychislitel'nye aspekty algebraicheskoi geometrii i kommutativnoi algebry. M.: Mir, 2000. 687 s. [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. Rezhim dostupa: http://drops.dagstuhl.de/opus/volltexte/2007/1013/pdf/07021.CourtoisNicolas.Paper.1013.pdf (data obrashcheniya 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. Rezhim dostupa: https://people.eecs.berkeley.edu/~alanmi/publications/2001/tech01_zdd_.pdf (data obrashcheniya 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.
