Существует множество способов объединять блочные алгоритмы для получения новых алгоритмов. Стимулом создавать подобные схемы является желание повысить безопасность, не пробираясь через тернии создания нового алгоритма. DES является безопасным алгоритмом, он подвергался криптоанализу добрых 20 лет и, тем не менее, наилучшим способом вскрытия остается грубая сила. Однако ключ слишком короток. Разве не плохо было бы использовать DES в качестве компонента другого алгоритма с более длинным ключом ? Это позволило бы получить преимущества длинного ключа с гарантией двух десятилетий криптоанализа .
Одним из способов объединения является многократное шифрование- для шифрования одного и того же блока открытого текста алгоритм шифрования используется несколько раз с несколькими ключами . Шифрование каскадом похоже на многократное шифрование, но использует различные алгоритмы . Существуют и другие методы.
Повторное шифрование блока открытого текста одним и тем же ключом с помощью того же или другого а л-горитма неразумно. Повторное использование того же алгоритма не увеличивает сложность вскрытия грубой силой. (Не забывайте, мы предполагаем, что алгоритм, включая количество шифрований, известен криптоан а-литику.) При различных алгоритмах сложность вскрытия грубой силой может возрастать, а может и остаться неизменной. Если вы собираетесь использовать методы, описанные в этой главе, убедитесь, что ключи для п о-следовательных шифрований различны и независимы.
15.1 Двойное шифрование
Наивным способом повысить безопасность алгоритма является шифрование блока дважды с двумя разли ч-ными ключами. Сначала блок шифруется первым ключом, а затем получившийся шифротекст шифруется вт о-рым ключом. Дешифрирование является обратным процессом.
C = EKi(EKi(P))
P = DKi(DK2(Q)
Если блочный алгоритм образует группу (см. раздел 11.3), то всегда существует К3, для которого C = EK2(EKi(P)) = EKj(P)
Если алгоритм не образует группу, то при помощи исчерпывающего поиска взломать получающийся дважды зашифрованный блок шифротекста намного сложнее. Вместо 2" (где п - длина ключа в битах), потребуется 22й попыток. Если алгоритм использует 64-битовый ключ, для обнаружения ключей, которыми дважды зашифрован шифротекст, потребуется 2128 попыток.
Но при вскрытии с известным открытым текстом это не так. Меркл и Хеллман [1075] придумали способ обменять память на время, который позволяет вскрыть такую схему двойного шифрования за 2Й+1 шифрований, а не за 22". (Они использовали эту схему против DES, но результаты можно обобщить на все блочные алгоритмы.) Это вскрытие называется "встреча посередине",с одной стороны выполняется шифрование а с другой - дешифрирование, получившиеся посередине результаты сравниваются .
В этом вскрытии криптоаналитику известны Ри Сь Р2 и С2, такие что
С^Е^Е^Р,))
C2=EK2(EKi(P2))
Для каждого возможного К (или Ки или К2), криптоаналитик рассчитывает EdP{) и сохраняет результат в памяти. Собрав все результаты, он для каждого К вычисляет ЩС,) и ищет в памяти такой же результат. Если такой результат обнаружен, то возможно, что текущий ключ - К2, а ключ для результата в памяти - Кг. Затем криптоаналитик шифрует Рх с помощью Кг и К2. Если он получает С2, то он может гарантировать (с вероятностью успеха 1 к 22-2и, где т - размер блока), что он узнал и Къ и К2. Если это не так, он продолжает поиск. Максимальное количество попыток шифрования, которое ему, возможно, придется предпринять, равно 2*2", или T+l. Если вероятность ошибки слишком велика, он может использовать третий блок шифротекста, обесп е-чивая вероятность успеха 1 к 22"-3и Существуют и другие способы оптимизации [912].
Для такого вскрытия нужен большой объем памяти: 2" блоков. Для 56-битового ключа нужно хранить 256 64-битовых блоков, или 1017 байтов. Такой объем памяти пока еще трудно себе представить, но этого хватает, чт о-бы убедить самых параноидальных криптографов в том, что двойным шифрованием пользоваться не стоит .
При 128-битовом ключе для хранения промежуточных результатов потребуется 10 39 байтов. Если предположить, что есть способ хранить бит информации, используя единственный атом алюминия , устройство памяти, нужное для выполнения такого вскрытия, будет представлять собой алюминиевый куб с ребром, длиной 1 км . Кроме того, вам понадобится куда-то его поставить ! Вскрытие "встреча посередине" кажется невозможным для ключей такого размера.
Другим способом двойного шифрования, который иногда называют Davies-Price,является вариантом СВС [435].
С=Е^ЪЕ^С^))
р= /),1(с,)е^2(с,_1))
Утверждается, что "у этого режима нет никаких особых достоинств", к тому же он, по видимому, так же чувствителен ко вскрытию "встреча посередине" как и другие режимы двойного шифрования .