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

На правах рукописи

004600420

Саранцев Алексей Васильевич

ПОСТРОЕНИЕ ВЗАИМНО ОДНОЗНАЧНЫХ ПРЕОБРАЗОВАНИЙ НА ОСНОВЕ ОДНОТИПНЫХ

ДВОИЧНЫХ ФУНКЦИЙ В СВЯЗИ С ЗАДАЧАМИ ЗАЩИТЫ ИНФОРМАЦИИ

05.13.19 — методы и системы защиты информации, информационная безопасность

АВТОРЕФЕРАТ диссертации на соискание учёной степени

Москва — 2010

1 ДПР 2010

004600420

Работа выполнена на кафедре №713 факультета прикладной математики Института криптографии, связи и информатики Академии ФСБ России

Научный руководитель: доктор технических наук,

доцент В. Г. Никонов

Официальные оппоненты: доктор технических наук,

профессор Е. Е. Тимонина

кандидат технических наук В. Б. Нетыкшо

Ведущая организация: Пограничная академия

ФСБ России

Защита состоится апреля 2010 г. в часов на заседании диссертационного совета Д 212.198.13 при государственном учреждении Российский государственный гуманитарный университет (РГГУ) по адресу: г.Москва, Миусская пл., д. б (Профессорский зал).

С диссертацией можно ознакомиться в библиотеке Российского государственного гуманитарного университета.

'11

Автореферат разослан марта 2010 г.

Учёный секретарь диссертационного совета, кандидат технических наук,

старший научный сотрудник '.. )/)/'.., _______Д. Б.Халяпин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Развитие информационных технологий, совершенствование средств обработки и хранения информации способствует расширению сферы использования вычислительных средств. Достижения в области аппаратной и программной реализации алгоритмов обработки данных обеспечивают удобство эксплуатации технических средств. Объём обрабатываемых данных растёт в соответствии с возрастающими потребностями современного общества, поэтому автоматизированное использование компьютерных технологий является одним из самых практичных методов обработки информации.

Решение задач идентификации и аутентификации, контроля целостности и распознавания образов требует построения преобразований фрагментов информации, зависящих от некоторого секрета. Традиционные криптографические методы защиты информации используют обратимые преобразования, зависящие от секретного ключа. Основным требованием, предъявляемым к таким преобразованиям, является стойкость к атакам, направленным на нахождение защищаемой информации, без знания секретного ключа, либо нахождение самого секретного ключа. Стойкость обычно измеряется временем, которое необходимо для успешного выполнения атаки при некоторых фиксированных ресурсах, имеющихся в распоряжении у злоумышленника, реализующего атаки на систему защиты. Повышение стойкости системы защиты путём усложнения аналитической и статистической структуры используемых преобразований приводит к увеличению объёма ресурсов, требуемых для реализации системы защиты. Уровень стойкости системы защиты характеризуется нижней оценкой времени, требуемого на нарушение системы защиты, и определяется в первую очередь вычислительными ресурсами потенциального взломщика, а также временем, в течение которого защищаемая информация должна оставаться недоступной взломщику. Повышение стойкости системы защиты приводит к росту материальных затрат потенциального нарушителя, используемых для оплаты технических, интеллектуальных и организационных средств при проведении атаки. Материальные средства, выделяемые на проведение атаки, определяются выгодой, которую получит нарушитель при нанесении ущерба системе защиты. Такая выгода противника может быть

оценена стоимостью атакуемых активов. Широкое применение приобретают компактные узлы и блоки переработки информации в системах управления, идентификации и контроля, размещённые в условиях, когда основным ценовым параметром становится емкостная сложность реализации преобразования. При этом вопросы стойкости используемой системы защиты не являются первоочередными, поскольку ценность обрабатываемой этими узлами информации стремительно падает с течением времени. Такие узлы используются для контроля доступа, идентификации транспортных средств, отслеживания активов, контроля производственных запасов, автоматизации производства и складской обработки, контроля за перемещением потоков грузов и транспорта и других задач. Особую ценность минимизация емкостной сложности реализации узлов переработки информации приобретает, в частности, в аэрокосмической области при решении задач идентификации удалённых объектов. ,

Цель работы состоит в разработке новых математических и технических принципов построения просто реализуемых на современной элементной базе биективных преобразований, используемых в средствах защиты информации и обеспечения информационной безопасности.

Методы исследования. В процессе проведения исследования для изучения инженерных вопросов реализации схем защиты информации применялись алгебраические методы и методы математической логики.

Научная новизна диссертации состоит в следующем.

1) Дано теоретическое описание регулярных систем двоичных функций, построенных на основе группы сдвига и произвольной двоичной функции степени нелинейности 2.

2) Проведено исчерпывающее изучение строения регулярных систем, координатные функции которых эквивалентны относительно преобразования циклического сдвига координат, и построены классы двоичных функций степени нелинейности 3, порождающие такие системы.

3) Описано множество регулярных систем, построенных на основе фильтрующего генератора с нелинейной функцией усложнения второй степени.

4) Проведена каталогизация регулярных систем однотипных двоичных функций от четырёх переменных.

Теоретическая ценность представлена следующими содержащимися в работе положениями.

1) Выделены и исследованы инварианты подстановок, задаваемых регулярными системами однотипных двоичных функций, позволяющие существенно сократить количество представителей при каталогизации систем однотипных функций.

2) Описаны классы преобразований, порождаемые нелинейными функциями с помощью операции сдвига и операции циклического сдвига координат векторов пространства Уп.

3) Исследована структура регулярных систем, построенных на основе аффинного регистра сдвига с нелинейной функцией усложнения второй степени нелинейности от трёх переменных.

Практическая значимость работы состоит в том, что предложенный в диссертации способ задания биективного отображения приводит к существенному снижению емкостной сложности реализации этого отображения на новой и перспективной элементной базе. Представленный в приложении к диссертации каталог всех регулярных геометрически эквивалентных систем функций от четырёх переменных позволяет при разработке систем защиты информации выбирать легко реализуемые в пороговой логике преобразования с заданными характеристиками нелинейности.

Апробация работы проведена на XXXI Международной конференции «Информационные технологии в науке, образовании, социологии и бизнесе»; V, VI и VII Всероссийских симпозиумах по прикладной и промышленной математике; совместных семинарах кафедр №711, №712 и №713 Института криптографии, связи и информатики (ИКСИ) Академии ФСБ России. Результаты диссертации включены в отчёт по теме №4 Академии криптографии Российской Федерации, использованы в одном из курсов вузовского потока ИКСИ.

Публикации. Основные результаты диссертации опубликованы в 8 работах, из них три статьи опубликованы в рецензируемых журналах, рекомендованных ВАК для опубликования результатов докторских диссертаций.

Структура и объём работы. Диссертация состоит из введения, трёх глав, каталога, заключения и списка литературы. Она изложена на 141 странице, включает 28 таблиц и 4 рисунка. Список литературы содержит 53 наименования. '

СОДЕРЖАНИЕ РАБОТЫ

В первой главе диссертации введены понятия регулярной системы однотипных функций и функции, порождающей эту систему, определено понятие типа регулярной системы. Описаны классы регулярных систем функций, эквивалентных относительно просто реализуемых групп преобразований: группы сдвигов и группы, порождённой преобразованием циклического сдвига координат векторов. Получен ряд необходимых условий того, что данная двоичная функция порождает регулярную систему. Описаны регулярные системы функций, порождаемые двоичными функциями степени нелинейности 2 с помощью преобразований сдвига векторов. Исследованы свойства подстановок, координатные функции которых эквивалентны относительно преобразования циклического сдвига переменных.

Во второй главе диссертационной работы построены классы регулярных систем функций, эквивалентных относительно преобразования, реализуемого за один такт работы регулярного регистра сдвига с аффинной двоичной функцией обратной связи. Доказано, что подстановки, задаваемые этим классом систем, имеют вторую степень нелинейности. Найдены классы двоичных функций степени нелинейности 3, порождающие регулярные системы с помощью преобразования циклического сдвига неременных. Указан в явном виде способ построения системы координатных функций обратной подстановки.

В третьей главе предложен принцип каталогизации регулярных систем геометрически эквивалентных двоичных функций, основанный на перечислении представителей типов систем. С помощью этого принципа получено полное описание рассматриваемых регулярных систем двоичных функций от четырёх переменных, которое в виде каталога представлено в приложении. Среди всех классов геометрической эквивалентности сбалансированных

функций выделены классы, порождающие регулярные системы. Для каждого из этих классов построены порождаемые соответствующими функциями подстановки, для классификации которых использовано введённое автором отношение эквивалентности. Для каждой подстановки, приведённой в каталоге, указаны характеристики нелинейности.

Перейдём к краткому изложению основных результатов диссертационной работы.

Пусть Уп — пространство двоичных векторов длины п, множество всех двоичных функций от п переменных обозначим через Тп, а множество всех отображений пространства Уп в пространство Ут через Тп,т. Произвольное отображение Ф € может быть задано упорядоченным набором или системой координатных функций (Д.... ,/т), где 6 Т^ г 6 1,т. При таком задании действие отображения

Одним из важных требований, предъявляемых к отображениям Тп,т, является сбалансированность или уравновешенность. Напомним, что отображение Ф £ (т < п) называется сбалансированным, если мощность полного прообраза любого вектора из Ут равна 2п~т. В случае, когда длины входных и выходных векторов совпадают, то есть тп=п, сбалансированное отображение Ф € Гп,п является биективным. Биективные отображения из 3-п,т задают подстановки степени 2" на множестве Уп. Множество всех подстановок на Уп будем обозначать 5(У„).

Система координатных функций (Л,... ,/п), /< £ 1 £ 1,п, биективного отображения называется регулярной системой. Систему координатных функций подстановки 7г € 5(14) будем обозначать через Сп.

Известные критерии регулярности преобразований пространства Уп, заданных двоичными координатными функциями, не дают достаточных условий для задания координатных функций регулярных систем в явном виде.

Всесторонне изучены такие классы регулярных преобразований пространства Уп как линейные и аффинные преобразования, регистровые пре-

Ф:жь-»у, 1=(ль...,1„)еК, У = {Уи---,Ут)^Уг

определяется системой уравнений

(1.1)

образования, перестановочные многочлены полей характеристики, преобразования «треугольного» типа и другие. Известны также способы построения классов регулярных преобразований, задаваемых системами координатных функций ограниченной степени нелинейности.

В диссертации исследуется класс преобразований пространства У„, координатные функции которых могут быть получены из одной и той же двоичной функции посредством преобразования её координат с помощью легко реализуемых сервисных команд. Для описания свойств этих отображений и их классификации удобнее рассматривать множества таких преобразований переменных, которые образуют некоторую группу С в группе 5(УП). В этом случае координатные функции рассматриваемых отображений принадлежат одному и тому же классу эквивалентности относительно группы. Определим действие группы б < 5(14) на множестве Тп двоичных функций от п переменных формулой

г(х) = /(*"''), /е^аес.х

Функции / и /г называются эквивалентными относительно группы С, или б-эквивалентными (С-однотипными), если существует элемент а 6 С, такой, что Н = /а. В этом случае будем использовать обозначение / ~ И.

Отношение ~ разбивает множество Тп на классы эквивалентных элементов, которые будем называть (7-типами. (7-тип, содержащий функцию /, будем обозначать [/]с-

Определение 1.1. Система двоичных функций (/1,... ,/п) от п переменных называется С-однотипной, если все функции этой системы принадлежат одному С-типу.

Система б-однотипных функций может быть задана в виде

(/,/"', •••,/""-'), «<€(?,¿еТТй-Г- (1-2)

Будем говорить, что система (1.2) порождается функцией / с помощью подстановок «1,02,... ,ап_х из группы й, а саму функцию / будем называть порождающей.

Представляют интерес б-однотипные системы, обладающие свойством регулярности. Для реализации действия подстановки 7Г € 5(К,) с помощью

системы б-однотипных координатных функций С* достаточно реализовать одну порождающую функцию и п—1 сервисную команду, определяемую подстановку из группы С?. Требование к снижению емкостной сложности реализации преобразования обуславливает необходимость уменьшения объёма памяти, используемой для реализации порождающей функции и соответствующих сервисных команд. В связи с этим в диссертации рассматриваются такие преобразования векторов из Уп, которые с одной стороны легко реализуются программными и аппаратными способами, а с другой — при действии на переменные порождающей функции сохраняют её характеристики нелинейности. В частности, к таким преобразованиям относятся аффинные преобразования пространства У„.

Обозначим через СР(2)*п п множество всех обратимых матриц порядка п над полем С.Р(2). Пусть А € п и Ь € К- Действие подстановок Фа и Фа,ь из 8(Уп) определим формулами

Ух 6 К, : хфл = хА, хфл* = хА + Ь. Обозначим через

СЦп,2) =|^:ЛеСР(2);п} и

АСЦп, 2) = : ЛбС^(2);п,6 £ Уп}

полную линейную и нолную аффинную группы размерности п над нолем С?Р(2) соответственно.

В диссертации рассмотрены следующие подгруппы группы АС?2/(п, 2).

Группа Нп сдвигов пространства Уп- Для т)а б Нп 1;а : х ж + а, авУп.

Группа 5П перестановок переменных. Для подстановки т € 5„, соответствующей подстановке те5п = 5(1, п),

т : х = (хи.....хп) к» (жт-1(1), хт-ц2),..., жт-1(п)).

Группа — группа Джевонса или группа однотипных преобразований,

Яп — ЗпНп.

(

Группа (а) — циклическая группа, порождённая преобразованием циклического сдвига координат вектора, а~х : ж = (ж1,...,х„) (ж2, ...,хп,х{), хеУп.

Группа {р{) — циклическая группа, порождённая преобразованием, реализуемым за один такт работы регистром сдвига с аффинной функцией обратной связи,

Р11 :х = {хъ... ,хп) (х2,... ,хп, 1{х)),

хеУп, 1{х) =Ж1 + ^"=2а<:г; + ао1 а2,...,ап,а0еСГ(2).

Без каких-либо ограничений на выбор группы С задача построения регулярных систем б-однотипных функций являлась бы тривиальной, поскольку любая подстановка на V,, задаётся регулярной системой 5(14)-однотипных функций. Более того, согласно приведённому далее утверждению 1.1 любая подстановка 7г € 5(14) может быть задана системой координатных функций вида /",..., , а£5(14), которую будем обозначать через С(/; а).

Утверждение 1.1. Для произвольной подстановки 7Г € 5(14) справедливо равенство

где / — первая координатная функция подстановки 7Г, а € 5(14) — подстановка циклического сдвига вектора вправо.

Пусть подстановка 7Г £ 5(14) задаётся системой С-однотипных координатных функций Сж. Для всех подстановок а, /3 € 5(14) система функций Са7Гр всегда будет регулярной, а вот свойство С-однотипности её координатных функций может быть нарушено, что подтверждается приведёнными в диссертации примерами систем функций от произвольного числа переменных.

Обозначим через (М) = {а £5(14) I аМ = Ма] нормализатор множества М С 5(14) в группе 5(14).

Утверждение 1.2. Пусть ¿7 < 5(14) и подстановка тг£ 5(14) задаётся системой б-однотипных координатных функций. Тогда для любых а 6 Л'^у^С) и Р £ 5П система координатных функций подстановки ап/3 является регулярной системой (^-однотипных функций.

Следствие 1.1. Пусть <? < 5(14) и подстановка т € 5(14) задаётся системой Сж — . ,/„) б-однотипных координатных функций такой, что /5 6 [/Ид, где Д = /1 + 1. Тогда для любых а £ Л^у^Сг) и /3 € ¿¡)п система координатных функций подстановки а7г/3 является регулярной системой б-однотипных функций.

Следствие 1.2. Свойство функции / 6 состоящее в том, что она порождает регулярную систему б-однотипных функций, является инвариантом С-типа [/]с.

Из следствия 1.2 вытекает корректность определений 1.2 и 1.3.

Определение 1.2. б-тип [/]с называется порождающим, если его представитель / порождает регулярную систему С?-однотипных функций.

Определение 1.3. С-типом регулярной системы б-однотипных функций называется С-тин порождающей функции системы.

Утверждение 1.3. Пусть С < 5(^4) и / £ 74- Если функция / порождает регулярную систему (7-однотипных функций, являющуюся системой координатных функций некоторой подстановки 7г€5(14), то система координатных функций подстановки жв порождается функцией /, где в — преобразование, осуществляющее инвертирование значений координат вектора, в : х х+1, для любого хвУп.

В диссертации исследован способ построения регулярных систем с использованием преобразований сдвига векторов пространства Уп. Действие подстановки г/а из группы сдвигов Нп на вектор х £ У„ состоит в покоординатном сложении векторов ж и а. В случае, когда длины суммируемых векторов не превосходят разрядность процессора, операция покоординатного сложения двоичных векторов может быть выполнена за один такт его работы. Поэтому реализация подстановки, координатные функции которой образуют регулярную систему .//„-однотипных функций, состоит в реализации одной двоичной функции от п переменных и п—1 операции покоординатного сложения в 14.

На основе результатов аффинной классификации квадратичных форм над полем СР(2), в диссертации описаны все регулярные системы #„-однотипных функций, порождаемые функцией степени нелинейности 2.

Утверждение 1.4. Функция / £ Тп второй степени нелинейности порождает регулярную систему //„-однотипных функций в том и только том случае, когда выполнены следующие два условия:

1) п — нечётно;

2) / аффинно эквивалентна функции

Х1Х2 + Х3Х4 + . . . + Хп—2Хп~1 + х„.

Одним из основных результатов диссертации является теорема 1.1, в которой описаны все регулярные системы Я„-однотипных функций второй степени нелинейности.

Теорема 1.1. Квадратичная форма над полем С?/7'(2)

/(х) = х\хг + ж3х4 + ... + хп-2Х„-1 + хп порождает регулярную систему Я„-однотипных функций

(/, Г1'1, ■ • •, ), 4«, 6 Я„, г € 1, п-1, в том и только том случае, когда п нечётно и векторы (О,... ,0,1) ,«1,..., ап_!

линейно независимы.

Задав на множестве всех элементов группы сдвигов отношение частичного порядка, отвечающее лексикографическому порядку векторов из К,, и используя формулы для вычисления мощности класса аффинно эквивалентных функций, в диссертации найдено количество //„-однотипных регулярных систем.

Следствие 1.3. Пусть п>3 — нечётно, /(х) = 24X2 + ... + хп_2£п-1 + хп. Тогда имеет место равенство

2-ПГо(2П-21)_

|и

А01п,2) ~~ /п-хл2

- (2« — 1) - (2« — 1) ■... - — 1)

и существует

(2" - 2) (2П - 22) ■... • (2П - 2"-1) регулярных систем вида (/, р1,..., /т>"-1) Я„-однотипных функций, у которых порождающие преобразования упорядочены в соответствии с отношением частичного порядка.

Таким образом, в случае, когда п — нечётное число, в работе описаны все регулярные системы //„-однотипных функций, порождаемые двоичной функцией второй степени нелинейности. Непосредственной проверкой с помощью вычислительной техники автором диссертации установлено, что описанными выше системами исчерпываются все регулярные системы Ну и Щ-однотипных функций, а регулярных систем /^-однотипных функций не существует. В то же время показано, что существуют функции, порождающие регулярные системы #„-однотипных функций, степень нелинейности которых больше 2. Для построения такого примера была использована известная аффинная классификация кубических форм от шести переменных.

Далее в диссертации изучено строение регулярных систем, задаваемых с помощью преобразований, реализуемых перестановкой переменных порождающей функции. Техническая реализация таких преобразований состоит в изменении порядка считывания содержимого ячеек памяти, в которых записаны значения координат входного вектора ж, а программная — в умножении вектора ж на подстановочную матрицу, соответствующую подстановке т. Использование только одного преобразования перестановки переменных порождающей функции позволяет сократить емкостную сложность реализации регулярной системы. В диссертации обоснован выбор в качестве преобразования, используемого для порождения регулярной системы, преобразования циклического сдвига переменных. Пусть далее а € 5„ — такая подстановка, что

а'1 :х = (хи..:,хп) (х2,...,х„,х1),хеуп.

Используя алгоритм построения всех порождающих функций систем вида С(/; <т), аннонсированный РожковымМ. В., в диссертации описано множество всех подстановок, задаваемых рассматриваемыми системами.

Утверждение 1.5. Множество подстановок, системы координатных функций которых имеют вид С(/;сг), образует группу, являющуюся централизатором подстановки а в группе

Алгоритм построения всех регулярных систем вида С(/; а) позволяет задать порождающую функцию / только вектором её значений. Такое задаг ние функции при больших значениях п не приемлемо в виду значительных емкостных затрат. Поэтому практическую значимость представляет описание

классов порождающих функций, допускающих простую реализацию, а также способов построения новых функций на основе комбинации известных.

Пусть ш&81уп) — подстановка такая, что 1

ш:х = {хи...,хп) 1-4 (х„,х„_1,. ,.,Ж1), хеУ„.

Поскольку множество подстановок, координатные функции которых (а)-эквивалентны, образуют группу, для каждой подстановки 7Г £ 5(14) такой, что Ст, = С(/;ст), / € Тп, система координатных функций подстановки 7Г-1 есть С(Ь,\а) для некоторой функции /г£Тп.

Утверждение 1.6. Пусть 7Г £ 5(14) такая подстановка, что системой её координатных функций Ся является система функций С(/; а), а системой координатных функций обратной подстановки я--1 — система С(к;<т), для некоторых функций € Тп соответственно. Тогда для произвольного I € 2 системы и С^к"'"*2^; регулярны и подстановки, задаваемые

этими системами координатных функций взаимно обратны.

Через С<(а) обозначим правый ¿-циркулянт с порождающим вектором а 6 У„, то есть квадратную п х п-матрицу над полем 2), первая строка которой является вектором а, а остальные строки отличаются от предыдущей строки циклическим сдвигом на Ь позиций вправо. Далее речь пойдёт только о правых ¿-циркулянтах, поэтому правые ¿-циркулянты будем называть просто ¿-циркулянтами. Поскольку группа СГ(2)*пп обратимых матриц над полем СР(2) изоморфна полной линейной группы СЬ(п, 2), подстановку а = Фа € С?Х(п, 2), соответствующую обратимому ¿-циркулянту А £ С?2Г(2)* будем также называть ¿-циркулянтом. Отметим, что в этом случае ¿ и п взаимно простые числа.

Утверждение 1.7. Пусть а £ СЬ(п, 2) — обратимый ¿-циркулянт. Если функция / £ Тп порождает регулярную систему С(/; а), то функция также порождает регулярную систему С(/а; а).

Если при этом С(/; а)=С„, 7г£5(У„), то

с) = Са-1,^, где р - фС1{ 1,0.....о)-

Утверждение 1.8. Пусть А = С4(а) е СР(2)*П для вектора аеУп веса к а = .....0,^.1^,0.....0),

•1 ч

0 ^ ¿1 < ... < г/с ^ я — 1, ¿1,... ,г/ь е Мо; а = фАт, а подстановка 7Г е 8(Уп), такая, что Сп — С(/; а) для некоторой функции Тогда система

координатных функций подстановки на имеет вид:

Утверждения 1.7 и 1.8 показывают, что для любой подстановки ж € 5(Ю, заданной системой координатных функций С(/; а), и произвольных <и г-циркулянтов а и /3 соответственно, подстановка а-тг/З задаётся системой координатных функций С(д\сг) для некоторой функции д е Тп. Способ нахождения функции д по известным /, а и ¡3 вытекает из этих утверждений.

В первой главе диссертационной работы показано, что в целях минимизации емкостной сложности реализации регулярной системы С?-однотипных функций (/, /а1,..., У""-1), < 5(У„), г е 1, п—1, подстановки а* долж-

ны быть технически просто реализуемы. Более того, даже в случае, когда оц = а', г £ 1, гг— 1, для некоторого а € 3(Уп), вопрос выбора простой реализации подстановки а остаётся актуальным. В связи с этим во второй главе описываются классы регулярных систем вида С(/;р;), при построении которых используется преобразование р(~х, реализуемое за один такт работы

линейного регистра сдвига длины п с аффинной функцией обратной связи п-1 _

1(х) = а0 + XI + £ щхг, х = (я1,... ,х„)бУ„, 6(]?.Г(2), г€1,п—1.

г=1

В отечественной и зарубежной литературе исследованы свойства фильтрующих генераторов с аффинной функцией обратной связи и нелинейной двоичной функцией выхода /. В двоичном случае фильтрующий генератор позволяет из начального состояния ж € К, выработать двоичную последовательность 71,72,..., знак с номером г, г€М, которой равен

74 = /'¡"'(х) .

За п тактов работы фильтрующий генератор реализует преобразование (хь ... ,хп) И- (7х,... ,7п), (хи ... ,хп), (7ь ... ,7п) € Уп,

задаваемое системой координатных функций ...../р" Во введён-

ных обозначениях эта система обозначается С(/; р{). Система С(/; р{) является (/^-однотипной, где (р{) — циклическая группа, порождённая подстановкой р1. Регулярность системы функций С(/;р;) эквивалентна условию единственности решения системы нелинейных уравнений рекуррентного типа

{/*(*) =7<+1, ¿ебТ^Т, (2.3)

для всех векторов (71,72,..., 7п) € К,.

В общем случае задача решения систем нелинейных, в том числе и квадратичных уравнений, относится к классу ЛГР-сложных задач. В рассматриваемом случае необходимо исследовать 2" систем уравнений с различными правыми частями. При решении поставленного вопроса во второй главе диссертации получено описание класса функций второй степени нелинейности, порождающих регулярные системы вида С(/; р{), и вычислены степени нелинейности подстановок, задаваемых этими системами.

Теорема 2.1. Пусть п > 3, п — нечётно, /, 1£Тп. Тогда в каждом из следующих четырёх случаев:

1) / = х2 + х3 + х\х2 + а и I = х\ + Ьхп-1,

2) / = XI + х3 + х\х2 + а и I = х\ + Ьх„_1 + 6,

3) / = хх + х2 + х2х3 + а и I = XI + Ьх3,

4) / = Х1+Х3 + х2х3 + аи1 = Х1 + Ьх3 + Ь,

где а, Ь 6 СР{2), система функций С(/; р;) регулярна и является системой координатных функций подстановки тг е5'(К,) с характеристиками

х о х П+1

Л* = I и А^-1 = —.

При доказательстве теоремы 2.1 в явном виде получено решение соответствующей системы нелинейных уравнений и указаны алгебраические связи между подстановками, порождаемыми представленными в теореме функциями.

Преобразование циклического сдвига вектора является частным случаем преобразований, реализуемых аффинным регистром сдвига. Доказательство регулярности соответствующих систем функций также основывается на

нахождении решения системы нелинейных уравнений. При этом используется свойство преобразований задаваемых системами вида С(/;<т), состоящее в задании обратного преобразования системой функций такого же вида. Это свойство и лемма 2.1 позволяют доказать теорему 2.2, для удобства формулировки которой нумерация координат векторов из У„ начинается с 0.

Лемма 2.1. Пусть / £ Если для некоторой функции /г £ суперпозиция функций /1^/, /",..., тождественно равна функции х0, то системы функций С(/; <т) и С (/г; а) являются регулярными, и подстановки а, /3 £ 5(У„), задаваемые этими системами, являются взаимно обратными, то есть а =

Теорема 2.2. Пусть / £.7Г„. Система С(/; а) регулярна в каждом из следующих случаев:

1) п > 5, / = XI + Х0Х2Х3 или / = х2 + х0х!хз;

2) п ^ 5, п — нечетное, / = Хх + Х0Х2Х3 или / = х2 + Х0Ж1Х3;

3) п ^ 5, п не делится на 3,

(a) / = х0 + Х1Х2Ж3 или / = х3 + Х0Х1Х2,

(b) / = х0 + Х1Х2Ж3 ИЛИ / = Х3 + Х0Х1Х2.

Каждая из указанных функций порождает регулярную систему с помощью циклического сдвига координат только для представленных значений п.

При доказательстве регулярности систем функций, порождаемых функциями, представленными в теореме 2.2, были получены в явном виде порождающие функции систем, задающих обратные преобразования.

Новые классы функций третьей степени нелинейности, порождающих регулярные системы (сг)-однотипных функций, могут быть построены с использованием утверждений, доказанных в первой главе диссертации.

Прикладной задачей исследования регулярных систем б-однотипных функций является описание всех таких систем для фиксированной группы (3 преобразований пространства Уп. В третьей главе диссертации эта задача решается для систем <Эп-однотипных функций, п = 4. Выбор в качестве группы преобразований группы Джевонса С}п обусловлен тем, что эта группа является максимальной среди всех групп преобразований пространства Уп, которые

не нарушают геометрического строения двоичной функции. ф„-однотипные двоичные функции представляют собой одну и ту же логическую форму, записанную в разных системах координат, поэтому значительная часть свойств этих функций либо остаётся неизменной внутри типа, либо меняется несущественно.

В соответствии с общими принципами классификации отображений на множестве подстановок, задаваемых регулярными системами Q„-однотипных функций, вводится следующее отношение эквивалентности. Две подстановки 7Ti, 7Гг d S(V„) называются эквиалентными, если существуют такие подстановки а 6 NAGnn2){Qn), Р € Qn, что 7Ti = СОТ2/З. Из утверждения 1.2 и следствия 1.1 следует, что разбиение на классы эквивалентности относительно введённого отношения эквивалентности не нарушает свойства геометрической эквивалентности координатных функций систем, задающих эквивалентные подстановки. Из утверждения 3.1, следует, что в случае чётного п в качестве нормализатора NAGUn,2){Qn) группы Джевонса Qn в полной аффинной группе AGL(n,2) может быть выбрано произведение группы Q„ на линейную подстановку Фа-

Утверждение 3.1. Для любого четного п £ N группа Джевонса Q„ является нормальным делителем в группе Q*, равной Qn<f>a, где А = I + J, I — единичная п х n-матрица, J-nx n-матрица, все элементы которой равны 1.

Введённое отношение эквивалентности позволило при составлении «Каталога регулярных систем (¡^-однотипных двоичных функций» использовать «Классификацию минимальных базисных представлений вссх булевых функций от четырёх переменных», составленную В. Г. Никоновым. «Каталог...» составлен с использованием разработанного автором лично программного обеспечения в среде СУБД Paradox. Для вычислений характеристик функций и порождаемых ими систем использовалось разработанное автором программное обеспечение. Достоверность проведенных вычислений подтверждается непосредственным сравнением результатов вычислений, полученных с помощью пакетов прикладных программ, разработанных другими исследователями, а также апробацией в учебном процессе ИКСИ. Вёрстка «Каталога...» осуществлялась в издательской системе ВД^Х, чт0 обеспечивает совместимость отображения результатов каталогизации в системах, поддерживающих

форматированный вывод данных. В «Каталоге...» использован принцип классификации двоичных функций с помощью графов связности вершин, что значительно облегчает работу с каталогом и позволяет устанавливать корреляционные связи с классификационными исследованиями, проводимыми В. Г. Никоновым, В. А. Носовым и С. А. Гизуновым.

Дополнением к оглавлению «Каталога...» служит «Таблица представителей классов геометрической эквивалентности», представленная в диссертации. В этой таблице содержатся записи, однозначно соответствующие каждому из 58 типов сбалансированных функций. Каждая запись имеет следующий формат:

Тип Мин. тип ИеС стр.

8 .Ь.сА -> 8.Ь'.с!А' г

В таком формате отражены:

1) 8.Ь.сА — номер типа по каталогу «...минимальных базисных представлений всех булевых функций от четырёх переменных»;

2) 8.Ь'.с!А' — номер типа; который принадлежит тому же классу, что и тип с номером 8.Ь.сА. Если данное поле не пусто, то в каталоге приводятся регулярные системы, порождаемые типом с номером 8.Ь'.(/А'. В противном случае в каталоге представлен тип с номером 8.6.сА.

3) г — количество представителей классов эквивалентности регулярных систем, порождаемых типом;

4) я — номер страницы, на которой представлена содержательная часть каталога, соответствующая рассматриваемому типу.

В содержательной части каталога результаты классификационных исследований для каждого из класса эквивалентности сбалансированных двоичных функций представлены в следующей последовательности. Сначала указывается заголовок:

Класс Ж [8.Ь.с.а<- 8.Ъ'.</А' : В, Ь]

в котором отражены:

1) Ь — номер класса эквивалентности;

2) В,Ъ — обратимая 4 х 4-матрица В 6 СР(2)*4х4 и вектор Ь6Уц такие, что функции / и /', являющиеся представителями типов (¡^-эквивалентности с номерами Ъ.Ь.с.й и 8.Ь'.с!.й' соответственно, связаны соотношением

Далее для каждого из типов, входящих в класс эквивалентности представлена следующая информация о представителе типа:

- номер типа;

- вектор значений;

- кратчайшая дизъюнктивная нормальная форма;

- многочлен Жегалкина. Информация о типе представляется в формате:

Затем указывается номер типа, представитель которого исследовался, и данные соответствующие каждому из типов, входящих в рассматриваемый класс:

- мощность типа геометрической эквивалентности;

- количество представителей регулярных систем, порождаемых представителем типа;

- общее количество регулярных систем, порождаемых представителем типа.

в.ь.с.а

КДНФ: /(*) =

Далее в виде таблиц перечисляются все г представителей регулярных систем, порождённых представителем типа.

i N(ai) Ща2) N(a 3) X 2

Записи, соответствующие каждому из представителей систем, отражают следующие данные.

1) i — порядковый номер системы;

2) N(ai), N(a2), Nfa) — номера элементов c*i, с*2, аз группы Q4, которые вместе с функцией / порождают регулярную систему двоичных функций (/(ж), /(ж"1), /(ж"2), /(ж"3)). Для получения подстановки а = TTja € Qi, т е r/a € Я4, по её номеру N(a) необходимо найти строку и столбец «Таблицы номеров элементов группы С?4», представленной в диссертации, на пересечении которых находится искомое число N(a). Строка таблицы определяет подстановку те 54, а столбец — вектор a eVt.

3) X ~~ константа, по значению которой из таблицы «Мощности классов эквивалентных систем», представленной в диссертации, устанавливается мощность класса эквивалентности регулярной системы функций (/(ж) ,/(xQl) ,/(ж°2), /(ж"3)), а также общее количество классов эквивалентности такой мощности, представленных в классификации.

4) г — константа, по значению которой из таблицы «Характеристики нелинейности систем-представителей», представленной в диссертации, устанавливаются значения разностной характеристики ¡Л, порядка нелинейности fü и степени нелинейности А. Характеристики нелинейности ßl, fü и X вычисляются по формулам

uli, = max |{же V„ : (ж + а)* + хж = Ь}|,

«EV„\{0},feV„

= ^max(o) \\{xeV„: (а, ж) + (Ь, ж*}}| - 2""11,

п

где (а, Ь) = a,ibi — скалярное произведение векторов а = (ai,... ,a„), 1=1

6 = (6i,...,6„) из Vn,

К = min deg ( a,/, ) .

«•=(<»1.....«.№\(0) )

Суммарные результаты проведённой каталогизации позволяют сделать вывод в том что, среди 402 классов геометрически эквивалентных двоичных функций содержится 58 классов сбалансированных функций, которые относительно введённого в диссертации отношения эквивалентности образуют 37 классов (^-эквивалентности. Из этих 37 классов 24 класса порождают регулярные системы (¡^-однотипных функций. Возможные значения характеристик нелинейности систем-представителей представлены в таблице 3.1. Следует отмстить, что среди построенных классов систем содержатся классы, обладающие оптимальными или близкими к ним характеристиками нелинейности.

А fit ц1 N

3 4 2 8

3 4 4 27

2 4 2 350

2 4 4 274

2 4 6 1

3 4 6 1

3 6 2 9

А /ii pi N

3 6 4 131

3 6 6 48

3 6 8 2

2 6 2 167

2 6 4 1952

2 6 6 384

2 6 8 32

Л fit pi N

2 6 12 8

2 6 16 4

1 8 4 542

1 8 6 298

1 8 8 395

1 8 10 33

1 8 16 37

Таблица 3.1. Характеристики нелинейности систем-представителей (N — количество представителей с заданными характеристиками нелинейности)

Для обращения в «Каталог...» и использования результатов классификационных исследований для произвольной сбалансированной функции д € .7*4 необходимо выполнить следующую последовательность действий.

1) Определяем класс [/]qj, / 6 (^-эквивалентности, в который входит функция д. При этом определяем подстановку а€<24, для которой f{x) = д{ ха), х 6 V4, если [f]Q. = [f]Qf. Если же [f]Q. = [f]Qi U [f]Qi, f G то есть класс (¡^-эквивалентности состоит из двух типов Q\-эквивалентности с представителями / и /', то определяем подстановку a€Qi, для которой /(х) = д(ха) или f'{x) — д(ха), X6V4. Если данный класс (¡^-эквивалентности, а значит и рассматриваемая функция д, порождает регулярные системы (^-однотипных функций, то можно пе-

реходить к построению системы регулярных функций с требуемыми характеристиками.

2) По таблицам представителей типа, анализируя значения расмотренной выше константы г, выбираем систему функций, обладающую заданными характеристиками, и указываем подстановки а, = т^ь, 6 <24, т\ £ 5*4, €Нц, ¿61,3, для которых система функций

(Дж),Дж°>),Д*а2),/(*аз))

регулярна и является системой координатных функций некоторой подстановки 77 6 5(14). Если [/]д. = [/]<,.111Яд4, /'€*4, и }'(х) = г(х°), где а — найденная на предыдущем этапе подстановка из ¿¡>4, то, определив по каталогу подстановку 4>£СЦ, для которой /(ж) = /'(ж1'"), указываем подстановки Д = (^а)-1 а; (фа) = £ С?4, ¡и 6 54, % £ г £ 1,3, для которых система функций (д(х) ,д(х^) , <?(ж^2) ,д{х^3)) регулярна и является системой координатных функций подстановки

7г* = (^а)_17гб5(У4).

Если же на предыдущем этапе установлено, что = [/]д4 и /(ж) = д{ха), то искомые подстановки Д, £ <Э4,г £1,3, равны г £ 1,3,

соответственно.

В диссертации получены следующие основные результаты, выносимые на защиту.

1) Для синтеза взаимно однозначного отображения двоичных векторов длины п в диссертации предложено использовать не п координатных функций, а одну функцию с совокупностью легко реализуемых сервисных команд.

2) Для предложенного способа построения подстановок проведено исследование аналитических свойств систем функций и порождаемых ими преобразований в системах защиты информации.

3) Предложен метод каталогизации всех двоичных функций и составлен каталог регулярных систем, порождаемых функциями от четырёх переменных.

Публикации автора по теме диссертации

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

2. Никонов В. Г., Саранцев А. В. Построение и классификация регулярных систем однотипных функций // Материалы XXXI Международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе». — Т. 5 из Прил. 1. — М.: «Академия естествознания», 2004.-С. 173-174.

3. Саранцев А. В. Биективные отображения, заданные регулярными системами однотипных двоичных функций // Обозрение прикладной и промышленной математики. — Т. 11 из Вып. 3,— М.: Редакция журнала «ОПи-ПМ», 2004.-С. 583-584.

4. Саранцев А. В. Построение регулярных систем нелинейных двоичных функций на базе аффинного регистра сдвига // Материалы XXXI Международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе». — Т. 5 из Прил. 1. — М.: «Академия естествознания», 2004.— С. 176-177.

5. Саранцев А. В. Построение регулярных систем однотипных двоичных функций с использованием регистра сдвига // Вестник МГУ Л "Лесной вестник". — 2004. — № 1(32).- С. 164-169.

6. Саранцев А. В. Классификация регулярных систем однотипных функций, построенных с помощью циклического сдвига // Обозрение прикладной и промышленной математики, — Т. 12 из Вып. 1.— М.: Редакция журнала «ОПиПМ», 2005. - С. 182-184.

7. Саранцев А. В. Подходы к классификации регулярных систем однотипных двоичных функций, построенных с помощью циклического сдвига // Вестник МГУЛ "Лесной вестник". - 2005. - № 6(42). - С. 176-180.

8. Саранцев А. В. Регулярные системы однотипных двоичных функций степени 3, построенные с помощью циклического сдвига // Обозрение прикладной и промышленной математики. — Т. 14 из Вып. 1. — М.: Редакция журнала «ОПиПМ», 2007. - С. 147-148.

Подписано в печать 18.03.2010 Формат 60х84У1б. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,5. Тираж 100 экз. Заказ №484. Типография «Реглет» 119526, г. Москва, пр-т Вернадского, 39 (495)363-78-90, www.reglet.ru

Введение

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

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

1.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 Представители классов регулярных систем.

Развитие информационных технологий, совершенствование средств обработки и хранения информации способствует расширению сферы использования вычислительных средств. Достижения в области аппаратной и программной реализации алгоритмов обработки данных обеспечивают удобство эксплуатации технических средств. Объём обрабатываемых данных растёт в соответствии с возрастающими потребностями современного общества, поэтому автоматизированное использование компьютерных технологий является одним из самых практичных методов обработки информации.

Решение задач идентификации и аутентификации, контроля целостности и распознавания образов требует построения преобразований фрагментов информации, зависящих от некоторого секрета. Традиционные криптографические методы защиты информации используют обратимые преобразования, зависящие от секретного ключа. Основным требованием, предъявляемым к таким преобразованиям, является стойкость к атакам, направленным на нахождение защищаемой информации, без знания секретного ключа, либо нахождение самого секретного ключа. Стойкость обычно измеряется временем, которое необходимо для успешного выполнения атаки при некоторых фиксированных ресурсах, имеющихся в распоряжении у злоумышленника, реализующего атаки на систему защиты. Повышение стойкости системы защиты путём усложнения аналитической и статистической структуры используемых преобразований приводит к увеличению объёма ресурсов, требуемых для реализации системы защиты. Уровень стойкости системы защиты характеризуется нижней оценкой времени, требуемого на нарушение системы защиты, и определяется в первую очередь вычислительными ресурсами потенциального взломщика, а также временем, в течение которого защищаемая информация должна оставаться недоступной взломщику. Повышение стойкости системы защиты приводит к росту материальных затрат потенциального нарушителя, используемых для оплаты технических, интеллектуальных и организационных средств при проведении атаки. Материальные средства, выделяемые на проведение атаки, определяются выгодой, которую получит нарушитель при нанесении ущерба системе защиты. Такая выгода противника может быть оценена стоимостью атакуемых активов. Широкое применение приобретают компактные узлы и блоки переработки информации в системах управления, идентификации и контроля, размещённые в условиях, когда основным ценовым параметром становится емкостная сложность реализации преобразования. При этом вопросы стойкости используемой системы защиты не являются первоочередными, поскольку ценность обрабатываемой этими узлами информации стремительно падает с течением времени. Такие узлы используются для контроля доступа, идентификации транспортных средств, отслеживания активов, контроля производственных запасов, автоматизации производства и складской обработки, контроля за перемещением потоков грузов и транспорта и других задач [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 изложен принцип классификации регулярных систем С-однотипных функций, основанный на перечислении представителей типов систем. Для классификации регулярных систем п~однотипных функций в работе использовалось отношение эквивалентности на множестве задаваемых ими подстановок, которое позволило объединить (^„-типы порождающих функций и сохранить такие свойства как общее количество порождаемых систем и количество представителей, неэквивалентных относительно двухстороннего умножения на элементы группы Рассматриваемое отношение эквивалентности на множестве регулярных систем однотипных функций сохраняет такие характеристики нелинейности, которые приводятся для каждого из представителей систем.

Теоретические результаты классификационных исследований использованы для каталогизации (^-однотипных функций. Введённое отношение эквивалентности позволило при составлении «Каталога регулярных систем (^-однотипных двоичных функций» использовать «Классификацию минимальных базисных представлений всех булевых функций от четырёх переменных», составленную В. Г. Никоновым. «Каталог.» составлен с использованием разработанного автором лично программного обеспечения в среде СУБД Paradox. Для вычислений характеристик функций и порождаемых ими систем использовалось разработанное автором программное обеспечение. Достоверность проведённых вычислений подтверждается непосредственным сравнением результатов вычислений, полученных с помощью пакетов прикладных программ, разработанных другими исследователями, а также апробацией в учебном процессе ИКСИ. Вёрстка «Каталога.» осуществлялась в издательской системе что обеспечивает совместимость отображения результатов каталогизации в системах, поддерживающих форматированный вывод данных. В «Каталоге.» использован принцип классификации двоичных функций с помощью графов связности вершин, что значительно облегчает работу с каталогом и позволяет устанавливать корреляционные связи с классификационными исследованиями, проводимыми В. Г. Никоновым, В. А. Носовым и С. А. Гизуновым.

В тексте диссертации представлено подробное описание «Каталога.» и рассмотрен пример, иллюстрирующий порядок использования результатов каталогизационных исследований. Для удобства чтения диссертации оглавление и таблицы каталога, который имеет самостоятельное значение, включены в качестве приложения после текстового блока работы. В каталоге для каждого С^-типа сбалансированной двоичной функции приведена система представителей регулярных систем, порождаемых этой функцией с помощью преобразований из группы СЦ4. У каждого из представителей указаны инвариантные относительно двустороннего умножения на элементы группы (^4 характеристики нелинейности.

В диссертации получены следующие основные результаты, выносимые на защиту.

1) Для синтеза взаимно однозначного отображения двоичных векторов длины п в диссертации предложено использовать не п координатных функций, а одну функцию с совокупностью легко реализуемых сервисных команд.

2) Для предложенного способа построения подстановок проведено исследование аналитических свойств систем функций и порождаемых ими преобразовании в системах защиты информации.

3) Предложен метод каталогизации всех двоичных функций и составлен каталог регулярных систем, порождаемых функциями от четырёх переменных.

Основные результаты диссертационного исследования опубликованы в работах [15, 28, 31], докладывались на У,У1 и VII Всероссийских симпозиумах по прикладной и промышленной математике [26, 30, 32], на XXXI Международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе» [16, 27].

Заключение

В диссертации предложен новый метод построения систем двоичных функций, задающих взаимно однозначные отображения пространства векторов. Этот метод приводит к синтезу систем функций, эквивалентных относительно просто реализуемых групп преобразований систем, что закладывает потенциальную возможность их компактного синтеза. При этом осуществляется задание не всех функций системы, а лишь одной из них, так что остальные функции системы формируются посредством действия на переменные порождающей функции преобразованием однотипности. К одному из направлений в построении систем функций, задающих подстановки большой степени, следует отнести исследование порождающих функций, с ограниченной сложностью реализации.

Для всех преобразований, построенных в работе с помощью классов регулярных систем получены координатные функции обратных к ним преобразований. Следует отметить, что подстановки, задаваемые такими системами действуют на векторах произвольной длины, что расширяет арсенал способов синтеза подстановок больших степеней.

В диссертационной работе получены результаты по следующим направлениям:

- выделены и исследованы инвариантные относительно двустороннего умножения на элементы подгрупп группы подстановок на Уп характеристики подстановок, задаваемых регулярными системами однотипных функций;

- описан класс нелинейных функций, порождающих регулярные системы с помощью преобразований сдвига векторов пространства Уп;

- изучено строение регулярных систем, координатные функции которых эквивалентны относительно циклического сдвига координат;

- дано описание регулярных систем, построенных на основе произвольного аффинного регистра сдвига с нелинейной функцией усложнения второй степени от трёх переменных, и обратных к ним систем;

- описаны классы подстановок и обратных к ним, координатные функции которых являются эквивалентными относительно преобразования, реализуемого за один такт циклического сдвига векторов;

- предложен метод каталогизации всех двоичных функций и составлен каталог регулярных систем ¿^-однотипных функций с указанием характеристик нелинейности.

1. Гизунов С. А., Носов В. А. О классификации всех булевых функций 4-х переменных по классам Шефера // Обозрение прикл. и пром. машем. Сер. Дискретная математика. — 1995. — Т. 2, № 3. — С. 440-467.

2. Глухое М. М., Елизаров В. П., Нечаев А. А. Алгебра,— М.: Гелиос АРВ, 2003.-Т. 1.-336 с.

3. Глухое М. М., Ремизов А. В., Шапошников В. А. Обзор по теории к-значных функций. — М.: в/ч 33965, 1988. — Т. 1.— 153 с.

4. Горшков С. П. Применение теории ИР-полных задач для оценки сложности решения систем булевых уравнений // Обозрение прикл. и пром. машем. Сер. Дискретная математика. — 1995. — Т. 2, № 3. — С. 325398.

5. Грушо А. А., Применко Э. А., Тимонина Е. Е. Теоретические основы компьютерной безопасности: учебное пособие. — М.: Издательский центр «Академия», 2009. — 272 с.

6. Джевонс У. С. Основы науки: Трактат о логике и научном методе: Перевод со 2-го английского издания; Пер.: М. Антонович,— СПб.: Изд. Л.Ф. Пантелеева (репринтная копия), 1881.— 744 с.

7. Каргаполов М. И., Мерзляков Ю. И. Основы теории групп, — М.: Наука, 1977. 240 с.

8. Колбин С. Л. О некоторых свойствах взаимно обратных систем функций q-знaчнoй логики // Дискретная математика. — 1994. — Т. 6, № 2. С. 145-149.

9. Курош А. Г. Теория групп.— М.: Гос. изд-во технико-теор. лит-ры, 1953.- 467 с.

10. Лахири С. ИРГО. Руководство по внедрению. — М.: КУДИЦ-ПРЕСС, 2007.- 312 с.

11. Лидл Р., Нидеррайтер Г. Конечные поля, — М.: МИР, 1988.— Т. 1.— 430 с.

12. Логачёв О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. — М.: МЦНМО, 2004. — 469 с.

13. Никонов В. Г. Классификация минимальных базисных представлений всех булевых функций четырёх переменных // Обозрение прикл. и пром. машем. Сер. Дискретная математика. — 1994.— Т. 1, № 3.— С. 458-545.

14. Никонов В. Г. Пороговые представления булевых функций // Обозрение прикл. и пром. мат,ем. Сер. Дискретная математика. — 1994. — Т. 1, № З.-С. 402-457.

15. Носов В. А. Основы комбинаторной теории для инженеров, — М.: в/ч 33965, 1990. 254 с.

16. Носов В. А. Специальные главы дискретной математики: учебное пособие. — М.: в/ч 33965, 1990. — 156 с.

17. Основы криптографии: учебное пособие / А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, Ч. А. В. М.: Гелиос АРВ, 2001.-480 с.

18. Поваров Г. Н. О групповой инвариантности булевых функций // Применение логики в науке и технике. — М, 1960.

19. Погорелое Б. А. Группы подстановок (монография).— М.: ВКШ, 1987.- 316 с.

20. Применко Э. А., Скворцов Э. Ф. Об условиях регулярности конечных автономных автоматов // Дискретная математика.— 1990.— Т. 2, № 1.-С. 26-30.

21. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика, — М.: МИР, 1980. — 480 с.

22. Рожков М. В. Метод построения регулярных систем булевых функций с помощью полноцикловой подстановки // Материалы II межведомственной конференции «Научно-техническое и информационное обеспечение деятельности спецслужб». — М.: 1998.— С. 30-30.

23. Рожков М. В. Об особенностях строения систем однотипных регулярных к-значиых функций // Материалы II межведомственной конференции «Научно-техническое и информационное обеспечение деятельности спецслужб». — М.: 1998,— С. 31-32.

24. Саранцев А. В. Биективные отображения, заданные регулярными системами однотипных двоичных функций // Обозрение прикладной и промышленной математики. — Т. 11 из Вып. 3. — М.: Редакция журнала «ОПиПМ», 2004. С. 583-584.

25. Саранцев А. В. Построение регулярных систем однотипных двоичных функций с использованием регистра сдвига // Вестник МГУЛ "Лесной вестник". 2004. - № 1(32). - С. 164-169.

26. Саранцев А. В. Регулярные системы однотипных двоичных функций // МАБИТ.-М.: МГУ, 2004.

27. Саранцев А. В. Классификация регулярных систем однотипных функций, построенных с помощью циклического сдвига // Обозрение прикладной и промышленной математики. — Т. 12 из Вып. 1. — М.: Редакция журнала «ОПиПМ», 2005. С. 182-184.

28. Саранцев А. В. Подходы к классификации регулярных систем однотипных двоичных функций, построенных с помощью циклического сдвига // Вестник МГУЛ "Лесной вестник". — 2005. — № 6(42).— С. 176180.

29. Саранцев А. В. Регулярные системы однотипных двоичных функций степени 3, построенные с помощью циклического сдвига // Обозрение прикладной и промышленной математики.— Т. 14 из Вып. 1.— М.: Редакция журнала «ОПиПМ», 2007. — С. 147-148.

30. Сачков В. Н. Введение в комбинаторные методы дискретной математики. М.: МЦНМО, 2004. - 424 с.

31. Сачков В. Н., Тараканов В. Е. Комбинаторика неотрицательных матриц. М.: ТВП, 2000. - Т. 2. - 448 с.

32. Севастьянов Б. А. Некоторые задачи, связанные с булевыми функциями // Труды по дискретной математике. — М.: ФИЗМАТЛИТ, 2001. — Т. 4. С. 223-230.

33. Словарь криптографических терминов // Под ред. Б.А.Погорелова и В.Н.Сачкова. М.: МЦНМО, 2006.- 94 с.

34. Смирнов В. Г. Системы булевых уравнений рекуррентного типа // Обозрение прикл. и пром. матем. Сер. Дискретная математика. — 1995. Т. 2, № 3. - С. 477-482.

35. Солодовников В. И. О полугруппе, порождённой автоматными отображениями обратимого автомата // Труды по дискретной математике. — М.: ФИЗМАТЛИТ, 2001.- Т. 4. С. 231-242.

36. Фомичёв В. М. Дискретная математика и криптология.— М.: ДИАЛОГ-МИФИ, 2003. С. 400.

37. Черемушкин А. В. Методы аффинной и линейной классификации двоичных функций // Труды по дискретной математике. — М.: ФИЗМАТЛИТ, 2001. Т. 4. - С. 273-314.

38. Clifford N. К. On the types of Compound Statment involving Four classes // Proc. of Literaru and Phil. Soc. of Manchester.— 1877,— Vol. 16.- Pp. 83-101.

39. Cole P., Ranasinghe D. Networked Rfid Systems and Lightweight Cryptography: Raising Barriers to Product Counterfeiting. — SpringerVerlag, 2007.- 355 pp.

40. Courtois N., Pieprzyk J. Cryptanalysis of block ciphers with overdefined systems of equations // ASIACRYPT.— 2002.

41. Daemen J., Rijmen V,— National Institute of Standards and Technology (U.S.): Advanced Encryption Standard (AES).— Available at http://csrc.nist.gov/publications/fips/fipsl97/fips-197.pdf, 2001.

42. Efficient algorithms for solving overdefined systems of multivariate polinomial equations / N. Courtois, A. Klimov, J. Patarin, A. Shamir // Eurocrypt. 2000. - Pp. 392-407.

43. Harrison M. A. Introduction to switching and automata theory. — New York: McGraw-Hill, 1965,- 188 pp.

44. Kitsos P., Zhang Y. RFID Security. — Springer-Verlag, 2008. — 446 pp.

45. Lightweight security for mobile commerce transactions / K.-Y. Lam, S.-L. Chung, M. Gu, J.-G. Sun // Computer Communications.— 2003.— Vol 28, no 18. Pp. 2052-2060.

46. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. CRC Press, 1996. - 745 pp.

47. Ninomiya I. A study of the structures of Boolean functions and its applications to the synthesis of switching circuits // Mem. Faculty Eng. — Nagoya Univ., 1961.-Vol. 13 Pp. 149-363.

48. Nyberg K., Knudsen L Provable secuiity against a differential attack // Advances in Cryptology CRYPTO'92. Proceedings.- 1993,— Pp 566574.

49. Seberry J., Zhang X. A4., Zheng J. Relationships among nonlincarity criteria (extended abstract) // Advances in Cryptology EUROCRYPT'94. Proceedings. - 1994. — Pp. 376-388.

50. Vajda I., Buttyran L. Lightweight authentication protocols for low-cost rfid tags // In Second Workshop on Security in Ubiquitous Computing -Ubicomp 2003. Seattle, Washington, USA: 2003.