Оценки экспонентов перемешивающих орграфов регистровых преобразований, используемых в системах защиты информации тема диссертации и автореферата по ВАК РФ 05.13.19, кандидат наук Коренева Алиса Михайловна

• Коренева Алиса Михайловна
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Коренева Алиса Михайловна

ВВЕДЕНИЕ

Глава 1. Характеристики перемешивающего орграфа преобразования регистра сдвига с одной обратной связью над пространством двоичных векторов

§ 1.1 Обзор известных оценок экспонентов примитивных орграфов

§ 1.2 Определяющие свойства перемешивающего орграфа регистрового преобразования с одной обратной связью над пространством двоичных векторов

§ 1.3 Описание множеств путей и контуров в перемешивающем орграфе регистрового преобразования с одной обратной связью над пространством двоичных векторов

§ 1.4 Условия примитивности и оценки экспонентов перемешивающего орграфа регистрового преобразования с одной обратной связью над пространством двоичных векторов

§ 1.5 Выводы

Глава 2. Характеристики перемешивающего орграфа регистрового преобразования, построенного на основе модифицированного аддитивного генератора (МАГ)

§ 2.1 Уравнения функционирования и определяющие свойства МАГ

§ 2.2 Описание множеств путей и контуров в перемешивающем орграфе преобразования множества состояний МАГ

§ 2.3 Примитивность и оценки экспонента перемешивающего орграфа МАГ

§ 2.4 О приложениях МАГ в системах защиты информации

2.4.1 Перемешивающие свойства генератора ключевого расписания на основе МАГ

2.4.2 Перемешивающие свойства нелинейных узлов замены, построенных с использованием МАГ

§ 2.5 Выводы

Глава 3. Характеристики перемешивающего орграфа преобразования регистра сдвига с двумя обратными связями над пространством двоичных векторов

§ 3.1 Биективность преобразования регистра сдвига с несколькими обратными связями над пространством двоичных векторов и определяющие свойства перемешивающего орграфа

§ 3.2 Примитивность перемешивающего орграфа преобразования регистра сдвига на основе МАГ с двумя обратными связями

§ 3.3 Оценки экспонентов перемешивающего орграфа преобразования регистра сдвига на основе МАГ с двумя обратными связями

§ 3.4 Сравнение экспонентов перемешивающих орграфов регистровых преобразований с одной и двумя обратными связями и рекомендации по выбору параметров

§ 3.5 Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ

СПИСОК ЛИТЕРАТУРЫ

Введение диссертации (часть автореферата) на тему «Оценки экспонентов перемешивающих орграфов регистровых преобразований, используемых в системах защиты информации»

ВВЕДЕНИЕ

Актуальность темы исследования. В декабре 2016 года Указом Президента РФ № 646 утверждена новая Доктрина информационной безопасности Российской Федерации [4], представляющая собой основополагающий документ, направленный на обеспечение национальной безопасности РФ в информационной сфере. Новая доктрина подтвердила курс на ликвидацию зависимости от зарубежных разработчиков в сфере информационных технологий и защиты информации. В связи с этим является актуальным создание и внедрение отечественных разработок в области информационной безопасности.

Проектирование современных систем защиты информации осуществляется на основе фундаментальных научных принципов и законов. Важным свойством систем защиты информации является перемешивание входных данных, которое достигается с помощью специального класса функций векторных пространств. Перемешивание заключается в достижении сложных связей статистических и аналитических характеристик элементов выходных данных по отношению к характеристикам элементов входных данных [1, с. 207, 30, с. 58]. Принцип перемешивания был выдвинут и теоретически обоснован в 1949 году К.Э. Шенноном (1916 — 2001) в известной статье «Теория связи в секретных системах» [40]. В дальнейшем развитие исследований принципа перемешивания нашло воплощение в многочисленных характеристиках и свойствах дискретных функций многих переменных, так как ряд специальных свойств систем защиты информации тесно связан с исследованием перемешивающих свойств преобразований.

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

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

Для функции двоичных конечномерных векторных пространств существенную зависимость каждого бита выхода от всех битов входа называют свойством полного перемешивания. Функции со свойством полного перемешивания называются совершенными. Обобщениями свойства совершенности функций являются такие свойства, как строгий лавинный критерий, критерии распространения, свойство «бент» [32, с. 209, 52, 56]. Техническая и программная реализация совершенных функций осложнена большим количеством связей между знаками входа и выхода. В работах К.Э. Шеннона предложено реализовывать сложные преобразования в виде суперпозиции нескольких простых, таким образом, полное перемешивание часто достигается с помощью итераций удобно реализуемых преобразований с относительно слабыми перемешивающими свойствами [1, с. 207]. По такому принципу построены итеративные блочные алгоритмы. Известно, что базовый режим простой замены алгоритма DES реализует композицию 16-ти раундовых преобразований, каждое из которых не является совершенным. Однако композиция 5-ти раундовых преобразований уже является совершенной [32, с. 206]. Таким образом, глубина композиции (степень преобразования), при которой достигается хорошее перемешивание, является важной оценочной характеристикой системы защиты информации. Актуальной задачей для обоснования качества системы защиты является исследование условий, при которых достигается полное перемешивание входных данных.

В связи с высокой вычислительной сложностью точного решения задачи определения множества существенных переменных координатных функций при исследовании перемешивающих свойств итераций преобразования векторного пространства широкое распространение получил оценочный матрично-графовый подход (далее — МГП), который вычислительно проще. Основной задачей матрично-графового подхода является оценка глубины композиции функций, при которой каждый бит выходного значения композиции зависит от всех битов

входного вектора, то есть достигается полное перемешивание. Такой подход активно разрабатывается в работах [7-24, 38, 63].

Для изложения сути МГП введём необходимые обозначения и определения. Ориентированным графом Г=(Х,Ц) (далее орграфом) называется пара, состоящая из непустого множества вершин X и множества дуг Ц, определяемого бинарным отношением на X, то есть ЦсХ2. Вершины принято изображать точками на плоскости, а дуги — стрелками (дуга (х,у) изображается стрелкой, исходящей из вершины х и заходящей в вершину у).

Обозначим через Уп векторное пространство строк длины пеЫ с координатами из поля СР(2) (п-мерное пространство двоичных векторов). Элементы векторного пространства ¥п будем называть п-мерными двоичными векторами.

Пусть преобразование ф.Уп^Уп задано координатными булевыми функциями ф0(х0,...3Хи-1),...,фи-1(х0,...3Хи-1). Функция ф/х0,...,Хи-1), уе{0,...,и-1}, зависит существенно от переменной х/ (и в этом случае переменная х/ называется существенной) тогда и только тогда, когда существует пара соседних по /-той координате векторов, на которых функция фу принимает различные значения, /=0,...,п-1. Обозначим через Е(фу) множество номеров существенных переменных функции фу(х0,.,хп-1), _/=0,...,п-1. Для оценки перемешивающих свойств преобразования ф используется его перемешивающая матрица М(ф)=(ту) размера пхп, в которой элемент ту равен 1 тогда и только тогда, когда /еЕ(фД в противном случае ту равен 0, у=0,...,п-1. Равносильно для исследования перемешивающих свойств рассматривается п-вершинный перемешивающий орграф Г(ф) с множеством вершин {0,...,п-1}, матрица смежности вершин которого совпадает с М(ф) (две вершины орграфа называются смежными, если они соединены дугой [2, с. 13]). Таким образом, в Г(ф) имеется дуга (/у) тогда и только тогда, когда /еЕ(ф/).

Перемешивающие свойства преобразования ф оцениваются с помощью исследования путей в орграфе Г(ф) (путём в орграфе называется такая

последовательность дуг [2, с. 13], что концевая вершина каждой предыдущей дуги совпадает с начальной вершиной следующей дуги). Связь между множеством путей орграфа Г(ф) и матрицей смежности его вершин М(ф) определяется известной теоремой [37, ч.1, с. 55]: если (М(ф))-(т(}), teN, уе{0,..., п-1}, то число путей

длины t из 1 в / в Г(ф) равно т(^. Отсюда следует, что М(фг) < (М(ф)) (отношение <

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

Основным свойством неотрицательных матриц и орграфов в контексте применения МГП для исследования множеств существенных переменных степеней преобразований является примитивность. Матрицу М=(т/ над полем Я назовём неотрицательной (положительной), если неотрицательны (положительны) все её элементы. Неотрицательная матрица М примитивная, если некоторая её степень не содержит нулевых элементов. Орграф Г примитивный, если некоторая его степень является полным орграфом (то есть любые две вершины орграфа соединены дугой [2, с. 14]). Наименьшая из таких степеней называется экспонентом орграфа (экспонентом матрицы) и обозначается expГ (expМ). Экспоненты орграфа Г и матрицы М смежности его вершин совпадают, их величина позволяет оценить число итераций преобразования, при котором возможно полное перемешивание входной информации.

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

используемых для защиты информации. Ряд практических примеров показал, что оценки, полученные при МГП, являются весьма точными [24].

К активно используемым в системах защиты информации преобразованиям относятся регистры сдвига над различными алгебраическими структурами. Регистром сдвига принято называть специальную теоретико-автоматную модель генератора рекуррентных последовательностей. Регистр сдвига можно рассматривать как автомат, выходом которого является рекуррента, сгенерированная с помощью некоторой функции, называемой генератором рекурренты или обратной связью регистра [31, с.3]. Преобразования множества состояний регистров сдвига (далее будем называть их регистровыми преобразованиями) весьма удобно реализуются как аппаратным способом, так и программно на ЭВМ. Перемешивающие свойства регистра определяются его длиной и функцией обратной связи.

В диссертации исследуются перемешивающие орграфы преобразований для различных классов регистров сдвига n над множеством Vr двоичных r-мерных векторов, n, r — натуральные числа, n>1, r>1. На основе таких регистров сдвига построены сети Фейстеля (алгоритмы DES, ГОСТ 28147-89), их различные обобщения (в частности, алгоритмы CLEFIA, CAST-256, RC6, MARS и др.), алгоритмы хеширования (MD5, SHA-256 и др.) [25—27, 41, 42, 46, 47, 60, 69, 77, 78, 80]. Одним из важных для приложений частных классов регистровых преобразований над Vr являются преобразования множеств состояний аддитивных генераторов (линейные регистры сдвига над кольцом вычетов по модулю 2r) [44, 48, 51, 64], на основе которых построены некоторые алгоритмы (Fish, Pike, Mush) [41]. Преобразования множеств состояний аддитивных генераторов являются биективными, они просто реализуются на современной элементной базе. Вместе с тем, преобразования аддитивных генераторов не достигают полного перемешивания входных данных при сколь угодно большом числе итераций. В связи с этим в работе исследована актуальная задача оценки перемешивающих свойств модификаций аддитивных генераторов (МАГ), позволяющих достигать

полного перемешивания знаков начального состояния генератора.

Степень разработанности темы исследования. Исследование регистровых преобразований над различными алгебраическими структурами получило развитие в работах многих авторов: Голомб (Golomb S. W.), Де Брейн (N.G. De Bruijn), Гюнтер (C.G. Gunther), Рюппель (R.A. Rueppel), Горески (M Goresky), Клэппер (A. Klapper), В.А. Башев, А.С. Кузьмин, В.Л. Куракин, А.А. Нечаев, В.И. Солодовников, О.А. Логачёв, В.М. Фомичёв и др. [31, 55, 58, 59 и др.]. В работах указанных авторов исследуются теоретико-автоматные, групповые и полугрупповые свойства регистров сдвига. Активно изучаются свойства координатных выходных последовательностей, порождаемых регистрами сдвига, в том числе их периодические свойства, линейная сложность, статистические свойства.

Исследованиям перемешивающих свойств регистров сдвига над пространством Vr при r>1 посвящено меньшее количество работ. Одни из первых результатов были представлены на конференции ASIACRYPT'96 [69]. Дальнейшее применение матрично-графового подхода к исследованию свойств регистров сдвига над Vr нашло развитие в работах японских и французских авторов: Сузаки (T. Suzaki), Минемацу (K. Minematsu), Бергер (T.P. Berger), Миньер (M Minier), Томас (G.Thomas) [46, 47, 77, 78]. Укажем основные результаты их исследований.

Обозначим через R(n,r,t) — класс автономных регистров сдвига длины n над Vr с t обратными связями, n>t>1, n,r,teN (то есть в указанных обозначениях класс R(2,r,1) соответствует классической сети Фейстеля; классы R(n,r,1), R(n,r,n/2), R(n,r,n-1) — так называемым обобщённым сетям Фейстеля 1-го, 2-го и 3-го типов), определение которых приводится в [60, стр. 12]).

Двоичные r-мерные векторы можно рассматривать как блоки информации, составляющие nr-мерный вектор состояния регистра сдвига. Для регистрового преобразования фeR(n,r,t) определим блоковый перемешивающий n-вершинный орграф Г^(ф): в Г^(ф) имеется дуга (ij) тогда и только тогда, когда хотя бы один бит

у-го выходного блока преобразования ф существенно зависит от некоторых битов /-го входного блока преобразования ф, у=0,...,и-1. Регистр левого сдвига из класса Я(п,т,1), в ячейках которого записаны г-мерные векторы, представлен слева на рисунке 0.1, а справа изображён соответствующий блоковый перемешивающий орграф Г5(ф).

Хо Xr-1 Хг Х2г-1 ... x(n-1)r xnr-1

1 i n-1

Рисунок 0.1 — Регистр ф над Vr с 1-й обратной связью и перемешивающий орграф Гв(ф) Для w-вершинного блокового орграфа Гв(ф) преобразования ф^Я(п,г,1) известны оценки: ехрГВ(ф)<(п-1)2+1 при циклическом сдвиге блоков и ехрГВ(ф)<п(п+2)/2-2 при замене сдвигов блоков их определённой перестановкой [46, стр. 4]. При чётном n для регистрового преобразования феЯ(п,г,п/2) получена оценка ехрГд(ф)<п [77]. Данная оценка улучшена до 2log2n при условии замены циклического сдвига блоков их определённой перестановкой. Для регистрового преобразования феЯ(п,г,п-1) выполнена оценка ехрГВ(ф)<п. С использованием результатов исследования перемешивающих свойств преобразований фЕ^(п,г,?) предложены блочные алгоритмы (в 2012 году — TWINE [78], в 2016 году — Lilliput [47]), рекомендуемые для защиты информации в условиях ограниченных ресурсов пользователя.

Следует отметить, что исследование блокового перемешивающего орграфа ГВ(ф) проще, так как он имеет в r раз меньше вершин, чем перемешивающий орграф

Г(ф) регистрового преобразования. При этом точность полученных с помощью

блокового орграфа результатов ниже, так как для любого преобразования (eR(n,r,t) выполнено неравенство ехрГ5(ф)<ехрГ(ф).

В диссертации исследуются примитивность и экспоненты nr-вершинных перемешивающих орграфов для регистровых преобразований ф из классов R(n,r,1) и R(n,r,2) (регистры сдвига с одной и двумя обратными связями над Vr). В частности, определяются значения параметров регистровых преобразований, при которых экспоненты перемешивающих орграфов принимают наименьшие значения или близкие к наименьшим.

Постановка задачи о распознавании примитивности неотрицательной матрицы была дана в 1912 году Фробениусом (F.G. Frobenius) [57]. Термин «экспонент» был введён в 1962 году в работе Далмэджа и Мендельсона (A.L. Dulmage, N.S. Mendelsohn) [53].

Конечным экспонентом обладает только примитивная матрица и примитивный орграф. Примитивный орграф является сильно связным (то есть любая пара различных вершин орграфа соединена путём [2, с. 14]). Иначе говоря, сильная связность орграфа — необходимое условие примитивности. Критерий примитивности сильно связного орграфа Г, доказанный в 1961 году Перкинсом (P. Perkins) [70], определяется множеством контуров в орграфе (контуром в орграфе называется путь [2, с. 13], у которого начальная вершина совпадает с конечной). Длина пути (контура) равна числу дуг, составляющих путь (контур). Обхватом орграфа называется наименьшая из длин его контуров. В орграфе Г множество контуров {Ci,...,Cs} длин l1,...,ls соответственно, где s>1, называется примитивным, если НОД^,...,^)^. При s=1 примитивное множество контуров вырождается в единственную петлю. Критерий примитивности орграфа можно сформулировать так: сильно связный орграф Г примитивный тогда и только тогда, когда Г содержит примитивное множество контуров [37, ч. 1, с. 185].

Исследованию примитивности орграфов и матриц и получению оценок экспонентов посвящено большое количество работ зарубежных и российских учёных: Фробениус (F.G. Frobenius), Виландт (H. Wielandt), Далмэдж

(A.L. Dulmage), Мендельсон (N.S. Mendelsohn), Бруалди (R.A. Brualdi), В.Н. Сачков, В.А. Носов, А.В. Князев, В.М. Фомичёв и др. [6, 29, 45, 49, 50, 57, 61, 62, 66, 67, 7076 и др.]. Обзор результатов исследования примитивности и известных оценок экспонентов содержится в 1 главе диссертации.

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

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

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

1. Описать множества путей и контуров в перемешивающих орграфах с помощью множеств существенных переменных координатных функций.

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

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

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

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

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

- критерии примитивности перемешивающих орграфов;

- оценки экспонентов перемешивающих орграфов.

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

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

Положения, выносимые на защиту.

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

2. Для регистров сдвига с одной обратной связью, построенных на основе модифицированных аддитивных генераторов (МАГ) — доказана теорема о существенных переменных координатных функций обратной связи, доказан критерий примитивности перемешивающих орграфов и получены оценки их экспонентов.

3. Для регистров сдвига с двумя обратными связями, построенных на основе МАГ — получено описание характеристик перемешивающих орграфов, доказан критерий их примитивности и получены оценки экспонентов.

Публикации. Результаты исследований опубликованы в 17 научных работах, из которых 2 научные статьи — в журналах Scopus и 4 научные статьи — в журналах RSCI.

Степень достоверности и апробация результатов работы. Достоверность полученных результатов обосновывается их математическими доказательствами и рецензированием при опубликовании.

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

- Международной телекоммуникационной конференции молодых учёных и студентов «Молодёжь и наука» в рамках Научной сессии НИЯУ МИФИ-2011 (Москва, 1-5 февраля, 2011);

- Международной конференции Eurocrypt в рамках рамп-сессии (Кембридж, 15-19 апреля, 2012 г.);

- Международной научно-практической конференции «Комплексная защита информации» (Суздаль, 15-18 мая 2012 г.);

- Международной научно-практической конференции студентов, аспирантов и молодых учёных «Информационные технологии в науке, бизнесе и образовании» (Москва, 12 и 13 декабря, 2012 г.);

- Всероссийской конференции «Сибирская научная школа-семинар с международным участием «Компьютерная безопасность и криптография» SIBECRYPT (Иркутск, 3-7 сентября, 2012 г.; Томск, 2-7 сентября, 2013 г.; Екатеринбург, 8-13 сентября, 2014 г.; Новосибирск, 7-12 сентября, 2015 г.; Новосибирск, 5-10 сентября, 2016 г.; Красноярск, 4-9 сентября, 2017 г.);

- Международной научно-практической конференции «РусКрипто» (Московская область, Солнечногорский район, 27-30 марта 2013 г.; 17-20 марта 2015 г.; 21-24 марта 2017 г.);

- Симпозиуме «Современные тенденции в криптографии» CTCrypt (Ярославль, 6-8 июня, 2016 г.; Санкт-Петербург (Репино), 5-7 июня, 2017 г.);

- Научном семинаре «Математические методы криптографического анализа», МГУ имени М.В. Ломоносова (2014 г., 2016 г.);

- Научном семинаре кафедры радиотехники и систем управления, МФТИ (2017 г.).

Структура и объём диссертации. Диссертация состоит из введения, трёх глав, заключения и библиографического списка, включающего 80 наименований. Текст диссертации изложен на 110 страницах с 14 рисунками и 8 таблицами.

Полученные в диссертации результаты соответствуют пункту 13 паспорта специальности 05.13.19 — «Методы и системы защиты информации, информационная безопасность». Результаты диссертации относятся к математическим принципам и решениям по созданию новых и совершенствованию существующих методов и средств защиты информации.

В первой главе диссертации систематизируются отечественные и зарубежные результаты исследования примитивности орграфов и даётся обзор известных оценок экспонентов. Исследуются перемешивающие орграфы биективных преобразований регистров сдвига длины п с одной обратной связью над Уг. Описываются простые пути и контуры в перемешивающем орграфе (теорема 1.1), оцениваются их длины (теорема 1.2). Доказывается достаточное условие примитивности перемешивающего орграфа (теорема 1.3), получаются оценки его экспонента в различных условиях (теорема 1.4), уточняющие известные оценки экспонентов для тех же орграфов.

Во второй главе диссертации исследуется класс регистровых преобразований, построенных на основе аддитивных генераторов (АГ) по модулю 2г, модифицированных с использованием подстановки на множестве значений функции обратной связи. Функция обратной связи таких регистров является композицией функции обратной связи АГ и преобразования множества Уг. Доказывается критерий биективности преобразования множества состояний модифицированного аддитивного генератора (МАГ) (теорема 2.1). С использованием комбинаторных свойств биекции 12г ^Уг описывается множество существенных переменных функции обратной связи регистра сдвига, построенного на основе МАГ (теорема 2.2). Для перемешивающего орграфа даётся описание путей и контуров, доказываются критерии сильной связности (теорема 2.3) и примитивности (теорема 2.4) и оценивается экспонент (теорема 2.5). Полученная оценка экспонента уточняет как известные оценки экспонентов для тех же орграфов, так и оценки экспонентов, полученные в первой главе, для

класса примитивных перемешивающих орграфов всех подстановочных регистров сдвига длины п над Уг.

В третьей главе диссертации исследуется примитивность перемешивающих орграфов биективных регистров сдвига с двумя обратными связями над пространством V, устанавливается ряд свойств таких регистровых преобразований. Для регистровых преобразований с несколькими обратными связями доказывается критерий биективности (теорема 3.1). Для биективных регистровых преобразований из класса регистров сдвига с двумя обратными связями описываются множества дуг, простых путей и контуров в перемешивающем орграфе (теоремы 3.2, 3.3, 3.4). Для преобразований регистров сдвига с двумя обратными связями, построенных на основе МАГ, доказывается критерий примитивности (теорема 3.5), получаются оценки экспонента (теорема 3.6), которые уточняют все другие известные оценки экспонентов для тех же орграфов.

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

Личный вклад автора. В параграфе 1.1 главы 1 представлен обзор известных результатов, связанных с исследованием примитивности орграфов и оценками их экспонентов. Результаты, представленные в параграфах 1.2 - 1.4 главы 1, в параграфах 2.1 - 2.3 главы 2 и в главе 3 получены автором самостоятельно. Научным руководителем В.М. Фомичёвым были поставлены задачи по разработке критериев примитивности и по получению оценок экспонентов перемешивающих орграфов регистровых преобразований над двоичным векторным пространством, а также предложены идеи использования МАГ в системах защиты информации (параграф 2.4).

БЛАГОДАРНОСТИ

Автор выражает искреннюю благодарность научному руководителю доктору физико-математических наук, профессору Фомичёву Владимиру Михайловичу за постановку задач, конструктивную критику, внимание и многолетнюю поддержку.

Глава 1. Характеристики перемешивающего орграфа преобразования регистра сдвига с одной обратной связью над пространством двоичных

векторов

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

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

В параграфе 1.2 описан перемешивающий орграф преобразования регистра сдвига с одной обратной связью и получен критерий сильной связности перемешивающего орграфа через свойства орграфа с меньшим числом вершин.

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

Список литературы диссертационного исследования кандидат наук Коренева Алиса Михайловна, 2018 год

СПИСОК ЛИТЕРАТУРЫ

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

2 Берж, К. Теория графов и её применения / К. Берж; пер. с фр. А.А. Зыкова, под ред. И.А. Вайнштейна. — М.: ИЛ, 1962. — 319 с.

3 ГОСТ Р 34.12—2015 «Информационная технология. Криптографическая защита информации. Блочные шифры». — М.: Стандартинформ, 2015. — 16 с.

4 Доктрина информационной безопасности Российской Федерации [Электронный ресурс] // Российская газета (издание Правительства Российской Федерации, официальный публикатор документов). — Режим доступа:

https://rg.ru/2016/12/06/doktrina-infobezobasnost-site-dok.html (дата обращения 12.03.2018).

5 Кнут, Д.Э. Искусство программирования, том 2. Получисленные алгоритмы / Д.Э. Кнут; 3-е изд.: пер с англ. — М.: Издательский дом «Вильямс», 2003. — 832 с.

6 Князев, А.В. Оценки экстремальных значений основных метрических характеристик псевдосимметрических графов: дис.... д-ра физ.-мат. наук: 01.01.09 / Князев Александр Викторович. — М., 2002. — 203 с.

7 Когос, К.Г. Положительные свойства неотрицательных матриц / К.Г. Когос, В.М. Фомичёв // Прикладная дискретная математика. — 2012. — №4 (18). — С. 5-13.

8 Коренева, А.М. О некоторых результатах систематизации теоретико-графовых моделей, используемых для решения задач криптологии / А.М. Коренева // Тезисы докладов XIV Международной телекоммуникационной конференции студентов и молодых учёных «Молодёжь и наука». Ч. 3. — М.: НИЯУ МИФИ, 2010. — С. 239-241.

9 Коренева, А.М. Систематизация теоретико-графовых моделей в криптологии / А.М. Коренева // Безопасность информационных технологий. — 2011. — №3. — С. 47-49.

10 Коренева, А.М. Применение теоретико-графового подхода для определения значения экспонента матрицы существенной зависимости / А.М. Коренева // Безопасность информационных технологий. — 2011. — №4. — С. 126129.

11 Коренева, А.М. Криптографические свойства блочных шифров, построенных на основе регистров сдвига / А.М. Коренева, В.М. Фомичёв // Прикладная дискретная математика. — 2012. — №5 (Приложение). — С. 49-51.

12 Коренева, А.М. Теоретико-графовый подход к оценке перемешивающих свойств криптографических преобразований / А.М. Коренева // Безопасность информационных технологий. — 2012. — С. 149-150.

13 Коренева, А.М. Об одном обобщении блочных шифров Фейстеля / А.М. Коренева, В.М. Фомичёв // Прикладная дискретная математика. — 2012. — №3 (17). — С. 34-40.

14 Коренева, А.М. Современная криптология: Eurocrypt 2012 и Sibecrypt 2012. Научная проблематика и личные впечатления / А.М. Коренева // Сборник трудов V Международной научно-практической конференции студентов, аспирантов и молодых учёных. — М.: «Научные технологии», 2012. — С.72-74.

15 Коренева, А.М. О блочных шифрах, построенных на основе регистров сдвига с двумя обратными связями / А.М. Коренева // Прикладная дискретная математика. — 2013. — №6 (Приложение). — С. 39-41.

16 Коренева (Дорохова), А.М. Уточнённые оценки экспонентов перемешивающих графов биективных регистров сдвига над множеством двоичных векторов / А.М. Дорохова, В.М. Фомичёв // Прикладная дискретная математика. — 2014. — №1 (23). — С. 77-83.

17 Коренева (Дорохова), А.М. Оценки экспонентов перемешивающих графов некоторых модификаций аддитивных генераторов / А.М. Дорохова // Прикладная дискретная математика. — 2014. — №7 (Приложение). — С. 60-64.

18 Коренева (Дорохова), А.М. О примитивности перемешивающих графов преобразований регистров сдвига с двумя обратными связями / А.М. Дорохова // Прикладная дискретная математика. — 2015. — №8 (Приложение). — С. 8-11.

19 Коренева, А.М. О существенных переменных функции переходов модифицированного аддитивного генератора / А.М. Коренева, В.М. Фомичёв // Прикладная дискретная математика. —2016. — № 9 (Приложение). — С.51-54.

20 Коренева, А.М. Экспериментальное исследование экспонентов раундовых перемешивающих матриц обобщённых сетей Фейстеля / А.М. Коренева, В.Н. Мартышин // Прикладная дискретная математика. — 2016. — № 9 (Приложение). — С. 48-51.

21 Коренева, А.М. Перемешивающие свойства модифицированных аддитивных генераторов / А.М. Коренева, В.М. Фомичёв // Дискретный анализ и исследование операций. — 2017. — №.2 (24) — С. 32-52.

22 Коренева, А.М. О примитивности перемешивающих орграфов биективных регистров сдвига с двумя обратными связями / А.М. Коренева // Прикладная дискретная математика. — 2017. —№37.— С.32-51.

23 Коренева, А.М. Сравнение экспонентов перемешивающих орграфов регистровых преобразований с одной и двумя обратными связями / А.М. Коренева // Прикладная дискретная математика. — 2017. — № 10 (Приложение). — С. 84-87.

24 Кяжин, С.Н. О точности матрично-графового подхода к оценке перемешивающих свойств преобразований / С.Н. Кяжин, Ф.В. Лебедев // Прикладная дискретная математика. —2016. — №9 (Приложение). — С. 57-59.

25 Мао, В. Современная криптография. Теория и практика / В. Мао. — М.: Вильямс, 2005. — 786 с.

26 Панасенко, С.П. Алгоритмы шифрования. Специальный справочник / С.П. Панасенко. — СПб.: БХВ-Петербург, 2013. — 576 с.

27 Пудовкина, М.А. Об оценке числа раундов с невозможными разностями в обобщённых алгоритмах шифрования Фейстеля / М.А. Пудовкина, А.В. Токтарёв // Прикладная дискретная математика. — 2015. — № 1. — С. 37-51.

28 МР 26.2.003—2013 «Информационная технология. Криптографическая защита информации. Задание узлов замены блока подстановки алгоритма шифрования ГОСТ 28147-89». — М.: —ТК 26. —2013.

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

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

31 Солодовников, В.И. Регистры сдвига и криптоалгоритмы на их основе /

B.И. Солодовников. — Lambert Academic Publishing, 2017. — 121 с.

32 Фомичёв, В.М. Методы дискретной математики в криптологии / В.М. Фомичёв. — М.: ДИАЛОГ-МИФИ, 2010. — 424 с.

33 Фомичёв, В.М. Свойства путей в графах и мультиграфах / В.М. Фомичёв // Прикладная дискретная математика. — 2010. — №1(7). —

C. 118-124.

34 Фомичёв, В.М. Оценки экспонентов примитивных графов / В.М. Фомичёв // Прикладная дискретная математика. — 2011. — №2(12). — С. 101-112.

35 Фомичёв, В.М. Оценка экспонента некоторых графов с помощью чисел Фробениуса для трёх аргументов / В.М. Фомичёв // Прикладная дискретная математика. — 2014. — №2 (24). — C. 88-96.

36 Фомичёв, В. М. Новая универсальная оценка экспонентов графов / В.М. Фомичёв // Прикладная дискретная математика. №3.— 2016. — С. 78-84.

37 Фомичёв, В. М. Криптографические методы защиты информации. В 2 ч. Часть 1. Математические аспекты: учебник для академического бакалавриата / В.М.

Фомичёв, Д.А. Мельников; под ред. В.М. Фомичёва. — М.: Юрайт, 2016. — с. 209.

38 Фомичёв, В.М. Локальная примитивность матриц и графов / В.М. Фомичёв, С.Н. Кяжин // Дискретный анализ и исследование операций. — Т. 24, №1, 2017. — С. 97-119.

39 Фомичёв, В.М. Об алгоритмической реализации s-боксов [Электронный ресурс] / В.М. Фомичёв, Д.И. Задорожный, А.М. Коренева, Д.М. Лолич, А.В. Юзбашев // Материалы конференции РусКрипто2017. — Режим доступа: https://www.ruscrypto.ru/resource/archive/rc2017/files/02 fomitchev zadorozhny korene va lolich yuzbashev.pdf (дата обращения 12.03.2018)

40 Шеннон, К.Э. Теория связи в секретных системах / К.Э. Шеннон // Работы по Теории информации и кибернетике. — М.: ИЛ, 1963.— С. 333-369.

41 Шнайер, Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си / Б. Шнайер. — М.: Триумф, 2002. — 816 с.

42 Щербаков, Л.Ю. Прикладная криптография. Использование и синтез криптографических интерфейсов / Л.Ю. Щербаков, А.В. Домашев. — М.: Русская редакция, 2003. — 416 c.

43 Akelbek, M. Coefficients of ergodicity and the scrambling index [Электронный ресурс] / M. Akelbek, S. Kirkland // Eprints Maynooth University, 2009. — Режим доступа:

http://eprints.maynoothuniversity.ie/2060/1/SK coefficients.pdf (дата обращения 12.03.2018)

44 Anderson, R. On Fibonacci Keystream Generators [Электронный ресурс] / R. Anderson // Fast Software Encryption. — 1995. — Vol. 1008 of LNCS. — С. 346-352. — Режим доступа: https://www. cl. cam. ac. uk/~rj a 14/Papers/fibonacci. pdf (дата обращения 12.03.2018).

45 Barghi, A. Exponents of Primitive Digraphs [Электронный ресурс] / A. Barghi // Mathematics at Dartmouth Colledge. — Режим доступа:

https://math.dartmouth.edu/~pw/M100W11/amir.pdf (дата обращения 12.03.2018).

46 Berger, T.P. Extended Generalized Feistel Networks Using Matrix Representation [Электронный ресурс] / T.P. Berger, M. Minier, G.Thomas. — HAL, 2014. — Режим доступа: https: //hal. archives-ouvertes. fr/hal-00913881/file/Berger_Minier_Thomas_Extended_Generalized_Feistel_Networks_using_ Matrix Representation.pdf(дата обращения 12.03.2018).

47 Berger, T.P. Extended Generalized Feistel Networks Using Matrix Representation to Propose a New Lightweight Block Cipher: Lilliput / T.P. Berger, J. Francq, M. Minier, G.Thomas // IEEE Transactions on Computers. — 2016. — Vol. 65, № 7. — С. 2074-2089.

48 Blocher, U. Fish: A fast software stream cipher / U. Blocher, M. Dichtl // Fast Software Encryption. — 1994. — Vol. 809 of LNCS. — С. 41-44.

49 Brualdi, R. A. Generalized exponents of primitive directed graphs / R. A. Brualdi, B. Liu // Journal of Graph Theory. — 1990. — №14. — С. 483-499.

50 Brualdi, R. A. Combinatorial Matrix Theory / R.A. Brualdi, H.J. Ryser // Encyclopedia of Mathematics and its Applications 39, Cambridge University Press, Cambridge, 1991.

51 Coppersmith, D. The shrinking generator / D. Coppersmith, H. Krawczyk, Y. Mansour // Advances in cryptology — CRYPTO' 93. — 1993. — Vol. 773 of LNCS. — С. 22-39.

52 Desmedt, Y. Dependence of output on input DES: small avalanche characteristics / Y. Desmedt, J.J. Quisquater, M. Davio // Workshop on the Theory and Application of Cryptographic Techniques. — 1984. — C. 359-376.

53 Dulmage, A. L. The exponent of a primitive matrix / A.L. Dulmage, N. S. Mendelsohn // Canad. Math. Bull. — 1962. — № 5. — С. 241-244.

54 Dulmage, A. L. Gaps in the exponent set of primitive matrices / A.L. Dulmage, N. S. Mendelsohn // Illinois J. Math. — 1964. — №8. — С. 642-656.

55 Fomichev, V. On Efficiency of Block Encryption by Improved Key Schedule [Электронный ресурс] / V. Fomichev, A. Koreneva // Rump-session CTCrypt 2016. — Режим доступа: http://ctcrypt.ru/files/files/2016/12%20fomichev.pdf (дата обращения 12.03.2018).

56 Forre, R. The strict avalanche criterion: spectral properties of booleans functions and an extended definition / R. Forre // Advances in cryptology — CRYPTO'88. — 1990. — Vol. 403 of LNCS. — C. 450-468.

57 Frobenius, F.G. Über Matrizen aus nicht negativen Elementen / F. G. Frobenius // Sitzungs ber. Pre. Akad, Wiss., Berlin. — 1912. — С. 456-477.

58 Golomb, S. W. Shift Register Sequences. — A Retrospective Account / S.W. Golomb // In: Gong G., Helleseth T., Song HY., Yang K. (eds) Sequences and Their Applications. — SETA 2006. — Vol. 4086 of LNCS.

59 Goresky, M. Algebraic Shift Register Sequences / M. Goresky, A. Klapper // — Cambrige University Press. — 2012. — 514 p.

60 Hoang, V.T. On Generalized Feistel Networks [Электронный ресурс] / V.T. Hoang, P. Rogaway. — Cryptology ePrint Archive. — 2010. — Режим доступа:

https://eprint.iacr.org/2010/301.pdf (дата обращения 12.03.2018).

61 Huang, Y. Generalized r-exponents of primitive digraphs / Y. Huang, B. Liu // Taiwanese Journal of Mathematics. —2011. — Vol. 15, №. 5. — С. 1999-2012.

62 Kim, B.M. Nonnegative primitive matrices with exponent 2 / B.M. Kim, B.C. Song, W. Hwang // Linear Algebra and its Applications. — 2005. — Vol. 407. — С. 162168.

63 Koreneva, A. One Little Cipher Story [Электронный ресурс] / A. Koreneva, V.Fomichev. — Rump Session EuroCrypt 2012. — Режим доступа:

https://www.iacr.org/conferences/eurocrypt2012/Rump/koreneva.pdf (дата обращения 12.03.2018).

64 Koreneva, A.M. Mixing properties of Modified Additive Generators / A.M. Koreneva, V. M. Fomichev // Journal of Applied and Industrial Mathematics. — 2017. —

Vol. 11, №2. — C. 215-226.

65 Krawczyk, H The Shrinking Generator: some practical considerations / H. Krawczyk // Fast Software Encryption. — 1994. — Vol. 809 of LNCS. — C. 45-46.

66 Liu, B. Generalized exponents of Boolean matrices / B. Liu // Linear Algebra and its Applications. — 2003. —№. 373. — C. 169-182.

67 Lewin, M. A system of graphs in the exponent set of primitive matrices / M. Lewin, Y. Vitek // Illinois Journal Math. —1981. — № 25. — C. 87-98.

68 Menyachikhin, A. Spectral-linear and spectral-difference methods for generating cryptographically strong S-boxes / A. Menyachikhin // CTCrypt Preproceedings. — 2016. — C. 232-245.

69 Nyberg, K. Generalized Feistel Networks / K. Nyberg // In Advances in cryptology — ASIACRYPT'96. —1996. — Vol. 1163 of LNCS. — C.91-104.

70 Perkins, P. A theorem on regular graphs / A. Perkins // Pacific J. Math. — 1961, vol. II. — C. 1529-1533.

71 Shader, B.L. Exponents of nonnegative matrix pairs / B.L. Shader, S. Suwilo // Linear Algebra and Its Applications. — 2003. — Vol. 363. — C. 275-293.

72 Shao, J.Y. On the Exponent of a Primitive Digraph / J.Y. Shao // Linear algebra and its applications. — 1985. — № 64. — C. 21-31.

73 Shao, J.Y. On the Exponents of Primitive Digraphs with the Shortest Elementary Circuit Length s / J.Y. Shao, W.Q. Dong, C.F. Dong // Linear algebra and its applications. — 1988. — №104.—C. 1-27.

74 Shao, J. Generalized primitive exponents with the complete characterization of the extremal digraphs / J. Shao, J. Wang, G. Li // Chinese Journal of Contemporary Mathematics. — 1994. — №4 (15). — C. 317-324.

75 Shen, J. A problem on the exponent of primitive digraphs / J. Shen // Linear algebra and its applications. —1996. — Vol. 244. — C. 255-264.

76 Shen, J. Local exponents of primitive digraphs / J. Shen, S. Neufeld // Linear

Algebra and its Applications. — 1998. —№268. — С. 117-129.

77 Suzaki, T. Improving the generalized Feistel / T. Suzaki and K. Minematsu // In Fast Software Encryption. — 2010. — Vol. 6147 of LNCS. — C. 19-39.

78 Suzaki, T. TWINE: A Lightweight Block Cipher for Multiple Platforms / T. Suzaki, K. Minematsu, S. Morioka, E. Kobayashi // In Selected Areas in Cryptography. — 2012. — Vol. 7707 of LNCS. — C. 339-354.

79 Wielandt, H. Unzerlegbare nicht negative Matrizen / H. Wielandt // Math. Zeitschr. — 1950. — № 52. — С. 642-648.

80 Yanagihara, S. Improving the Permutation Layer of Type 1, Type 3, Source-Heavy, and Target-Heavy Generalized Feistel Structures [Электронный ресурс] / S. Yanagihara, T. Iwata. — 2013. Режим доступа: http://www.selmer.uib.no/WCC2013/pdfs/Yanagihara.pdf (дата обращения 12.03.2018).