Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии

/юточные системы шифрования

Следовательно, корни минимального многочлена указан­ ного произведения последовательностей имеют вид:

	в ч'1 +ч'2 +...+ЯЧ = в ^	,	0 < у , < ? ,
	т-1
причем	у, < д < г . А поскольку последовательность
	КО = /(К 0> -..,К * + т -1)),		/ > О,

представляется в виде суммы последовательностей вида (6), то минимальный многочлен ту(х) делит Р <г>(х). Откуда следует оценка ранга ЛРП V .

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

стра сдвига большей длины.
Заметим, что степень	многочлена	Р^г\ х ) равна числу
целочисленных наборов	(/0,...5/да_]) ,	таких, что 0
т- 1

Уу‘, = г , и представляется в виде

у=0

к>О

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

271

Гпава 9

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

А щ р <г>{ х) .

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

Комбинирующие генераторы

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

Рис. 38

Рассмотрим один частный случай комбинирующего гене­ ратора, когда функция усложнения / имеет степень нелиней­ ности /, и ее представление свободно от квадратов:

/(Х\ ...х() = Х	X С ,.	■*/, ••••• х1к •	(7)
к=1	1</|<...<1к<1

272

/юточные системы шифрования

Теорема 4. Пусть и{ и( — ЛРП максимального пе­

риода с примитивными характеристическими многочленами

(.г),..., Р{(х) над полем	СТ(д) попарно взаимно простых
степеней: п8 = (1е§/\Д х),	{п8, п ^ ~ 1 для 8Ф у\ л*, у = 1 ,/.

Тогда для функции усложнения вида (7) линейная сложность последовательности V вида

40 = /(«1(0»«2(0,-,И/СО)» г* о

равна

	^	^		ГК >		00
	&=1 1< /]<...</^</			/=1
_	ГО.если С.-,		=0,
где С, ,	= ,	'1"'А	*	л
1~*	[ 1 ,еош			0.
Д оказательство. Согласно (7),					последовательность	V
представляется в виде суммы последовательностей вида
	Л-7к ' иЛ 0") ‘ и./2 0) ■			‘0)>	С71_ ]к ^ 0 ,	(9)

где 1 < к < 1 , 1 < у, < ... < у* < ( .

Если в произведение (9) вместо элементов линейных ре­ куррентных последовательностей подставить их выражения через функцию “след”, то получится представление в виде

суммы последовательностей вида		с	, Й	■	Л и
			(аД ч		) , где
<х}—	корень многочлена Р}	(х)	в поле		С Р ( д т),
т = щ	• п 2 •... -п5, 0 < 1В < пк	, 5 =\ , к ,		с —	некоторая

константа из поля СР{дт) .

273

Алава 9

Отсюда следует, что корни минимального многочлена

произведения (9) имеют вид а ^ 1\

1к , 0 < /5 <п^ ,

з = 1, к . Непосредственно проверяется, что все такие элемен­ ты являются попарно различными и могут быть представлены

в виде (а^	г
	при подходящем значении г . В силу

свойств многочленов над конечными полями отсюда следует, что минимальный многочлен произведения (9) является не­

приводимым многочленом степени		•п ^	.
Можно заметить, что при различных наборах			индексов
1 < }\ <...<	1 < к < ! , минимальные многочлены для по­

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

Композиции линейных регистров сдвига

Рассмотрим еще один тип генераторов, представляющий собой композицию линейных регистров сдвига. Так называет­ ся схема, в которой выход одного из регистров подается на вход другого регистра (см. рис. 39).

Р (х )

0 ( х )

Р ис.39

274

/юточные системы шифрования

Функционирование такой схемы описывается следующим образом. Пусть V — ЛРП, вырабатываемая первым регист­ ром сдвига, закон рекурсии которого определяется характери­ стическим многочленом Р (х ) .

Пусть задано начальное состояние второго регистра сдви­

га, закон рекурсии которого определяется характеристиче-

/77-1

ским многочленом С (х ) = х т

• Тогда выходная по-

следовательность композиции регистров сдвига задается со­

отношением

/77-1

М? + т) = ] Г М‘ + ^)8^+ у(0> г^О.

Непосредственно из определения композиции регистров сдвига вытекает, что минимальный многочлен выходной по­ следовательности делится на минимальный многочлен после­ довательности V и делит произведение Р( х) - С( х) .

Схемы с динамическим изменением закона рекурсии

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

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

275

I лава9

Один из путей построения подобных схем основан на ди­ намическом изменении закона рекурсии линейного регистра сдвига.

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

Рассмотрим два многочлена		А(х) = х т+	х ] ,
В(х) = х т +' ^ Ъ кх к степени	т и	последовательность	V ,
удовлетворяющую условиям:
т- 1
у(2/ + т) = - ] Г а} • у(2/ + у),
7=0
т-1
у(2/ + 1 + т) =	у(27 + 1 + * ) , / > 0.

к=0

Ясно, что в четных тактах закон рекурсии последователь­ ности V определяется характеристическим многочленом А(х) , а в нечетных тактах - - характеристическим многочленом В(х).

Образуем многочлены А (0)(х), Л0)(х), В (0)(х), В 0)(х)

следующим образом:

Л(0)Ск) = ^ а	2]х 2],	^ 0)(х) = ' ^ а 2у+1х 2-/+\
7^0		7^0
В {0\ х ) = ^ Ь	2]х 2^	Я(1)(*) = 2 > 2у+1*2у+1-
7-0

276

/юточные системы шифрования

Несложно проверить, что получаемая в результате после­ довательность V является линейной рекуррентной последо­ вательностью с характеристическим многочленом

Н(х) = А{1)(х)В{1)(х) - А {0)(х)В{()\ х).

К классу генераторов с динамическим изменением закона рекурсии относятся также линейные регистры сдвига с нерав­ номерным движением информации. Так называются регист­ ры, для которых число тактов работы до получения (/ + 1)-го знака выходной последовательности зависит либо от значения числа г, либо от состояния регистра в такте /. Получаемая в результате последовательность будет некоторой выборкой с переменным шагом из исходной ЛРП, вырабатываемой ли­ нейным регистром сдвига.

В одном из возможных вариантов значение шага выборки меняется в соответствии с некоторой последовательностью периода /. В этом случае удается описать минимальные мно­ гочлены получаемых псевдослучайных последовательностей [Оо188].

Теорема	5. Пусть	— набор из		/ > 2 чисел
	/-1
множества	0,ф1—2 и В = ^	с^^ . Пусть при		г - к ' 1 - ^ г
	7=0
элементы последовательности V задаются формулой
		г-1
	(с0	^	),

где с — ненулевой, а в — примитивный элементы поля &Р(цп). Пусть, кроме того, простые делители числа I де-

277

Глава 9

■, но не делят (дп —1,0 ) . Пусть, наконец,

д - - \

лят

( Ф - Ю )

цп = 1 (тос14), если I кратно четырем. Тогда минимальный многочлен М у (х) последовательности V имеет вид М у (х) = Р(х(), где Р(х) — минимальный многочлен элемен­ та в ° .

			т
Д оказательство.	Пусть	Р(х) =	•	Тогда

5=0

Р(х*) = • Умножая последний многочлен на после-

5=0

довательность V и полагая г = к( + г , получаем:

№/ )у ](/)= № ')у ](^ + г)=

тт

=^ / А {+А =^ / А к(+г+ш)=

5=0	5=0
т
5=0
171		г-1
		с(,+зй
		/ л ^
= % Г , - « ( ( с в		г *	) =
5=0
	г-1
		т
= 1Г,‘1"	с в	( ] Г / 50 ’° ) = 0 .
		5=0

278

/юточные системы шифрования

Отсюда следует, что многочлен Р( х1) является характе­

ристическим для последовательности V . Кроме того, в усло­ виях теоремы, он является неприводимым. Это следует из свойств неприводимых многочленов над конечными полями

[Лид88]. Таким образом, Р( х1) является минимальным мно­

гочленом последовательности V , что и требовалось доказать.

Схемы с элементами памяти

Дополнительные возможности для усложнения ЛРП от­ крывает использование в криптографических алгоритмах эле­ ментов памяти.

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

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

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

279

Глава 9

Ро

1 *

1’

Р<- 1

Рис. 40

Пусть и и V — последовательности над полем Р , а вы­ ходная последовательность у вырабатывается с использова­

нием <7 ячеек памяти К0,...9КЧ_}. Если — заполнение у -й ячейки памяти перед началом / -го такта работы схемы, то преобразование информации в / -м такте описывается фор­ мулами

г(0 = Лу(/)(0 »

ГК , (/), если /' * у(/), [«(/), если ] = у(/>-

Таким образом, последовательность V определяет адреса, по которым в память записываются элементы последователь­ ности и.

Рассмотрим вопрос о периодах выходных последователь­ ностей генератора Макларена—Марсальи указанного типа.

Пусть последовательность и имеет период					г , а адресная
последовательность		V принимает значения			0Д,...,д--1 и
имеет	период	(.	Начальное	заполнение		памяти
/?о(0),...,Т?^_1(0) выбирается произвольно.
Пусть /0 — такое наименьшее натуральное число, что для
любого	к е {0,1,..., # - 1}		существует	/ е 0,^	такое, что

280