Участница:Александра/Метод встречи посередине: различия между версиями
| Строка 21: | Строка 21: | ||
Исходные данные: открытый текст <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>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>, <math>k_2 \in K_2</math>, где <math>K_1, K_2</math> | Вычисляемые данные: ключи шифрования <math>k_1 \in K_1</math>, <math>k_2 \in K_2</math>, где <math>K_1, K_2</math> — множества возможных ключей. | ||
Трудоёмкость полного перебора всех возможных пар <math>k_1,k_2</math> составляет в среднем <math>\frac{|K_1||K_2|}{2}</math>. Однако используя дополнительную память, можно сократить перебор. | Трудоёмкость полного перебора всех возможных пар <math>k_1,k_2</math> составляет в среднем <math>\frac{|K_1||K_2|}{2}</math>. Однако используя дополнительную память, можно сократить перебор. | ||
Версия от 09:14, 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{ 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_1^' &=T_2^{-1}(x,k_2^1)\\\\ z_2 & =T_1(x,k_1^2) & z_2^' & =T_2^{-1}(x,k_2^2)\\ ... & ................. & ... & .................... \\ z_{|K_1|} & =T_1(x,k_1^{|K_1|}) & z_{|K_1|}^' & =T_2^{-1}(x,k_2^{|K_1|}) \end{align} }[/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|)\log(|K_1|+|K_2|) }[/math] (например, при использовании сортировки слиянием). Значения [math]\displaystyle{ i,j }[/math], при которых [math]\displaystyle{ z_i=z_j^' }[/math] однозначно определяют искомую пару ключей [math]\displaystyle{ k_1=k_1^i,k_2=k_2^j }[/math]. Для нахождения такой пары достаточно просмотреть отсортированную таблицу один раз.
Далее таблица сортируется по значениям [math]\displaystyle{ z_i }[/math], сложность сортировки составит [math]\displaystyle{ O(|K_1|\log(|K_1|)) }[/math]
Литература
<references \>
- ↑ (June 1977) «Exhaustive Cryptanalysis of the NBS Data Encryption Standard». Computer 10 (6): 74–84. DOI:10.1109/C-M.1977.217750