МЕТОДЫ ПОСТРОЕНИЯ ПОДСТАНОВОК ПРОИЗВОЛЬНОГО КОНЕЧНОГО ПОЛЯ И ИХ ЛИНЕЙНАЯ ХАРАКТЕРИСТИКА

Подстановки в конечном поле (биективные преобразования) активно изучаются во многих приложениях, в том числе и в теории защиты информации. Подстановки часто используются в качестве элементов для построения узлов обработки информации. В середине XX века К. Шеннон теоретически обосновал основные требования к отображениям, осуществляемым на таких узлах. В настоящее время при построении биективных преобразований эти требования обеспечиваются композицией нелинейных представлений, заданных таблицей в поле GF(2). Представленная статья обобщает результаты работы [1] о методах увеличения размерности стационарных функциональных систем. Именно в данной работе исследованы подходы к построению новых подстановок из исходных подстановок в конечном поле. Для построенных подстановок вычислена линейная характеристика. Задача построения подстановок, заданных координатными функциями, является сложной. Актуальность темы статьи определяется необходимостью поиска новых, теоретически обоснованных методов построения классов подстановок в многомерных пространствах, обладающих требуемыми комбинаторно-алгебраическими свойствами. В работе рассмотрено несколько методов построения подстановок конечных полей из исходных подстановок, действующих на векторы меньшей размерности. В бинарном случае это позволяет найти нелинейность рассматриваемых подстановок, характеризующих сродство линейных комбинаций координатных функций подстановок ко всему классу аффинных функций. Результаты представленной работы несколько расширяют возможности построения подстановок для произвольного конечного поля.

1. Никонов В.Г., Саранцев А.В. Методы компактной реализации биективных отображений, заданных регулярными системами однотипных булевых функций // Вестник Российского университета дружбы народов. Серия: Прикладная и компьютерная математика. – 2003. – Т. 2. – № 1. – С. 94–105.

2. Лидл Р., Нидеррайтер Г. Конечные поля. – М.: Мир, 1988. – 822 c.

3. Бугров А.Д. Кусочно-аффинные подстановки конечных полей // Прикладная дискретная математика. – 2015. – № 4 (30). – C. 5–23.

4. Логачев О.А., Сальников А.А., Ященко В.В. Булевы функции в теории кодирования и криптологии. – М.: Изд-во МЦНМО, 2012. – 584 c.

5. Abornev A.V. Recursively-generated permutations of a binary space // Математические основы криптографии. – 2014. – Т. 5. – № 2. – С. 7–20.

6. Рожков М.И. Биективные отображения, порождаемые фильтрующим генератором // Прикладная дискретная математика. – 2014. – Т. 1. – № 23. – С. 27–39.

7. Blondeau C., Nyberg К. Perfect Nonlinear Functions and Cryptography // Finite Fields Appl. – 2015. – Т. 32. – С. 120–147.

8. Li C.H. The finite primitive permutation groups containing an abelian regular subgroup // Proc. London Math. Soc., MR MR2005881 (2004i:20003) – 87. – 2003. – С. 725–747.