Участница:Александра/Метод встречи посередине: различия между версиями
ASA (обсуждение | вклад) |
|||
| (не показано 37 промежуточных версий 3 участников) | |||
| Строка 1: | Строка 1: | ||
| + | {{Assignment|Algoman|Konshin}} | ||
| + | |||
| + | |||
{{algorithm | {{algorithm | ||
| name = Метод встречи посередине | | name = Метод встречи посередине | ||
| Строка 4: | Строка 7: | ||
| pf_height = <math>O(1)</math> | | pf_height = <math>O(1)</math> | ||
| pf_width = <math>O(n)</math> | | pf_width = <math>O(n)</math> | ||
| − | | output_data = <math>n</math> | + | | input_data = <math>O(\log(n))</math> |
| + | | output_data = <math>\log(n)</math> | ||
}} | }} | ||
| Строка 39: | Строка 43: | ||
</math> | </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>. Для нахождения такой пары достаточно просмотреть отсортированную таблицу один раз. | + | Для всех <math>k_1^i \in K_1</math>, <math>k_2^j \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>. Для нахождения такой пары достаточно просмотреть отсортированную таблицу один раз. |
Если же пара открытый текст/шифртекст определяет ключ не единственном образом, то выходом алгоритма будет некоторое множество пар <math>k_1,k_2</math>, одна из которых является истинным ключом. Для выбора истинного ключа достаточно проверить ключи из полученного множества на других парах открытый текст/шифртекст. | Если же пара открытый текст/шифртекст определяет ключ не единственном образом, то выходом алгоритма будет некоторое множество пар <math>k_1,k_2</math>, одна из которых является истинным ключом. Для выбора истинного ключа достаточно проверить ключи из полученного множества на других парах открытый текст/шифртекст. | ||
| Строка 50: | Строка 54: | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| − | + | В случае использования хэш-таблицы достаточно большого размера основную сложность алгоритма составляет опробование ключей <math>k_1,k_2</math>. | |
| + | Одним из самых трудоёмких шагов также оказывается сортировка таблицы. | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| Строка 70: | Строка 75: | ||
2. В случае записи значений в порядке вычисления отсортировать массив | 2. В случае записи значений в порядке вычисления отсортировать массив | ||
| − | 3. Опробовать ключи <math>k_2^j</math>, ища совпадения с таблицей значений <math> | + | 3. Опробовать ключи <math>k_2^j</math>, ища совпадения с таблицей значений <math>z_j^'</math>. Для нахождения совпадения использовать поиск по хэш-таблице (если она есть) или бинарный поиск |
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| + | Всюду далее считаем, что алгоритм не прекращает работу при нахождении первого совпадения, а ищет все совпадения. | ||
1. Сложность вычисления таблиц значений <math>z_i,z_j^'</math> составит <math>O(|K_1|+|K_2|)</math> операций опробования | 1. Сложность вычисления таблиц значений <math>z_i,z_j^'</math> составит <math>O(|K_1|+|K_2|)</math> операций опробования | ||
| Строка 78: | Строка 84: | ||
2. Объединение таблиц и их сортировка будет иметь сложность <math>O((|K_1|+|K_2|)\log(|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> для каждого поиска | + | 3. Сложность бинарного поиска в отсортированном массиве — <math>O(\log_2(|K_1|))</math> для каждого поиска |
4. Сложность поиска в достаточно большой хэш-таблице составит <math>O(1)</math> для каждого поиска | 4. Сложность поиска в достаточно большой хэш-таблице составит <math>O(1)</math> для каждого поиска | ||
| Строка 86: | Строка 92: | ||
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> | 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> | + | 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> | 3. C генерацией одной (достаточно большой) хэш-таблицы — <math>O(|K_1|) + O(|K_2|)=O(|K_1|+|K_2|)</math> | ||
| Строка 96: | Строка 102: | ||
=== Информационный граф === | === Информационный граф === | ||
| − | Опишем граф алгоритма. На вход подаётся открытый (Open) и закрытый (Close), т.е. зашифрованный, текст. Далее открытый текст шифруется (Enc) на ключах <math>k_1^i</math>, а зашифрованный | + | Опишем информационный граф алгоритма. На вход подаётся открытый (Open) и закрытый (Close), т.е. зашифрованный, текст. Далее открытый текст шифруется (Enc) на ключах <math>k_1^i</math>, а зашифрованный расшифровывается (Dec) на ключах <math>k_2^j</math>. Далее полученные криптограммы сравниваются (Cmp) и все ключи, на которых они совпали, являются выходом алгоритма. |
| − | [[file:meet.png|thumb|center| | + | [[file:meet.png|thumb|center|900px|Рисунок 1. Граф алгоритма c отображением входных и выходных данных. Open — открытый текст, Close — шифртекст, Enc — операция зашифрования, Dec — операция расшифрования, Cmp — операция сравнения, Keys — вычисленные ключи]] |
=== Ресурс параллелизма алгоритма === | === Ресурс параллелизма алгоритма === | ||
| Строка 123: | Строка 129: | ||
Будем считать, что размер входных данных (открытый текст и шифртекст) совпадает с размером ключа (на практике это сравнимые величины), а сортировка слиянием делит массивы пополам. Тогда вычислительная мощность алгоритма — <math>O(\sqrt n)</math>. | Будем считать, что размер входных данных (открытый текст и шифртекст) совпадает с размером ключа (на практике это сравнимые величины), а сортировка слиянием делит массивы пополам. Тогда вычислительная мощность алгоритма — <math>O(\sqrt n)</math>. | ||
| − | Дуги информационного графа, исходящие из вершин зашифрования и расшифрования, образуют пучки | + | Дуги информационного графа, исходящие из вершин зашифрования и расшифрования, образуют пучки мощности <math>\sqrt n</math>, т.е. из каждой такой вершины выходит <math>\sqrt n</math> дуг. Длинных дуг в алгоритме нет. В случае поиска всех пар ключей с совпадающими криптограммами алгоритм полностью детерминирован. |
| + | |||
| + | == Программная реализация алгоритма == | ||
| + | |||
| + | === Особенности реализации последовательного алгоритма === | ||
| − | + | === Локальность данных и вычислений === | |
| − | == | + | === Возможные способы и особенности параллельной реализации алгоритма === |
=== Масштабируемость алгоритма и его реализации === | === Масштабируемость алгоритма и его реализации === | ||
| + | Исследование масштабируемости реализации алгоритма проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета]. Изменяемые параметры запуска: | ||
| + | * Размер ключа – от 8 до 20 бит с шагом 1 | ||
| + | * Число ядер – от 1 до 8 (значения являются степенью числа 2) | ||
| + | Ниже представлен график зависимости [[Глоссарий#Производительность|производительности]] от числа ядер и размера ключа (размер задачи – экспоненциальная функция от размера ключа). Для измерения производительности в качестве базовой операции используется операция опробования ключа и время в секундах. Количество арифметических операций, содержащихся в операции опробования, может быть разным в зависимости от используемого алгоритма шифрования. | ||
| + | [[File:Масштабируемость.jpg|thumb|center|900px|Рисунок 2. Масштабируемость реализации алгоритма]] | ||
| + | |||
| + | Как видно из графика, производительность почти не изменяется в зависимости от размера задачи и возрастает в зависимости от числа ядер. Росту производительности способствует то, что алгоритм содержит большое количество независимых операций опробования ключа, синхронизация между параллельно выполняющимися опробованиями не требуется. | ||
| + | |||
| + | [https://github.com/AlBatarina/Super2016/blob/master/meet_in_the_middle/meet.c Исследованная параллельная реализация на языке C] | ||
| + | |||
| + | === Динамические характеристики и эффективность реализации алгоритма === | ||
| + | |||
| + | === Выводы для классов архитектур === | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
Текущая версия на 17:24, 19 декабря 2016
 | Эта работа успешно выполнена Преподавателю: в основное пространство, в подстраницу Данное задание было проверено и зачтено. Проверено Konshin и Algoman. |
| Метод встречи посередине | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]O(\sqrt n\log(n))[/math] |
| Объём входных данных | [math]O(\log(n))[/math] |
| Объём выходных данных | [math]\log(n)[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]O(1)[/math] |
| Ширина ярусно-параллельной формы | [math]O(n)[/math] |
Автор описания: А.В.Батарина
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Метод "Встреча посередине" криптоанализа блочных шифров был впервые предложен в 1977 году Уитфилдом Диффи и Мартином Хеллманом [1]. Встреча посередине используется для ускорения перебора ключей шифра за счёт увеличения требуемой памяти. Метод применим в случае каскадного построения сложного шифра из нескольких простых, другими словами, в случае последовательного применения шифрующих преобразований на разных ключах к блокам открытого текста.
В качестве примера шифра, поддающегося атаке "встреча посередине" можно привести криптоалгоритм 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]y=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]|K_1||K_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^i \in K_1[/math], [math]k_2^j \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]. Для нахождения такой пары достаточно просмотреть отсортированную таблицу один раз.
Если же пара открытый текст/шифртекст определяет ключ не единственном образом, то выходом алгоритма будет некоторое множество пар [math]k_1,k_2[/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 Макроструктура алгоритма
Как видно из описания, атака "встреча посередине" использует (или может использовать в качестве оптимизации) следующие алгоритмы:
1. Алгоритм зашифрования/расшифрования
2. Алгоритм сортировки
3. Алгоритмы поиска, вставки в хэш-таблицу
1.5 Схема реализации последовательного алгоритма
Далее приводится последовательность действий для варианта алгоритма с генерацией одной таблицы значений [math]z_i[/math].
1. Вычислить таблицу [math]z_i[/math], записывая значения в порядке вычисления или используя хэш-таблицу
2. В случае записи значений в порядке вычисления отсортировать массив
3. Опробовать ключи [math]k_2^j[/math], ища совпадения с таблицей значений [math]z_j^'[/math]. Для нахождения совпадения использовать поиск по хэш-таблице (если она есть) или бинарный поиск
1.6 Последовательная сложность алгоритма
Всюду далее считаем, что алгоритм не прекращает работу при нахождении первого совпадения, а ищет все совпадения.
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]
Пусть n - количество всевозможных пар [math]k_1,k_2[/math] и пусть [math]|K_1|=|K_2|[/math]. В этом случае [math]|K_1|=|K_2|=\sqrt n[/math].
Тогда сложность алгоритма в первых двух пунктах составляет [math]O(\sqrt n\log(n))[/math], в третьем — [math]O(\sqrt n)[/math].
1.7 Информационный граф
Опишем информационный граф алгоритма. На вход подаётся открытый (Open) и закрытый (Close), т.е. зашифрованный, текст. Далее открытый текст шифруется (Enc) на ключах [math]k_1^i[/math], а зашифрованный расшифровывается (Dec) на ключах [math]k_2^j[/math]. Далее полученные криптограммы сравниваются (Cmp) и все ключи, на которых они совпали, являются выходом алгоритма.
1.8 Ресурс параллелизма алгоритма
Как видно из информационного графа, для реализации атаки "встреча посередине" в параллельном варианте потребуются выполнение следующих двух ярусов (в предположении, что [math]|K_1|=|K_2|[/math]):
1. [math]\sqrt n[/math] зашифрований и столько же расшифрований
2. [math]n[/math] сравнений
Таким образом, высота ЯПФ составляет 2, ширина - [math]n[/math].
1.9 Входные и выходные данные алгоритма
Вход: На вход подаётся открытый текст [math]x[/math] и шифртекст [math]y[/math], а также алгоритм зашифрования/расшифрования. В случае блочного шифра открытым текстом и шифртекстом является последовательность блоков. Для атаки "встреча посередине", как правило, берётся один блок для максимального ускорения операций зашифрования и расшифрования.
Выход: Результатом работы алгоритма является множество пар [math]k_1^i,k_2^j[/math], для которых нашлись совпадения. Только одна из пар является настоящим ключом. Чтобы отсеять лишние, необходимо проверить все пары на блоках открытого и шифрованного текста, которые в алгоритме не использовались.
1.10 Свойства алгоритма
Соотношением последовательной и параллельной сложности алгоритма является [math]O(\sqrt n\log(n))[/math].
Будем считать, что размер входных данных (открытый текст и шифртекст) совпадает с размером ключа (на практике это сравнимые величины), а сортировка слиянием делит массивы пополам. Тогда вычислительная мощность алгоритма — [math]O(\sqrt n)[/math].
Дуги информационного графа, исходящие из вершин зашифрования и расшифрования, образуют пучки мощности [math]\sqrt n[/math], т.е. из каждой такой вершины выходит [math]\sqrt n[/math] дуг. Длинных дуг в алгоритме нет. В случае поиска всех пар ключей с совпадающими криптограммами алгоритм полностью детерминирован.
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
Исследование масштабируемости реализации алгоритма проводилось на суперкомпьютере "Ломоносов"[2] Суперкомпьютерного комплекса Московского университета. Изменяемые параметры запуска:
- Размер ключа – от 8 до 20 бит с шагом 1
- Число ядер – от 1 до 8 (значения являются степенью числа 2)
Ниже представлен график зависимости производительности от числа ядер и размера ключа (размер задачи – экспоненциальная функция от размера ключа). Для измерения производительности в качестве базовой операции используется операция опробования ключа и время в секундах. Количество арифметических операций, содержащихся в операции опробования, может быть разным в зависимости от используемого алгоритма шифрования.
Как видно из графика, производительность почти не изменяется в зависимости от размера задачи и возрастает в зависимости от числа ядер. Росту производительности способствует то, что алгоритм содержит большое количество независимых операций опробования ключа, синхронизация между параллельно выполняющимися опробованиями не требуется.
Исследованная параллельная реализация на языке C
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
Одна из реализаций атаки "встреча посередине" с использованием хэш-таблицы представлена в свободном доступе по ссылке github
3 Литература
<references \>
- ↑ (June 1977) «Exhaustive Cryptanalysis of the NBS Data Encryption Standard». Computer 10 (6): 74–84. DOI:10.1109/C-M.1977.217750
- ↑ Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.
