Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 20: Строка 20:
  
 
Исходные данные: открытый текст <math>x</math>, шифртекст <math>y</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>.
+
 
,
+
Алгоритм зашифрования -- композиция двух преобразований <math>T_1(x,k_1)</math> и <math>T_2(x,k_2)</math>, т.е. <math>y=T_2(T_1(x,k_1),k_2)</math>.
Вычисляемые данные:  
+
 
 +
Алгоритм расшифрования -- <math>x=T_1^{-1}(T_2^{-1}(x,k_2),k_1)</math>
 +
 
 +
Вычисляемые данные: ключи шифрования <math>k_1 \in K_1</math>
  
 
Формулы метода:
 
Формулы метода:

Версия 10:09, 14 октября 2016


Метод встречи посередине
Последовательный алгоритм
Последовательная сложность [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.2 Усложнённые шифры

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

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

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

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

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

Вычисляемые данные: ключи шифрования [math]k_1 \in K_1[/math]

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


2 Литература

<references \>

  1. (June 1977) «Exhaustive Cryptanalysis of the NBS Data Encryption Standard». Computer 10 (6): 74–84. DOI:10.1109/C-M.1977.217750