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

	331
а \\В	а и В	а ХпВ
а г\В	а 22В
А ® В =
	а ,В	а В
	п\	^пп

6. Если Нт и Н„ - матрицы Адамара, то их кронекеровское произведе-

ние Н т ® Н " - снова матрица Адамара.

Из свойств кронекеровского произведения следует, что элементы матрицы

Нт® Н „		,	, т.
т	п равны ± 1. Кроме того,
(ЦпЩ		Ж	®ЦП)Т =(Н„, О Ц Ж 1 ®Нтт)=
= (п Е и )® (п Е й)= п и Е п т
где	Ет	- единичная матрица порядка т .
	2. Матрицы Силъвестра-Адамара их свойства.
	Матрицы Сильвестра-Адамара имеют порядок п, где п=2к, к=1, 2 , . . п
и определяются рекурретным соотношением
			н к = щ ® н	к, ,		,
	где			2 к=1,2,...
				/1	!	>
		Н х= (1),		Н 2 =
				V1	‘	К .

Матрица Сильвестра-Адамара обладает свойством симметричности, а

именно

н' = н „

что следует из ее определения.

332

Независимо от свойства 6 можно убедиться, что матрица Н2к действи­ тельно является матрицей Адамара. Доказательство можно провести индукци­

ей по к. Имеем:	Н2 - матрица Адамара,
		н „	) ( н „	\
	=			Я 2„
		^ 2 * 1/ у Н 2Ы - Н ^
	1
^ ы Н	^ - . 7	о	= 2	=2кЕ.
			О	Е-кч
\			V	У
В силу равенства
	Н ,к: - 2кЕ ,к
для обратной матрицы имеем выражение
	Я , Г ‘ = - т		Я „

Рассмотрим совокупность всех двоичных т -мерных векторов УО, VI,..., У2ш-1, координаты которых принимают значения 0 или 1. Будем пред­

полагать, что эти векторы расположены в порядке возрастания чисел, для кото­ рых они являются двоичными представлениями. Для векторов У1=(У1(1),...,У1(ш)), У)=(У)(1),...,У](ш)) будем рассматривать их скалярные

произведения

/	\	т
		0 < у 5 2 ’ - 1 ,
		г=1

где сложение ведется по модулю 2. Покажем, что матрица

н 2„ = ( ( - 1) (УАУ° ) , и = 0 ,1 Д . . . Д т - 1

есть Матрица Сильвестра-Адамара. Доказательство проведем индукцией по т. При ш=1 утверждение верно, так как матрица Н2 имеет вид

Г \	1 ^
Я 2 =	1
1

Введем обозначения

333

Матрицу Н2т+| представим в виде

Гя (1)

И— 2т

2т+0	гг(3)	Н У
V	2т	2 /

где

Я<1>=((-1Г'^)+(0'0)) =((-1Г'^)+(0’1))

Я^=((-1)(^^+<1'0)),Я<!>=((-1Г^)+(и)), .

где (0,0), (0,1), (1,0), (1,1) - скалярные произведения векторов размерности еди­ ница, 0 < 1 , ) < 2 ш - 1 . Очевидно,что

н $	= н $	= я ®	= я 2. ,	я < 1 » = - н г , _
&		•		.
где Н	- матрица Сильвестра-Адамара порядка 2т . Следовательно,

Я _ +1 = Н 0 ® Н . к

ш+1 и Я 2„ _ матрица Сильвестра-Адамара порядка 21

г.. 3.-ПреобразованияУолша-Адамара булевых функций.

Булеву функцию Гопределим отображением {: [ОР(2)]п -> ОР(2),

где ОР(2) есть п-я декартова степень множества ОР(2).

Пусть [ОР(2)]п = { У 0 , У 1 , . . . , У 2 ш . 1}, где векторы расположены в поряд-

3,34

ке возрастания чисел, для которых они являются двоичными разложениями. Вектор

с = ( Г ( у 0 ) , г с у 1 ) , . . . ^ ( у 22 _ , ) )

называется таблицей истинности булевой функции / .

Вектор

Р = ( Р ( У о ) ). . . , Р ( У 2 т _ 1) ) = ^ ( - 1 / <У“ ) , . . . , ( - 1 / (У2П,- ‘ ) "

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

Преобразованием Уолша-Адамара булевой функции / называется век­

тор

р = ( р ( и 0 ) , ... ,р ( п 2 т _ 1) ) ,

координаты которого для всех двоичных векторов Ц>,....Иг"1-! определяются равенством

р (1 ;)= ] Г р ( У ) ( - 1 ) (У’и)

Уе У

у*= 1 т

где Ут = {У0, V I У 2т_11 и скалярное произведение вычисляется по моду­ лю 2.

Из этих определений и записи матрицы Сильвестра-Адамара Н	порядка
2тследует, что
Р = Р- Н.	(1)
г г -1 _ ^ г г

Из этого равенства и равенства

п

^к

2к следует, что

335

А 1 I А

Р = РН'' = — РН

2 "

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

р(у)= ^ ЕРООН)0™ .

2 у € у ш

для любого двоичного вектора \] размерности т . Это равенство определяет об­ ратное преобразование Уолша-Адамара.

Для булевой функции / ( Г ) , множество

^(С/),(7еУг}

называют весовым спектром функции.

Пусть булевы функции / и § связаны равенством

2(У) = / ( А У + Ь),Уе Ут>

где А - обратимая двоичная матрица т хт и Ь двоичный вектор размерно­

сти т . В этом случае говорят, что функция §(У)			получается из функции
/ ( V) аффинным преобразованием переменных. Имеем
Р ( Ц ) = ^ Р ( У ) ( - 1 ) ( у д ) > 6 ( 1 ; ) =			^ 0 ( У Х - 1 ) (У '0 )
У € У т	,	’	У € У т
где Р (П = (-1 У Ч		С(У) = (- 1)*(Г|, V € Ут. Покажем,

что в этом случае весовые спектры функций Г(У) и §(У) совпадают.

Положим У=А'1\у+А'1Ь. Тогда

336

0 ( 1 1 ) = X	\< г * )	+ 2 0 =
	( - 1 Т ' и ) Р { А Г

^	(_			(Г ) =
У е Г т
= ±	^	( - 1	,с/ 7V	) = ± / (^/ 1 )
	^ е Г т
где II-ПА'1 для всех			С/ € Ут .
Равенство Парсеваля

^Р 2 { г ) = 2 т

УеУ

г с Ат

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

Р - Р Т = (/7,/г)= 2	.Г 2( 0 = 2 1=2"
К бУ	к € У

Аналогичным образом из равенств

Р Р Т = { р , р ) = ^ р 2(у)=2т( р , р ) = 22т

УёУ ' ^ ±т

вытекаетравенство Парсеваля для векторов Н У ) :

^р 2 ( у ) = 2 2т

Уе У

г = 1 т

Для преобразований Уолша-Адамара имеет место соотношение ортого­ нальности

	'	,2 т
	2	,
^ у т	О , к =о

							337
ДОКАЖЕМ этот факт. Действительно,
Е	Р ф		) Р ф		+ У ) =
УбУ„
-	I	I		г (г Х-О*' " !				I	г(хХ-')и"а'"я
							Л * €У«
=	I	( -		> У "	V	(ИГ	) .Г (* ) 2	( -	1 )<«” ' ' ” > =
							УбУ.
=	Е	("		1 У*’’' }Р		(»г	) -Р (* >2 т Я (Ж >* ) =
	^ ^€Ут
=	2 т 2		( - 1 ) (И,’К)Р				2 ( ^ ) = 2 м X
	^ «У*							^ еУя
=	2 1т 8 (у			, 0 )
где -4^,х) - символ Кронекера.									, ^	N
Из доказанного равенства при У=0 следует равенство Парсеваля
	2		#	2(к )= 2 1т
	УеУ
	г с	1	т
									/\
В заключение данного пункта изложим трактовку значений р ( У										) пре­
образования Уолша-Адамара,						связанную с понятием расстояния Хэмминга
между функциями.
Если 11=(ЕГ1,И2,... ,4т),					У=(У1,У2,.., ,Ут ),			то скалярное произведение
							ш

(Ч ,У ) = 2 У М = 0 М 1 )

1 = 1

представляет собой линейную функцию И от переменных Х1=Уь х2=У2,...,

Хш=Ут. В силу равенства

п т =	Е н > ./(К)+(1У,П	(*)
	У<ЕУ.
с учетом того, что
	1, / ( У ) = ( Ц , У )
( - 1 )

- 1 , Д Г ) * ( Ц , Г )

	338
преобразование Уолша-Адамара	определяет разность между числом

совпадений и несовпадений булевой функци и ^(У)=^(хь х2,...,хт) с линейной

т

фикцией ( ^ ) = Х * У Л .

/=1

Расстояние Хэмминга'между функциями Г и § определяется равенством

4 Л * ) = ; / ( П * е < У ) ,У е [ с р { г % ]

Нетрудно проверить, что б является метрикой на множестве булевых

функций.
	к/ И	+ ( ^ , о
Из равенства	Уе У
	т
имеем
#(а)=(г”- а ( / , { 1 1 , г ) У 4 / , ( и , г ) ) ) .
Поэтому
	< / ( / , ( [ / , к ) ) = 2 - ' + 2		.
Аналогичным образом следует, что если		, V ) есть дополнение линейной
функции (С/", Г ) , т. е. аффинная функция, то
	а ( / , р , у ) ) = 2 -	+ ! / ( [ / )

Таким образом, расстояние функции Гдо линейной или аффинной функции

является минимальным тогда и только тогда, когда величина Гр) достига­ ет максимального значения.

4. Преобразование Фурье булевой функции. Для булевой функции {( имеющей таблицу истинности Г=(ДУ<>),...ДУгт-|))> где векторы Уо,...,У2т-1

339

расположены в порядке возрастания чисел, для которых они являются двоич­ ными разложениями, преобразование Фурье определяется как вектор

с К О Д ) , О Д ) ,- - ..е д а " 1-,)),

гае {Ио, II],..., О Д } совокупность всех двоичных векторов, а координаты СДИ) определяются равенством

Г ( 1 Г ) = 2 с г ( 1 1 Х - 1 ) < У ’ и ) ,

У е У ш

где, как и ранее, скалярное произведение (II,V) вычисляется по модулю 2.

Числа С((II) называются коэффициентами	Фурье булевой функции Г.
Из последнего равенства следует, что
/ = СГ - Н,	(2,

гдеНматрица Сильвестра-Адамара порядка 2Ш.А так как из соотношения (2) следует, что

то для коэффициентов Фурье получаем следующую формулу

2 О Д ) ( - 1 ) (У'и ) -

2У е У

у*= Аш

Рассмотрим некоторые свойства коэффициентов Фурье булевой функ­

ции.

2 ' где С({0) - значение коэффициента Фурье булевой функции Гдля нуле­

вого вектора, а / вес булевой функции Г, т. е. число таких значений

V € У и , для которых Г(У)=1.

Из свойства 1° следует, что булева функция Гявляется сбалансирован­ ной (равновероятной) тогда и только тогда, когда для нулевого коэффициента Фурье имеет место равенство

с Д о Ц .

340
2°. Для любого вектора	имеет место равенство
с , ( < / ) = ^ г Г Е / И -	1 / ( 0
	У-.{у ,у)=\

3°. Для любого вектора 17* О имеет место соотношение

С , р ) = \ - р ( . / ( у ) = Р , у ) ) .

где Р(ДУ)=(11,У)) - вероятность совпадения значений булевой функции с ли­ нейной функцией (и,V) при случайном равновероятном выборе вектора

V € У т , скалярное произведение (II,V) вычисляется по модулю 2.

ДОКАЖЕМ 3°. Действительно, имеем

	Р (Г (V ) = ( Ц , У ) ) =	1	Е Р ( Г ( У ) = ( ц , V ))
		ш
			ЧУе Ут
	т	у е у
	у 6 у
	( у , у )=1	( у , у	) = о
	I г ( / ) +	2 < ' ( у ) +2
	Уе У„	У е У т
	,(и»У )=1	(у ,у )=о
	Р ( Г ( У ) = (И , V ) ) = -^ -1 " Е ? (V ) = ( о >V ))
		2	^ у 6 у ,
			Е О - г < У »
	V е У |	V е У I
	(Ц,У)=1	(У , V /= О
	Е г(у )+		Е г(у)+ гт + 1 - -Сг(о)+7-
	V е V 1	V € V1 1

(У .V )=1

(у ,У > О