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

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

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

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

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

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

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

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

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

Исходные данные: открытый текст $x$, шифртекст $y$. Шифрующее преобразование -- композиция двух преобразований $T_1(x,k_1)$ и $T_2(x,k_2)$, где $k_1$ и $k_2$ - неизвестные ключи, т.е. $y=T_2(T_1(x,k_1),k_2)$. , Вычисляемые данные:

Формулы метода:

2 Литература

<references \>