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

Метод встречи посередине
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(\sqrt n\log(n)) }[/math]
Объём выходных данных	[math]\displaystyle{ n }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ O() }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ O() }[/math]

Автор описания: А.В.Батарина

Свойства и структура алгоритма

Общее описание алгоритма

Метод "Встреча посередине" криптоанализа блочных шифров был впервые предложен в 1977 году Уитфилдом Диффи и Мартином Хеллманом . Встреча посередине используется для ускорения перебора ключей шифра за счёт увеличения требуемой памяти. Метод применим в случае каскадного построения сложного шифра из нескольких простых, другими словами, в случае последовательного применения шифрующих преобразований на разных ключах к блокам открытого текста.

Усложнённые шифры

В качестве примера шифра, поддающегося атаке "встреча посередине" можно привести криптоалгоритм 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{ z_i,z_j^' }[/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]. Для нахождения такой пары достаточно просмотреть отсортированную таблицу один раз.

Оптимизации

1. От генерации второй таблицы со значениями [math]\displaystyle{ z_j^' }[/math] можно отказаться, перебирая ключи [math]\displaystyle{ k_2^j }[/math] до того момента, когда значение [math]\displaystyle{ z_j^' }[/math] совпадёт с одним из значений [math]\displaystyle{ z_i }[/math]. В таком случае опробование ключей [math]\displaystyle{ k_2^j }[/math] в среднем сократится вдвое. Также вдвое сократится объём используемой памяти. Для нахождения совпадающего значения в отсортированном массиве можно применить бинарный поиск.

2. Вместо сортировки таблицы со значениями [math]\displaystyle{ z_i }[/math] и последующего бинарного поиска можно использовать хэш-таблицу.

Макроструктура алгоритма

Основную сложность алгоритма составляет сортировка таблицы, полученной в результате опробования ключей. В случае использования хэш-таблицы достаточно большого размера вместо сортировки основную сложность составит опробование ключей [math]\displaystyle{ k_1,k_2 }[/math].

Схема реализации последовательного алгоритма

Далее приводится последовательность действий для варианта алгоритма с генерацией одной таблицы значений [math]\displaystyle{ z_i }[/math].

1. Вычислить таблицу [math]\displaystyle{ z_i }[/math], записывая значения в порядке вычисления или используя хэш-таблицу

2. В случае записи значений в порядке вычисления отсортировать массив

3. Опробовать ключи [math]\displaystyle{ k_2^j }[/math], ища совпадения с таблицей значений [math]\displaystyle{ z_i }[/math]. Для нахождения совпадения использовать поиск по хэш-таблице (если она есть) или бинарный поиск

Последовательная сложность алгоритма

1. Сложность вычисления таблиц значений [math]\displaystyle{ z_i,z_j^' }[/math] составит [math]\displaystyle{ O(|K_1|+|K_2|) }[/math] операций опробования

2. Объединение таблиц и их сортировка будет иметь сложность [math]\displaystyle{ O((|K_1|+|K_2|)\log(|K_1|+|K_2|)) }[/math] (например, при сортировке слиянием).

3. Сложность бинарного поиска в отсортированном массиве — [math]\displaystyle{ O(log_2(|K_1|)) }[/math] для каждого поиска

4. Сложность поиска в достаточно большой хэш-таблице составит [math]\displaystyle{ O(1) }[/math] для каждого поиска

Итого асимптотическая сложность алгоритма:

1. С генерацией двух таблиц — [math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ O(|K_1|) + O(|K_2|)=O(|K_1|+|K_2|) }[/math]

Пусть n - количество всевозможных пар [math]\displaystyle{ k_1,k_2 }[/math] и пусть [math]\displaystyle{ |K_1|=|K_2| }[/math]. В этом случае [math]\displaystyle{ |K_1|=|K_2|=\sqrt n }[/math].

Тогда сложность алгоритма в первых двух пунктах составляет [math]\displaystyle{ O(\sqrt n\log(n)) }[/math], в третьем — [math]\displaystyle{ O(\sqrt n) }[/math].

Информационный граф

Опишем граф алгоритма. На вход подаётся открытый (Open) и закрытый (Close), т.е. зашифрованный, текст. Далее открытый текст шифруется (Enc) на ключах [math]\displaystyle{ k_1^i }[/math], а зашифрованный расшифруется (Dec) на ключе [math]\displaystyle{ k_2^j }[/math]. Далее полученные криптограммы сравниваются (Cmp) и все ключи, на которых они совпали, являются выходом алгоритма.

Рисунок 1. Граф алгоритма c отображением входных и выходных данных. Open - открытый текст Close — шифртекст Enc — операция зашифрования Dec — операция расшифрования, Cmp — операция сравнения, Keys — полученные ключи

Ресурс параллелизма алгоритма

Как видно из информационного графа, для реализации атаки "встреча посередине" в параллельном варианте потребуются выполнение следующих двух ярусов (в предположении, что [math]\displaystyle{ |K_1|=|K_2| }[/math]):

1. [math]\displaystyle{ \sqrt n }[/math] зашифрований и столько же расшифрований

2. [math]\displaystyle{ n }[/math] сравнений

Таким образом, высота ЯПФ составляет 2, ширина - [math]\displaystyle{ n }[/math].

Литература

<references \>