Комбинаторно-алгебраические структуры итерационных функций в системах защиты информации Пудовкина Марина Александровна

Содержание к диссертации

Введение

Глава 1. Сплетения групп подстановок и pG-структуры 27

1.1. Введение 27

1.2. L-факторструктуры и сплетения 30

1.3. Расстояние от подстановки до группы IGW относительно метрики Хемминга .36

1.4. Расстояния от преобразований раундовой функции алгоритма блочного шифрования SMS4 до сплетений групп 47

1.5. Связь оценок расстояния W от множества подстановок до импримитивной группы с параметрами ряда методов 52

1.5.1. Связь параметров разностного метода и его обобщений с оценкой расстоянияW 52

1.5.2. Связь параметров (вероятностного) метода

гомоморфизмов с оценкой расстояния W 56

Глава 2. Метрики типа Хемминга и pG -структуры 58

2.1. Введение 58

2.2. Общие свойства конечных натурально-значных метрик

2.3. Натуральные метрики и pG -структуры .68

2.4. Подметрики и надметрики натуральных метрик 73

2.5. Натуральные метрики, инвариантные относительно группы сдвигов 79

2.6. Натуральные метрики, инвариантные относительно группы Джевонса

2.6.1. Основные определения и результаты .88

2.6.2. Классификация натуральных метрик орбиталов

надгрупп группы Джевонса 92

2.6.3. Натуральные подметрики метрики n,k 110

Глава 3. Классификация групп изометрий натуральных метрик графов орбиталов надгрупп группы Джевонса и их свойства 120

3.1. Введение 120

3.2. Группы автоморфизмов графов орбиталов надгрупп группы Джевонса .122

3.3. Дистанционно транзитивные графы орбиталов надгрупп группы Джевонса 143

3.4. Классы дистанционно транзитивных графов орбиталов надгрупп группы Джевонса .156

3.5. Группа инерции множества корреляционно-иммунных функций порядка m .174

Глава 4. Приводимость матрицы линейного преобразования XSL алгоритма блочного шифрования и pG -структуры 179

4.1. Введение 179

4.2. Свойства орбиталов и графов орбиталов группы Cn (g) 181

4.3. Дистанционно транзитивные и дистанционно регулярные классы графов орбиталов группыCn (g) 187

4.4. Натуральные метрики графов орбиталов группы Cn (g) .193

4.5. Свойства графов орбиталов группы Cn (g) для преобразований g из унитреугольной группы .200

4.6. Марковские XSL-алгоритмы блочного шифрования с приводимым линейным преобразованием 205

4.6.1. Марковские алгоритмы блочного шифрования 205

4.6.2. Инвариантные подмножества линейного преобразования -марковских XSL-алгоритмов блочного шифрования и разностный метод 208

4.6.3. Матрицы смежных классов для инвариантного подпространства линейного преобразования .210

4.6.4. Инвариантные множества алгоритма блочного шифрования ISEBERG .211

Глава 5. Криптографические приложения pG -структур 216

5.1. Введение 216

5.2. Инвариантные и невозможные pG -структуры обобщённого алгоритма Фейстеля 2-го типа .220

5.3. Цепи Маркова на разбиениях биграмм и 2-мерные pG -структуры 229

5.4. W -марковость преобразований нелинейного слоя и pG -структуры 239

5.5. Метод гомоморфизмов и W -марковость .246

5.6. Линейное раундовое преобразование XSL-алгоритма и W -марковость 254

Заключение .264

Список обозначений и сокращений .269

• Расстояния от преобразований раундовой функции алгоритма блочного шифрования SMS4 до сплетений групп
• Подметрики и надметрики натуральных метрик
• Дистанционно транзитивные графы орбиталов надгрупп группы Джевонса
• Инвариантные подмножества линейного преобразования -марковских XSL-алгоритмов блочного шифрования и разностный метод

Введение к работе

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

В основе криптографических методов защиты информации лежит использование стойких криптосистем, многие из которых основываются на блочных шифрсистемах. Блочная шифрсистема включает в себя алгоритмы шифрования (зашифрования, расшифрования), развёртывания ключа и режимы шифрования. Алгоритм зашифрования реализует криптографическую функцию, зависящую от ключа и называемую функцией зашифрования. Далее рассматривается блочная шифрсистема в режиме простой замены [16].

Пусть N - множество всех натуральных чисел, N0 = NU{0}, X -произвольное конечное множество (или алфавит открытого и шифрованного текста); X^і - t-я декартова степень множества X для t є N, (Х,Щ - аддитивная абелева группа на множестве X с бинарной операцией ; S(X)-симметрическая группа на X, S_n= S(X) при п =| X |; К - ключевое множество, К - множество раундовых ключей. Функции зашифрования f : X х К —> X соответствует множество частичных функций зашифрования if_k : X —» X \ к є к\,

где функция f_k на каждом фиксированном ключе шифрования к є К задана условием f_k : аи f(a,k) для всех аєХ. Отметим, что все рассматриваемые

далее множества конечны.

каждого к є К, где

раундовых функций,

заданных условием g^ : ел—> g^{l)(a,k^{l)) для всех

(а,к^(і))є ХхК, і = \,...,1. В этом случае /^(/) называется l-раундовой функцией

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

При разработке современных алгоритмов шифрования исходят из принципов, сформулированных К. Шенноном [56]. Функция зашифрования строится на основе итерационного способа. Согласно данному способу, каждая функция зашифрования /^(/): X х К —> X однозначно определяется / є N раундовыми функциями g^{l): X х К —> X, / = 1,...,/, и отображением ц/^{1): К —> К, реализующим алгоритм развёртывания ключа таким образом, что

<р^(/):*|->(*⁽¹⁾,...,*^(/))

для

(/)

Є(1) 2(¹)

-^X\k

_&г.:*

X}

частичных

множество

(і)

соответствующих g и

(і)

и U

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

В последние годы части схемы алгоритма шифрования, реализующие свойства усложнения, перемешивания, рассеивания, называются соответственно X -слоем (или слоем наложения ключа), S -слоем (или слоем s -боксов, нелинейным слоем), L -слоем (или линейным слоем). Далее под преобразованием X -, S - или L -слоя понимается преобразование, реализуемое X -, S - или L -слоем соответственно. Алгоритмы блочного шифрования с раундовой функцией, представимой в виде композиции преобразований слоев X, S и L, называются XSh-алгоритмами блочного шифрования. Примерами XSL-алгоритмов блочного шифрования являются: отечественный стандарт шифрования ГОСТ Р. 34.12 -2015 «Кузнечик», американский стандарт шифрования AES, алгоритмы Present [22], Square [33], 3D [52]. У ряда алгоритмов блочного шифрования Фейстеля функция усложнения раундовой функции также является композицией преобразований X, S - и L -слоев, но действует на половине блока.

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

U)

частичную функцию зашифрования f^^J . X—»Х, „/

неизвестном ключе к є К от случайной равномерно распределённой на S(X) подстановки. Такие соотношения будем называть структурами. Зачастую появление нового метода криптоанализа вызвано нахождением у алгоритма блочного шифрования новой структуры. Многие структуры могут задаваться посредством разбиений множества X^і, в том числе двумя множествами R,R', R,R'С; X^і, где множество R характеризует соотношения между блоками

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

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

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

В дискретной математике для классификации объектов часто используется их комбинаторно групповая классификация. Заметим, что подобный подход позволил Ф. Клейну объединить в своей «эрлангенской программе» [6] «различные отрасли геометрии относительно групп преобразований, поскольку к этому моменту геометрия, единая по своему существу, раздробилась на ряд почти раздельных дисциплин, которые развивались в значительной степени независимо друг от друга». В этом случае объектами изучения выступали инварианты этих преобразований, а основу составляли утверждения о соотношениях между инвариантными свойствами и группами, их сохраняющими. Наоборот, с конечными группами сопоставляются различные алгебраические и комбинаторные структуры, например, латинские квадраты, системы Штейнера, блок-схемы, конечные геометрии, графы, квадратичные формы, метрики (см., например, [12], [20], [21], [27], [28], [38], [53]). Различные способы задания простых групп, в том числе и как групп, сохраняющих некоторые структуры, содержатся в атласе конечных групп [31].

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

группа изометрий конечной натурально-значной метрики, например, метрики Хемминга % и её обобщений, определяющей данную структуру;

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

группа, порождённая преобразованиями, которые являются компонентами раундовых функций, или множеством {g_k | к є К} частичных раундовых

функций.

Основные группы подстановок, сохраняющие структуры на X, естественно разбить на классы: интранзитивных, импримитивных, унипримитивных (т.е. примитивных, но не 2-транзитивных) и 2-транзитивных групп (см. [12]). Кроме того, группе G < S(X) также могут соответствовать структуры при её действии на

множестве X^і при t > 2 (особенно для кратно транзитивных групп). Для интранзитивных групп подстановок естественными структурами являются орбиты и их объединения. С импримитивными группами в криптографии связан метод гомоморфизмов, а структурой является разбиение на блоки импримитивности. Среди примитивных групп подстановок, классифицированных в теореме О'Нэна-Скотта [46], с точки зрения криптографических приложений интерес представляют: примитивные подгруппы аффинных групп и подгруппы группы экспоненцирования. Аффинные группы определяют структуры, характеризующие, насколько заданное преобразование отлично от аффинного. Эти структуры встречаются в разнообразных методах линеаризации. Группа

экспоненцирования S Ї S_n является группой изометрий метрики Хемминга. При

q = 2 группа S₂ Т S_n также называется группой Джевонса [11]. В криптографии

группа S Ї S_n впервые возникла при геометрической интерпретации теоремы

А.А. Маркова о шифрах, не распространяющих искажения [13]. Каждая унипримитивная группа подстановок естественным образом задаёт структуру через 2-арные инвариантные отношения [64], являясь группой изометрий некоторой натурально-значной метрики.

Групповыми свойствами криптографических функций занимались М.М. Глухов, В.Н. Сачков, Б.А. Погорелов, А.В. Черемушкин, Ю.Н. Горчинский, СП. Горшков, B.C. Анашин, Ф.М. Малышев, М.В. Федюкин, Г.Н. Поваров, И.Г. Шапошников, А.В. Тарасов, Д. Копперсмит, К. Патерсон, Р. Венсдорф, Б. Калиски, Р. Ривест и др. Большая часть работ посвящена описанию группы (g_k\k єК\, а также групповых свойств преобразований раундовых функций.

Например, в работах [43], [50], [57], [61] рассмотрена цикловая структура таких преобразований, а в работах [8], [29], [30], [32], [40], [58], [62], [63] доказано равенство lg_k | к є К\ = А{Х) для алгоритмов блочного шифрования DES,

RIJNDAEL, а также для некоторых классов XSL-алгоритмов блочного шифрования и алгоритмов Фейстеля, где А(Х)- знакопеременная группа на X. Так, в работах [4], [11], [17], [19], [26], [39], [49] описываются группы, сохраняющие множества криптографических функций. Кроме того, в ряде работ [3], [7], [10], [37] предпринималась попытка переноса соответствий Галуа, рассматривая вместо уравнений над полями GF(2") различные отношения на множестве X.

Неявно вопросы, посвященные связям свойств группы (g_k \к єК} с

существованием структур у алгоритма блочного шифрования, описаны в [47], [63]. Так, в [63] отмечено, что для отсутствия некоторых структур у алгоритма блочного шифрования требуется примитивность, простота и большой порядок группы (g_k\k є К). В работе [47], посвященной описанию групповых свойств

алгоритмов блочного шифрования, утверждается, что условие lf^^l) \kє К) = S(X) достаточно для гарантирования её стойкости. Однако в [51]

приведён пример /-раундового алгоритма блочного шифрования, у которого существует структура, но при этом выполняются равенства: lg_k \kєК) = S(X),

lf];^l) \кє К) = S(X) для чётного числа раундов / и (f^^l) \кє К) = А(Х) для

нечётного числа раундов /. Таким образом, включение А(Х) f^l) \ к є К\, а

также «естественные» требования примитивности и 2-транзитивности недостаточны для отсутствия структур у алгоритма блочного шифрования.

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

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

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

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

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

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

1. Через разбиения t -грамм множества X^і определены p_G -структуры, и в этих

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

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

описание способов задания p_G -структур;

нахождение степени сохранения p_G -структуры множеством G;

нахождение расстояний между преобразованиями из множества Н cz S(X) и элементами группы автоморфизмов p_G -структуры

относительно некоторой метрики на X . Эти направления реализованы для p_G -структур с импримитивной группой

автоморфизмов.

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

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

4. Выделены два класса p_G -структуры, задаваемые следующими разбиениями:

1) разбиения множества X, в том числе на смежные классы по подгруппе транзитивной абелевой группы (X,); 2) разбиения, соответствующие натурально-значным метрикам на множестве X, в частности, метрикам типа Хемминга. Исследованы алгебраические и комбинаторные свойства таких p_G -структур, в том числе:

описаны группы автоморфизмов p_G -структур;

описаны свойства графов, соответствующих p_G -структурам,

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

блочного шифрования.

Данные задачи соответствуют п. 54 Перечня научно-технических проблем обеспечения информационной безопасности РФ («Разработка фундаментальных проблем теоретической криптографии и смежных с ней областей математики»).

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

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

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

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

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

2. Показано, что один из естественных способов описания структур алгоритмов блочного шифрования состоит в сопоставлении им некоторых разбиений множества X^і (p_G -структуры). Описаны классы разбиений

множества X^і для ґє{1,2}, задающие p_G -структуры, а также их алгебраические, комбинаторные и криптографические свойства.

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

XSL-алгоритмов блочного шифрования описаны свойства графов орбиталов группы C_n(g), порождённой преобразованиями Х- и L-слоев. В том числе

получены условия, при которых графы орбиталов группы C_n(g)

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

4. Выявлена связь натурально-значных метрик, p_G -структур и метрик,
инвариантных относительно преобразования линейного слоя, в том числе

метрик типа Хемминга. В связи с этим полностью классифицированы метрики типа Хемминга на V_n, группа изометрий которых является

надгруппой группы Джевонса S₂t S_n. Среди графов орбиталов надгрупп группы Джевонса описаны такие классы графов как дистанционно транзитивные и антиподальные, в том числе проведено сопоставление с ранее известными графами.

5. Предложено понятие L -факторструктуры преобразования, обобщающее известную линейную структуру преобразования, и описана группа автоморфизмов L -факторструктуры.

6. Для каждого тє{\,...,п} описана группа инерции множества всех корреляционно-иммунных функций порядка т, отображающих V_n в GF(2).

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

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

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

9. Дана интерпретация широко известных результатов [44] о марковости
алгоритмов блочного шифрования в терминах укрупнения состояний
вероятностных автоматов. Она распространена на _w-марковские

алгоритмы блочного шифрования. Для разбиения W = {Wq,...^^} алфавита текстов X, блоки которого являются смежными классами по некоторой подгруппе W₀ группы (Х,<8>), доказана эквивалентность между _w-

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

Соответствие диссертации паспорту специальности. Тема и содержание диссертационной работы соответствуют требованиям паспорта специальности 05.13.19 - Методы и системы защиты информации, информационная безопасность и соответствует следующим областям исследований паспорта специальности: 9. Модели и методы оценки защищённости информации и

информационной безопасности объекта; 13. Принципы и решения (технические, математические, организационные и др.) по созданию новых и совершенствованию существующих средств защиты информации и обеспечению информационной безопасности.

Результаты, выносимые на защиту.

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

2. Описание натурально-значных метрик, инвариантных относительно группы сдвига V_n.

3. Классификация подметрик метрики Хемминга на V_n и их групп изометрий,

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

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

5. Общие оценки величины 2_w(g), характеризующей удаленность произвольного преобразования от сплетения групп подстановок, сохраняющего p_G -структуру. Полное описание подстановок, максимально

далеких от сплетения групп подстановок при заданной системе импримитивности.

6. Обобщения -марковости алгоритмов блочного шифрования до _w-

марковости. Описание свойств _w-марковских алгоритмов блочного шифрования и _w-марковских преобразований, в том числе условий на разбиение W множества X, при которых имеет место _w-марковость.

Научная и практическая значимость работы определяется следующим.

1. Разработкой общего способа поиска и построения p_G -структур,

обусловленных комбинаторно-алгебраическими свойствами

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

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

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

3. Классификацией подметрик метрики Хемминга на V_n и их групп изометрий,

являющихся надгруппами группы Джевонса S₂1 S_n; классификацией

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

6. Описанием для каждого тє{\,...,п} группы инерции множества всех двоичных корреляционно-иммунных функций порядка т, отображающих V_n в GF{2).

7. Введением понятий _w-марковских алгоритмов блочного шифрования и _w-марковских преобразований и описанием их свойств.

8. Описанием p_G -структуры семейства обобщённых алгоритмов Фейстеля 2-

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

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

Внедрение результатов исследований. Основная часть диссертационных исследований выполнялась в 2005 - 2016 гг. в рамках темы 4(и других тем) Академии криптографии РФ.

Результаты исследований внедрены в Обществе с ограниченной ответственностью «Специальный Технологический Центр» (ООО «СТЦ») (г. Санкт-Петербург) и в Акционерном обществе «Макросистемы» (г. Москва), а также на кафедре «Информационная безопасность» Московского государственного технического университета имени Н.Э. Баумана (национального исследовательского университета). Они также использованы в тематиках дипломных проектов и аспирантских исследований.

Личный вклад соискателя. Основные результаты диссертации являются новыми и получены автором самостоятельно.

Апробация результатов диссертации. Основные результаты диссертации докладывались на следующих научных конференциях и семинарах: семинар кафедры алгебры МГУ им. М.В. Ломоносова; семинар «Математические методы криптоанализа» МГУ им. М.В. Ломоносова; семинар отдела алгебры и топологи ИММ УрО РАН (г. Екатеринбург); семинар НИИ прикладных проблем математики и информатики БГУ (г. Минск); совместный семинар City College of New York, Stevens Institute of Technology (r. New York); семинар кафедры информационной безопасности МГТУ им. Н.Э. Баумана; семинары и конференции ИКСИ Академии ФСБ РФ; семинар 16 центра ФСБ РФ; международный семинар «Дискретная математика и её приложения» (г. Москва, 2007, 2009, 2012); Общероссийская научно-практическая конференция «Методы и технические средства обеспечения безопасности информации» (г. Санкт-Петербург, 2006, 2007); Сибирская научная школа-семинар с международным участием «Компьютерная безопасность и криптография» (2007 - 2012, 2014 - 2016); международная конференция «Рускрипто» (Московская область, 2008-2013, 2016); международный семинар «Workshop on mathematical cryptology» (Spain, 2008); международный семинар «Asymptotic group theory and applications» (USA, 2009); Белорусская математическая конференция (г. Минск, 2010); международная конференция «Central European conference on cryptology» (Poland, 2010); международный семинар «West European workshop on research in cryptography» (Germany, 2011, 2013); международная конференция «Discrete mathematics, algebra, and their

applications» (г. Минск, 2009); Общероссийская научная конференция «Математика и безопасность информационных технологий» (г. Москва, 2005 -2011); международный семинар «Foundations and practice of security» (France, 2011); международная конференция «International conference on Bulgarian and Balkans cryptography» (Bulgaria, 2012); международная конференция «Вероятностные методы в дискретной математике» (г. Петрозаводск, 2012); международная конференция «Современные тенденции в криптографии» (г. Нижний Новгород, 2012).

Исследования по теме диссертации поддержаны в 2006 - 2016 гг. Академией криптографии РФ.

Структура и объём работы. Диссертация состоит из введения, пяти глав, заключения и приложения. Список литературы включает 154 наименования. Работа изложена на 300 страницах с примерами и таблицами.

Благодарности. Автор выражает глубокую благодарность научному консультанту д.ф.-м.н., профессору Погорелову Б.А. за постоянное внимание к работе и её обсуждение, а также благодарности за поддержку коллективам кафедр «Информационная безопасность» МГТУ им. Н.Э. Баумана и «Криптология и кибербезопасность» НИЯУ МИФИ.

Расстояния от преобразований раундовой функции алгоритма блочного шифрования SMS4 до сплетений групп

Для t \, G S(X) рассмотрим группу (G,X ), у которой действие G на Xі задано условием Н:а\- (а -х,...,а ) для всех а = (а;-1,...,а0)є Xі, heS(X). Группа подстановок G S(X) называется t -транзитивной, если для всех пар наборов а, а є Xі, в каждом из которых элементы попарно различны, существует такая подстановка h є G, что а = ah.

В ряде работ [12], [22], [23], [30], [37] предпринималась попытка переноса соответствий Галуа, рассматривая вместо уравнений над полями GF(2") различные отношения на множестве X. Примером одного из таких переносов (см., например, [22], [23], [151]) является теория инвариантных отношений, применяемая для описания свойств группы (G,X ) для t 2. Подмножество [/с! , сохраняемое группой G, называется инвариантным отношением арности t, а орбиты группы (G,X ) - t-орбитами группы G (см. [22]). 2-орбиты группы также называют орбиталами (см. [41]). Теория инвариантных отношений естественным образом включает в себя линейные представления и кольца Шура (эквивалентное понятие - ассоциативные схемы отношений), с помощью их комбинаций и дальнейшего развития возможно получать новые результаты. Так, в серии работ [22], [23], [24] теория инвариантных отношений использовалась для исследования примитивных представлений неабелевых простых групп и описания свойств некоторых максимальных подгрупп симметрической и знакопеременной группы. В [151] 2-арные инвариантные отношения применялись для описания свойств унипримитивных групп, т.е. примитивных, не 2-транзитивных групп подстановок. Отмечено, что естественный пример 2-арных инвариантных отношений на множестве X задаётся метрическим пространством {X,ju) с метрикой //:X2 -J, где без ограничения общности JcN0, и группой изометрий Isom// = g є S(X) \/л(а,а ) = ju(ag ,a g) У (a, a ) el2 . В этом случае для унипримитивной группы изометрий Isom// 2-арным инвариантным отношением является множество і(а,а )єХ2 \ju(a,a ) = j\ для каждого j є J. Для 2-транзитивной группы не существует нетривиальных 2-арных инвариантных отношений.

Для большинства алгоритмов блочного шифрования группа (gk \ к є К) равна симметрической S(X) или знакопеременной А(Х). Заметим, что, хотя группа (fll) \k є К j на алфавите X обычно транзитивна, но 2-транзитивность может реализовываться «медленно» (возникать на длинах, близких или больших числа раундов) или вообще отсутствовать. Поэтому можно рассматривать структуры, определяемые блоками разбиения множества X2. Подобные структуры используются в методе невозможных разностей, т.к. при отсутствии 2-транзитивности для некоторых пар открытого текста возникают невозможные пары шифртекстов, что равносильно существованию структуры.

Групповыми свойствами криптографических функций занимались М.М. Глухов, В.Н. Сачков, Б.А. Погорелов, А.В. Черемушкин, Ю.Н. Горчинский, СП. Горшков, В.С. Анашин, Ф.М. Малышев, М.В. Федюкин, Г.Н. Поваров, И.Г. Шапошников, А.В. Тарасов, Д. Копперсмит, К. Патерсон, Р. Венсдорф, Б. Калиски, Р. Ривест и др. Большая часть работ посвящена описанию группы (gk к є К\, а также групповых свойств преобразований раундовых функций.

Например, в [103], [120], [141], [146] рассмотрена цикловая структура таких преобразований, а в [34], [76], [77], [81], [142], [149], [150] доказано равенство (gk \к є К\ = А(Х) для алгоритмов блочного шифрования DES, RIJNDAEL, а также для некоторых классов XSL-алгоритмов блочного шифрования и алгоритмов Фейстеля. В ряде работ, например, [18], [39], [54], [58], [72], [97], [118] описываются группы, сохраняющие множества криптографических функций.

В [134] описаны подходы к синтезу шифрсистем, содержащих структуру, знание которой позволяет найти ключ шифрования с трудоемкостью, существенно меньшей трудоёмкости полного перебора. При этом предполагается, что если описание структуры неизвестно, то её «сложно» обнаружить, т.е. трудоёмкость её нахождения не меньше трудоёмкости полного перебора. Такая структура названа «лазейкой», а сама шифрсистема - шифрсистемой с «лазейкой» (см. [134]). Для модифицированных алгоритмов LOKI и CAST описаны данные структуры, основанные на возможности линеаризации с «большой» вероятностью или на существовании линейных соотношений, связывающих открытый текст, шифртекст и, возможно, раундовые ключи. В [130] рассмотрены алгоритмы шифрования, у которых множество всех частичных раундовых функций порождает импримитивную группу. Для них «лазейкой» является система импримитивности, знание которой позволяет применить метод гомоморфизмов, уменьшив трудоёмкость нахождения ключа шифрования. Если такая система импримитивности не известна, то для её нахождения используется, например, один из алгоритмов, приведённых в [135]. Обычно трудоёмкость данного этапа больше трудоёмкости полного перебора.

Неявно вопросы, посвящённые связям свойств группы (gk к є К\ с существованием структур у алгоритма блочного шифрования, рассматривались в [114], [149]. Так, в [149] отмечено, что для отсутствия некоторых структур у алгоритма блочного шифрования с раундовой функцией g требуется примитивность, простота и большой порядок группы (gk к є К\. В работе [114], посвящённой описанию групповых свойств алгоритмов блочного шифрования, утверждается, что условие (f l) к є К} = S(X) достаточно для гарантирования её стойкости. Однако в [122] приведён пример /-раундового алгоритма блочного шифрования, у которого существует структура, но при этом выполняются равенства: (gk к є К\ = S(X), lf l) к є К) = S(X) для чётного числа раундов / и f[l) к є К) = А(Х) для нечётного числа раундов /. Таким образом, включение А(Х) с (f l) к є К\, а также «естественные» требования примитивности и 2 транзитивности недостаточны для отсутствия структур у алгоритма блочного шифрования.

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

Подметрики и надметрики натуральных метрик

В настоящее время метрики используются для исследований в различных областях математики и её приложениях. Существует много работ, в которых рассматриваются разные свойства метрик и их обобщений, что отражается изданием «Энциклопедии по расстояниям» [86] в 2009 г. В дискретной математике, теории графов, теории кодирования, теории ассоциативных схем, теории информации и криптографии часто используются метрики, принимающие значения из множества N0, т.е. натурально-значные метрики. Натурально-значными метриками, например, являются метрики Хемминга и Левенштейна [29], где метрика Хемминга хп на множестве X" задаётся условием Хп (K-i ".,a0X(A-i "- А )) {1 є { -- w }I аг ф А} для всех ((аи_1,...,а0),(у и_1,...,Д)) є (Хп)2, а метрика Левенштейна [29], называемая также метрикой редактирования, равна минимальному числу элементарных преобразований (удаление, вставка и замена) символов, необходимых для преобразования одного слова в другое. В отличие от метрики Хемминга, она позволяет определять расстояние между словами разной длины.

Метрики Хемминга и Левенштейна широко используются в криптографии и криптоанализе. Так, относительно данных метрик проводилось исследование отображений, не размножающих искажения. Изначальная проблема, поставленная А.А. Марковым [33] в 1956 г., заключалась в описании подстановок geS(X") с условием Xn\ag- Р) - гХ„{а Р), справедливым для всех а,{ЗєХп при фиксированном числе г є Ж+, т.е. не размножающих искажений типа замены букв и сохраняющих длину слов, где Ж+ - множество всех действительных положительных чисел. Полученный им результат при г = 1, в настоящее время известный как теорема А.А. Маркова [4], задает класс шифров, не распространяющих искажения типа замены букв относительно метрики Хемминга Хп на X". Б.А. Погореловым в [40] для метрики Хемминга %п на X" дана геометрическая характеризация преобразований, фигурирующих в теореме А.А. Маркова, в терминах операции экспоненцирования групп. Показано, что множество всех таких преобразований совпадает с группой экспоненцирования S(X) Ї Sn, являющейся группой изометрий метрического пространства (Хп,%п).

Как следствие для метрического пространства {Vn,xn) приведён первый пример группы преобразований, увеличивающих число искажений типа замены букв не более, чем в г = 2 раза, которая является надгруппой группы Джевонса S2Ї Sn. Группа S2 Т Sn совпадает с группой ASn, порожденной группой подстановочных матриц Sn и подстановочным представлением группы сдвигов (Vn,@) пространства Vn. Свойства преобразований, удовлетворяющих проблеме А.А.

Маркова, также описаны в [42]. В серии работ М.М. Глухова, А.В. Бабаша, Г.П. Шанкина [6], [7], [9], [14], [15] рассматривались различные вариации проблемы А.А. Маркова. Так, исследовались инъективные отображения с различными типами искажений, например, пропусками, заменами и вставками букв относительно метрик Хемминга и Левенштейна. Метрика Хемминга также используется при определении разных параметров в теории кодирования и криптографии, например, нелинейности функции [82], кодового расстояния линейного кода.

В методах криптоанализа метрика Левенштейна применялась, например, для анализа генераторов с неравномерным движением регистров [93], а метрика Хемминга - в корреляционном методе [91], [117], [139], а также в линейном и разностном методах. Заметим, что в криптографии также используются неархимедовы метрики, например, в работах М. Горецкого, А. Клаппера [94], [95], В.С. Анашина [5], [61], [62]. В [13] Э.М. Габидулин предложил нехеммингову метрику в поле Галуа, названую ранговой, и на её основе - класс ранговых кодов и криптосистемы с открытым ключом [55], [92], [106]. Метрики вводят на различных алгебраических объектах. Так, В.М. Сидельниковым [51], [52] рассмотрены дистанционно транзитивные и дистанционно регулярные метрики на группах. Дистанционно транзитивной метрикой на аддитивной абелевой группе (Х,+) называется метрика, инвариантная относительно группы сдвигов на X. Для группы Fn+ такие метрики рассматриваются в разделе 2.5 данной главы. К данному классу принадлежит метрика Хемминга на Vn. На симметрической группе S(X) часто также используется метрика Хемминга %, задаваемая условием % : (s,g) \- [а є X \ as Ф as \\ для s,g є S(X). Другие метрические пространства, связанные с симметрической группой S(X), приведены в обзоре [87]. Так, каждому метрическому пространству (X,//) можно поставить в соответствие метрическое пространство (S(X), //), полагая ju (s,g) = max\ju(as,ag) а є X\ для всех s,ge S(X). Такая метрика ju называется метрикой движения [74]. Такие метрики могут применяться, например, в методе связанных ключей [64]. В этом случае подстановка s ассоциируется с частичной функцией зашифрования fk на ключе k, а подстановка g - с частичной функцией зашифрования fk, на связном ключе к .

Один из естественных способов построения натурально-значных метрик, который также используется в диссертационной работе, основан на использовании связных графов. Метрикой связного (орграфа) графа Г = (Х,Г) (см., например, [71]) с множеством вершин X и множеством рёбер (дуг) Г называется метрика на множестве X, заданная как длина кратчайшего пути между парами вершин из X. Отметим, что тогда и только тогда метрика связного орграфа является метрикой, согласно её определению в [35], когда для каждой пары (а,Р) є Г справедливо включение (Р,а) є Г. Граф Г = (Х,Г) совместно с функцией весов w:T—»М+ называется взвешенным графом. На множестве вершин X связного взвешенного графа Г = (X,Y) определена взвешенная метрика цТ , заданная условием juf : (а,Р) ь- min X w(u), Р{а,Р)ивР(а,Р) где минимум берётся по всем путям Р(а,Р) из вершины а є X в вершину Р є X графа Г. Отметим, что взвешенная метрика с функцией весов w, заданной условием w(a,P) = 1 для каждого ребра (а,Р) є Г является метрикой связного графа. Метриками связного графа, например, являются метрики: ранговая, Хемминга и Левенштейна. Метрике Хемминга хп ставится в соответствие граф с множеством вершин X" и множеством рёбер (а,а ) є X" %п(а,а ) = l, называемый графом Хемминга, а при X = {0,1} - также п -мерным кубом. Использование натурально-значных метрик является удобным средством для исследований в разных разделах дискретной математики. Поэтому естественно применить натурально-значные метрики и для задания pG -структур,

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

Дистанционно транзитивные графы орбиталов надгрупп группы Джевонса

В данной главе, следуя «эрлангской программе» Ф. Клейна [26], продолжается описание групповых свойств 2-мерных pG -структур, задаваемых орбиталами надгрупп группы Джевонса. Соответствующие им натуральные метрики описаны в разделе 2.6 главы 2. Проводится полная классификация групп автоморфизмов графов орбиталов надгрупп группы Джевонса ASn. Отсюда следует описание групп изометрий натуральных метрик, задаваемых орбиталами. Для классификации использовано описание надгрупп группы Джевонса AS в аффинной группе AGLn, полученное в [40]. В [40] показано, что надгруппами группы ASn являются группы AS ) , AR ) , AS(2) , АО ) , АО(2) , ASpn, где S = Sn+1, R = Sn+1, S(n2) = Sn+2, Spn - симплектическая подгруппа группы GLn, 0 ) ,ОІ2) - ортогональные подгруппы группы GLn для чётного п. Получено, что если группа автоморфизмов графа орбитала примитивна, то она совпадает с одной из групп AS{J1) , AR( n1) , AS , AO( n1) , AO( n2) , ASpn, S(Vn). Если же группа импримитивна, то системы импримитивности имеют блоки вида а,а1и или Fn(0), Fn(1). Поэтому группа автоморфизмов совпадает со сплетением или полупрямым произведением групп 2, S1, AS 1-)1, AR 1-)1, AS( 2-1), AO 1-)1, AO( 2-1), ASpn-1.

В алгебраической комбинаторике «активно» исследуются дистанционно транзитивные и дистанционно регулярные графы. Так, классификации дистанционно транзитивных графов уделяется повышенное внимание более 40 лет (см., например, [67], [68], [69], [101], [102], [132]). Это вызвано тем, что не только некоторые известные графы дистанционно транзитивны, но также тем, что некоторые «интересные» группы являются группами автоморфизмов дистанционно транзитивных графов. Так, дистанционно транзитивными являются графы Хемминга, Джонсона, Гроссманна, полный двудольный и т.д.

В [67] приведён обзор результатов, посвящённых классификации примитивных дистанционно транзитивных графов, у группы автоморфизмов которых существует подгруппа G = M\G0, подобная некоторой подгруппе полулинейной группы ГLn(GF(pr)), при этом группа М действует регулярно на множестве вершин графа и подобна подстановочному представлению группы сдвигов и-мерного векторного пространства над полем GF(pr), где р - простое число, г є N. В этом случае примитивный дистанционно транзитивный граф изоморфен одному из следующих графов: 1) графу Хемминга; 2) сложенному(п + 1)-кубу для чётного и; 3) половинному (п + 1)-кубу для чётного и; 4) сложенному половинному (п + 2)-кубу для чётного п; 5) графу билинейной формы; 6) графу знакопеременной формы; 7) графу эрмитовой формы; 8) аффинному Е6 графу; 9) графу смежно-группового расширенного троичного кода Голея; 10) графу смежно-группового усечённого кода Голея; 11) графу смежности усечённого кода Голея; 12) графу смежно-группового двоичного кода Голея; 13) половинному графу графа смежно-группового двоичного кода Голея. Заметим, что для графов орбиталов надгрупп группы

Джевонса справедливо равенство М = V . В [101] также собраны результаты, посвящённые свойствам дистанционно транзитивных графов. Согласно [140], дистанционно транзитивные графы с импримитивной группой автоморфизмов являются двудольными или антиподальными. Так, классифицированы (см., например, [69]) посредством задания массива пересечений и соответствующей комбинаторной структуры все дистанционно транзитивные графы диаметра 3 с импримитивной группой автоморфизмов. Данная классификация зависит от того, является ли граф двудольным, антиподальным или одновременно двудольным и антиподальным.

Из описания групп автоморфизмов графов орбиталов следует, что большее число дистанционно транзитивных графов орбиталов надгрупп группы Джевонса имеют импримитивную группу автоморфизмов, тем самым являясь двудольными или антиподальными графами. На основе этого в главе 3 проводится классификация дистанционно транзитивных графов орбиталов надгрупп группы Джевонса. Получающееся при этом полное описание всех дистанционно транзитивных графов орбиталов надгрупп группы Джевонса на основе подхода, отличающегося от применяемых ранее комбинаторных конструкций алгебраической теории графов [69], может позволить выявить новые связи между классами дистанционно транзитивных графов. Показано, что среди дистанционно транзитивных графов орбиталов надгрупп группы Джевонса имеются графы, изоморфные следующим графам: 1) графу Хемминга; 2) полному графу К ; 3) полному двудольному графу К г х\ 4) половинному in + 1)-кубу; 5) сложенному {п +1) -кубу; 6) сложенному половинному {п + 2) -кубу; 7) графам знакопеременных форм; 8) графу Тейлора (для графов диаметра 3); 9) дополнению 2х2и -решётки (для графов диаметра 3); 10) дополнению графа 2" 1К2, состоящего из 2й"1 двух вершинных компонент связности; 11) графу Адамара порядка 2" 2 (для графов диаметра 4); 12) графам инцидентности 2-[2n l ,u("\2u("S2)) блок-схем (для графов диаметра 3 при нечётном п 5),

При этом графы диаметра 2 изоморфны одному из следующих классов графов: 1) графу К дополнению графа 2" 1К2; 3) графам знакопеременных форм, группы автоморфизмов которых изоморфны аффинным ортогональным группам АО , АО при чётном п. Также приведён пример применения полученной классификации групп автоморфизмов графов орбиталов надгрупп группы Джевонса ASn для описания группы инерции IS(V\(Cnm) множества Спт корреляционно-иммунных функций порядка т из множества Рп = {/ \f Vn — {0,1}}. Доказывается, что IS(V\(Cnm) совпадает с группой ASn только при нечётном т є {1,...,и-2}, а при чётном т Е{\,...,П-2} - с группой AR{nl). Тем самым исправляется описание группы инерции, полученное в [118], где утверждалось, что Isiv\{Cnm) = ASn для каждого т є {\,...,п-2}.

Инвариантные подмножества линейного преобразования -марковских XSL-алгоритмов блочного шифрования и разностный метод

Алгоритмы блочного шифрования реализуются итеративным применением в раундах более простых (базовых) преобразований, которые должны обеспечивать свойства перемешивания, рассеивания и усложнения. Для обеспечения данных свойств в раунде обычно используются преобразования (слои) трёх типов: аддитивное наложение ключа, нелинейные преобразования над отдельными частями блока текста (s -боксы) и линейные преобразования g, переставляющие между собой части этого блока. Схемы, реализующие подобные алгоритмы, получили название SP-сетей. В последнее время перестановку отдельных блоков стали заменять более общими линейными или аффинными преобразованиями векторных пространств над полем GF(2). Блочные шифрсистемы с таким построением раундовых преобразований и побитным подмешиванием раундового ключа в каждом раунде называют XSL-сетями. В частности, по такому принципу реализованы алгоритмы блочного шифрования AES, «Кузнечик».

В ряде случаев линейные преобразования, обеспечивающие хорошее рассеивание, являются приводимыми. Например, шифрсистемы ARIA, Camellia, MIBS имеют линейные преобразования с характеристическими многочленами над полем GF{2) вида (х 1)г для некоторого натурального числа г. Приводимыми являются и подстановочные матрицы, используемые в XSL-сетях. Это приводит к импримитивности группы Cn(g) = (g,V \, порожденной приводимой матрицей g є GLn и подгруппой Fn+ = iha :Vn — Vn \a є Vn \, где ha : ft \- ft a преобразование-сдвиг пространства Vn на вектор а є Vn, реализующее преобразование слоя наложения ключа. При этом систем импримитивности, частично упорядоченных по вложению, может быть довольно много. Системы импримитивности сохраняются линейным слоем и слоем наложения ключа. Поэтому обеспечивать необходимое «рассеивание» блоков импримитивности в алгоритме шифрования могут только слои s -боксов.

В главе 4 рассматриваются свойства графов орбиталов группы Cn{g) для приводимой матрицы g є GLn и описываются натуральные метрики этих орбиталов. Исследование группы Cn(g) непосредственно связано с выявлением влияния приводимости линейного преобразования g на свойства XSL-алгоритма блочного шифрования. Так, если линейное преобразование g приводимо и W0 -соответствующее инвариантное подпространство, то группа Cn(g) имеет рс , ) структуру (W,W)l, где W = \\VQ,...,Wr- , Wj - у -й класс смежности группы (Vn,@) по подгруппе W0 для у = 0,...,г-1. Причём для каждого і є {0,...,r-l} существует такой элемент /. є {0,...,г-1}, что рс ( }-структура (W,W)j является (Wt,W )-инвариантной. В этом случае группа Cn(g) обладает рс , }-структурой, которая может влиять на свойства XSL-алгоритма. Существование рс ( } -структуры у группы Cn(g), порожденной преобразованиями X,L-слоёв XSL-алгоритма, может влиять на свойства всего алгоритма. В частности, из существования такой рс , } -структуры следуют атаки на алгоритмы блочного шифрования PRINTcipher, Robin, iSCREAM, Zorro [111] и ISEBERG [143].

В терминах характеристического или минимального многочленов g приведены условия: связности графов орбиталов, их изоморфизма, примитивности и 2-транзитививности группы Cn(g). Указаны условия дистанционной транзитивности и дистанционной регулярности графов орбиталов.

Рассмотрены также свойства графов орбиталов группы Сп (g) в двух случаях: когда g лежит в «небольших» надгруппах подстановочных групп и когда g берётся из унитреугольной группы UTn, п = 2т. Приведены условия на орбиталы, при которых соответствующие метрики изоморфны метрике Хемминга (на пространстве Vm, т п), а также их надметрикам или подметрикам. Описаны

натуральные метрики и другие характеристики графов орбиталов группы Cn{g) для циркулянтной матрицы g и матрицы алгоритма блочного шифрования Е2.

Также для марковского XSL-алгоритма блочного шифрования с приводимым линейным преобразованием вместо «классической» г-раундовой разностной характеристики в разностном методе рассматривается г-раундовая характеристика, заданная последовательностью смежных классов инвариантного подпространства линейного преобразования. Полученные при таком подходе вероятности могут увеличить число атакуемых раундов XSL-алгоритма. Приведённый подход эффективнее по сравнению со способом нахождения вероятностей «классических» разностных характеристик. Предложенный подход проиллюстрирован на примере инволютивного алгоритма блочного шифрования ISEBERG [143], представленного на конференции FSE в 2004 г. Проведено сравнение полученных результатов с результатами работы [144]. Всюду в работе матрицу линейного преобразования g є GLn в стандартном базисе є ,...,є \ будем также обозначать как g. Рассматриваемые в работе s-боксы биективны. Всюду п 2, если не оговорено противное.

Свойства орбиталов и графов орбиталов группы С (g) + и Пусть geGLn, d - число орбит группы (g) на Vn. Для пары (a,j3)eV рассмотрим орбитал Г, «)(g) = (a,/?)c"(g) группы Cn(g) = (gha а є Vn\ = {g)V„ соответствующий Г\p)(g) = \Vn,Г, «)(g)) граф орбитала. Так как группа Cn(g) содержит все сдвиги, то её орбиталы самопарные, а графы орбиталов неориентированные. Очевидно, что справедливы следующие утверждения. Лемма 4.2.1. Если g- произвольное преобразование из GLn, а,/3,а ,/3 , произвольные векторы из Vn, а Ф /?, то: 1) (« ,/? ) є (a,P)C{g) тогда и только тогда, когда а /3 є [а /?) ; 2) Г, «}(g) = Г(а, ff){g) для любых векторов со свойством a j3 e(aj3) ; 3) число нетривиальных орбиталов группы Cn{g) равно d -1. Таким образом, все различные нетривиальные графы орбиталов группы Cn(g) суть графы Id Jg),...,Y,d \(g), где J3f ,...,/Зр - все различные орбиты группы (g) на ки. Условия изоморфизма графов орбиталов группы будут приведены в утверждениях 4.2.7 и 4.2.8.