Группа инерции. 
Криптографические методы защиты информации

Напомним следующее определение.

Определение 5.11. Подстановкой непустого множества X называется любое биективное отображение множества X в себя.

Стоит отметить, что если множество X конечно, то понятие подстановки совпадает с определенным нами ранее понятием перестановки, см. стр. 51. Действительно, если |Х| = п, то любое биективное отображение может быть задано в виде.

где все значения Xi различны, г = 1,… , п, и X = U"₌₁ж_п. Поэтом}' для конечных множеств данные нами определения подстановки и перестановки — эквивалентны.

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

Множество всех подстановок образует абелеву группу, которую принято называть группой подстановок. Будем рассматривать группу G ~ группу подстановок на множестве F^.

Определение 5.12. Функции /, h называются эквивалентными относительно группы G и обозначаются / ~ h, если существует а € G, при котором для любого х € Щ верно тождество

Упражнение 5.6.1. Доказать, ч то введенное отношение ~ является отношением эквивалентности на множестве булевых функций от п переменных.

Символом.

обозначим класс эквивалентности, содержащий функцию /. Если класс [/]g состоит только из функции /, то функция называется инвариантной относительно группы G.

Определение 5.13. Множество

называется группой инерции функции / в группе G.

Упражнение 5.6.2. Доказать, что множество /(/)g является подгруппой группы G.

Если порядок группы /(/)g равен 1, то говорят, что функция имеет тривиальную группу инерции. При изучении групп инерции важными для практики являются следующие группы подстановок.^[1]

где а = (од,…, ег") — перестановка чисел (1,2, п).

Функция называется симметрической, если она инвариантна относительно группы S".

2. Группа ?" инвертирований переменных a? i,…, z", которая состоит из 2″ отображений вида.

• 3. Группа Джевонса Q_n — ?_n х S_n, являющаяся прямой суммой групп S_n и ?". Отображения заключаются в перестановке переменных и инвертировании их части. Порядок группы Джевонса равен п!2'
• 4. Группа линейных преобразований GL_n(2), задаваемых невырожденной двоичной матрицей А_пхп — (ау), а_г] € F2:

Порядок группы GL"{2) равен ПГ^о (2^П — 2^г).

5. Группа аффинных преобразований AGL_n(2) = GL_n{2) х ?", являющаяся прямым произведением групп GL_n{2) и Она состоит из отображений вида.

где А_пхп — (ау), a_tj € IF₂ — невырожденная п х п матрица, 6 € F?>. Порядок группы v4GL"(2) равен.

Упражнение 5.6.3. Пусть G € {Sn, GL_n{2), AGL_n{2)} и функция h € [f]_G. Докажите, что.

• 1. INI = 11/11-
• 2. deg h = deg/.

Упражнение5.6.4. Докажите, что |[/]g| —.

Указание. Докажите, что для а, 0 € G равенство f (o (x)) — f (9(x)) выполнено тогда и только тогда, когда а и в принадлежат одному смежному классу группы G но подгруппе HJ)a-

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

Ниже приведены точные значения числа классов эквивалентности для каждой из рассматриваемых групп при п < 6.

Задачи и упражнения к разделу 5.6

• 1. Найдите все функции от двух переменных с тривиальной группой инерции в группе 2.
• 2. Установите связь между группами инерции функций /(х) и h = f (a (x)), a eG.

3. Пусть I (f)_G = G, f = f (xi,… , x_n), ip = (p (xi,… , x_n). Докажите, что ^{[2][3][4][5][6][7]}

• [1] Группа Sn перестановок переменных х, Х2,? ? ., хп, состоящаяиз п! отображений вида
• [2] Докажите, что функция f (x,…, хп) является симметрической, если и только если при каждом фиксированном индексе t вее многочлене Жегалкина все члены степени t либо одновременноприсутствуют, либо одновременно отсутствуют.
• [3] Пусть G = Sn, f{x i, …, хп) = fi (x ь…, хп) + /2(жь …, хп), где множество степеней нелинейности мономов XjY, •? •, Xjs, 1 <�•••< js < п, входящих в многочлен Жегалкина функции /ьимеет пустое пересечение с аналогичным множеством функции /2.Докажите, что
• [4] Найдите группу инерции функции / = хХ2+ ж2жз + хх-$ + хв группе Si.
• [5] ЯВЛЯЮТСЯ ЛИ фуНКЦИИ / = ХХ2 + Ж2Хз + XjХз + X! и h =х2×3 + х'1 эквивалентными относительно группы S3?
• [6] Найдите группу инерции функции / = x + х2 + Х3 + Х4 вгруппе У4.
• [7] ЯВЛЯЮТСЯ ЛИ фуНКЦИИ / = XiХ2 + Х2Хз + Х1Х3 + Х4 + Х5 и/1 = xix2X3 + xix2 + Х4 + Х5 эквивалентными относительно группыДжевонса Qs?