Associate Professor of the Department of Information Security, BMSTU, Director of the «RusCrypto» Association, Ph.D. (Math.)
доцент кафедры информационной безопасности МГТУ им. Н.Э. Баумана, директор ассоциации «РусКрипто», кандидат физико-математических наук
Recently the reversible cellular automata are increasingly used to build high-performance cryptographic algorithms. The paper establishes a connection between the reversibility of homogeneous one-dimensional binary cellular automata of a finite size and the properties of a structure called «binary filter with input memory» and such finite automata properties as the prohibitions in automata output and loss of information. We show that finding the preimage for an arbitrary configuration of a one-dimensional cellular automaton of length L with a local transition function f is associated with reversibility of a binary filter with input memory. As a fact, the nonlinear filter with an input memory corresponding to our cellular automaton does not depend on the number of memory cells of the cellular automaton. The results obtained make it possible to reduce the complexity of solving massive enumeration problems related to the issues of reversibility of cellular automata. All the results obtained can be transferred to cellular automata with non-binary cell filling and to cellular automata of dimension greater than 1.
В последнее время обратимые клеточные автоматы все чаще применяются для построения высокопроизводительных криптографических алгоритмов. Устанавливается связь обратимости однородных одномерных бинарных клеточных автоматов конечного размера со свойствами конструкции, называемой нелинейный фильтр с входной памятью и такими свойствами конечных автоматов, как наличие запретов и потеря информации. В работе показано, что нахождение прообраза для произвольной конфигурации одномерного клеточного автомата длины L с локальной функцией связи f связано с нахождением прообраза (а по сути с обратимостью) нелинейного фильтра с входной памятью с регистром длины R (где R - размер окрестности соответствующего одномерного клеточного автомата) и функцией выхода, совпадающей с локальной функцией связи клеточного автомата. При этом нелинейный фильтр с входной памятью, соответствующий клеточному автомату, не зависит от числа ячеек памяти клеточного автомата. Полученные результаты позволяют снизить сложность решения массовых задач переборного типа, связанных с вопросами обратимости клеточных автоматов. Все полученные результаты можно перенести на клеточные автоматы с небинарным заполнением ячеек и на клеточные автоматы размерности большей 1.