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

				351
ны некоторой степени ^	в -Г(х) не могут в				порождать члены степени
выше, чем ^ . Отсюда следует, что
	0 ( а - / ) < 0 ( / )
Эту формулу применим к случаю, когда действие определяется а .
Имеем
0 ( / ) = 0 ( а - ‘ - ( « - / ) ) < 0 ( « . / )
Из приведенных формул следует, что
0 ( а - / ) = 0 ( / )
Следовательно, а е			.
б) Покажем теперь, что				— АСЬ(п)
Пусть а е АСЬ(п)		Тогда при действии а на ( х				, х п) имеем не-
линейную компоненту	СС ( X	1	г )	"Г ( X	X ^ — у	' следует, что
	/ч			■и из •' 4 1’"'’	" ’
^ а ‘ ■Стало быть	Г ) > 1, в то время как 0(1)=1- Отсюда вытекает,
ЧТ0а е ^ ( О )

9. Совершенно нелинейные функции.

Булева функция ^ ^ СР{22) иазывается СОвершенно

\ . .	-	ае[О Р(2)]я
нелинейной функцией, если для каждого ненулевого вектора		|-	4

значения функции Г(х+а) и Г(х) совпадают точно для половины векторов

хе[ОР(2)]я

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

352

Для произвольной функции ^	~^ О Р { 2 ) расстояние д0
линейных структур можно вычислить следующим образом. Пусть

а^[вР{2)}1					„		т	[ОР( 2)]1	можно
	1-	4 /л		- ненулевой вектор. Тогда пространство
разбить на 2			неупорядоченных пар вида (х, х+а). Обозначим через П° чис*
ло элементов множества					цг
					0 пар вида (х, х+а), для которых ^(х)=й[х+а), а через
Н	1 - число таких пар множества					цг	/(х ) Ф /( х + а )
						1, что ■' 4 7 ■/ 4		у .
		Любая булева функция может быть получена из функции Г путем изме­

нения соответствующего множества е-значений. Таким способом функцию Г можно преобразовать в функцию с линейной структурой, изменяя значения ли*

бо для х, либо для х+а для пары (х, х+а)	6 IV	■ .
	0, или путем изменения 1-значений,
либо х, либо х+а для пары (х, х+а) е ^	. Таким образом, П° значений можно

изменить так, чтобы получить функцию § с линейной структурой такой, что

^ (х ) Ф # ( х + а ) для всех х, а и, значений изменить так, что получить фун* кцию § с линейной структурой такой, что &(х) = ^ (х + а ) для всех х. Для

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

П = ГП1П(й0, Щ) есть расстояние функции/ до ближайшей функции с ли­

нейной структурой С1. Заметим, что п зависит от вектора О- , то есть

п = п / ( а ) = т т ( п 0( а ) , п х( а )).

Отсюда расстояние до линейных структур определяется формулой

« ( /) = т т п г ( а ) .

	а*0		1
„	п Л а ) + п Л а )			= 2"“'	, то из этой формулы следует, что
Так как	и у	7	1X7
п Л а ) < 2 п~2	для всех		/7 3^0	. Максимум расстояния достигается для со-
у			'
	„	„ ,			п 0 ( а )	= п х( а ) = 2 п~2	для
вершенно нелинейной функции и в этом случае и х						1
^ ^ ^ или, что эквивалентно,				'	. Таким образом доказана сле­
дующая

353

Теорема 3. Класс х ^ совершенно нелинейных функций совпадает с классом функций, имеющих максимальное расстояние до линейных структур,

равное 2П‘2

{ ( х \	р ( х \	= ( - 1 у/(*)х>	, то из
Если '} к } - совершенно нелинейная функция и	4 '	4 )

определения совершенной нелинейности следует, что для любого ненулевого

вектора	а	Е \0 Р ( 2 ) \п	имеет место равенство
		ь

^ Р ( х ) Р ( х + а ) = О

х е [ С Р (2)]	т
Рассмотрим преобразование Уолша-Адамара для совершенно нели­
нейной функции / О	) . По определению имеем: •

Р ( и ) =		X			.
		*е[С Р(2)Г
Из этого равенства следует, что
Р \ и ) = 2" +					^ Р ( х ) Р ( х + а)
		ае[СР(2)]т			х ь[СР(2)]т
		аФО
Пользуясь этими равенствами, с учетом соотношения
^	Р ( х ) Р ( х + а ) = О
х е [ О Р	(2 )] т				'	■
находим, что				п
	Р	( и ) ' =	2	2		( * )
Теорема 4. Булева функция			/' ( X)		является совершенно нелинейной то­
гда и только тогда, когда матрица Н				=	(/*му ) 5строки и столбцы которой
помечены 2 ” векторами пространства \ Н (2 )]						и элементы имеют вид
		к и* = - ^ - г Р ( и + V) _

является матрицей Адамара.

12 Зак. 5

354

Из равенства (*) следует, что

^ 1. Кроме того, скалярное произ­

ведение и -й и -й строк удовлетворяет равенствам

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

П

Обратно, если Ьиу — ±1,то Р ( и + V ) — + 2 2 т. е. функ-

является совершенно нелинейной. Ортогональность строк матрицы

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

Функция У \Х) , для которой преобразование Уолша-Адамара удовле-

творяет условию (*), называется бент-функцией. Таким образом, справедлива следующая

Теорема 5. Класс совершенно нелинейных функций совпадает с клас­

сом бент-функций.

Из равенства (*) следует, что бент-функций могут существовать только для четных п . Из свойств совершенно нелинейных функций следует, что поря­ док нелинейности бент-функции не превосходит п/2.

10. Расстояние до аффинных функций и корреляция.

Пусть Ь п ( х ) = ( и , х) - произвольная линейная функция и

^ . Тогда из определения преобразования Уолша-Адамара

следует, что

Р{и) = |{х : / ( * ) = Ьи(х)}| - \{х : / ( х ) Ф Ьи(х)}|

Отсюда следует, что

355

где (2 означает расстояние Хэмминга. Расстояние до соответствующей аф­ финной функции Ь'и = Ь и + 1 вычисляется по формуле

								Л
таккак в этом случае преобразование Уолша-Адамара равно
Формула			—	п -1	1	А	)	может быть использо­
				^	^	^
вана для отыскания наилучшей аппроксимации булевой функции /										с помо­
щью линейной функции (и,х)			путем отыскания для данной функции / такого
А
м, что Р(и) достигает максимума, т. е.
				а(Г)= 2”-1-1 т а х Р(и) .
							^	и
Из равенства (*) следует, что для совершенно нелинейных функций
расстояние с1(Т) до ближайшей аффинной функции равно								<100= 2 п	-1	~ -1
										- 2 2
Если у' не является совершенно нелинейной функцией, то из равенства
										п
Парсеваля	^	( М )	—	2	следует, что Л ш Р(и)					^ .
“								и
Следовательно, в этом случае б(0< 2 П-1 —2 2							и, стало быть, эта фун­

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

Итак, доказана следующая теорема.

Теорема 6. Класс совершению нелинейных функций совпадает

с классом функций, для которых достигается максимум расстояния до аффин-

ных функций, равный 2 т- 1 — 2 2 1

12*

				356
В начале пункта 10 указывалась формула
				=	2 — 1 -
Из этой формулы следует, что расстояние совершенно нелинейной фу-
нкции /	до любой аффинной функции равно либо					2 т 1	+	—— 1
								2 2
т	- 1	— -		1
либо 2		— 2	2	. Этот факт можно выразить с использованием по­
нятия корреляции функций.
Корреляция С ( / , §) для булевых функций /						и § определяется равенс­
твом
2 “ С		( / , з )	=	| { х : / ( х ) =	§(х)} -	| { х : / ( х	)	ф # ( х ) | .
Для §		= Ь и в соответствии с равенством
	1	х п		л	-		[ 2 т ,1Л = М?
—Г		^		Р(и + у)Р(м> + у) = \

имеем	С ( Г , Ь ) = — / ( м )	.
	V •/ > и / 2 ” \

Из этого равенства и (*) следует, что абсолютная величина корреляции между совершенно, нелинейной функцией и любой аффинной функцией пред-

т

ставляет собой постоянную, равную 2 2 .

Если, же функция § не является совершенно нелинейной, то ее корре-

т

ляция С(§, Ь) с аффинной функцией Ь больше 2 2 по абсолютной величине.

Отсюда вытекает следующая

)

Теорема 7. Класс совершенно нелинейных функций совпадает с клас­ сом функций, для которых корреляция со всеми аффинными функциями дости­ гает минимума.

Отметим, что корреляция С (/,0 ) булевой функции / с нулевой фун­ кцией определяет степень сбалансированности / . Ясно, что совершенно нели­

нейная функция никогда не может быть сбалансированной. Вместе с тем, отме-

т

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

11. Булевы функции от нечетного числа аргументов.

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

При нечетном п для булевой функции ? € ^)(и) рассмотрим функции

/ о . / .	е Ф ( л - 1 ) такие> что				=	ДО,				и
Д *!	~		.Обозначим через					и	1- преобразования
		/ * ( х		д ;	)	[ д ;	д ;	Л	соответственно. Для
Уолша-Адамара функций •’0 4				т_1/ и •/14 1,'“’			т_1'
преобразования Уолша-Адамара ^				^	функции Р		при и ~ ^и0 ’и1 ’—’ит-\)
	Ро(и) = Р(и)	к0 = 0			Р((и) = Р{и)			при	м0 =1 ~		я
положим		при	0 1	и	1				0	. Таким обра-
						/V ^		/V	/V
зом Р = (Р,',Ро). Тогда имеют место равенства:							=	^0		^1 >
Л /V	/V
р ;= р о -р ь
	Теперь, если		совершенно нелинейные функции, то
					п-1

Р0(и) = Р1(и) = ±2 2 _

Д^	I	/V^
1Р о ( и )	и	Р ' 1 ( и ) могут принимать точно два зна-

к- 1

'У

чения 0 или , . Стало быть и Р(и) принимает эти же два значения. Ис­

пользуяравенство Парсеваля, можно показать, что ровно половина значений

358

к-1

равна 0, а другая половина равна ,	'У
	. Можно также показать, что для

класса функции П (п ) , для которого преобразование Уолша-Адамара входя-

		к- 1
щих в него функций принимает два значения 0 и ,		, порядок нелинейности
	к- 1
функции /	(и ) не превосходит , 2 , а расстояние до аффинных
функций определяется величиной
	п +1
а ( Г ) = 2 " - 1 - 2 ~ 2
Таким образом, при п нечетном функция /		€ ГГ(и) является при­

мерно так же далекой от аффинных функций, как и совершенно нелинейные функции при п четном. -

Параграф 6.8 Регистры сдвига, одноканальные линии задержки

Линейным регистром сдвига (ЛРС) называют устройство - регистр сдвига с линейной обратной связью и линейной функцией выхода. Получаемая с ЛРС последовательность является линейнрй рекуррентной последовательнос­ тью. Ниже приводится основные понятия и широко известные основные алгеб­ раические результаты по изучению свойств таких последовательностей. Изло­ жение материала основано на книге (М.М. Глухов, В.П. Елизаров, А.А. Нечаев «Алгебру. Часть II», Москва, 1991).

Читателю, желающему познакомиться с этими результатами более де­ тально, рекомендуем прочесть Приложение 2.

Далее Я - коммутативное кольцо с единицей е, N —множество нату­ ральных чисел, =N^0, 2 - множество целых чисел, ОР(я) - поле из ц эле­ ментов.

Определение 1. Последовательностью над Я назовем любую функцию и : Р^ —» Я, при этом для каждого 1€ Р^ элемент и(1) назовем 1-м членом после­

довательности и. Множество всех последовательностей над Я обозначим Я°°.

359

Для наглядности последовательность ие К* можно записать в виде бес­ конечного вектора

и=(и(0),и(1),...,и(1),...). (1)

Последовательность (О, О,...,О,...) будем называть нулевой, и обо­ значать через (0).

Определение 2. Последовательность иеК°° называют линейной рекур­

рентной последовательностью (ЛРП) порядка т>0 над К., если существуют
константы Г0, Г|,...,Гт.1еИ -такие, что любого 1е
и(1+ш)= Гт.1и(1+щ-1)+...+ Г,и(Н-1)+ Гои0).		(2)
В этом случае соотношение (2) называют законом рекурсии ЛРП и,
многочлен Р(х)=хт - Гт.|Хт''	Г)Х - Го - характеристическим многочленом

ЛРП и, а вектор и(0,...ш-1)=(и(0),...,и(т-1)) - ее начальным вектором. После­ довательность (0) считается по определению единственной ЛРП порядка 0 с характеристическим многочленом Р(х)=е.

Пример 1. (Последовательность Фибоначчи). Эта последовательность

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

цев? Если обозначить искомую величину через и(1), то нетрудно увидеть, что ц(0)=1, и(1)=1 и и(1+2)=и(1+1)+и(0 для 1б]\. Таким образом, и - ЛРП над Ъ

(кольцом целых чисел) с характеристическим многочленом Р(х)= х2 -х -1 и на­ чальным вектором и(0,1)=(1,1).

Арифметическая последовательность. Для любых элементов а, <1 из кольца В последовательность V с общим членом у(1)=а+сН, 1е {0,1,...} есть ЛРП порядка 2 с характеристическим многочленом Р(х)=х2-2х+е=(х-е)2 и начальным вектором (а,а+<1).

Геометрическая последовательность. Для любых элементов а, ц из кольца К последовательность а,ац,..,,ая',... есть ЛРП порядка 1 с характери­ стическим многочленом Р(х)=х~я и начальным вектором а.

Конгруэнтная последовательность. Для любых элементов я, б из кольца К. последовательность ш(0),\у(1),...,\у(Г),..., определяемая соотноше­ ниями ш(0)=а, \у(1+1)=яш(1)+б, 1еЫ0 есть ЛРП порядка 1 с характеристическим многочленом Р(х)=(х-е)(х-я) и начальным вектором \у(0,1)=(а,ая+б). Арифме­ тическая прогрессия есть частный случай конгруэнтной последовательности при я=е.

Пример 2. Линейный регистр сдвига с характеристическим многочле­

ном Р(х)=хш- Гпих1"'1- ... - Г)Х - Го - это конечный автомат вида

360

Здесь ц(0 - ячейка памяти, содержащая элемент ц(з)еК. ;Т5 - узел, осу­ ществляющий умножение на Р8; знак + обозначает узел, осуществляющий сложение в К.. В начальный такт работы в ячейках памяти регистра записан на­

чальный вектор р(0,..., т-1) = (|д(0),... ,ц ( т - 1 ) ) ЛРП .	Такой регистр схе­
матически обычно изображается следующим образом.

|1 ®

ц.(1+ш-1)

^ —

Заметим, что заполнение ц(1,..., 1+ш-1) регистра в 1-й такт работы вы­

ражается через его начальное заполнение ц(0,..., т -1 ) формулой р(1, ... , 1+Щ-1) = ц(0,..., т-1)- 8(Р)',

где '

	( 0	0	. .	0	/о )
	е	0	. .	0	/,
	5 ( Г ) = 0 е		. .	0
					Л
		0	. .	е	./т-1 )

- сопровождающая матрица для унитарного многочлена Р(х).