Участник:Огнева Мария/Метод встречи посередине: различия между версиями
Sleo (обсуждение | вклад) |
|||
| (не показано 18 промежуточных версий 1 участника) | |||
| Строка 1: | Строка 1: | ||
| − | + | {{Assignment|Sleo}} | |
{{algorithm | {{algorithm | ||
| name = Метод встречи посередине | | name = Метод встречи посередине | ||
| Строка 28: | Строка 28: | ||
# Метод криптоанализа: универсальный. | # Метод криптоанализа: универсальный. | ||
#:С определенными вариациями метод применим ко многим шифрам. | #:С определенными вариациями метод применим ко многим шифрам. | ||
| − | # | + | # Применим для любого многократного шифрования одним алгоритмом по разным ключам, а также для случая, если множество ключей криптографического алгоритма замкнуто относительно композиции (для любых ключей k' и k" найдется ключ k такой, что результат шифрования любого текста последовательно на k' и k" равен результату шифрования того же текста на k). |
=== Описание метода для алгоритма двойного шифрования === | === Описание метода для алгоритма двойного шифрования === | ||
На данной странице будет рассмотрен более простой вариант - двойное шифрование <ref>Грушо А.А., Применко Э.А., Тимонина Е.Е. ''Анализ и синтез криптоалгоритмов. Курс лекций.'' - Москва: 2000. - 110 с.</ref> (две итерации шифрования). Пусть <math>p, c</math> – открытый (plaintext) и шифрованный текст (ciphertext) соответственно. Тогда сокращение полного перебора происходит следующим образом: | На данной странице будет рассмотрен более простой вариант - двойное шифрование <ref>Грушо А.А., Применко Э.А., Тимонина Е.Е. ''Анализ и синтез криптоалгоритмов. Курс лекций.'' - Москва: 2000. - 110 с.</ref> (две итерации шифрования). Пусть <math>p, c</math> – открытый (plaintext) и шифрованный текст (ciphertext) соответственно. Тогда сокращение полного перебора происходит следующим образом: | ||
| − | #Находим множество всех шифртекстов <math>W</math>, получаемых одинарным шифрованием открытого текста p по всем возможным ключам первой итерации. | + | #Находим множество всех шифртекстов <math>W</math>, получаемых одинарным шифрованием открытого текста <math>p</math> по всем возможным ключам первой итерации. |
| − | #Находим множество всех шифртекстов <math>Z</math>, получаемых одинарным дешифрованием шифрованного текста c по всем возможным ключам второй итерации. | + | #Находим множество всех шифртекстов <math>Z</math>, получаемых одинарным дешифрованием шифрованного текста <math>c</math> по всем возможным ключам второй итерации. |
#Если множества <math>W</math> и <math>Z</math> имеют непустое пересечение, то искомым ключом шифрования будет являться пара ключей, при помощи которых это пересечение было зашифровано из <math>p</math> и дешифровано из <math>c</math>. | #Если множества <math>W</math> и <math>Z</math> имеют непустое пересечение, то искомым ключом шифрования будет являться пара ключей, при помощи которых это пересечение было зашифровано из <math>p</math> и дешифровано из <math>c</math>. | ||
| Строка 77: | Строка 77: | ||
Примем за <math>n</math> количество всевозможных ключей <math>k= (k_1,k_2)</math>. Если предположить, что <math>|K_1|=|K_2|</math>, то <math>|K_1|=|K_2|=\sqrt n</math>. | Примем за <math>n</math> количество всевозможных ключей <math>k= (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>. |
== Информационный граф == | == Информационный граф == | ||
Опишем информационный граф алгоритма. | Опишем информационный граф алгоритма. | ||
| − | На вход подаётся открытый и шифрованный тексты. После открытый текст шифруется (Enc) по всем ключам <math>k_1</math>, а дешифрованный дешифруется (Dec) по всем ключам <math>k_2</math>. Далее полученные тексты сравниваются между собой (Cmp) и все ключи, на которых они совпали, являются | + | На вход подаётся открытый и шифрованный тексты. После открытый текст шифруется (Enc) по всем ключам <math>k_1</math>, а дешифрованный дешифруется (Dec) по всем ключам <math>k_2</math>. Далее полученные тексты сравниваются между собой (Cmp) и все ключи, на которых они совпали, являются выходами алгоритма. |
[[file:Graph MITM.jpg|thumb|center|600px|Рисунок 1. Граф алгоритма c отображением входных и выходных данных. Plaintext — открытый текст, ciphertext — шифрованный текст, Enc — операция шифрования, Dec — операция дешифрования, Cmp — операция сравнения, Key — полученный ключ]] | [[file:Graph MITM.jpg|thumb|center|600px|Рисунок 1. Граф алгоритма c отображением входных и выходных данных. Plaintext — открытый текст, ciphertext — шифрованный текст, Enc — операция шифрования, Dec — операция дешифрования, Cmp — операция сравнения, Key — полученный ключ]] | ||
== Ресурс параллелизма алгоритма == | == Ресурс параллелизма алгоритма == | ||
| − | Как видно из информационного графа, для реализации метода в параллельном варианте | + | Как видно из информационного графа, для реализации метода в параллельном варианте потребуется выполнение следующих двух ярусов ярусно-параллельной формы (ЯПФ): |
# <math>2* \sqrt{n}</math> шифрований/дешифрований | # <math>2* \sqrt{n}</math> шифрований/дешифрований | ||
# <math>n</math> сравнений | # <math>n</math> сравнений | ||
| Строка 94: | Строка 94: | ||
== Входные и выходные данные алгоритма == | == Входные и выходные данные алгоритма == | ||
| − | '''Входные данные''': открытый текст <math>p</math> и шифрованный текст <math>c</math>,имеющие одинаковую длину. | + | '''Входные данные''': открытый текст <math>p</math> и шифрованный текст <math>c</math>, имеющие одинаковую длину. |
| − | Так как рассматриваемые шифры являются блочными, то равенство длины | + | Так как рассматриваемые шифры являются блочными, то равенство длины текстов длине ключа не является обязательным, тексты могут быть длиннее. В такой ситуации тексты представляют собой последовательность блоков, а для шифрования/дешифрования берётся один блок текстов (от открытого и от шифрованного) для максимального ускорения операций. |
Примем, что длина ключей <math>k_1</math> и <math>k_2</math> равна 64 битам. То есть длина текста равна 64 битам или кратна этому числу. | Примем, что длина ключей <math>k_1</math> и <math>k_2</math> равна 64 битам. То есть длина текста равна 64 битам или кратна этому числу. | ||
| Строка 102: | Строка 102: | ||
'''Выходные данные''': множество пар <math>(k_1,k_2)</math>, для которых нашлись совпадения. | '''Выходные данные''': множество пар <math>(k_1,k_2)</math>, для которых нашлись совпадения. | ||
| − | Лишние пары могли получиться при шифровании/дешифровании одного | + | Лишние пары могли получиться при шифровании/дешифровании одного из блоков текстов. Тогда для получения истинного ключа необходимо проверить все пары на блоках открытого и шифрованного текста, которые в алгоритме не использовались. |
Длина искомого ключа: 128 бит. | Длина искомого ключа: 128 бит. | ||
| Строка 109: | Строка 109: | ||
Соотношение последовательной и параллельной сложности для данного метода равно <math>O(\sqrt n\log n)</math>. | Соотношение последовательной и параллельной сложности для данного метода равно <math>O(\sqrt n\log n)</math>. | ||
| − | При этом вычислительная мощность алгоритма, равная | + | При этом вычислительная мощность алгоритма, равная отношению числа операций к суммарному объему входных и выходных данных, составляет <math>O(\sqrt{n})</math>. |
Алгоритм полностью детерминирован при условии корректности данных. | Алгоритм полностью детерминирован при условии корректности данных. | ||
| − | Дуги информационного графа, исходящие из вершин, соответствующих операциям шифрования/дешифрования образуют пучки мощности <math>\sqrt{n}</math>. | + | Дуги информационного графа, исходящие из вершин, соответствующих операциям шифрования/дешифрования, образуют пучки мощности <math>\sqrt{n}</math>. |
= Программная реализация алгоритма = | = Программная реализация алгоритма = | ||
| + | |||
| + | == Особенности реализации последовательного алгоритма == | ||
| + | == Локальность данных и вычислений == | ||
| + | == Возможные способы и особенности параллельной реализации алгоритма == | ||
== Масштабируемость алгоритма и его реализации == | == Масштабируемость алгоритма и его реализации == | ||
| + | |||
| + | |||
| + | == Динамические характеристики и эффективность реализации алгоритма == | ||
| + | == Выводы для классов архитектур == | ||
== Существующие реализации алгоритма == | == Существующие реализации алгоритма == | ||
Реализаций метода в виде библиотек не обнаружено. | Реализаций метода в виде библиотек не обнаружено. | ||
| − | В свободном доступе существуют коды для метода встречи | + | В свободном доступе существуют коды для метода встречи посередине с использованием шифрования Blowfish и хэш-таблиц на [https://gist.github.com/dchest/1062437 C], а также с использованием шифрования 2DES на [https://github.com/le1ca/class-resources/blob/master/ddes/ddes.py питоне]. |
= Литература = | = Литература = | ||
| Строка 127: | Строка 135: | ||
[[Категория:Криптографические алгоритмы]] | [[Категория:Криптографические алгоритмы]] | ||
| − | + | *[https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B2%D1%81%D1%82%D1%80%D0%B5%D1%87%D0%B8_%D0%BF%D0%BE%D1%81%D0%B5%D1%80%D0%B5%D0%B4%D0%B8%D0%BD%D0%B5 Метод встречи посередине] | |
| + | *[https://en.wikipedia.org/wiki/Meet-in-the-middle_attack Meet-in-the-middle attack] | ||
| + | |||
| + | '''Сноски:''' | ||
Текущая версия на 02:29, 14 ноября 2016
 | Эта работа прошла предварительную проверку Дата последней правки страницы: 14.11.2016 Данная работа соответствует формальным критериям. Проверено Sleo. |
| Метод встречи посередине | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]O(\sqrt n\log n)[/math] |
| Объём входных данных | [math]O(1)[/math] |
| Объём выходных данных | [math]O(1)[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]2[/math] |
| Ширина ярусно-параллельной формы | [math]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 Общее описание алгоритма
Криптоанализом назвают науку восстановления (дешифрования) открытого (нешифрованного) текста без доступа к ключу. Попытка криптоанализа называется атакой.
Методом встречи посередине (англ. meet-in-the-middle attack) называется класс атак на криптографические алгоритмы (алгоритмы шифрования), которые асимптотически уменьшают время полного перебора по всем ключам, но при этом увеличивают объем требуемой памяти. Впервые данный метод был предложен Уитфилдом Диффи и Мартином Хеллманом в 1977 году [1] для блочных шифров.
1.1.1 История
Алгоритм шифрования DES был принят в качестве стандарта в 1977 году. Длина ключа нового стандарта составляла 56 бит, довольно большое число по тем временам, но оставляла возможность полного перебора ([math]2^{56} [/math]). В 1977 Диффи и Хеллман предложили устройство, стоимостью примерно 20 млн. долларов, которое смогло бы найти ключ DES за один день. Поэтому появилась необходимость увеличить стойкость алгоритма DES, используя технику многократного шифрования. Этот способ позволяет искусственно увеличить длину ключа, применяя несколько раз операцию шифрования с разными ключами. Так для алгоритма 2DES (двойное шифрование) длина ключа равна 112 бит, то есть полный перебор становится бессмысленной затеей. В 1981 году Ральф Меркл и Мартин Хеллман[2] подробно разбирают безопасность двойного шифрования и описывают метод встречи посередине, позволяющий восстановить ключ шифрования не за [math]2^{112}[/math] операций шифрования, а за относительно пустяковые [math]2^{57}[/math] за счет перебора не одного длинного ключа, а двух более коротких. Следующая модернизация DES - Triple DES с 168-битным ключом - требует от метода встречи посередине [math]2^{56} [/math] памяти и [math]2^{112}[/math] операций.
1.1.2 Особенности метода
- Способ шифрования: симметричный.
- Для шифрования и расшифрования применяется один и тот же криптографический ключ.
- Условия криптоанализа: атака на основе открытого текста.
- Известны открытый и шифрованный текст, алгоритм шифрования и дешифрования, необходимо найти ключ.
- Метод криптоанализа: универсальный.
- С определенными вариациями метод применим ко многим шифрам.
- Применим для любого многократного шифрования одним алгоритмом по разным ключам, а также для случая, если множество ключей криптографического алгоритма замкнуто относительно композиции (для любых ключей k' и k" найдется ключ k такой, что результат шифрования любого текста последовательно на k' и k" равен результату шифрования того же текста на k).
1.1.3 Описание метода для алгоритма двойного шифрования
На данной странице будет рассмотрен более простой вариант - двойное шифрование [3] (две итерации шифрования). Пусть [math]p, c[/math] – открытый (plaintext) и шифрованный текст (ciphertext) соответственно. Тогда сокращение полного перебора происходит следующим образом:
- Находим множество всех шифртекстов [math]W[/math], получаемых одинарным шифрованием открытого текста [math]p[/math] по всем возможным ключам первой итерации.
- Находим множество всех шифртекстов [math]Z[/math], получаемых одинарным дешифрованием шифрованного текста [math]c[/math] по всем возможным ключам второй итерации.
- Если множества [math]W[/math] и [math]Z[/math] имеют непустое пересечение, то искомым ключом шифрования будет являться пара ключей, при помощи которых это пересечение было зашифровано из [math]p[/math] и дешифровано из [math]c[/math].
1.2 Математическое описание алгоритма
Пусть алгоритм шифрования описывается как [math]Enc(k, t) [/math], дешифрования [math]Dec(k, t) [/math], где [math]k[/math] – ключ, [math]t[/math] – текст. Тогда получаемый двойным шифрованием по ключам [math]k_1[/math] и [math]k_2[/math] шифрованный текст равен: [math]c = Enc(k_2, Enc(k_1, p))[/math]. Открытый текст получается из шифрованного двойным дешифрованием: [math]p=Dec(k_1, Dec(k_2, c))[/math].
Исходные данные: тексты [math]p, c[/math].
Вычисляемые данные: ключ [math]k=(k_1, k_2)[/math], где [math]k_1 \in K_1[/math], [math]k_2 \in K_2[/math]. Предположим для упрощения, что для известной пары [math](p, c)[/math] существует единственный ключ [math](k_1, k_2)[/math]. Составим таблицы [math]W[/math] и [math]Z[/math]:
- для всех [math]k^i_1 \in K_1[/math]: [math]w(k^i_1) = Enc (k^i_1, p)[/math]
- для всех [math]k^j_2 \in K_2[/math]: [math]z(k^j_2) = Dec (k^j_2, c)[/math]
Таблицы объединяются и сортируются по полученным промежуточным шифртекстам [math]z_i, w_j[/math]. Пара [math]z_i = w_j[/math], которую можно найти одиночным просмотром объединенной таблицы, определяет искомый ключ [math](k^i_1, k^j_2) [/math].
В более общем случае, может получиться не одна пара [math]z_i = w_j[/math]. Тогда необходимы еще пары [math](p, c)[/math] для определения истинного ключа.
1.3 Вычислительное ядро алгоритма
Основную сложность алгоритма составляет перебор ключей [math]k^i_1,k^j_2[/math], а так же сортировка полученных массивов [math]W[/math] и [math]Z[/math].
1.4 Макроструктура алгоритма
Метод использует в качестве составных частей следующие алгоритмы:
- Алгоритм зашифрования/расшифрования
- Алгоритм сортировки
- Будем считать, что используется быстрая сортировка или сортировка слиянием, которые в среднем работают за [math]O(n \log n)[/math].
- Алгоритм поиска
- Совпадающие значения матриц [math]W[/math] и [math]Z[/math] будем искать одиночным просмотром всей таблицы.
1.5 Схема реализации последовательного алгоритма
Последовательность действий метода:
- Вычислить таблицы [math]W[/math] и [math]Z[/math], записывая значения в порядке вычисления и сохраняя соответствующие ключи для шифрования/дешифрования.
- Отсортировать массив [math]W \cup Z[/math].
- Найти совпадения в отсортированной таблице.
1.6 Последовательная сложность алгоритма
- Сложность вычисления таблиц [math]W[/math] и [math]Z[/math] составит [math]O(|K_1|+|K_2|)[/math] операций.
- Объединение таблиц и их сортировка будет иметь сложность: [math]O([|K_1|+|K_2|]\log[|K_1|+|K_2|])[/math].
- Поиск совпадений: [math]O(|K_1|+|K_2|)[/math].
Общая сложность всего метода равна: [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]
Примем за [math]n[/math] количество всевозможных ключей [math]k= (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].
1.7 Информационный граф
Опишем информационный граф алгоритма.
На вход подаётся открытый и шифрованный тексты. После открытый текст шифруется (Enc) по всем ключам [math]k_1[/math], а дешифрованный дешифруется (Dec) по всем ключам [math]k_2[/math]. Далее полученные тексты сравниваются между собой (Cmp) и все ключи, на которых они совпали, являются выходами алгоритма.
1.8 Ресурс параллелизма алгоритма
Как видно из информационного графа, для реализации метода в параллельном варианте потребуется выполнение следующих двух ярусов ярусно-параллельной формы (ЯПФ):
- [math]2* \sqrt{n}[/math] шифрований/дешифрований
- [math]n[/math] сравнений
То есть, высота ЯПФ составляет [math]2[/math], ширина – [math]n[/math] (т.к. [math]n\gt 2* \sqrt n[/math]).
1.9 Входные и выходные данные алгоритма
Входные данные: открытый текст [math]p[/math] и шифрованный текст [math]c[/math], имеющие одинаковую длину.
Так как рассматриваемые шифры являются блочными, то равенство длины текстов длине ключа не является обязательным, тексты могут быть длиннее. В такой ситуации тексты представляют собой последовательность блоков, а для шифрования/дешифрования берётся один блок текстов (от открытого и от шифрованного) для максимального ускорения операций.
Примем, что длина ключей [math]k_1[/math] и [math]k_2[/math] равна 64 битам. То есть длина текста равна 64 битам или кратна этому числу.
Выходные данные: множество пар [math](k_1,k_2)[/math], для которых нашлись совпадения.
Лишние пары могли получиться при шифровании/дешифровании одного из блоков текстов. Тогда для получения истинного ключа необходимо проверить все пары на блоках открытого и шифрованного текста, которые в алгоритме не использовались.
Длина искомого ключа: 128 бит.
1.10 Свойства алгоритма
Соотношение последовательной и параллельной сложности для данного метода равно [math]O(\sqrt n\log n)[/math].
При этом вычислительная мощность алгоритма, равная отношению числа операций к суммарному объему входных и выходных данных, составляет [math]O(\sqrt{n})[/math].
Алгоритм полностью детерминирован при условии корректности данных.
Дуги информационного графа, исходящие из вершин, соответствующих операциям шифрования/дешифрования, образуют пучки мощности [math]\sqrt{n}[/math].
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
Реализаций метода в виде библиотек не обнаружено. В свободном доступе существуют коды для метода встречи посередине с использованием шифрования Blowfish и хэш-таблиц на C, а также с использованием шифрования 2DES на питоне.
3 Литература
Сноски:
- ↑ Diffie Whitfield, Hellman Martin E. Exhaustive Cryptanalysis of the NBS Data Encryption Standard. - Journal Computer vol.10 pp.74–84 - June 1977
- ↑ Merkle Ralph C., Hellman Martin E. On the security of multiple encryption. - Journal Communications of the ACM, num.7 vol.24 pp.465-467 - July 1981
- ↑ Грушо А.А., Применко Э.А., Тимонина Е.Е. Анализ и синтез криптоалгоритмов. Курс лекций. - Москва: 2000. - 110 с.
