40 Глава 3. ТЕСТИРОВАНИЕ УЗЛОВ КРИПТОСХЕМ КАК МЕТОД КОМПРОМЕТАЦИИ ШИФРОВ

равно нулю с вероятностью 15/16, поэтому его присутствие может быть незаметным на фоне искажений, вносимых в рекурренту битами открытого текста.

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

3.3. Задача восстановления параметров искаженной линейной рекурренты

Задачи восстановления точек съема обратной связи и начального заполнения РСЛОС являются реальными задачами практической криптографии. Хотя они изучались многими авторами, для больших длин регистров, в общем случае, практически приемлемого решения не найдено.

3.3.1. Представление элементов рекурренты через элементы начального заполнения

Для рассмотрения некоторой качественной характеристики различия и связи указанных задач опишем работу РСЛОС в матричных обозначениях.

Пусть R(s) - рекуррентная последовательность, генерируемая РСЛОС с начальным заполнением s0 = (a0 ,K,an−1 ).

Последовательность R(s) удобно рассматривать в виде последовательности s0, s1,… состояний регистра, т.е. последовательности векторов.

Введем матрицу:

	0 0	K 0	b
			0
1 0 K 0			b1
A = K K K					, b {0,1}, b =1.
		1 K bn−2			i	0
0 0
	0 0	K 1 b
			n−1

Тестирование линейной рекуррентной составляющей криптоузла 41

Очевидно, матрица A обратима и

s0 A = (a0 ,K,an−1 ) A = (a1,K,an−1 , nj−=10 a jbj ).

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

соотношение sk A =sk+1 ,	поэтому		s0Ak = sk , (k = 0,1,2K). Отсюда следует,
что если s0 = s(01) s0(2),	то	R(s0 )= R(s0(1)) R(s0(2)) (последовательности
суммируются поэлементно).
Пусть ei (i = 0,1,Kn −1)		- строки единичной матрицы порядка n. Из
предыдущего следует, что R(s0 )= a0R(e0 ) a1R(e1 ) K an−1R(en−1 ).
Подписав последовательности			R(ei ) друг под другом, мы получим

матрицу M = (h0 ,h1,K), состоящую из n строк и бесконечного числа столбцов hk . Легко видеть, что последовательность h0 ,h1,K является рекуррентой,

удовлетворяющей тому же соотношению, что и R(s0 ). Начальным заполнением является последовательность столбцов (h0 ,h1,K,hn−1 ). По построению эти столбцы являются столбцами единичной матрицы, таким образом, мы всегда можем вычислить любой из векторов hk .

В терминах столбцов матрицы M элемент ak последовательности R(s0 )

равен a = n−1 a			h(k ), где h(k ) - координаты вектора h						k	. Если мы рассмотрим
k	j=0	j	j			j
выражение	n−1	a		h(k )		как функцию от	a ,a ,K,a	n−1	с коэффициентами		h(k )
	j=0		j		j		0 1				j
и обозначим ее s,hk					, то ak = s0 ,hk , ,		(k = 0,1,2K).
Номера координат вектора hk , равные единице, указывают, какие
компоненты вектора s0						участвовали в выражении ak		= s0 ,hk , .

42 Глава 3. ТЕСТИРОВАНИЕ УЗЛОВ КРИПТОСХЕМ КАК МЕТОД КОМПРОМЕТАЦИИ ШИФРОВ

Таким образом, мы можем сказать суммой каких элементов начального

заполнения является любой элемент ak рекуррентной последовательности

R(s0 ).

3.3.2. Производные соотношения

Вспомним, что s0Ak =sk . Строки e0Ak = e(0k ), …, en−1Ak =en(k−)1 , образуют некоторую квадратную подматрицу Hk матрицы M . Столбцами этой

подматрицы	являются	вектора (hk ,,K,hn+k−1 ).		С	другой	стороны,
Hk = EnAk ,	где матрица	En образована	строками	ei и	поэтому	является
единичной.
Поскольку матрица		A обратима, то	для всех	целых	k Hk = Ak , т.е.
AHk = Hk+1 .

В матрице M последний столбец матрицы Hk+1 следует за последним столбцом матрицы Hk . Поэтому соседние столбцы в матрице M связаны

соотношением Ahk = hk+1 .
Воспользуемся тем, что, по условию,				R(s0 )	- рекуррента максимального
периода. Из	теории матриц		известно,	что	в этом случае полином
f (x)= xn b	xn−1 K b x b , связанный с матрицей A , обладает важными
n−1	1	0
свойствами [24].
Прежде всего, он является полиномом минимальной степени,
аннулирующим A : f (A)= 0 .			Этот полином делит любой другой полином,

аннулирующий матрицу A . Фактически, соотношение f (A)= 0 является иной формой записи рекуррентного закона для столбцов матрицы M .

Далее. Полином f (x) является неприводимым полиномом, более того, он

является примитивным. В контексте нашей тематики последнее означает, что

f (x)

{Akh0}

(k = 0,1,2K)

Тестирование линейной рекуррентной составляющей криптоузла 43

если h0 ≠ 0 , то множество векторов однократно содержит все ненулевые вектора соответствующего линейного пространства,

т.е. пространства V2n . Следовательно, матрица M содержит все ненулевые

вектора из V2n .

Заметим, что поскольку двойка и ноль сравнимы по модулю два, то в полиноме f 2 (x), отсутствуют удвоенные произведения. Полиному f 2 (x)

можно сопоставить матрицу размерности 2n, аналогичную матрице A.

Поскольку f 2 (x) делится на f (x), то можно сделать вывод, что последовательность R(s0 ) удовлетворяет еще одному рекуррентному соотношению, даже с тем же числом слагаемых, что и исходное. В общем случае, любые подобные соотношения называются производными. Они соответствуют полиномам вида f (x)g(x).

Покажем, что существуют производные трехчленные соотношения. Выберем из M два неравных столбца h0 и hm . Их сумма является столбцом в

матрице M :	h0 hm =hd .	Поэтому	равенство сохранится при умножении
слева на матрицу A. Таким образом,			для любого начального заполнения s,
получим:	s,h0 s,hm = s,hd . Следовательно, для рекурренты R(s)
выполняется	трехчленное	соотношение ai am+i = ad +i , (i = 0,1,2K).

Заметим, что, как правило, d чрезвычайно велико.

3.3.3. Некоторые сведения о подходах к восстановлению параметров искаженной линейной рекурренты

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

восстановления номеров точек съема и начального заполнения решаются достаточно эффективно при реальных значениях параметров рекурренты.

44 Глава 3. ТЕСТИРОВАНИЕ УЗЛОВ КРИПТОСХЕМ КАК МЕТОД КОМПРОМЕТАЦИИ ШИФРОВ

Основными параметрами, влияющими на эффективность решения указанных задач, являются абсолютная величина отклонения вероятности искажения рекурренты от 1/2 и количество членов в рекуррентном соотношении.

При приближении вероятности искажения к 1/2 требуется все большее

количество знаков искаженной рекурренты для ее восстановления.
Для	истинной	рекурренты		биты	с	номерами
0 +i,k1 +i,k2 +i,K,kr		+i,n +i в сумме		дают	ноль для	любого i.
Соотношение	ai ak +i K ak		+i ai+n	= 0 , а также любое производное
	1	r

соотношение, которому удовлетворяет рекуррента, называется также проверкой четности или проверочным соотношением.

Для искаженной рекурренты c0 ,c1,K проверочное соотношение не для

всех значений i равняется нулю, поскольку	последовательность искажений
u0 ,u1,K ненулевая.
Вместе с тем, для последовательности	{ci }={ai ui }		проверочное
соотношение дает значения ui uk +i K uk		+i un+i = ri ,	которые не
1	r

зависят от рекурренты.

Это позволяет составлять системы искаженных уравнений и использовать вероятностные оценки относительно ui .

Очевидно, чем больше членов в вероятностном соотношении, тем ближе вероятности величин ri к 1/2. Поэтому многие методы восстановления искаженной рекурренты используют, так или иначе, проверочные соотношения с минимально возможным количеством слагаемых [33].

Например, при не очень большой вероятности искажений можно оценить вероятность искажения бита ck , рассматривая проверочные соотношения: