Участница:Александра/Метод встречи посередине: различия между версиями
| Строка 29: | Строка 29: | ||
Трудоёмкость полного перебора всех возможных пар <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>. Однако используя дополнительную память, можно сократить перебор. | ||
| − | Предположим, что открытый текст <math>x</math> и шифртекст <math>y</math> однозначно определяют ключи <math>k_1,k_2</math>. Составим | + | Предположим, что открытый текст <math>x</math> и шифртекст <math>y</math> однозначно определяют ключи <math>k_1,k_2</math>. Составим две таблицы: |
<math> | <math> | ||
| Строка 40: | Строка 40: | ||
</math> | </math> | ||
| − | Сложность вычисления составит <math>|K_1|</math> операций опробования. Далее таблица сортируется по значениям <math>z_i</math>, сложность сортировки составит | + | И |
| + | |||
| + | <math> | ||
| + | \begin{align} | ||
| + | & z_1^'=T_2^{-1}(x,k_2^1)\\ | ||
| + | & z_2^'=T_2^{-1}(x,k_2^2)\\ | ||
| + | &...................\\ | ||
| + | & z_{|K_1|}^'=T_2^{-1}(x,k_2^{|K_1|}) | ||
| + | \end{align} | ||
| + | </math> | ||
| + | |||
| + | Для всех <math>k_1 \in K_1</math>, <math>k_2 \in K_2</math>. | ||
| + | Сложность вычисления составит <math>|K_1|+|K_2|</math> операций опробования. | ||
| + | |||
| + | Далее таблица сортируется по значениям <math>z_i</math>, сложность сортировки составит <math>O(|K_1|\log(|K_1|))</math> | ||
== Литература == | == Литература == | ||
<references \> | <references \> | ||
Версия 11:03, 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], [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]x[/math] и шифртекст [math]y[/math] однозначно определяют ключи [math]k_1,k_2[/math]. Составим две таблицы:
[math] \begin{align} & z_1=T_1(x,k_1^1)\\ & z_2=T_1(x,k_1^2)\\ &...................\\ & z_{|K_1|}=T_1(x,k_1^{|K_1|}) \end{align} [/math]
И
[math] \begin{align} & z_1^'=T_2^{-1}(x,k_2^1)\\ & z_2^'=T_2^{-1}(x,k_2^2)\\ &...................\\ & z_{|K_1|}^'=T_2^{-1}(x,k_2^{|K_1|}) \end{align} [/math]
Для всех [math]k_1 \in K_1[/math], [math]k_2 \in K_2[/math]. Сложность вычисления составит [math]|K_1|+|K_2|[/math] операций опробования.
Далее таблица сортируется по значениям [math]z_i[/math], сложность сортировки составит [math]O(|K_1|\log(|K_1|))[/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
