Участница:Александра/Метод встречи посередине
| Метод встречи посередине | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]O(\sqrt(n)\ln(n))[/math] |
| Объём выходных данных | [math]n[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]O()[/math] |
| Ширина ярусно-параллельной формы | [math]O()[/math] |
Автор описания: А.В.Батарина
Содержание
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Метод "Встреча посередине" криптоанализа блочных шифров был впервые предложен в 1977 году Уитфилдом Диффи и Мартином Хеллманом [1]. Встреча посередине используется для ускорения перебора ключей шифра за счёт увеличения требуемой памяти. Метод применим в случае каскадного построения сложного шифра из нескольких простых, другими словами, в случае последовательного применения шифрующих преобразований на разных ключах к блокам открытого текста.
1.1.1 Наиболее частые случаи использования
1.1.1.1 Блочный шифр с ключевым расписанием
1.1.1.2 Усложнённые шифры
В качестве примера шифра, поддающегося атаке "встреча посередине" можно привести криптоалгоритм 2DES, являющийся модификацией шифра DES. В 2DES открытый текст шифруется дважды алгоритмом DES на двух разных 56-битных ключах. Однако из-за атаки "встреча посередине" сложность перебора двойного ключа (112 бит) шифра 2DES составляет [math]2^57[/math] вместо ожидаемых [math]2^112[/math].
2 Литература
<references \>
- ↑ (June 1977) «Exhaustive Cryptanalysis of the NBS Data Encryption Standard». Computer 10 (6): 74–84. DOI:10.1109/C-M.1977.217750
