Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)

341

Таким образом,

р(г(у)=(и,у))=-сг(1;)+±

Отсюда вытекает требуемое равенство из свойства 3° .

Вкриптографических исследованиях иногда используют вектор

д.=(д,(г/,),...,дДг/2.))

координаты которого связаны с коэффициентами Фурье равенством

дД(/)= -2"СДц), с/*о.

		\
Вектор	/ называется статистистической структурой булевой
функции, а его координаты — у (Н {		—у {Н2„ ) . коэффициентами стати­
стической структуры этой функции.		Для 11=0 полагают

Д/ (0 ) = 2 ” “, - 2 " С / ( 0 ) .

4°. Для коэффициентов Фурье булевой функции имеет место соотноше-

сг(о)= Х с?(у>

УеУ

у^ 1 т

ДОКАЖЕМ это равенство, действительно, из равенства (2) следует, что

. Х с } ( к ) = ^ г Х / 2И = И = С / ( о )

Уе У	^ УеУГ Л.т	**
Из доказанного сейчас равенства для коэффициентов статистической
структуры вытекает	равенство Парсеваля

ХД/0/)=22(т'1

Уе У

		342
Из формул	СГ(0) = ^ - Н Л у) = М ) и
	\ /	2
А г ( и ) = - 2 т с Д и ) ,		1 ] ф 0 для коэффициентов Фурье булевой
функции получаем, что для		I / ф О

Д,(о)= 2”-1-2-сДо) „ С/ (0)= М

Из равенств ^ / \ У / ~ 4 4. ^ / \ / и / V / 2 ”* сле‘

дует, что

Д / ( 0 ) + 2 " С / ( 0 ) = 2 " - 1.

Для коэффициентов статистической структуры имеют место нера­

венства
5 -1
2 2	< Д / ( С / ) < 2 ” 4 .
Оценка сверху для Д /■		) следует из равенства
Р(Г(У	= (11, V 4	+ ^ г - .

Оценка снизу вытекает из равенства Парсеваля . Действительно, до­

пустим, что А 0 - 0 < 2

Тогда

^ Д 2/ ( к ) < 2 2 (тЧ ),

Уе У

г ^ х т

что противоречит равенству Парсеваля.

343

5. Схема Грина быстрых преобразований Уолша и Фурье.

Для матриц Сильвестра-Адамара Н ^ ш имеет место следующая фак­

торизация (разложение матрицы в произведение матриц)

н г . = м ™ м ™ к м ™ ,

гае М® = Е2„,_, ® Н2, М<“ >= Н2 ® Е2т -,, . м 2т = Е2т-1 ® Н2 ® Е2„-1 , 2 < 1 < Ш-1.

Е*- единичная матрица порядка к.

ДОКАЖЕМ указанную факторизацию индукцией по т. При т=1 имеем

=Е ! ® Н 2 = н 2(

т.е. указанная факторизация справедлива.

С учетом этих равенств имеем

= № , ® Ь ф . . . < р г ® М ^ ) { Н г ® Е г ) = Н 2 Ш ^ . . М ^

Так как по предположению индукции верно равенство

н 2- = м ^ к м ; : ' , ю
К	= я 2„,

и факторизация доказана.

		344
Например, при т =2 факторизация имеет вид
	9 где
1	1	0	°1
1	- 1	0
			0
0	0	1	1	9
0	0	1	- к
	( 1	0	1		0 ^
м<2) = н2®е2	0	1	0		1
	1	0	- 1		0
		1	0	-	к
„	= Е	9111-1	Н 2 ®Е. ГП-1 5 2 < 1 < т - 1
Из равенств 1УА0ш	^
следует, что матрица	» 0 3 / Зда, содержит в каждой строке и в каждом

столбце ровно два ненулевых элемента, равных либо 1, либо -1. Следователь­ но, умножение любой вектор-строки размерности 2т на столбец матрицы

м	(О
	2т связано с одной операцией сложения или вычитания компонент даннои

вектор-строки, а общее число таких операций при умножении вектора-строки

на матрицу -Л/-™ равно 2Ш. Так как умножение вектора-строки на матрицу

Я	2 ш	можно свести к последовательному умножению на матрицы
2^1 ?		2*	, то общее число операций при таком умножении ра-
вно	ш2т.			Н по­
	Отметим, что число умножений вектора-строки на матрицу
рядка 2т без			применения схемы быстрого, умножения требует 22т	операций.

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

345

Применение этой схемы к равенствам (1) и (2) называют, соответствен­ но, быстрым преобразованием Уолша-Адамара и быстрым преобразованием Фурье.

б.Критерий нелинейности булевых функций.

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

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

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

/ ( * ! = (1 + X 1 + *2 )•••(! + )

содержит все нелинейные члены после перемножения. Однако функция § (Х |,...,Х П) = Г (Х !,...,Х П) = Х^Х2 ...Х П состоит из одного члена и

является криптографически неприемлемой.

Как и ранее, ниже для различения обозначений Р - функция, а Р2 - конечноеподе из двух элементов, для поля будем использовать обозначение 0Р(2), столь же общепринятое, как и Р2. Для множества всех двоичных наборов длины к (координатного векторного пространства над полем ОР(2)) используем обозначение [ОР(2)]к.

Критерий нелинейности булевых функций.

В криптографических приложениях часто используются функции вида

Я: [ОГ (2)]п-» [СР(2)]т

346

Например, преобразования 8-блоков шифрсистемы БЕЗ (см. пара­ граф 1.4) определяются функцией

5: [СГ(2)У -> [СР(2)]

Вместе с тем, критерий нелинейности удобно сводить к критериям не­ линейности булевых функций вида

/: \ОР{2)У —> СР(2)

Вэтих целях используется понятие линейной структуры. Говорят, что

5:	[ОР(2)У -> [СР(2)Т				имеет линейную
функция и	\ / л	т	\	/1
структуру, если существует такой ненулевой вектор а ^					и
нетривиальное линейное отображение
Ь :	[ОР	(2 )] "	->	СР	( 2 )

такое, что сумма

Ы5(х + а) + Ы5(х)

принимает одно и то же значение, равное 0 или 1, для всех х е [^^(^)] Эта

С

линейная структура и может быть выражена через линейные структуры буле­

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

У ' ( х 1

) — (^0 +

й ;Х ;

+ . . .

+ <212

По определению считаем, что функция/ нелинейна, если ее алгебраи­ ческая нормальная форма (многочлен Жегалкина) содержит члены степени выше первой. Расстояние функции $до ближайшей аффинной функции Ь опре­ делим равенством

		г ( / ) =	т т с 1 ( / , Ь )
		Ье.А(п)
где	_ расстояние Хэмминга между Г и Ь и А(п) - множество всех аф­
финных функций		’'">х т) а0+	а 1Х \ ■*"••• + а пГХт

_

347

Для исследования		_ расстояния функции Гдо множества А(п)
рассмотрим	- группу всех обратимых преобразований пространства

[0^(2)] р эхой группе рассмотрим подгруппу АОЦп) всех аффинных пре­

образований. Известно, что любой элемент			А О Ь (п ) может быть
записан в виде	с х(% \= А х "Ьа	, где А - регулярная (невырожденная) матрица
	' ’
ихи и а е [О Р (д )]т
Положим,
	Ф ( п ) = \ / : [ С Г ( 2 ) Г - > С Р ( 2 ) \
множество всех булевых функций от п переменных.
Действие группы		на множество	определим равенством

« • / О ) = / ( « ( • * ) )

/ е Ф(и),а € П(п),х е [СГ(2)]]

где

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

И : Ф(п) —» IV

которая принимает значения из соответствующего множества XV. Функция Гудовлетворяет критерию нелинейности, если И(^))е\У1,

- соответствующим образом определенное подмножество. Существен­

но,чтобы значения И были инвариантны при таких преобразованиях из

5

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

Для определения критерия рассмотрим максимальную подгруппу

— ^ ( п) } которая оставляет Б инвариантным, т. е.

Д Г > ) = { а : П ( а • / ) = ! > ( / ) , / е Ф ( и ) , а <= П ( и ) }

Группу будем называть группой симметрий Б. Исследование критериев нелинейности связано с описанием группы симметрий.

348

с

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

АСЬ(п)

' . Этот результат получим в качестве следствия из теоремы, сформу­ лированной ниже.

„

Н а Ф(п)

/

еФ(п)

й

Пусть

—

'

' и для •'

' '

обозначим

ё н (5 ) = гшп (1 (Т ,Н ); П ( п )

- группа всех обратимых преобразований

V

ЬеН

(2)Г

Положим,

^

.(^) ={а: а-Ь е Ндля всех

ЬеН,аеО(п)}.

Будем называть

а " (и)

.

.

„

4

' группой симметрии множества Н.

Теорема 1. Для любого подмножества ^

группа симметрий

(21 совпадает с группой симметрий Н, т. е.

Щ т) = П.т{п)

ДОКАЗАТЕЛЬСТВО состоит из двух пунктов.

а)

Покажем, что ^

~

)

Возьмем СХ, е

(п ) и

/ е

Ф

(« )

Пусть Н Ъ Н

такое

что < * » ( /) =

< * ( / > Ю

тогда

< / « ( / )

=

а ( / , Н

) =

с Ц

а - / , а - к ) , таккак„„ерациядейСтвия

на Ф(п) оставляет инвариантным расстояние Хэмминга. Из определения

0.н (п)

а - Н е Н

и, следовательно,

4

7 следует, что

"

1

<}{а • / , а • к) > йн(а ■/ )

Таким 0бразом,

^

/ ) при

любом а.

п (и)

а И(п)

Так как

4

есть подгруппа группы

4 , то существует оо-

ратный элемент ^

. Действуя этим элементом, получаем, что

349

4н (а ’/ ) -		<*н(а	* ( « • / ) ) ^ ЛН ( / ) . Следовательно,
ан( 0 = а н (а • о			и пт<л) ^			).
б)	Покажем, что			) — ^ (^ ) . Заметим, что для любого
(X 0 . н	( п )	существует такое			Н У \ Н			п V» е±. И
	4 7					, что СХ • Л				хт и, следовательно,
йн { а ' Н ) ф 0 ~							^	( Л	= 0	~ с* г(а \
нк	7	.С другой стороны, так как						и 47 7		, то ОС^ 3 (С1д ^ _

получили Противоречие- Следствие 1. Группа симметрий 1(8) для минимума расстояний 8 до

множества аффинных функций Ь есть аффинная группа А О Ь ( п )

С учетом теоремы 1 остается показать, что							4	7 - аффинная труп-
ш А О Ц п )
Очевидно, что			А О Ц п ) с а л М ( п ) „
			1 7 —	4	'. Кроме того, для любого
а е П < п ) \ Л в Ц п )				.		.	.
у	7	у	7 существует такой индекс 1, что 1 -я компонента
<1|(х1 ,...,х п )		вектора а х	не является аффинной. Тогда, если § ( х 1 ,...,х п ) = XI, то
функция а § ( х 1,... ,х п )= а ((х 1,... ,х п )				Л ('п )^ . Отсюда следует, что
а е П А{п)(п).
7.	Расстояние до линейных структур.
Линейная структура булевой функции ^
определяется существованием такого вектора						ае\(ЭР'{2)1"			, что выражение
							1
С(х+а)+!(х) принимает для всех Х е						одно и то же значение, равное О

или 1. Обозначим через Ь3(ц) множество булевых функций, имеющих линей­ ные структуры. Заметим, что Ь8(п)содержит в себе множество А(п) всех аф­ финных функций. Для булевой функции Гопределим расстояние до линейной труктуры как расстояние Гдо множества Ь8(п):

« / ( / ) = а ( / , Ь З { п ) ) = ш п < * ( / > )

350

Расстояние до линейной структуры может быть одним из критериев не­ линейности булевой функции. Это вытекает, в частности, из следствия из тео­ ремы 1.

Следствие 2. Для группы Да) симметрий расстояния до линейной

АвЫ п) = Л а )

структуры а имеет место включение 4 у ' .

Применим теорему 1 и покажем, что					0(пГ"> => АСЦп)
					4 у	х .
„	/ € Ь8(п )			а € [вР(2)\
Пусть	•'	х ' и пусть			4 / -1 есть линейная структура
.	х е [ОГ(2)1”					_
I, т.е. для всех	1	4 7Л	выполнено равенство г(х+а)+цх)=С, где посто-
С е в Р (2 )		_	сее АОЬ(п)
янная	4 ' . Тогда для				равенство
	/(а (х + а~1(а)))+ /{а{х)) = С
выполняется для всех		х € [СГ(2)]‘				(а) есть линейная
		*■	4 / -1 . Это означает, что а
,	_			а е
структура <х-г. Отсюда следует, что

8. Порядок нелинейности.

( = ф (п )

Для булевой функции ^ ' обозначим через 0(1) - степень члена в алгебраической нормальной форме, имеющего наивысший порядок. Величину 0(1) будем называть порядком нелинейности булевой функции. По-

. О : Ф(и) —» {ОД,К, и},

рядок нелинейности, определяемый функцией 4 ' ’ удовлетворяет требованиям критерия нелинейности в силу следующей теоре­ мы.

Теорема 2. Группа симметрий функции 0 совпадает с аффинной группой АОЦп).

ДОКАЗАТЕЛЬСТВО содержит два пункта.

а) Покажем, что АСЬ(п) ^ А(О) Пусть % 6 АОЬ{п) и выдран

извольная функция ? е Ф(п) . Вычислим алгебраическую нормальную форму

для %'■?’, используя ее связь с		. В	некоторые нелинейные
члены	МОГут исчезать, а некоторые - появляться как новые. Однако чле-