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

ck ck +k K ck			+k cn+k = rk ,
	1	r
ck −k	ck K ck		+k −k	cn+k −k	= rk −k
1		r	1	1	1

и т.д., где «шаблон» для выбора битов сдвигается на соответствующие значения

ki влево, пока обозначение	cn+k в	шаблоне не окажется	левее бита,
первоначально обозначенного как ck .
По построению этот бит	входит	во все рассмотренные	проверочные

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

Исходя из вероятностей искажений, можно заранее рассчитать вероятности ri , в предположении, что uk =1 и проверить, согласуются ли полученные значения с распределением {ui }.

По крайней мере, часть битов рекурренты может быть восстановлена.

Заметим, что этого может оказаться достаточно для восстановления всей рекурренты. Например, n подряд идущих битов позволяют развернуть рекурренту на нужное число шагов назад и определить начальное заполнение.

Тем же свойством обладают любые n битов, расположенные на местах, где соответствующие вектора hi линейно независимы.

Аналогично можно использовать проверки на четность для отбраковки вариантов при поиске точек съема обратной связи [10].

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

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

Пусть отрезку c0,c1,K, cN−1	искаженной рекурренты длины N при
истинных значениях точек съема	и истинном начальном заполнении

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

соответствует	последовательность искажений, содержащая N− единиц и
N+ = N − N−	нулей.	Пусть z = (z0 , z1,K, zn−1 ) - искомое начальное
заполнение и	N+ ≥ N− .	Рассмотрим предполагаемый вариант набора точек
съема.

Обозначим отрезок рекурренты R(z), соответствующий последовательности c0 ,c1,K, cN −1 через t0 ,t1,K,tN −1 . Искажения имеют вид uk = ck tk .

Преобразуем теперь значения битов с помощью преобразования

(гомоморфизма) T : T (0)=1, T (1)= −1. Легко проверить, что сумма битов по модулю два перейдет при этом в обычное умножение: T(x y)=T(x)T(y).

Обозначим T(x) через xˆ .

Нам не известно начальное заполнение, однако мы знаем вектора hk .
Поскольку tk = z,hk , то мы можем выразить tk через						z0 , z1,K, zn−1		в
виде суммы по модулю два,		скажем gk (z).		Из свойств преобразования				T
следует, что	uˆk = cˆk gˆk (z),	где	gˆk (z) -	произведение		переменных		из
z0 , z1,K, zn−1 , номера которых известны, а cˆk = ±1.
Таким	образом,	мы	можем		образовать		полином
	N −1
P(z0 , z1,K, zn−1 )= ∑cˆk gˆk (z0 , z1,K, zn−1 ).
	k =0
Рассмотрим уравнение P(z)= B , где B -					целое число от нуля до N,			а
переменные	удовлетворяют	ограничениям		zi = ±1. Предположим, мы				в

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

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

N −1

Однако P(z)= ∑uˆk (z), т.е. B = P(z)= N+ − N− , откуда мы получаем

k =0

оптимальное для данного набора точек съема значение N− , т.к. N+ + N−

известно и равно N.

Таким образом, определение точек съема обратной связи РСЛОС сводится к вопросу разрешимости уравнения P(z)= B , zi = ±1, а нахождение начального заполнения регистра – к поиску самих решений.