Нахождение статистических аналогов для трех циклов алгоритма DES
Матсуи не описывал алгоритма получения эффективных линейных аналогов для алгоритма DES, состоящего из r циклов, но из финальных результатов можно предположить, что основная идея состоит в следующем: использовать связанные тройные суммы с наибольшим D.
Прежде чем пояснить вышесказанное на примере, рассмотрим несколько базовых определений:
Лемма 1. Если S(1),…, S(n) – независимые бинарные случайные величины, тогда
D(S(1)Å… ÅS(n)) = ПD(S(i)), (9)
где i=1,…, n.
Доказательство.Так как S(1) и S(2) независимы и при этом Р(S(1)=1)=р1, Р(S(2)=1)=р2, Р(S(1)=0)=1– р1 и Р(S(2)=0)=1 – р2. Тогда:
Р(S(1)ÅS(2) = 1) = Р(S(1)=1)Р(S(2)=0) + Р(S(1)=0)Р(S(2)=1) = р2(1 – р1) + р1(1 – р2) = р2 – р1р2 + р1 – р1р2 = р2 + р1 – 2р1р2.
D(S(1)ÅS(2)) = 1 – 2р(S(1)ÅS(2) =1) = 1 – 2(р2 + р1 – 2р1р2) = 1 – 2р2 – 2р1 + 4р1р2 = (1 – 2р1)( 1 – 2р2) = D(S(1))D( S(2)).
Замечание 1. Массе называл тройной суммой S(i) для i-го раунда случайную величину вида
S(i) = fi (X(i)) Å gi (Y(i)) Å hi (K(i)), (10)
где fi, gi, hi – равновероятностные булевы функции.
В определении Матсуи fi, gi, hi – линейные функции.
Определение 2. Последовательные тройные суммы S(1+i) и S(i) называются связанными, если fi+1 = gi.
Из определения следует, что S(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. Если S(1),…, S(n) – связанные тройные суммы, то тогда S1… n = S(1)Å… ÅS(n) = f1 (X(1)) Å gn (Y(n)) Å 
, (11)
и S1… n называется n-раундовой тройной суммой.
В случае линейных функций формула (11) дает линейное соотношение
S1… n =(X(1), a) Å (Y(n), b) Å 
, (12)
которое выполняется с вероятностью, определяемой D(S(1)Å… ÅS(n)) и леммой 1.
Определение 4. Эффективным линейным статистическим аналогом называется линейный статистический аналог (12) из заданного множества с наибольшим D.
 |
Поясним все вышесказанное на примере. Для этого рассмотрим схему 3-раундового DES (см рис. 3.1).
Эффективными линейными статистическими аналогами 1-ой и третьей итераций являются уравнения
X(1)17 Å Y(1)2 Å Y(1)8 Å Y(1)24 Å Y(1)14 = K(1)26,
X(3)17 Å Y(3)2 Å Y(3)8 Å Y(3)24 Å Y(3)14 = K(3)26,
каждое из которых выполняется с вероятностью 3/16.
Учитывая, что Х(1) = PR, X(3) = CL, Y(1) = PL Å X(2), Y(3) = CR Å X(2), после сложения этих уравнений получим
(PR Å CL) 17 Å (PL Å CR) 2 Å (PL Å CR) 8 Å (PL Å CR) 24 Å (PL Å CR) 14 = (К(1) Å К(3)) 26. (13)
По лемме 1 D = (5/8)*(5/8) = 25/64 и это уравнение выполняется с вероятностью р = (1 – D)/2 = 39/128.
Найти биты ключа К(1) Å К(3) можно, решая уравнение (13) с использованием следующего алгоритма.
Алгоритм. Пусть N – число всех открытых текстов и Т – число открытых текстов, для которых левая часть (13) равна 0.
Если Т> N/2, то
К(1) Å К(3) =
Если Т< N/2, то
К(1) Å К(3) =
Успех алгоритма возрастает с ростом N и D = |1 – 2p|. Вероятность успеха определяется следующей леммой.
Лемма 2. Пусть N – число открытых текстов и р – вероятность выполнения линейного уравнения (2). Предположим, что D = |1 – 2p| ® 0. Тогда вероятность успеха алгоритма имеет вид
Р ® 
,
Где
. (14)
Числовые вычисления (14) сведены в таблице 3.5.
Таблица 3.5
| N | 1/16 D2 | 1/8D2 | 1/4D2 | 1/2D2 |
| Pусп | 0,841 | 0,921 | 0,977 | 0,998 |
Аналогичным образом можно строить уравнения нахождения битов ключа и для большего количества циклов. Самое главное при этом вывести такие уравнения, левые части которых нам известны.