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