Участник:Огнева Мария/Метод встречи посередине

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

Основные авторы описания: М.С. Огнева

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

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

Криптоанализом назвают науку восстановления (дешифрования) открытого (нешифрованного) текста без доступа к ключу. Попытка криптоанализа называется атакой. Методом встречи посередине (англ. meet-in-the-middle attack) называется класс атак на криптографические алгоритмы (алгоритмы шифрования), которые асимптотически уменьшают время полного перебора по всем ключам, но при этом увеличивают объем требуемой памяти. Впервые данный метод был предложен Уитфилдом Диффи и Мартином Хеллманом в 1977 году для блочных шифров.

1.1.1 История

Алгоритм шифрования DES был принят в качестве стандарта в 1977 году. Длина ключа нового стандарта составляла 56 бит, довольно большое число по тем временам, но оставляла возможность полного перебора ([math]2^{56} [/math]). В 1977 Диффи и Хеллман предложили устройство, стоимостью примерно 20 млн. долларов, которое смогло бы найти ключ DES за один день. Поэтому появилась необходимость увеличить стойкость алгоритма DES, используя технику многократного шифрования. Этот способ позволяет искусственно увеличить длину ключа, применяя несколько раз операцию шифрования с разными ключами. Так для алгоритма 2DES (двойное шифрование) длина ключа равна 112 бит, то есть полный перебор становится бессмысленной затеей. В 1981 году Ральф Меркл и Мартин Хеллман подробно разбирают безопасность двойного шифрования и описывают метод встречи посередине, позволяющий восстановить ключ шифрования не за [math]2^{112}[/math] операций шифрования, а за относительно пустяковые [math]2^{57}[/math] за счет перебора не одного длинного ключа, а двух более коротких. Следующая модернизация DES - Triple DES с 168-битным ключом - требует от метода встречи посередине [math]2^{56} [/math] памяти и [math]2^{112}[/math] операций.

1.1.2 Особенности метода

1. Способ шифрования: симметричный.

   Для шифрования и расшифрования применяется один и тот же криптографический ключ.

2. Условия криптоанализа: атака на основе открытого текста.

   Известны открытый и шифрованный текст, алгоритм шифрования и дешифрования, необходимо найти ключ.

3. Метод криптоанализа: универсальный.

   С определенными вариациями метод применим ко многим шифрам.

4. Применимо для любого многократного шифрования одним алгоритмом по разным ключам, а также для случая, если множество ключей криптографического алгоритма замкнуто относительно композиции (для любых ключей k' и k" найдется ключ k такой, что результат шифрования любого текста последовательно на k' и k" равен результату шифрования того же текста на k).

1.1.3 Описание метода для алгоритма двойного шифрования

На данной странице будет рассмотрен более простой вариант - двойное шифрование (две итерации шифрования). Пусть [math]p, c[/math] – открытый (plaintext) и шифрованный текст (ciphertext) соответственно. Тогда сокращение полного перебора происходит следующим образом:

1. Находим множество всех шифртекстов [math]W[/math], получаемых одинарным шифрованием открытого текста p по всем возможным ключам первой итерации.
2. Находим множество всех шифртекстов [math]Z[/math], получаемых одинарным дешифрованием шифрованного текста c по всем возможным ключам второй итерации.
3. Если множества [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] для определения истинного ключа.

3 Литература

[1] Грушо А.А., Применко Э.А., Тимонина Е.Е. Анализ и синтез криптоалгоритмов. Курс лекций. - Москва: 2000. - 110 с.