girniy.ru 1




Тогда

= .

Отсюда

E = = = .

При n = 2 E 10, что дает мало шансов ожидать перекрытия даже при очень большой интенсивности переписки.

Если А - случайное отображение (не взаимно-однозначное) и - длина цикла, а h - длина подхода, то тогда h ~ , ~ и h+ ~ . Следовательно, при n = 2 h+ ~ 2~ 10, что является не очень большой величиной и можно ожидать перекрытия гаммы.


2.7. Корреляционные атаки на поточные шифры.

Чаще всего цель статистических методов криптоанализа [Meier 89] состоит в том, чтобы построить критерий Н, необходимый для применения метода “разделяй и побеждай”. Оказывается, что большинство поточных шифров дают возможность применять против них корреляционные методы атак. Идея метода состоит в том, чтобы заменить исходное преобразование в шифре другим, зависящим от части ключа, что открывает возможность применения метода “разделяй и побеждай” или аналитических методов. В последнем случае часто стремятся свести задачу криптоанализа к решению системы линейных уравнений. Замена одного преобразования другим осуществляется так, чтобы сохранялась корреляционная связь с известной последовательностью знаков шифра, полученной при настоящем преобразовании. Тогда при опробовании части ключа эта статистическая связь дает критерий Н для определения правильного варианта опробоваемой части ключа. Если происходит сведение к линейной системе уравнений, то указанная статистическая связь позволяет построить линейную систему относительно элементов ключа.


Пример 1. Рассмотрим генератор поточного шифра [Meier 89], в котором имеется известная двучленная линейная рекуррентная последовательность, усложненная некоторой булевой функцией f (неравновероятной), как это представлено на рис. 1.







a a a a






f




a



x z y



Рис.1



a = a + a , 1 k r, i = 1, 2, …. (1)


Мы считаем, что известна последовательность z = (z,…,z) длины N. Таким образом, задача будет решаться в предположении, что известны открытые и шифрованные тексты. Выходная последовательность линейного регистра будет обозначаться а
= (a,…,a). Неизвестным ключом является начальное заполнение регистра, которое выбирается случайно и равновероятно.

Для целей криптоанализа примем следующую модель схемы 1.







a a a a

a



z

Рис. 2

Здесь = (,…,) - последовательность независимых одинаково распределенных {0, 1} случайных величин с вероятностью 0, равной р. Соответствие вероятностной модели на рис. 2 детерминированному автомату рис. 1 может быть оправдана, если нам удастся найти начальное заполнение регистра. Поэтому мы и далее будем строить грубые вероятностные модели, оправдывая сделанные допущения достижимостью конечной цели. Если ключ определить не удается, то это может произойти из-за ошибки статистического критерия, или неадекватности модели. В любом случае криптоанализ надо начинать заново.


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

а + a+ a = 0, (2)

a + a+ а = 0, (3)

a+ а + a = 0, (4)

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

С(х) = 1 + x+ x.

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

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

Отсюда мы можем получить новые трехчленные соотношения.

Возможны другие производные соотношения, если в (2) вместо a

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

a= a+ a.

Или в (2) вместо a подставить правую часть равенства

a = a + a ,

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


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

a + b = 0

a + b = 0 (5)

.................

a + b = 0

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

z + y = L

z + y = L (6)

.................

z + y = L

Если z = a, y = b, то

L = 0. i= 1,...,m. (7)

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



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


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

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

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

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

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

Аналогично рассмотрим набор случайных величин

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

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

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

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

z = a + ,

y = b+ ,

где - независимые, одинаково распределенные случайные величины с
P( = 0) = p.

Обозначим

b = , i=1,...m,

y = , i=1,...m.

Положим

L = z + y, i=1,...m.


Пусть вероятность s(t,p) = s = P(y= b) не зависит от i. По формуле полной вероятности получим рекурренту

s(t,p) = ps(t-1,p) + (1-p)(1- s(t-1,p)),

s(1,p) = p.

Замечание 3. Для t=2 s(2,p) = p+ (1-p).

Обозначим через B события, состоящие в том, что k из m линейных форм L равны 0. Тогда следующий вывод ”z = a” определяется апостериорной вероятностью

P(z=a B) = = p.

Это апостериорная вероятность того, что z=a. Аналогично

P(za B) = = 1-p.

Идея состоит в том, что мы интуитивно ожидаем, что p увеличивается по сравнению с р, если z = a и уменьшается, если z a. Поэтому найдем математическое ожидание p в двух случаях z = a и za. При
z = a

E( p) = E(p z = a) =

= .


Далее при z a

E( p) = E(p z a) =

= .

При р= 3/4, t=2, m=20 получим

E( p) = 0,9,

E( p) = 0,3.

Осталось оценить число допустимых соотношений m как функции от длины регистра r и длины текста N. Пусть t-членное соотношение получено с использованием равенства

(С(х)) = С(х), j = 2, i= 1,...,m.

Тогда длина задействованного участка при i=m равна r2. Таких соотношений N- r2>0. Тогда общее число соотношений равно

T = = N( log +1) - =

= N(log + 1) - (2-1)r =

= Nlog + N - ( - 1)r =


= Nlog + r - N. (1)

Каждое соотношение (1) связано с t+1 знаками последовательности z. Поэтому среднее число m соотношений на один знак равно

m = = (log +- 1)(t+1).

Для наших приложений (t + 1) << 1. Отсюда из формулы (1) получим приближенное равенство

m (t + 1) log.


2.9. Линейный криптоанализ блочных шифров.


Линейный криптоанализ [Matsui 93] является атакой при известном открытом и шифрованном текстах на итеративные шифры типа DES, в которых “криптографически слабая” функция повторяется r раз. Предполагается, что открытый текст выбирается случайно и равновероятно, а подключи в каждом раунде независимы друг от друга.

Замечание 1. По-видимому, не имеет значения каким образом выбирается открытый текст.