НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o202.pdf (305.34Кб)

УДК 004.056.55+519.713

Россия,  МГТУ им. Н.Э. Баумана

Ранее автором были разработаны принципы построения симметричных криптоалгоритмов на основе обобщенных клеточных автоматов. Эти криптоалгоритмы имеют высокую производительность при аппаратной реализации. Данная работа продолжает это направление исследований. В ней исследуются коллизии, возникающие при работе обобщенных клеточных автоматов.
Основной задачей настоящей работы является разработка метода построения обобщенных клеточных автоматов, устойчивых к определенному виду коллизий.
Будем называть t-шаговой коллизией веса w два различных начальных заполнения обобщенного клеточного автомата, различающиеся в w разрядах и дающие одинаковые заполнения после t шагов. Заметим, что любая t-шаговая коллизия одновременно является и (t+u)-шаговой коллизией.
Очевидно, что существование коллизий в обобщенном клеточном автомате, при условии наличия эффективных алгоритмов их нахождения, резко ухудшает криптографические свойства основанных на нем криптоалгоритмов. Поэтому очень важны методы синтеза обобщенных клеточных автоматов устойчивых к коллизиям.  В данной работе мы изучим устойчивость к одношаговым коллизиям веса 1.
В работе показывается, что для отсутствия одношаговых коллизий веса 1 достаточно чтобы от каждой ячейки клеточного автомата линейно зависела какая-либо другая ячейка. Для этого достаточно, чтобы ребра, имеющие номер k относительно каких-либо вершин вместе с этими вершинами образовывали 2-фактор графа обобщенного клеточного автомата, а локальная функция связи должна быть линейна по  аргументу, имеющему номер k.
Приведены условия существования  2-фактора. Приведен метод, позволяющий найти 2-фактор в данном графе. Он основан на алгоритме поиска максимального паросочетания в двудольном графе.
Таким образом, в статье развита теория обобщенных клеточных автоматов, свободных от одношаговых коллизий веса 1. Такие автоматы важны для криптографических применений. Разработан метод построения таких автоматов, работающий за полиномиальное время.

1. Ключарёв П.Г. Блочные шифры, основанные на обобщённых клеточных автоматах // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 12. С. 361-374. DOI: 10.7463/0113.0517543
2. Ключарёв П.Г. Обеспечение криптографических свойств обобщённых клеточных автоматов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 3. Режим доступа: http://technomag.bmstu.ru/doc/358973.html (дата обращения 01.08.2014).
3. Ключарёв П.Г. Построение псевдослучайных функций на основе обобщённых клеточных автоматов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 10. С. 263-274. DOI: 10.7463/1112.0496381
4. Ключарёв П.Г. Криптографические хэш-функции, основанные на обобщённых клеточных автоматах // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2013. № 1. С. 161-172. DOI: 10.7463/0113.0534640
5. Панасенко С.П. Алгоритмы шифрования. Специальный справочник. СПб.: БХВ-Петербург, 2009. 576 с .
6. Чичварин Н.В. Выбор методов защиты проектной документации от несанкционированного доступа // Информационные технологии. 2014. № 5. С. 41-48.
7. Buchmann J. Introduction to Cryptography. Springer New York, 2004. 338 p. (Ser. Undergraduate Texts in Mathematics). DOI: 10.1007/978-1-4419-9003-7
8. Davidoff G., Sarnak P., Valette A. Elementary number theory, group theory and Ramanujan graphs. Cambridge: Cambridge University Press, 2003. 154 p. (London Mathematical Society Student Texts; vol. 55).
9. Hoffstein J., Pipher J., Silverman J.H. An Introduction to Mathematical Cryptography. Springer New York, 2008. (Ser. Undergraduate Texts in Mathematics). DOI: 10.1007/978-0-387-77993-5
10. Hoory S., Linial N., Wigderson A. Expander graphs and their applications // Bulletin of the American Mathematical Society. 2006. Vol. 43, no. 4. P. 439 - 562.
11. Hopcroft J. E., Karp R. M. An nˆ5/2 algorithm for maximum matchings in bipartite graphs // SIAM Journal on Computing. 1973. Vol. 2, no. 4. P. 225-231.
12. Lubotzky A., Phillips R., Sarnak P. Ramanujan graphs // Combinatorica. 1988. Vol. 8, no. 3. P. 261-277. DOI: 10.1007/BF02126799
13. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. Taylor & Francis, 1996. 816 p.
14. Paar C., Pelzl J. Understanding Cryptography: A Textbook for Students and Practitioners. Springer Berlin Heidelberg, 2010. 372 p. DOI: 10.1007/978-3-642-04101-3
15. Panasenko S., Smagin S. Lightweight cryptography: Underlying principles and approaches // International Journal of Computer Theory and Engineering. 2011. Vol. 3, no. 4. P. 516-520. DOI: 10.7763/IJCTE.2011.V3.360
16. Petersen J. Die theorie der regularen graphs // Acta Mathematica. 1891. Vol. 15, no. 1. P. 193-220. DOI: 10.1007/BF02392606
17. Plummer M. D. Graph factors and factorization: 1985–2003: a survey // Discrete Mathematics. 2007. Vol. 307, no. 7. P. 791-821. DOI: 10.1016/j.disc.2005.11.059
18. Preneel B. Stream ciphers and lightweight cryptography // Proc. of the 2nd International Workshop on ZUC Algorithm and Related Topics. Beijing, China, 2011.
19. Von Baebler F. Uber die zerlegung regulärer streckenkomplexe ungerader ordnung // Commentarii Mathematici Helvetici. 1937. Vol. 10, no. 1. P. 275-287.