Развитие информационных технологий, совершенствование средств обработки и хранения информации способствует расширению сферы использования вычислительных средств. Достижения в области аппаратной и программной реализации алгоритмов обработки данных обеспечивают удобство эксплуатации технических средств. Объём обрабатываемых данных растёт в соответствии с возрастающими потребностями современного общества, поэтому автоматизированное использование компьютерных технологий является одним из самых практичных методов обработки информации.
Решение задач идентификации и аутентификации, контроля целостности и распознавания образов требует построения преобразований фрагментов информации, зависящих от некоторого секрета. Традиционные криптографические методы защиты информации используют обратимые преобразования, зависящие от секретного ключа. Основным требованием, предъявляемым к таким преобразованиям, является стойкость к атакам, направленным на нахождение защищаемой информации, без знания секретного ключа, либо нахождение самого секретного ключа. Стойкость обычно измеряется временем, которое необходимо для успешного выполнения атаки при некоторых фиксированных ресурсах, имеющихся в распоряжении у злоумышленника, реализующего атаки на систему защиты. Повышение стойкости системы защиты путём усложнения аналитической и статистической структуры используемых преобразований приводит к увеличению объёма ресурсов, требуемых для реализации системы защиты. Уровень стойкости системы защиты характеризуется нижней оценкой времени, требуемого на нарушение системы защиты, и определяется в первую очередь вычислительными ресурсами потенциального взломщика, а также временем, в течение которого защищаемая информация должна оставаться недоступной взломщику. Повышение стойкости системы защиты приводит к росту материальных затрат потенциального нарушителя, используемых для оплаты технических, интеллектуальных и организационных средств при проведении атаки. Материальные средства, выделяемые на проведение атаки, определяются выгодой, которую получит нарушитель при нанесении ущерба системе защиты. Такая выгода противника может быть оценена стоимостью атакуемых активов. Широкое применение приобретают компактные узлы и блоки переработки информации в системах управления, идентификации и контроля, размещённые в условиях, когда основным ценовым параметром становится емкостная сложность реализации преобразования. При этом вопросы стойкости используемой системы защиты не являются первоочередными, поскольку ценность обрабатываемой этими узлами информации стремительно падает с течением времени. Такие узлы используются для контроля доступа, идентификации транспортных средств, отслеживания активов, контроля производственных запасов, автоматизации производства и складской обработки, контроля за перемещением потоков грузов и транспорта и других задач [48, 10, 47, 53, 42]. Особую ценность минимизация емкостной сложности реализации узлов переработки информации приобретает, в частности, в аэрокосмической области при решении задач идентификации удалённых объектов.
В алгоритмах защиты широко используются взаимно однозначные преобразования или подстановки двоичных векторов. Пусть Уп — множество двоичных векторов длины п, п Е М, Ф — некоторое биективное преобразование множества Уп, задающее подстановку 7 Г 6 3(Уп). Подстановка 7 г может быть задана таблично. При таком задании каждому вектору х 6 Уп ставится в соответствие его образ ж71″. Одномерный массив образов {хж: х 6 Уп} индексируется векторами х Е Уп и сохраняется в памяти. Реализация действия подстановки 7 Г на вектор х состоит в считывании содержимого памяти по адресу, соответствующему вектору х. Объём памяти, необходимый для табличного задания подстановки на Уп, составляет к-2П битов, где к — минимальный размер в битах области памяти, в которой может быть сохранён п-мерный двоичный вектор и к которой может быть реализована адресация. Например, если в некотором вычислительном устройстве минимальной адресуемой областью памяти является один байт, то для сохранения 7-мерного двоичного вектора и последующей адресации к нему потребуется 8 битов памяти. Для табличного задания подстановки 7 г Е ^(Уг) в этом случае потребуется 8−27, при том что 27 памяти фактически не используется. Если задать подстановку тт Е 5(14) с помощью системы координатных функции Сп = (Д,. ,/"), сохранить каждую координатную функцию /?, г Е 1, п, отдельно и с помощью дополнительных вычислений организовать доступ к значению /(ж) для всех х € Уп таким образом, чтобы каждая функция занимала в памяти 2п битов, то для реализации подстановки 7 Г потребуется п-2п битов памяти.
Цель диссертации состоит в разработке новых математических и технических принципов построения просто реализуемых на современной элементной базе биективных преобразований, используемых в средствах защиты информации и обеспечения информационной безопасности. Центральной идеей работы является минимизация емкостной сложности подстановочного преобразования за счёт реализации не п координатных функций, а лишь одной функции с системой просто реализуемых сервисных команд.
Объектом исследования являются методы построения взаимно однозначных преобразований на основе однотипных двоичных функций, а предметом — алгоритмы построения нелинейных подстановок.
В процессе проведения исследования для изучения инженерных вопросов реализации схем защиты информации применялись алгебраические методы и методы математической логики. Основные результаты работы получены с использованием теории булевых функций и теории алгоритмов, а также путём разработки специальных программных средств и проведения вычисл ител ьн ых экспериментов.
Научная новизна диссертации состоит в следующем.
1) Дано теоретическое описание регулярных систем двоичных функций, построенных на основе группы сдвига и произвольной двоичной функции степени нелинейности 2.
2) Проведено исчерпывающее изучение строения регулярных систем, координатные функции которых эквивалентны относительно преобразования циклического сдвига координат, и построены классы двоичных функций степени нелинейности 3, порождающие такие системы.
3) Описано множество регулярных систем, построенных на основе фильтрующего генератора с нелинейной функцией усложнения второй степени.
4) Проведена каталогизация регулярных систем однотипных двоичных функций от четырёх переменных.
Теоретическая ценность представлена следующими содержащимися в работе положениями.
1) Выделены и исследованы инварианты подстановок, задаваемых регулярными системами однотипных двоичных функций, позволяющие существенно сократить количество представителей при каталогизации систем однотипных функций.
2) Описаны классы преобразований, порождаемые нелинейными функциями с помощью операции сдвига и операции циклического сдвига координат векторов пространства Уп.
3) Исследована структура регулярных систем, построенных на основе аффинного регистра сдвига с нелинейной функцией усложнения второй степени нелинейности от трёх переменных.
Практическая значимость работы состоит в том, что предложенный в диссертации способ задания биективного отображения приводит к существенному снижению емкостной сложности реализации этого отображения на новой и перспективной элементной базе. Представленный в приложении к диссертации каталог всех регулярных геометрически эквивалентных систем функций от четырёх переменных позволяет при разработке систем защиты информации выбирать легко реализуемые в пороговой логике преобразования с заданными характеристиками нелинейности.
Пусть Уп — пространство двоичных векторов длины п, Тп — множество двоичных функций от п переменных Любое преобразование Ф пространства Уп может быть задано системой (/1,. ,/п) двоичных функций / е 1, п, называемых координатными функциями преобразования Ф. Действие преобразования Ф: ж 4 у, 6 определяется системой уравнений у£ = Л (®), гем. (0.1).
Биективность преобразования Ф, или регулярность системы координатных функций преобразования Ф, является одним из требований, предъявляемых к преобразованиям векторных пространств.
В диссертационной работе исследуются системы функций, эквивалентных относительно некоторой группы преобразований пространства Уп. В качестве такой группы преобразований научным руководителем диссертационной работы Никоиовым В. Г. предложено использовать преобразования однотипности, образующие группу Джевонса, обозначаемую через, а также геометрические преобразования, которые включают в себя преобразования однотипности и преобразование, заключающееся в инвертировании значений координатных функций. Выбор таких преобразований обусловлен несколькими соображениями. Во-первых, являясь изометрическими, такие преобразования сохраняют геометрическое строение координатных функций. Кроме того, в этом случае возникает возможность проводить классификацию функций и систем однотипных функций с помощью графов связности единичных вершин п-кубов. Такой подход был использован Никоновым В. Г. в работе «Классификация минимальных базисных представлений всех булевых функций четырёх переменных» [13] и впоследствии Гизуновым С. А. и Носовым В. А. в работе «Классификация всех булевых функций 4-х переменных по классам Шефера» [1].
В первой главе диссертации вводятся понятия регулярной системы С-однотипных функций и функции порождающей эту систему, описываются классы регулярных систем функций, эквивалентных относительно просто реализуемых групп преобразований: группы сдвигов Нп и группы (о), порождённой преобразованием циклического сдвига координат векторов. В § 1.1 приведены критерии регулярности систем однотипных функций. Введено понятие типа регулярной системы, которое соответствует типу порождающей функции. Доказано, что свойство порождать регулярную систему с помощью преобразований произвольной группы С является инвариантом функций, эквивалентных относительно нормализатора группы С в группе 3(уп) подстановок на Уп.
Преобразование сдвига двоичных векторов относится к числу наиболее просто программно реализуемых преобразований. Поэтому в случае, когда система функций является #п-однотипной, сложность реализации системы определяется сложностью реализации порождающей функции. В § 1.2 доказано, что регулярная система #п-однотипных функций может порождаться только сбалансированной нелинейной функцией, существенно зависящей от всех переменных. Доказано, что свойство порождать регулярную систему Яп-однотипных функций является инвариантом класса аффинной эквивалентности. На основании этого факта описаны все порождающие функции степени нелинейности 2.
В § 1.3 приведены результаты исследований регулярных систем, построенных на основе преобразования, а циклического сдвига координат векторов пространства Уп. Такие системы являются частным случаем регулярных систем вида С (/- 7г) = /7Г,., /7Г", где 7 г е В настоящей работе доказано, что этот алгоритм позволяет построить все регулярные системы (а)-однотипных функций, и все построенные системы задают множество подстановок, являющееся централизатором подстановки, а в ?/" — В то же время, предложенный алгоритм не позволяет задать порождающую функцию системы С (/- а) в явном виде, однако даёт возможность описать класс преобразований, с помощью которых можно из одной регулярной системы вида С (/- сг) получать новые регулярные системы, так же порождаемые некоторой двоичной функцией и преобразованием а. Доказано, что свойство представимости регулярной системы в виде С (/- сг) является инвариантом класса эквивалентности относительно умножения справа и слева на обратимые правые (0,1)—циркулянты. Этот факт позволяет получать новые классы порождающих функций систем вида С (/- сг). Система, задающая обратную подстановку, так же реализуется на основе циклического сдвига координат порождающей функции, что позволяет эффективно реализовать обратную подстановку.
Во второй главе работы построены классы регулярных систем функций вида С (/- р/), где р1 — преобразование, реализуемое за один такт работы регулярного регистра сдвига с аффинной двоичной функцией обратной связи I.
Регулярность системы С (/- р{) эквивалентна наличию единственного решения системы уравнений рекуррентного типа уш, г е 0^=1, для всех векторов у = (у,., уп) Е Уп. Решение частного случая системы такого вида позволило в § 2.2 описать классы функций степени нелинейности 2 от трёх переменных и аффинных регистров сдвига, позволяющие строить регулярные системы (р/)-однотипных функций. Полученное представление координатных функций в виде многочлена Жсгалкина позволило вычислить как степени нелинейности б преобразований вида С (/-р/), так и степени нелинейности в! обратных к ним преобразований. Эти степени оказались равными б, = 2 и в! = ^^ соответственно.
В § 2.3 построены классы двоичных функций степени нелинейности 3, порождающих регулярные системы с помощью одной функции и преобразования, реализуемого за один такт циклического сдвига координат вектора.
В главе III изложен принцип классификации регулярных систем С-однотипных функций, основанный на перечислении представителей типов систем. Для классификации регулярных систем п~однотипных функций в работе использовалось отношение эквивалентности на множестве задаваемых ими подстановок, которое позволило объединить (^&bdquo—типы порождающих функций и сохранить такие свойства как общее количество порождаемых систем и количество представителей, неэквивалентных относительно двухстороннего умножения на элементы группы Рассматриваемое отношение эквивалентности на множестве регулярных систем однотипных функций сохраняет такие характеристики нелинейности, которые приводятся для каждого из представителей систем.
Теоретические результаты классификационных исследований использованы для каталогизации (^-однотипных функций. Введённое отношение эквивалентности позволило при составлении «Каталога регулярных систем (^-однотипных двоичных функций» использовать «Классификацию минимальных базисных представлений всех булевых функций от четырёх переменных», составленную В. Г. Никоновым. «Каталог.» составлен с использованием разработанного автором лично программного обеспечения в среде СУБД Paradox. Для вычислений характеристик функций и порождаемых ими систем использовалось разработанное автором программное обеспечение. Достоверность проведённых вычислений подтверждается непосредственным сравнением результатов вычислений, полученных с помощью пакетов прикладных программ, разработанных другими исследователями, а также апробацией в учебном процессе ИКСИ. Вёрстка «Каталога.» осуществлялась в издательской системе что обеспечивает совместимость отображения результатов каталогизации в системах, поддерживающих форматированный вывод данных. В «Каталоге.» использован принцип классификации двоичных функций с помощью графов связности вершин, что значительно облегчает работу с каталогом и позволяет устанавливать корреляционные связи с классификационными исследованиями, проводимыми В. Г. Никоновым, В. А. Носовым и С. А. Гизуновым.
В тексте диссертации представлено подробное описание «Каталога.» и рассмотрен пример, иллюстрирующий порядок использования результатов каталогизационных исследований. Для удобства чтения диссертации оглавление и таблицы каталога, который имеет самостоятельное значение, включены в качестве приложения после текстового блока работы. В каталоге для каждого С^-типа сбалансированной двоичной функции приведена система представителей регулярных систем, порождаемых этой функцией с помощью преобразований из группы СЦ4. У каждого из представителей указаны инвариантные относительно двустороннего умножения на элементы группы (^4 характеристики нелинейности.
В диссертации получены следующие основные результаты, выносимые на защиту.
1) Для синтеза взаимно однозначного отображения двоичных векторов длины п в диссертации предложено использовать не п координатных функций, а одну функцию с совокупностью легко реализуемых сервисных команд.
2) Для предложенного способа построения подстановок проведено исследование аналитических свойств систем функций и порождаемых ими преобразовании в системах защиты информации.
3) Предложен метод каталогизации всех двоичных функций и составлен каталог регулярных систем, порождаемых функциями от четырёх переменных.
Основные результаты диссертационного исследования опубликованы в работах [15, 28, 31], докладывались на У, У1 и VII Всероссийских симпозиумах по прикладной и промышленной математике [26, 30, 32], на XXXI Международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе» [16, 27].
Заключение
.
В диссертации предложен новый метод построения систем двоичных функций, задающих взаимно однозначные отображения пространства векторов. Этот метод приводит к синтезу систем функций, эквивалентных относительно просто реализуемых групп преобразований систем, что закладывает потенциальную возможность их компактного синтеза. При этом осуществляется задание не всех функций системы, а лишь одной из них, так что остальные функции системы формируются посредством действия на переменные порождающей функции преобразованием однотипности. К одному из направлений в построении систем функций, задающих подстановки большой степени, следует отнести исследование порождающих функций, с ограниченной сложностью реализации.
Для всех преобразований, построенных в работе с помощью классов регулярных систем получены координатные функции обратных к ним преобразований. Следует отметить, что подстановки, задаваемые такими системами действуют на векторах произвольной длины, что расширяет арсенал способов синтеза подстановок больших степеней.
В диссертационной работе получены результаты по следующим направлениям:
— выделены и исследованы инвариантные относительно двустороннего умножения на элементы подгрупп группы подстановок на Уп характеристики подстановок, задаваемых регулярными системами однотипных функций;
— описан класс нелинейных функций, порождающих регулярные системы с помощью преобразований сдвига векторов пространства Уп;
— изучено строение регулярных систем, координатные функции которых эквивалентны относительно циклического сдвига координат;
— дано описание регулярных систем, построенных на основе произвольного аффинного регистра сдвига с нелинейной функцией усложнения второй степени от трёх переменных, и обратных к ним систем;
— описаны классы подстановок и обратных к ним, координатные функции которых являются эквивалентными относительно преобразования, реализуемого за один такт циклического сдвига векторов;
— предложен метод каталогизации всех двоичных функций и составлен каталог регулярных систем ¿-^-однотипных функций с указанием характеристик нелинейности.
