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

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

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

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

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

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

1.1.1 История

Алгоритм шифрования DES был принят в качестве стандарта в 1977 году. Длина ключа нового стандарта составляла 56 бит, довольно большое число по тем временам, но оставляла возможность полного перебора ([math]2^{56} [/math]). Поэтому появилась необходимость увеличить стойкость алгоритма 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. Применение: для любого многократного шифрования одним алгоритмом по разным ключам, а также для случая, если множество ключей криптографического алгоритма замкнуто относительно композиции (для любых ключей [math]k'[/math] и [math]k''[/math] найдется ключ [math]k [/math] такой, что результат шифрования любого текста последовательно на [math]k'[/math] и [math]k''[/math] равен результату шифрования того же текста на [math]k [/math]). На данной странице будет рассмотрен более простой вариант - двойное шифрование.

3 Литература

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

[10] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.