Изучение современных методов криптоанализа. Бабенко Л.К - 27 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

27
где f
i
, g
i
, h
i
– равновероятностные булевы функции.
В определении Матсуи f
i
, g
i
, h
i
– линейные функции.
Определение 2. Последовательные тройные суммы S
(1+i)
и S
(i)
называ-
ются связанными, если f
i+1
= g
i
.
Из определения следует, что Q(i) ⊕ S(1+i) = fi (X(i)) ⊕ gi (Y(i)) ⊕ hi
(K(i)) ⊕ fi+1 (X(i+1)) ⊕ gi+1 (Y(i+1)) ⊕ bi+1 (K(i+1)),
где Y(i) = X(i+1).
Определение 3. Если Q
(1)
,…, Q
(n)
– связанные тройные суммы, то тогда
Q
= Q ⊕… ⊕Q = f (X ) ⊕ g (Y ) ⊕
))((
∑
n
iK
,
i
h
1… n (1) (n) 1 (1) n (n)
1=i
называется n-раундовой тройной суммой.
(11)
и Q
1… n
формула (11) линей
В случае линейных функций дает ное соотношение
Q
1… n
=(X(1), α) ⊕ (Y(n), β) ⊕
))(,)((
1
iiK
(12)
кото
n
i
γ
∑
=
,
рое выполняется с вероятностью, определяемой ∆(Q
(1)
⊕… ⊕Q
(n)
) и лем-
мой 1.
Определение 4. Эффективным линейным статистическим аналогом на-
зывается линейный статистический аналог (12) из заданного множества с
наибольшим ∆.
Поясним все вышесказанное на примере. Для этого рассмотрим схему
3-раундового DES (рис. 3.1).
линейнымиЭффективными статистическими ана
й являются уравнения
логами 1-й и 3-й ите-
раци
1)
(13)
X(1)
17
⊕ Y(1)
3
⊕ Y(1)
8
⊕ Y(1)
14
⊕ Y(1)
25
= K(1)
26
,
Y(
X(3)
17
⊕ Y(3)
3
⊕ Y(3)
8
⊕ Y(3)
14
⊕ 3)
25
= K(3)
26
,
каждое из которых выполняется с вероятностью 3/16.
, что
, X
Учитывая Х(1) = P
R
(3) = C
L
, Y( = P
L
⊕ X(2), Y(3) = C
R
⊕ X(2),
после сложения этих уравнений получим
(P
⊕ C ) ⊕ (P ⊕ C ) ⊕ (P ⊕ C ) ⊕ (P ⊕ C ) ⊕ (P ⊕ C ) =
R L 17 L R 3 L R 8 L R 14 L R 25
(К(1) ⊕ К(3))
26
.
По лемме 1 ∆ = (5/8)*(5/8) = 25/64 и это уравнение выполняется с веро-
ятностью р = (1 – ∆)/2 = 39/128.
Найти биты ключа К(1) ⊕ К(3) можно, решая уравнение (13) с исполь-
зованием следующего алгоритма.
Алгоритм. Пуст
екстов, для кото
ь N – число всех открытых текстов и Т – число откры-
тых рых левая часть (13) равна 0.
сли Т> N/2, то
т
Е

Страницы