Участница:Александра/Метод встречи посередине: различия между версиями
| Строка 77: | Строка 77: | ||
2. C генерацией одной таблицы, сортировкой и бинарным поиском — <math>O(|K_1|) + O((|K_1|)\log(|K_1|)) + O(||K_2|\log_2(|K_1|))=O(max(|K_1|,|K_2|)\log(|K_1|))</math> | 2. C генерацией одной таблицы, сортировкой и бинарным поиском — <math>O(|K_1|) + O((|K_1|)\log(|K_1|)) + O(||K_2|\log_2(|K_1|))=O(max(|K_1|,|K_2|)\log(|K_1|))</math> | ||
| − | 3. C генерацией одной хэш-таблицы — <math>O(|K_1|) + O((|K_2 | + | 3. C генерацией одной (достаточно большой) хэш-таблицы — <math>O(|K_1|) + O((|K_2|))=O(|K_1|+|K_2|)</math> |
| − | |||
== Литература == | == Литература == | ||
<references \> | <references \> | ||
Версия 15:30, 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_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]k_1 \in K_1[/math], [math]k_2 \in K_2[/math]. Далее таблицы объединяются и сортируются по значениям [math]z_i,z_j^'[/math]. Индексы [math]i,j[/math], при которых [math]z_i=z_j^'[/math], однозначно определяют искомую пару ключей [math]k_1=k_1^i,k_2=k_2^j[/math]. Для нахождения такой пары достаточно просмотреть отсортированную таблицу один раз.
1.2.1 Оптимизации
1. От генерации второй таблицы со значениями [math]z_j^'[/math] можно отказаться, перебирая ключи [math]k_2^j[/math] до того момента, когда значение [math]z_j^'[/math] совпадёт с одним из значений [math]z_i[/math]. В таком случае опробование ключей [math]k_2^j[/math] в среднем сократится вдвое. Также вдвое сократится объём используемой памяти. Для нахождения совпадающего значения в отсортированном массиве можно применить бинарный поиск.
2. Вместо сортировки таблицы со значениями [math]z_i[/math] и последующего бинарного поиска можно использовать хэш-таблицу.
1.3 Макроструктура алгоритма
Основную сложность алгоритма составляет сортировка таблицы, полученной в результате опробования ключей. В случае использования хэш-таблицы достаточно большого размера вместо сортировки основную сложность составит опробование ключей [math]k_1,k_2[/math].
1.4 Схема реализации последовательного алгоритма
Далее приводится последовательность действий для варианта алгоритма с генерацией одной таблицы значений [math]z_i[/math].
1. Вычислить таблицу [math]z_i[/math], записывая значения в порядке вычисления или используя хэш-таблицу
2. В случае записи значений в порядке вычисления отсортировать массив
3. Опробовать ключи [math]k_2^j[/math], ища совпадения с таблицей значений [math]z_i[/math]. Для нахождения совпадения использовать поиск по хэш-таблице (если она есть) или бинарный поиск
1.5 Последовательная сложность алгоритма
1. Сложность вычисления таблиц значений [math]z_i,z_j^'[/math] составит [math]O(|K_1|+|K_2|)[/math] операций опробования
2. Объединение таблиц и их сортировка будет иметь сложность [math]O((|K_1|+|K_2|)\log(|K_1|+|K_2|))[/math] (например, при сортировке слиянием).
3. Сложность бинарного поиска в отсортированном массиве — [math]O(log_2(|K_1|))[/math] для каждого поиска
4. Сложность поиска в достаточно большой хэш-таблице составит [math]O(1)[/math] для каждого поиска
Итого сложность алгоритма (в худшем случае):
1. С генерацией двух таблиц — [math]O(|K_1|+|K_2|) + O((|K_1|+|K_2|)\log(|K_1|+|K_2|)) + O(|K_1|+|K_2|)=O((|K_1|+|K_2|)\log(|K_1|+|K_2|))[/math]
2. C генерацией одной таблицы, сортировкой и бинарным поиском — [math]O(|K_1|) + O((|K_1|)\log(|K_1|)) + O(||K_2|\log_2(|K_1|))=O(max(|K_1|,|K_2|)\log(|K_1|))[/math]
3. C генерацией одной (достаточно большой) хэш-таблицы — [math]O(|K_1|) + O((|K_2|))=O(|K_1|+|K_2|)[/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
