Построение взаимно однозначных преобразований на основе однотипных двоичных функций в связи с задачами защиты информации

• Автор: Саранцев, Алексей Васильевич
• Шифр специальности: 05.13.19
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 141 с.

Оглавление
Введение

1 Аппаратная и программная реализация подстановочных преобразований

1.1 Регулярные системы 7однотипиых функций

1.2 Регулярные системы пОДЮТИПНЫХ функций степени 2 . .

1.3 Регулярные системы сгоднотипных функций

1.4 Выводы
2 Построение регулярных систем однотипных двоичных функций на основе аффинного регистра сдвига

2.1 Системы однотипных двоичных функций на основе регистра

сдвига

2.2 Условия регулярности системы Ср для фильтрующего

генератора
2.3 Системы сгоднотипных функций степени 3.
2.4 Выводы
3 Классификация регулярных систем однотипных двоичных функций
3.1 Классы эквивалентности регулярных систем однотипных
двоичных функций.
3.2 Описание каталога регулярных систем однотипных функций .
3.3 Выводы.
Каталог регулярных систем однотипных двоичных функций
I Список графов связности единичных вершин сбалансированных двоичных функций от 4 переменных.
II Представители классов геометрической эквивалентности . .
III Таблицы
IV Представители классов регулярных систем
Заключение
Литература


Бнсктивность преобразования Ф, или регулярность системы координатных функций преобразования Ф, является одним из требований, предъявляемых к преобразованиям векторных пространств. В диссертационной работе исследуются системы функций, эквивалентных относительно некоторой группы преобразований пространства Уп. В качестве такой группы преобразований научным руководителем диссертационной работы Никоновым В. Г. предложено использовать преобразования однотипности, образующие группу Джевонса, обозначаемую через С? Выбор таких преобразований обусловлен несколькими соображениями. Во-первых, являясь изометрическими, такие преобразования сохраняют геометрическое строение координатных функций. Кроме того, в этом случае возникает возможность проводить классификацию функций и систем однотипных функций с помощью графов связности единичных вершин п-кубов. Никоновым В. Г. в работе «Классификация минимальных базисных представлений всех булевых функций четырех переменных» [) и впоследствии Гизуновым С. А. и Носовым В. А. в работе «Классификация всех булевых функций 4-х переменных по классам Шефера» [1]. В первой главе диссертации вводятся понятия регулярной системы С-однотипных функций и функции порождающей эту систему, описываются классы регулярных систем функций, эквивалентных относительно просто реализуемых групп преобразований: группы сдвигов Ыа и группы (о), порождённой преобразованием циклического сдвига координат векторов. В §1. Введено понятие типа регулярной системы, которое соответствует типу порождающей функции. Преобразование сдвига двоичных векторов относится к числу наиболее просто программно реализуемых преобразований. Поэтому в случае, когда система функций является //„-однотипной, сложность реализации системы определяется сложностью реализации порождающей функции. В §1. Доказано, что свойство порождать регулярную систему Яп-однотипных функций является инвариантом класса аффинной эквивалентности. На основании этого факта описаны все порождающие функции степени нелинейности 2. В §1. Такие системы являются частным случаем регулярных систем вида С(/; тг) = ^/, /*,. Уп). В настоящей работе доказано, что этот алгоритм позволяет построить все регулярные системы (сг)-однотипных функций, и все построенные системы задают множество подстановок, являющееся централизатором подстановки а в 5кп- В то же время, предложенный алгоритм не позволяет задать порождающую функцию системы С(/;<т) в явном виде, однако даёт возможность описать класс преобразований, с помощью которых можно из одной регулярной системы вида С(/;а) получать новые регулярные системы, так же порож-даемые некоторой двоичной функцией и преобразованием <т. Доказано, что свойство представимости регулярной системы в виде С(/; а) является инвариантом класса эквивалентности относительно умножения справа и слева на обратимые правые (0,1)—циркулянты. Этот факт позволяет получать новые классы порождающих функций систем вида С(/;а). Система, задающая обратную подстановку, так же реализуется на основе циклическою сдвига координат порождающей функции, что позволяет эффективно реализовать обратную подстановку. Во второй главе работы построены классы регулярных систем функций вида С(/; />/), где р — преобразование, реализуемое за один такт работы регулярного регистра сдвига с аффинной двоичной функцией обратной связи I. Уп) Є Кг- Решение частного случая системы такого вида позволило в §2. Полученное представление координатных функций в виде многочлена Жсгалкина позволило вычислить как степени нелинейности (1 преобразований вида С(/;р/), так и степени нелинейности (Iі обратных к ним преобразований. Эти степени оказались равными (I = 2 и в! В §2. В главе 1 изложен принцип классификации регулярных систем С-однотипных функций, основанный на перечислении представителей типов систем. Для классификации регулярных систем (^-однотипных функций в работе использовалось отношение эквивалентности на множестве задаваемых ими подстановок, которое позволило объединить (3„-типы порождающих функций и сохранить такие свойства как общее количество порождаемых систем и количество представителей, неэквивалентных относительно двухстороннего умножения на элементы группы С2п.