40
Положим
L i = z + y i , i=1,...m.
Пусть вероятность s(t,p) = s = P(y i = b i ) не зависит от 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 2 + (1-p) 2 .
Обозначим через B k события, состоящие в том, что k из m линейных форм L i равны 0. Тогда следующий вывод ”z = a” определяется апостериорной вероятностью
|
|
|
|
m |
|
|
|
|
|
|
|
|
|
|
|
psk (1− s)m−k |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
* |
|
|
|
P(z=a| B k ) = |
|
|
|
k |
|
|
= p |
. |
|
||
|
m |
m |
|
|
|||||||
|
|
|
|
|
|
|
|||||
|
|
|
psk (1 |
− s)m−k + |
(1- p)(1- s)k sm−k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
k |
k |
|
|
|
|
|
|||
Это апостериорная вероятность того, что z=a. Аналогично |
|
|
|
||||||||
|
|
|
m |
− s)k sm−k |
|
|
|
|
|
||
|
|
|
|
(1− p)(1 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
* |
|
P(z≠a| B k ) = |
|
|
k |
|
|
= 1-p |
. |
||||
m |
m |
|
|||||||||
|
|
|
|
|
|
||||||
|
|
psk (1− s)m−k + |
(1- p)(1- s)k sm−k |
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
||
|
k |
k |
|
|
|
|
|
||||
Идея состоит в том, что мы интуитивно ожидаем, что p * увеличивается по сравнению с р, если z = a и уменьшается, если z ≠ a. Поэтому найдем
математическое ожидание |
p * в двух случаях z = |
||||||
z = a |
|
|
|
|
|
|
|
E 0 ( p * ) = E(p * | z = a) = |
|
|
|
||||
m m |
psk |
(1− s)m−k |
sk (1 − s)m−k |
||||
= ∑ |
|
|
|
||||
psk (1 − s)m−k |
+ (1- p)(1- s)k sm−k |
||||||
k =0 k |
|
|
|
||||
Далее при z ≠ a |
|
|
|
|
|||
E1( p * ) = E(p * | z ≠ a) = |
− s)m−k sk |
|
|
|
|||
m m |
p(1 |
|
sm−k (1 |
|
|||
= ∑ |
|
|
|
|
− |
||
psk (1 − s)m−k + (1- p)(1- s)k sm−k |
|||||||
k =0 k |
|
|
|||||
При р= 3/4, t=2, m=20 получим
E 0 ( p * ) = 0,9, E1( p * ) = 0,3.
a и z≠a. При
.
s)k .
41
Осталось оценить число допустимых соотношений m как функции от длины регистра r и длины текста N. Пусть t-членное соотношение получено с использованием равенства
(С(х)) j = С(х j ), j = 2 i , i= 1,...,m.
Тогда длина задействованного участка при i=m равна r2 m . Таких соотношений N- r2 m >0. Тогда общее число соотношений равно
log2 |
N |
|
|
|
|
|
|
N |
|
|
log2 |
N |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
T = ∑r (N − 2m r) |
= N( log 2 |
+1) - |
∑r 2m r = |
|||||||||||||||||
r |
||||||||||||||||||||
m=0 |
|
|
|
|
|
|
|
|
|
N |
|
|
m=0 |
|||||||
|
|
|
|
|
N |
|
|
log2 |
+1 |
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
r |
|
|
|
|
|
|
|||||||
= N(log 2 |
|
|
|
|
|
+ 1) - (2 |
|
|
-1)r = |
|
|
|
|
|||||||
|
|
r |
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
= Nlog 2 |
|
N |
|
+ N - ( |
2N |
- 1)r = |
|
|
|
|
|
|
||||||||
|
|
r |
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
r |
|
|
|
|
|
|
|
|
|
|
|||||
= Nlog 2 |
N |
|
+ r - N. |
|
|
|
|
|
|
|
|
(1) |
||||||||
2r |
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Каждое соотношение (1) связано с t+1 знаками последовательности z. Поэтому среднее число m соотношений на один знак равно
m = |
T (t +1) |
= (log 2 |
N |
|
+ |
r |
- 1)(t+1). |
|||
N |
2r |
N |
||||||||
|
|
|
|
|
||||||
Для наших приложений |
|
r |
(t + 1) << 1. Отсюда из формулы (1) полу- |
|||||||
|
|
|||||||||
|
|
|
|
|
|
N |
|
|||
чим приближенное равенство m ≈ (t + 1) log 2 2Nr .
2.9. Линейный криптоанализ блочных шифров.
Линейный криптоанализ [Matsui 93] является атакой при известном открытом и шифрованном текстах на итеративные шифры типа DES, в которых “криптографически слабая” функция повторяется r раз. Предполагается, что открытый текст выбирается случайно и равновероятно, а подключи в каждом раунде независимы друг от друга.
Замечание 1. По-видимому, не имеет значения каким образом выбирается открытый текст.
42
Часто линейный криптоанализ является наиболее эффективным методом, тогда сложность линейного криптоанализа итеративных блочных шифров может являться мерой их слабости.
Линейный криптоанализ Мацуи r-раундового DES требует значительного числа открытых текстов. Это следует из следующей таблицы.
Количество ра- |
Количество известных открытых текстов |
|||||
ундов |
для нахождения ключа |
|
||||
8 |
221 |
|
|
|
|
|
12 |
233 |
|
|
|
→ Eurocrypt '93 |
|
|
|
|
||||
16 |
2 |
47 |
Crypto'94 |
43 |
|
|
|
→2 |
|
|
|
||
|
|
|
|
|
|
|
Сложность атаки связана с количеством необходимых известных открытых текстов, т.к. для любой пары (открытый текст, шифртекст) требуется небольшое количество вычислений для реализации алгоритма.
Например, атака на r=8 DES занимает 40 сек. на рабочей станции, а атака на r=12 DES занимает 50 час, что примерно в 4500 раз больше.
Эта атака может быть проведена, если имеется только шифртекст. Мацуи были получены следующие результаты:
•если известно, что открытый текст на английском языке, представленный в ASCII кодах, то при r=8 DES вскрывается при 2 29 известных шифртекстах;
•если открытый текст является случайным ASCII кодом, то при r=8
DES вскрывается при 237 известных шифртекстах.
Рассмотрим основную идею линейного криптоанализа. Пусть S – {0,1}
– случайная величина с P{S=1}=p. ∆(S) =|1−2 p | . |
|
|
Лемма 1. Если S(1 ) |
,K,S(n) - независимые бинарные случайные вели- |
|
чины, тогда |
n |
|
|
|
|
∆(S(1) K S(n) ) = ∏∆(S(i) ) . |
|
|
|
i=1 |
|
Д о к а з а т е л ь с т в о. В силу независимости S (1) |
и S (2) |
|
P(S(1) S(2) =1) = |
P(S (1) =1)P(S (2) =0) + P(S (1) =0)P(S (2) =1) = |
|
= p1+ p 2 - 2 p1 p 2 . |
|
|
Тогда |
|
|
∆(S (1) S (2) ) = 1 − 2 p(S(1) S(2) =1) = 1 − 2 p1 − 2 p2 |
+ 4 p1 p2 = |
|
43
= (1 − 2 p1 )(1 − 2 p2 ).= ∆(S (1) )∆ (S (2) ).
Утверждение леммы следует из-за ассоциативности операции :
S(1) (S(2) S(3) ) = (S(1) S(2) ) S(3) .
Заметим, что 0 ≤ ∆(S)≤ 1. При этом 0 = ∆(S) при р = 12 , а ∆(S)= 1 при
P(S=1) = 1 или P(S=0) = 1. |
|
|
|
||||
|
|
Рассмотрим схему произвольного итеративного блочного |
шифра |
в |
|||
i-ом раунде. |
|
|
|
|
|||
|
|
X (i) |
|
|
|
|
|
|
|
↓ |
|
|
|
|
|
|
|
|
← Kr(i) |
i=1, … , r. |
|
|
|
|
|
Е |
|
|
|
||
|
|
↓ |
|
|
|
|
|
|
|
Yr(i) |
|
|
|
|
|
|
|
Y (i) = E( X (i); K (i)) |
|
(1) |
|
||
|
|
Здесь Е – функция шифрования, X (i) - блок открытого текста в i-ом |
|||||
раунде, Yr(i) - блок шифртекста, K (i) - подключ, используемый в i-ом раун- |
|||||||
де. Yr(i) , Xr(i) Vn , Kr(i) Vm , n – размер блока, m – размер подключа. |
|
||||||
|
|
Обозначим |
через ( X ,αr) = X1α1 K X nαn = |
X i … Xi |
= |
||
|
|
|
|
|
1 |
k |
|
|
|
X[i1,…,i k ]- скалярное произведение двоичных векторов |
r |
и α , где |
|||
= |
|
X |
|||||
(αi |
,…,αi ) единичные координаты вектора α . |
|
|
|
|||
1 |
|
k |
|
|
|
|
|
Определение 1. Линейным статистическим аналогом нелинейной функции (1) будем называть случайную величину
S(i) = (Y (i),αr(i)) ( X (i), β(i)) (K (i),γr(i)), |
(2) |
если вероятность Р(S(i) = 1) = p ≠ 12 для случайно выбранного открытого текста Xr(i) .
Отклонение ∆(S(i)) =|1−2 p | определяет эффективность линейного статистического аналога (2).
Замечание 2. Массе [Massey 94] называет S(i) тройной суммой и предлагает обобщение линейного криптоанализа, рассматривая тройную сумму для i-гоrраунда какrслучайную величину S(i) вида
S(i) = fi ( X (i) ) gi (Y (i) ) hi ( K (i) ),
где fi ,gi ,hi - равновероятные булевы функции. В определении Мацуи fi ,gi ,hi - линейные функции.
Определение 2. Последовательные тройные суммы S(i+1) и S(i) называются связанными, если fi+1 = gi .