Содержание к диссертации
Введение
1 Аппаратная и программная реализация подстановочных преобразований 15
1.1 Регулярные системы (^-однотипных функций 15
1.2 Регулярные системы #п-однотипных функций степени 2 33
1.3 Регулярные системы (сг)-однотппных функций 39
1.4 Выводы 48
2 Построение регулярных систем однотипных двоичных функций на основе аффинного регистра сдвига 49
2.1 Системы однотипных двоичных функций на основе регистра сдвига 49
2.2 Условия регулярности системы С(/; р/) для фильтрующего генератора 52
2.3 Системы (<т)-однотипных функций степени 3 62
2.4 Выводы 70
3 Классификация регулярных систем однотипных двоичных функций 71
3.1 Классы эквивалентности регулярных систем однотипных двоичных функций 71
3.2 Описание каталога регулярных систем (-однотипных функций 76
3.3 Выводы 93
Заключение 133
Литература 135
- Регулярные системы #п-однотипных функций степени 2
- Регулярные системы (сг)-однотппных функций
- Условия регулярности системы С(/; р/) для фильтрующего генератора
- Описание каталога регулярных систем (-однотипных функций
Введение к работе
Актуальность темы. Развитие информационных технологий, совершенствование средств обработки и хранения информации способствует расширению сферы использования вычислительных средств. Достижения в области аппаратной и программной реализации алгоритмов обработки данных обеспечивают удобство эксплуатации технических средств. Объём обрабатываемых данных растёт в соответствии с возрастающими потребностями современного общества, поэтому автоматизированное использование компьютерных технологий является одним из самых практичных методов обработки информации.
Решение задач идентификации и аутентификации, контроля целостности и распознавания образов требует построения преобразований фрагментов информации, зависящих от некоторого секрета. Традиционные криптографические методы защиты информации используют обратимые преобразования, зависящие от секретного ключа. Основным требованием, предъявляемым к таким преобразованиям, является стойкость к атакам, направленным на нахождение защищаемой информации, без знания секретного ключа, либо нахождение самого секретного ключа. Стойкость обычно измеряется временем, которое необходимо для успешного выполнения атаки при некоторых фиксированных ресурсах, имеющихся в распоряжении у злоумышленника, реализующего атаки на систему защиты. Повышение стойкости системы защиты путём усложнения аналитической и статистической структуры используемых преобразований приводит к увеличению объёма ресурсов, требуемых для реализации системы защиты. Уровень стойкости системы защиты характеризуется нижней оценкой времени, требуемого на нарушение системы защиты, и определяется в первую очередь вычислительными ресурсами потенциального взломщика, а также временем, в течение которого защищаемая информация должна оставаться недоступной взломщику. Повышение стойкости системы защиты приводит к росту материальных затрат потенциального нарушителя, используемых для оплаты технических, интеллектуальных и организационных средств при проведении атаки. Материальные средства, выделяемые на проведение атаки, определяются выгодой, которую получит нарушитель при нанесении ущерба системе защиты. Такая выгода противника может быть
оценена стоимостью атакуемых активов. Широкое применение приобретают компактные узлы и блоки переработки информации в системах управления, идентификации и контроля, размещённые в условиях, когда основным ценовым параметром становится емкостная сложность реализации преобразования. При этом вопросы стойкости используемой системы защиты не являются первоочередными, поскольку ценность обрабатываемой этими узлами информации стремительно падает с течением времени. Такие узлы используются для контроля доступа, идентификации транспортных средств, отслеживания активов, контроля производственных запасов, автоматизации производства и складской обработки, контроля за перемещением потоков грузов и транспорта и других задач. Особую ценность минимизация емкостной сложности реализации узлов переработки информации приобретает, в частности, в аэрокосмической области при решении задач идентификации удалённых объектов.
Цель работы состоит в разработке новых математических и технических принципов построения просто реализуемых на современной элементной базе биективных преобразований, используемых в средствах защиты информации и обеспечения информационной безопасности.
Методы исследования. В процессе проведения исследования для изучения инженерных вопросов реализации схем защиты информации применялись алгебраические методы и методы математической логики.
Научная новизна диссертации состоит в следующем.
Дано теоретическое описание регулярных систем двоичных функций, построенных на основе группы сдвига и произвольной двоичной функции степени нелинейности 2.
Проведено исчерпывающее изучение строения регулярных систем, координатные функции которых эквивалентны относительно преобразования циклического сдвига координат, и построены классы двоичных функций степени нелинейности 3, порождающие такие системы.
Описано множество регулярных систем, построенных на основе фильтрующего генератора с нелинейной функцией усложнения второй степени.
4) Проведена каталогизация регулярных систем однотипных двоичных функций от четырёх переменных.
Теоретическая ценность представлена следующими содержащимися в работе положениями.
Выделены и исследованы инварианты подстановок, задаваемых регулярными системами однотипных двоичных функций, позволяющие существенно сократить количество представителей при каталогизации систем однотипных функций.
Описаны классы преобразований, порождаемые нелинейными функциями с помощью операции сдвига и операции циклического сдвига координат векторов пространства Vn.
Исследована структура регулярных систем, построенных на основе аффинного регистра сдвига с нелинейной функцией усложнения второй степени нелинейности от трёх переменных.
Практическая значимость работы состоит в том, что предложенный в диссертации способ задания биективного отображения приводит к существенному снижению емкостной сложности реализации этого отображения на новой и перспективной элементной базе. Представленный в приложении к диссертации каталог всех регулярных геометрически эквивалентных систем функций от четырёх переменных позволяет при разработке систем защиты информации выбирать легко реализуемые в пороговой логике преобразования с заданными характеристиками нелинейности.
Апробация работы проведена на XXXI Международной конференции «Информационные технологии в науке, образовании, социологии и бизнесе»; V, VI и VII Всероссийских симпозиумах по прикладной и промышленной математике; совместных семинарах кафедр №711, №712 и №713 Института криптографии, связи и информатики (ИКСИ) Академии ФСБ России. Результаты диссертации включены в отчёт по теме №4 Академии криптографии Российской Федерации, использованы в одном из курсов вузовского потока ИКСИ.
Публикации. Основные результаты диссертации опубликованы в 8 работах, из них три статьи опубликованы в рецензируемых журналах, рекомендованных ВАК для опубликования результатов докторских диссертаций.
Структура и объём работы. Диссертация состоит из введения, трёх глав, каталога, заключения и списка литературы. Она изложена на 141 странице, включает 28 таблиц и 4 рисунка. Список литературы содержит 53 наименования.
Регулярные системы #п-однотипных функций степени 2
Развитие информационных технологий, совершенствование средств обработки и хранения информации способствует расширению сферы использования вычислительных средств. Достижения в области аппаратной и программной реализации алгоритмов обработки данных обеспечивают удобство эксплуатации технических средств. Объём обрабатываемых данных растёт в соответствии с возрастающими потребностями современного общества, поэтому автоматизированное использование компьютерных технологий является одним из самых практичных методов обработки информации.
Решение задач идентификации и аутентификации, контроля целостности и распознавания образов требует построения преобразований фрагментов информации, зависящих от некоторого секрета. Традиционные криптографические методы защиты информации используют обратимые преобразования, зависящие от секретного ключа. Основным требованием, предъявляемым к таким преобразованиям, является стойкость к атакам, направленным на нахождение защищаемой информации, без знания секретного ключа, либо нахождение самого секретного ключа. Стойкость обычно измеряется временем, которое необходимо для успешного выполнения атаки при некоторых фиксированных ресурсах, имеющихся в распоряжении у злоумышленника, реализующего атаки на систему защиты. Повышение стойкости системы защиты путём усложнения аналитической и статистической структуры используемых преобразований приводит к увеличению объёма ресурсов, требуемых для реализации системы защиты. Уровень стойкости системы защиты характеризуется нижней оценкой времени, требуемого на нарушение системы защиты, и определяется в первую очередь вычислительными ресурсами потенциального взломщика, а также временем, в течение которого защищаемая информация должна оставаться недоступной взломщику. Повышение стойкости системы защиты приводит к росту материальных затрат потенциального нарушителя, используемых для оплаты технических, интеллектуальных и организационных средств при проведении атаки. Материальные средства, выделяемые на проведение атаки, определяются выгодой, которую получит нарушитель при нанесении ущерба системе защиты. Такая выгода противника может быть оценена стоимостью атакуемых активов. Широкое применение приобретают компактные узлы и блоки переработки информации в системах управления, идентификации и контроля, размещённые в условиях, когда основным ценовым параметром становится емкостная сложность реализации преобразования. При этом вопросы стойкости используемой системы защиты не являются первоочередными, поскольку ценность обрабатываемой этими узлами информации стремительно падает с течением времени. Такие узлы используются для контроля доступа, идентификации транспортных средств, отслеживания активов, контроля производственных запасов, автоматизации производства и складской обработки, контроля за перемещением потоков грузов и транспорта и других задач [48, 10, 47, 53, 42]. Особую ценность минимизация емкостной сложности реализации узлов переработки информации приобретает, в частности, в аэрокосмической области при решении задач идентификации удалённых объектов.
В алгоритмах защиты широко используются взаимно однозначные преобразования или подстановки двоичных векторов. Пусть Vn — множество двоичных векторов длины п, п Є N, Ф — некоторое биективное преобразование множества Vn, задающее подстановку 7Г Є S(Vn). Подстановка 7г может быть задана таблично. При таком задании каждому вектору ж Є Vn ставится в соответствие его образ ж71". Одномерный массив образов {ж71" : х Є Vn} индексируется векторами х Є Vn и сохраняется в памяти. Реализация действия подстановки 7Г на вектор х состоит в считыванпи содержимого памяти по адресу, соответствующему вектору х. Объём памяти, необходимый для табличного задания подстановки на Vn, составляет к-2П битов, где к — минимальный размер в битах области памяти, в которой может быть сохранён n-мерный двоичный вектор и к которой может быть реализована адресация. Например, если в некотором вычислительном устройстве минимальной адресуемой областью памяти является один байт, то для сохранения 7-мерного двоичного вектора и последующей адресации к нему потребуется 8 битов памяти. Для табличного задания подстановки 7г Є SiVj) в этом случае потребуется 8-27, при том что 27 памяти фактически не используется. Если задать подстановку 7Г Є S(Vn) с помощью системы координатных функций Сп = (Д,... ,/„), сохранить каждую координатную функцию fi, іє1,п, отдельно и с помощью дополнительных вычислений организовать доступ к значению /(ж) для всех ж Є Vn таким образом, чтобы каждая функция занимала в памяти 2п битов, то для реализации подстановки 7Г потребуется п-2п битов памяти.
Регулярные системы (сг)-однотппных функций
В процессе проведения исследования для изучения инженерных вопросов реализации схем защиты информации применялись алгебраические методы и методы математической логики. Основные результаты работы получены с использованием теории булевых функций и теории алгоритмов, а также путём разработки специальных программных средств и проведения вычисл итсл ьн ых экспериментов.
Научная новизна диссертации состоит в следующем. 1) Дано теоретическое описание регулярных систем двоичных функций, построенных на основе группы сдвига и произвольной двоичной функции степени нелинейности 2. 2) Проведено исчерпывающее изучение строения регулярных систем, координатные функции которых эквивалентны относительно преобразования циклического сдвига координат, и построены классы двоичных функций степени нелинейности 3, порождающие такие системы. 3) Описано множество регулярных систем, построенных на основе фильтрующего генератора с нелинейной функцией усложнения второй степени. 4) Проведена каталогизация регулярных систем однотипных двоичных функций от четырёх переменных. Теоретическая ценность представлена следующими содержащимися в работе положениями. 1) Выделены и исследованы инварианты подстановок, задаваемых регулярными системами однотипных двоичных функций, позволяющие существенно сократить количество представителей при каталогизации систем однотипных функций. 2) Описаны классы преобразований, порождаемые нелинейными функциями с помощью операции сдвига гг операции циклического сдвига координат векторов пространства Vn. 3) Исследована структура регулярных систем, построенных на основе аффинного регистра сдвига с нелинейной функцией усложнения второй степени нелинейности от трёх переменных.
Практическая значимость работы состоит в том, что предложенный в диссертации способ задания биективного отображения приводит к существенному снижению емкостной сложности реализации этого отображения на новой и перспективной элементной базе. Представленный в приложении к диссертации каталог всех регулярных геометрически эквивалентных систем функций от четырёх переменных позволяет при разработке систем защиты информации выбирать легко реализуемые в пороговой логике преобразования с заданными характеристиками нелинейности.
Пусть Vn — пространство двоичных векторов длины п, Тп — множество двоичных функций от п переменных Любое преобразование Ф пространства Vn может быть задано системой (/i,... ,fn) двоичных функций fi Є J-n, і Є1, п, называемых координатными функциями преобразования Ф. Действие преобразования Ф : х н у, х,у Є Vn, определяется системой уравнений
Биективность преобразования Ф, или регулярность системы координатных функций преобразования Ф, является одним из требований, предъявляемых к преобразованиям векторных пространств.
В диссертационной работе исследуются системы функций, эквивалентных относительно некоторой группы преобразований пространства Vn. В качестве такой группы преобразований научным руководителем диссертационной работы Никоиовым В.Г. предложено использовать преобразования однотипности, образующие группу Джевонса, обозначаемую через Qn, а также геометрические преобразования, которые включают в себя преобразования однотипности и преобразование, заключающееся в инвертировании значений координатных функций. Выбор таких преобразований обусловлен несколькими соображениями. Во-первых, являясь изометрическими, такие преобразования сохраняют геометрическое строение координатных функций. Кроме того, в этом случае возникает возможность проводить классификацию функций и систем однотипных функций с помощью графов связности единичных вершин n-кубов. Такой подход был исполь 10зован Никоновым В. Г. в работе «Классификация минимальных базисных представлений всех булевых функций четырёх переменных» [13] и впоследствии Гизуновым С. А. и Носовым В. А. в работе «Классификация всех булевых функций 4-х переменных по классам Шефера» [1].
В первой главе диссертации вводятся понятия регулярной системы G-однотипных функций и функции порождающей эту систему, описываются классы регулярных систем функций, эквивалентных относительно просто реализуемых групп преобразований: группы сдвигов Нп и группы (а), порождённой преобразованием циклического сдвига координат векторов. В 1.1 приведены критерии регулярности систем однотипных функций. Введено понятие типа регулярной системы, которое соответствует типу порождающей функции. Доказано, что свойство порождать регулярную систему с помощью преобразований произвольной группы G является инвариантом функций, эквивалентных относительно нормализатора N$yn)(G) группы G в группе S(yn) подстановок на Vn.
Условия регулярности системы С(/; р/) для фильтрующего генератора
В первой главе диссертационной работы отмечалось, что в целях упрощения технической реализации регулярной системы G-однотипных функций (/, /Ql,..., /ап_1)з &і Є G S(Vn), і є l,n—l, подстановки щ должны быть сами технически просто реализуемы. Более того, даже в случае, когда а; = а\ і Є l,n—1, для некоторого а є S(Vn), вопрос выбора простой реализации подстановки а остаётся актуальным. В данной главе описываются классы регулярных систем вида C(f; a) = (/, /Q,..., /71-1)) при построении которых используется преобразование а, реализуемое за один такт работы линейного регистра сдвига. Широкое распространение линейных регистров сдвига над конечными полями и кольцами обусловлено целым рядом факторов ([19]). Среди них можно отметить: - использование только простейших операций сложения и умножения, аппаратно реализованных практически на всех вычислительных средствах; - высокое быстродействие алгоритмов, создаваемых на их основе; - большое количество теоретических исследований свойств регистров сдвига. В диссертационной работе рассматриваются аффинные регистры сдвига над полем GF(2). За один такт работы регистр сдвига длины п a j Є GF(2), і Є 1, тг—1, реализует преобразование вектора х в вектор (х 2,. , хп, 1{х)). Необходимым и достаточным условием взаимно однозначности такого преобразования является существенная зависимость линейной функции / от переменной х\ ([5]). В этом случае регистр сдвига называется регулярным и задаёт подстановку на Vn, которую будем обозначать через pjl. Регистр сдвига с обратной функцией /, тождественно равной х\, осуществляет циклический сдвиг вектора х влево.
Такое преобразование было рассмотрено в 1.3. Во введённых обозначениях подстановка а равна/. В отечественной и зарубежной литературе (см. например [49]) исследованы свойства фильтрующих генераторов с аффинной функцией обратной связи и нелинейной двоичноії функцией выхода /. В двоичном случае фильтрующий генератор позволяет из начального состояния ж Є Vn выработать двоичную последовательность 71)72? ч знак с номером /, г Є N, которой равен За п тактов работы фильтрующий генератор реализует преобразование (х і,... ,жп) н- (7ъ 7п) пространства Vn, задаваемое системой координатных функций (f,fPl,..., /р" ), которая во введённых обозначениях есть C{f\pi). Система C(f;pi) является ( -однотипной, где (pi) — циклическая группа, порождённая подстановкой pi. Регулярность системы функций C(f;p{) эквивалентна определённости системы нелинейных уравнений рекуррентного типа [37] для всех векторов (7ь 72, , In) Є Vn. В общем случае задача решения систем нелинейных, в том числе и квадратичных уравнений, относится к классу iVP-сложных задач [45, 4].
В рассматриваемом случае необходимо исследовать определённость 2п систем уравнений с различными правыми частями. Наборы функций, порождающие полиномиально решаемые классы систем нелинейных уравнений представлены в работе [4]. Такими множествами функций являются аффинные функции, некоторые биюнктивные функции, а также дважды слабо положительные и дважды слабо отрицательные функции. Рассмат риваемые в этой главе функции к этим классам не относятся. Например, функция / = х2 + хз + х\Х2, рассматриваемая в 2.2. Во-первых, её степень нелинейности равна 2. Во-вторых, эта функция сбалансирована, а, как показано в работе [4], не существует сбалансированных дважды слабо положительных или дважды слабо отрицательных функций, зависящих более чем от двух переменных. И, наконец, с точностью до эквивалентности относительно группы 5з классы сбалансированных биюнктивных функций представлены двумя функциями [4]
Описание каталога регулярных систем (-однотипных функций
В главе предлагается принцип классификации регулярных систем геометрически эквивалентных функций, основанный на перечислении представителей типов систем. Среди всех классов геометрической эквивалентности сбалансированных функций выделены классы, порождающие регулярные системы. Для каждого из этих классов построены порождаемые соответствующими функциями подстановки, для классификации которых использовано введённое автором отношение эквивалентности. Приводится описание каталога регулярных систем ( -однотипных двоичных функций, представленного в приложении к диссертации.
В соответствии с общими принципами классификации отображений [33] на множестве подстановок из S(Vn) вводится отношение GH-эквивалентиости. В рассматриваемом случае выбираются две группы G и Я подстановок степени 2п. Подстановки тг,7г Є S(Vn) называются GH-эквивалентными, если существуют такие подстановки а Є G и /? 6 Н, что 7г = атт/З. Очевидно, что введённое отношение является отношением эквивалентности на множестве подстановок.
Задача построения полных каталогов классов эквивалентности подстановок имеет практическое приложение, поскольку такие каталоги дают фактический материал для проверки различных гипотез и предположений о свойствах представителей классов эквивалентности, а также позволяют получить суммарные сведения и обнаружить корреляционные связи между различными параметрами. При построении любой классификации необходимо уделять отдельное внимание выбору групп подстановок. Так, если группа мала, то использование классификации затруднительно в связи с необходимостью анализа большого количества представителей. С другой стороны, большая по мощности группа подстановок приводит к получению малоинформативной классификации, содержащей небольшое число представителей классов очень больших размеров. Помимо этого построение классификации подстановок с однотипными координатными функциями накладывает ограничение на выбор групп, поскольку возникает необходимость построения таких классов, представители которых сами задаются регулярными системами однотипных координатных функций. Как было показано в первой главе, эти требования предъявляются одновременно к группам G и Н.
Перейдём к построению классификаций. В первую очередь определим разбиение множества сбалансированных функций от п переменных на классы эквивалентности по нормализатору NsVn(G) группы 6?, объединяя при этом классы L/]jv5v,n(G) И П]м3уп(с) В каждом из полученных классов указываем представителей G типов. Далее анализируем каждый из представителей класса следующим образом. Для выбранного представителя / класса [/W (G) создаём упо-рядоченныи в соответствии с установленным заранее порядком элементов группы G = {а\,.. . A\G\} набор представителей G-типа [/](?. При этом, если группа инерции JGU) имеет мощность, большую 1, то из этого набора представителей исключаем совпадающие с / функции. Пусть где /0 = /, Т = [/]G ) упорядоченный набор представителей G-типа [f]G . Функцию / последовательно за п—1 шаг достраиваем, если это возможно, до регулярной системы, перебирая все возможные упорядоченные наборы из п—1 функции. При этом, если на шаге t Є l,n—2 получена несбалансированная [12] (і + 1)-мерная функция (/о, Л,... Jt) : Vt+1 - Vt+1, то переходим к рассмотрению следующей по порядку системе координатных функций.
В результате получаем регулярные системы вида (/, fai,..., fan l). Каждой такой системе соответствует упорядоченный по возрастанию набор подстановок {е,а\,... ,an-i}, е — единичная подстановка, имеющий свой порядковый номер при лексикографическом упорядочивании всех наборов из п преобразований группы G. Если для некото рого і Є 1,п—1 после упорядочивания по возрастанию номеров набор {аг Х " е aJl - 1,--- ,а ї1 an-i] будет иметь порядковый номер меньше, чем исходный набор {е, «i,... ,an-i}, то систему (/, /ttl,..., fan l) исключаем из рассмотрения. В итоге для выбранного (7-типа будет составлен набор систем-пред ставителей классов GQn-эквивалентности. В случае, когда группа G является подгруппой аффинной группы AGL(n,2), а именно такой случай будет рассмотрен при построении классификации регулярных систем ( -однотипных функций, инвариантами классов GQn-эквивалентности систем функций являются характеристики нелинейности .
Для нумерации подстановок группы Qn в работе использован следующий способ. Каждой подстановке rja из группы сдвигов Нп ставится в соответствие порядковый номер вектора аєУп при лексикографической сортировке векторов пространства Vn. Так, номер А а подстановки г)аєНп, a = (ai,... ,an) Є Vn, равен
