Участница:Александра/Метод встречи посередине

Метод встречи посередине
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(\sqrt(n)\ln(n)) }[/math]
Объём выходных данных	[math]\displaystyle{ n }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ O() }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ O() }[/math]

Автор описания: А.В.Батарина

Свойства и структура алгоритма

Общее описание алгоритма

Метод "Встреча посередине" криптоанализа блочных шифров был впервые предложен в 1977 году Уитфилдом Диффи и Мартином Хеллманом . Встреча посередине используется для ускорения перебора ключей шифра за счёт увеличения требуемой памяти. Метод применим в случае каскадного построения сложного шифра из нескольких простых, другими словами, в случае последовательного применения шифрующих преобразований на разных ключах к блокам открытого текста.

Усложнённые шифры

В качестве примера шифра, поддающегося атаке "встреча посередине" можно привести криптоалгоритм 2DES, являющийся модификацией шифра DES. В 2DES открытый текст шифруется дважды алгоритмом DES на двух разных 56-битных ключах. Однако из-за атаки "встреча посередине" сложность перебора двойного ключа (112 бит) шифра 2DES составляет [math]\displaystyle{ 2^{57} }[/math] вместо ожидаемых [math]\displaystyle{ 2^{112} }[/math].

Математическое описание алгоритма

Исходные данные: открытый текст [math]\displaystyle{ x }[/math], шифртекст [math]\displaystyle{ y }[/math].

Алгоритм зашифрования -- композиция двух преобразований [math]\displaystyle{ T_1(x,k_1) }[/math] и [math]\displaystyle{ T_2(x,k_2) }[/math], т.е. [math]\displaystyle{ y=T_2(T_1(x,k_1),k_2) }[/math].

Алгоритм расшифрования -- [math]\displaystyle{ x=T_1^{-1}(T_2^{-1}(x,k_2),k_1) }[/math]

Вычисляемые данные: ключи шифрования [math]\displaystyle{ k_1 \in K_1 }[/math], [math]\displaystyle{ k_2 \in K_2 }[/math], где [math]\displaystyle{ K_1, K_2 }[/math] -- множества возможных ключей.

Трудоёмкость полного перебора всех возможных пар [math]\displaystyle{ k_1,k_2 }[/math] составляет в среднем [math]\displaystyle{ \frac{|K_1||K_2|}{2} }[/math]. Однако используя дополнительную память, можно сократить перебор.

Предположим, что открытый текст [math]\displaystyle{ x }[/math] и шифртекст [math]\displaystyle{ y }[/math] однозначно определяют ключи [math]\displaystyle{ k_1,k_2 }[/math]. Составим следующую таблицу:

[math]\displaystyle{ \begin{align} z_1=T_1(x,k_1^1) \\ z_2=T_1(x,k_1^2) \\ ............................\\ z_{|K_1|}=T_1(x,k_1^{|K_1|}) \end{align} }[/math]

Сложность вычисления составит [math]\displaystyle{ |K_1| }[/math] операций опробования.

Литература

<references \>