Участница:Александра/Метод встречи посередине: различия между версиями
Нет описания правки |
Нет описания правки |
||
| Строка 6: | Строка 6: | ||
| output_data = <math>n</math> | | output_data = <math>n</math> | ||
}} | }} | ||
Автор описания: [[Участник:Александра|А.В.Батарина]] | Автор описания: [[Участник:Александра|А.В.Батарина]] | ||
| Строка 15: | Строка 16: | ||
==== Усложнённые шифры ==== | ==== Усложнённые шифры ==== | ||
В качестве примера шифра, поддающегося атаке "встреча посередине" можно привести криптоалгоритм 2DES, являющийся модификацией шифра DES. В 2DES открытый текст шифруется дважды алгоритмом DES на двух разных 56-битных ключах. Однако из-за атаки "встреча посередине" сложность перебора двойного ключа (112 бит) шифра 2DES составляет <math>2^{57}</math> вместо ожидаемых <math>2^{112}</math>. | В качестве примера шифра, поддающегося атаке "встреча посередине" можно привести криптоалгоритм 2DES, являющийся модификацией шифра DES. В 2DES открытый текст шифруется дважды алгоритмом DES на двух разных 56-битных ключах. Однако из-за атаки "встреча посередине" сложность перебора двойного ключа (112 бит) шифра 2DES составляет <math>2^{57}</math> вместо ожидаемых <math>2^{112}</math>. | ||
=== Математическое описание алгоритма === | |||
Исходные данные: открытый текст <math>x</math>, шифртекст <math>y</math>. | |||
Шифрующее преобразование -- композиция двух преобразований <math>T_1(x,k_1)</math> и <math>T_2(x,k_2)</math>, где <math>k_1</math> и <math>k_2</math> - неизвестные ключи, т.е. <math>y=T_2(T_1(x,k_1),k_2)</math>. | |||
, | |||
Вычисляемые данные: | |||
Формулы метода: | |||
Версия от 07:03, 14 октября 2016
| Метод встречи посередине | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(\sqrt(n)\ln(n)) }[/math] |
| Объём выходных данных | [math]\displaystyle{ n }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ O() }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ O() }[/math] |
Автор описания: А.В.Батарина
Свойства и структура алгоритма
Общее описание алгоритма
Метод "Встреча посередине" криптоанализа блочных шифров был впервые предложен в 1977 году Уитфилдом Диффи и Мартином Хеллманом [1]. Встреча посередине используется для ускорения перебора ключей шифра за счёт увеличения требуемой памяти. Метод применим в случае каскадного построения сложного шифра из нескольких простых, другими словами, в случае последовательного применения шифрующих преобразований на разных ключах к блокам открытого текста.
Блочный шифр с ключевым расписанием
Усложнённые шифры
В качестве примера шифра, поддающегося атаке "встреча посередине" можно привести криптоалгоритм 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{ k_1 }[/math] и [math]\displaystyle{ k_2 }[/math] - неизвестные ключи, т.е. [math]\displaystyle{ y=T_2(T_1(x,k_1),k_2) }[/math]. , Вычисляемые данные:
Формулы метода:
Литература
<references \>
- ↑ (June 1977) «Exhaustive Cryptanalysis of the NBS Data Encryption Standard». Computer 10 (6): 74–84. DOI:10.1109/C-M.1977.217750