Глава 4.

КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА БУЛЕВЫХ ФУНКЦИЙ

Основное в этой главе…

Нелинейность булевой

функции .……………………..….…...50

Критерии распространения и корреляционная иммунность..….58

Устойчивые булевы отображения……………………..…..62

50 Глава 4. КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА БУЛЕВЫХ ФУНКЦИЙ

Анализ стойкости криптосхем, основанных на комбинировании регистров сдвига [34, 35, 36], естественным образом приводит к необходимости исследования математических свойств булевых отображений, под которыми

понимаются отображения	f :GFn →GFm		(n ≥m) конечномерных векторных
	2	2

пространств над полем GF2 из двух элементов.

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

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

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

4.1. Нелинейность булевой функции

Булевой функцией называется булево отображение вида f: GF2n →GF2 .

Таким образом, область определения булевой функции состоит из (0,1)-

векторов размерности n, количество которых равно 2n. Операции с координатами векторов выполняются по модулю два. Булева функция принимает значения 0 или 1.

Булево отображение	f: GF n →GF m		можно представить в координатном
	2	2
виде как систему булевых функций		f = (f1, f2 ,K fm ), где fi (i =1,K,m) -

т.н. координатные функции.

x1, x2 ,K, xn

x1, x2 ,Kxn , f (x1, x2 ,K, xn ),

Нелинейность булевой функции 51

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

Таблица, представляющая булеву функцию f (x), состоит из строк вида причем наборы аргументов

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

Заметим, что в упорядоченном списке аргументов любые k ≤ n фиксированных столбцов содержат все k-мерные двоичные наборы. Полная совокупность таких наборов встречается в указанных столбцах 2n−k раз.

Обозначим количество единиц в векторе значений через wt(f ). Величина wt(f )называется весом булевой функции.

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

P(1)= wt(f )2n , P(0)=1− wt(f )2n .

Как меру различия между булевыми функциями f (x) и g(x) от n

переменных удобно использовать количество покоординатных несовпадений в векторах их значений. Данная мера dist(f , g )= wt(f g ) называется расстоянием Хэмминга между функциями f и g.

Расстоянием Хэмминга от функции f (x) до заданного множества

функций G называется значение dist(f ,G)= min dist(f , g ).

g G

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

52 Глава 4. КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА БУЛЕВЫХ ФУНКЦИЙ

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

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

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

любого v GF m #{u GF n : f (u)= v}= 2n−m .
2		2
Вектор значений равновероятной булевой функций, таким образом,
содержит одинаковое число нулей и единиц.
Свойством	равновероятности		обладают т.н. линейные функции вида
u(x)= a1x1 a2 x2 K an xn ,			где	a = (a1,a2 ,K,an )	-	вектор
коэффициентов,	a GF n .
	i	2
По аналогии со скалярным произведением будем обозначать линейные
функции через	a, x . Очевидно, равновероятными являются также аффинные
функции вида lab = l(a,b; x)= a, x			b , где b {0,1}. Множество аффинных

булевых функций от n переменных обозначим через An .

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

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

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

f (x)

Нелинейность булевой функции 53

Нелинейностью булевой функции f от n переменных называется параметр

N f

- расстояние

от

f до множества

аффинных

функций,

т.е. значение

N f

= min dist(f ,l),

l An .

l

Определение

нелинейности

расширяется

на

булевы

отображения

f = (f1, f2 ,K fm ),

исходя

из

свойств

совокупности всех

нетривиальных

линейных

комбинаций

l(c, f )= c1 f1 c2 f2 K cm fm

координатных

функций, с коэффициентами из GF2 .

В этом случае N

f

= min N

l(c, f )

, c GF n

, c ≠ 0 .

c

2

Рассмотрим наряду с функцией

f (x) функцию

~

(x)= f (Mx +c), где M

f

- невырожденная матрица порядка n, а x,c GF n .

2

Преобразование (замена переменных) вида

y = Mx +c называется

аффинным

преобразованием

пространства

GF n .

Данное

преобразование

2

является взаимно однозначным, следовательно, если исходный вектор значений

не изменять, то в табличном представлении функции возникает

перестановка векторов аргументов. Очевидно, эта перестановка не зависит от функции f.

Таким образом, ( )= (~). Кроме того, легко показать, что при

f

wt

f

wt

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

Следовательно, при аффинном преобразовании координат области определения нелинейность булевой функции не изменяется.

Для изучения свойств нелинейности булевой функции f (x) большое значение имеет преобразование Уолша-Адамара.

a GF2n

54 Глава 4. КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА БУЛЕВЫХ ФУНКЦИЙ

При преобразовании Уолша-Адамара элементы 0 и 1 поля GF2

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

булевой функции f (x) получается функция	W	f	(a), a GF n , связанная с
					2
вектором значений функции h(f ,a)= f (x) a, x				. В этом векторе единицы
соответствуют местам несовпадений правой части функции					f (x) с правой
частью линейной функции a, x .
Значением Wf (a) является разность между числом нулей и числом единиц
в векторе h(f ,a): Wf (a)= ∑(−1)f (x) a,x ,	где			x GF2n	пробегает все
x

множество аргументов.

Поскольку возведение минус единицы в целые степени, отличающиеся на четное слагаемое, дает одинаковый результат, то Wf (a) можно выразить через обычное скалярное произведение и вещественное сложение:

Wf (a)= ∑(−1)f (x )+(a,x ). x

Если зафиксировать f, то, очевидно, можно считать, что аргументом функции Wf (a) является линейная функция, заданная вектором и

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

В этом векторе элемент Wf (a) однозначно определяет расстояние

Хэмминга	между функциями	f (x)	и	la = a, x ,	а также	количество
аргументов, на которых они совпадают.
Действительно, если через n+ и n−			обозначить соответственно количество
нулей и	количество единиц	в векторе		значений	функции	f la , то

Нелинейность булевой функции 55

n −n =W

f

(a)

и

n

+ n = 2n , откуда

n = 2n−1

+

1

W

(a)

и

2

+ −

+

−

+

f

dist(f ,la )= n− = 2n−1 − 12Wf (a).

Сопоставим вектору значений булевой функции g вектор gˆ =T (g), в

котором gˆ(x)= (−1)g (x). Очевидно, выражение Wf (a)= ∑(−1)f (x )+(a,x ) можно

x

рассматривать как скалярное произведение векторов fˆ и lˆa .

Если при вычислении этого выражения вместо la использовать аффинную функцию la 1, то, поскольку T (la 1)= −lˆa , получим величину −Wf (a).

Поэтому выражение n+ = 2n−1 + 12 Wf (a) равно количеству нулей в векторе

значений функции f la , либо функции f la	1,		при Wf (a)≥ 0 ,
Wf (a)< 0 соответственно.
Таким образом, чем больше абсолютное значение		Wf	(a)		коэффициента

Уолша-Адамара, тем меньше расстояние от функции f до множества аффинных функций.

Следовательно, N

f

= mindist(f ,l)= 2n−1 −

1

max

Wf (a)

,

l A

, a GF n .

l

2

a

n

2

Говорят, что

функция

lab An является

аффинным статистическим

аналогом функции

f ,

если

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

равновероятном выборе аргументов p(l, f )>1 2.

56

Глава 4. КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА БУЛЕВЫХ ФУНКЦИЙ

Очевидно, вероятности

p(l, f ) можно вычислить через коэффициенты

W

(a),

исходя

из

соотношения

n = 2n−1

+

1

W

f

(a),

т.е.

2

f

+

p(l, f )= 12 + 21n 12Wf (a) .

Последовательность		1	W		(a)	,	где	аргументы	a GF n
	2			f					2

лексикографически упорядочены, называется статистической структурой функции f.

Исходя из значения ∑Wf2 (a),					можно оценить величину N f				следующим
		a
образом.
Заметим, прежде всего, что
∑Wf2 (a)= ∑ ∑(−1)f (x)(−1)(x,a)					2
						= ∑ 2n + ∑(−1)f (y )+ f (z )(−1)(y,a )+(z,a) =
a		a x				a		y,z
								y≠z
= ∑ 2n + ∑(−1)f (y )+ f (z )(−1)(a, y z )				= 22n + ∑(−1)f (y )+ f (z )∑(−1)(a, y z ) = 22n .
a		y,z					y,z	a
		y≠z					y≠z
Здесь внутренняя сумма ∑(−1)(a, y z )							обращается в ноль при y z ≠ 0 .
		a

Действительно, показатель (a, y z) равен количеству единиц в векторе a на местах, соответствующих номерам единичных компонент вектора y z .

Поскольку в сумме участвуют все 2n векторов a GF2n , то величина

(a, y z) принимает четные и нечетные значения равное число раз.

Нелинейность булевой функции 57

Далее. Предположим, что	max		Wf (a)		< 2n 2	. Тогда	∑Wf2 (a)< 22n , что
	a						a

невозможно. Таким образом, для любой булевой функции f, maxWf (a) ≥ 2n2

a

и, следовательно, N f = 2n−1 − 1 maxWf (a) ≤ 2n−1 −2n2−1 .

2 a

В случае, когда maxa Wf (a) = 2n2 , значение Nf максимально. При этом,

поскольку Nf является целым числом, n - необходимо четное.

Оказывается, существуют булевы функции, у которых все коэффициенты Уолша-Адамара равны ± 2n2 . Такие функции называются совершенными нелинейными функциями, бент-функциями или максимально нелинейными функциями.

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

Можно показать, что множество {Wf (a)} абсолютных величин

коэффициентов Уолша-Адамара булевой функции f не изменяется при аффинной замене переменных.

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

Следует отметить, что максимально нелинейные функции не являются равновероятными. Поэтому в криптографических приложениях важны методы построения равновероятных булевых функций, с нелинейностью близкой к максимальной: Nmax = 2n−1 −2n2−1, n = 2k .