38

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

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

аn + a n−r + a n−r+k −1 = 0,	(2)
a n+r−k+1 + a n−k +1 + аn = 0,	(3)
a n+r + аn + a n+k −1 = 0,	(4)

Характеристический многочлен рекурренты равен

С(х) = 1 + x k −1+ x r .

Тогда справедливо следующее равенство:

i при j = 2 i (С(х)) j = С(х j ).

Отсюда мы можем получить новые трехчленные соотношения. Возможны другие производные соотношения, если в (2) вместо a n−r

подставить правую часть равенства:

a n−r = a n−2r + a n−2r+k −1 .

Или в (2) вместо a n−r+k −1 подставить правую часть равенства

a n−r+k−1= a n−2r+k−1 + a n−2r+2k−2 ,

и т.д. Таким образом, можно набрать m линейных соотношений относительно аn .

Согласно модели для любого n p = P(z n = аn ) > 0,5. Фиксируем аn и индекс n будем далее опускать. Для m линейных соотношений из рекур-

ренты, обозначив через b i , i=1,...,m, суммы слагаемых без аn ,	получим
следующую систему
a + b1 = 0
a + b 2 = 0	(5)
.................
a + b m = 0

Реально вместо а будем подставлять z n . Обозначим значение сумм z i c линейными формами на соответствующих местах в формуле (5) через yi .

Получим линейные формы
z + y1 = L1
z + y 2 = L 2	(6)
.................
z + y m = L m
Если z = a, y i = b i , то
L i = 0. i= 1,...,m.	(7)

39

При достаточно большом количестве m соотношений в (5) мы надеемся, что удастся статистически различить случаи z = a от z ≠ a. Если статистически эти случаи различаются, то среди большого числа z n найдутся

такие, для которых такое статистическое обоснование z = a будет хорошо заметно. Тогда выразим все аn , соответствующие таким случаям (z = a)

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

система не решается, то надо опробовать малое число уравнений с неправильно определенной правой частью. Решая такие системы, находим ключ.

2.8. Статистические модели.

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

A = {a, b ij , i=1,...,m, j=1,...,t},

удовлетворяющих системе уравнений:

t

a + ∑bij = 0, i=1,...m.

j=1

Замечание 1. В модели, рассмотренной в п. 2.6, t=2. Аналогично рассмотрим набор случайных величин

Z = {z, y ij , i=1,...,m, j=1,...,t}.

Эти случайные величины представляют z n . Два набора связаны следую-

щим соотношениями

P(z=a) = p, P(b ij = y ij ) = p.

Замечание 2. Такие соотношения можно получить следующим образом. Так, например, в модели (2)

z = a + γ,

y ij = b ij + γij ,

где γ - независимые, одинаково распределенные случайные величины с

P(γ = 0) = p.

Обозначим

	t
b i =	∑bij , i=1,...m,
	j=1
	t
yi =	∑ yij , i=1,...m.
	j=1