Обратимость одномерных клеточных автоматов
- Авторы: Жуков А.Е.1,2
-
Учреждения:
- Московский государственный технический университет имени Н.Э. Баумана (национальный исследовательский университет)
- Ассоциация «РусКрипто»
- Выпуск: Том 22, № 1 (2021)
- Страницы: 7-15
- Раздел: Статьи
- URL: https://journals.rcsi.science/2312-8143/article/view/327530
- DOI: https://doi.org/10.22363/2312-8143-2021-22-1-7-15
- ID: 327530
Цитировать
Полный текст
Аннотация
В последнее время обратимые клеточные автоматы все чаще применяются для построения высокопроизводительных криптографических алгоритмов. Устанавливается связь обратимости однородных одномерных бинарных клеточных автоматов конечного размера со свойствами конструкции, называемой нелинейный фильтр с входной памятью и такими свойствами конечных автоматов, как наличие запретов и потеря информации. В работе показано, что нахождение прообраза для произвольной конфигурации одномерного клеточного автомата длины L с локальной функцией связи f связано с нахождением прообраза (а по сути с обратимостью) нелинейного фильтра с входной памятью с регистром длины R (где R - размер окрестности соответствующего одномерного клеточного автомата) и функцией выхода, совпадающей с локальной функцией связи клеточного автомата. При этом нелинейный фильтр с входной памятью, соответствующий клеточному автомату, не зависит от числа ячеек памяти клеточного автомата. Полученные результаты позволяют снизить сложность решения массовых задач переборного типа, связанных с вопросами обратимости клеточных автоматов. Все полученные результаты можно перенести на клеточные автоматы с небинарным заполнением ячеек и на клеточные автоматы размерности большей 1.
Об авторах
Алексей Евгеньевич Жуков
Московский государственный технический университет имени Н.Э. Баумана (национальный исследовательский университет); Ассоциация «РусКрипто»
Автор, ответственный за переписку.
Email: aez_iu8@rambler.ru
ORCID iD: 0000-0002-1663-7773
доцент кафедры информационной безопасности МГТУ им. Н.Э. Баумана, директор ассоциации «РусКрипто», кандидат физико-математических наук
Российская Федерация, 105005, Москва, 2-я Бауманская ул., д. 5, стр. 1; Российская Федерация, 111123, Москва, ул. Плеханова, д. 4АСписок литературы
- Zhukov A. Cellular automata in cryptography. Part 1. Voprosy kiberbezopasnosti [Cybersecurity issues]. 2017;3(21):70—76. (In Russ.) https://doi.org/10.21581/2311-3456-2017-3-70-76
- Zhukov A. Cellular automata in cryptography. Part 2. Voprosy kiberbezopasnosti [Cybersecurity issues]. 2017;4(22):47—66. (In Russ.) https://doi.org/10.21681/2311-3456-2017-4-47-66
- Lai X, Massey JL. Some connections between scramblers and invertible automata. In: Proc. 1988 Beijing Int. Workshop on Info. Theory, Beijing. China, July 4-7;1988:DI-5.1 — DI-5.5.
- Preparata FP. Convolutional transformations of binary sequences: Boolean functions and their resynchronizing properties. IEEE Trans. Electron. Comput. 1966;15(6):898—909.
- Sumarokov SN. Zaprety dvoichnyh funkcij i obratimost’ dlya odnogo klassa kodiruyushchih ustrojstv [Prohibitions of binary functions and reversibility for one class of coding devices]. Obozrenie prikladnoj i promyshlennoj matematiki, ser. diskretn. matem. [Obozrenie prikladnoy i promyshlennoy matematiki]. 1994;1(1):33—55.
- Babash AV. Zaprety avtomatov i dvoichnyh funkcij [Prohibitions of automata and binary functions]. Trudy po diskretnoj matematike [Proceedings of Discrete] Mathematics. 2006;9:7—20. (In Russ.)
- Olson RR. On the invertibility of finite state machines. Ph.D. diss. Notre Dame, Indiana, USA: Department of Electrical Engineering, University of Notre Dame; 1970.
- Huffman DA. Canonical forms for information loss less finite state logical machines. IRE Trans. Circuit Theory. 1959;6(spec. suppl.):41—59.
- Kohavi Z, Niraj K. Jha. Switching and Finite Automata Theory. Cambridge, UK: Cambridge University Press; 2009. https://doi.org/10.1017/CBO9780511816239
Дополнительные файлы
