Комбинирование блочных алгоритмов. Схемы двукратного и трехкратного шифрования и расшифрования.

В настоящее время блочный алгоритм DES считается относительно безопасным алгоритмом шифрования. Он подвергался тщательному криптоанализу в течение 20 лет, и самым практичным способом его взламывания является метод перебора всех возможных вариантов ключа. Ключ DES имеет длину 56 бит, поэтому существует 256 возможных вариантов такого ключа. Если предположить, что суперкомпьютер может испытать миллион вариантов ключа за секунду, то потребуется 2285 лет для нахождения правильного ключа. Если бы ключ имел длину 128 бит, то потребовалось бы 1025 лет (для сравнения: возраст Вселенной около 1010лет).

Нетрудно представить себе, что при постоянном прогрессе возможностей компьютерной техники недалеко то время, когда машины поиска ключа DES методом полного перебора станут экономичными для мощных в финансовом отношении государственных и коммерческих организаций.

Возникает естественный вопрос: нельзя ли использовать DES в качестве строительного блока для создания другого алгоритма с более длинным ключом?

В принципе существует много способов комбинирования блочных алгоритмов для получения новых алгоритмов. Одним из таких способов комбинирования является многократное шифрование,
т.е. использование блочного алгоритма несколько раз с разными ключами для шифрования одного и того же блока открытого текста. Двухкратное шифрование блока открытого текста одним и тем
же ключом не приводит к положительному результату. При использовании одного и того же алгоритма такое шифрование не влияет на сложность криптоаналитической атаки полного перебора.
Рассмотрим эффективность двухкратного шифрования блока открытого текста с помощью двух разных ключей. Сначала шифруют блок Р ключом K₁ а затем получившийся шифртекст E_K1(P)
шифруют ключом К₂. В результате двухкратного шифрования получают криптограмму

C = E_K2(EK1(P)).

Расшифрование является обратным процессом:P = D_K1(D_K2(C)).

Если блочный алгоритм обладает свойствами группы [125], то всегда найдется такой ключ К₃, что С = Е_K2(Е_K1(Р))=Е_K3(Р).

Если же блочный алгоритм не является группой, то результирующий двухкратно шифрованный блок текста окажется намного сложнее для взламывания методом полного перебора вариантов.

Вместо 2ⁿ попыток, где n-длина ключа в битах, потребуется 2²ⁿ . попыток. В частности, если n = 64, то двухкратно зашифрованный блок текста потребует 2¹²⁸ попыток для нахождения ключа.
Однако Р. Меркль и М. Хеллман показали на примере DES, что, используя метод "обмена времени на память" и криптоаналитическую атаку "встреча посредине", можно взломать такую схему двухкратного шифрования за 2ⁿ⁺¹ попыток [34]. Хотя эта атака потребует очень большого объема памяти (для алгоритма с 56-битовым ключом потребуется 256 64-битовых блоков или 1017 бит памяти).

Более привлекательную идею предложил У. Тачмен [125]. Суть этой идеи состоит в том, чтобы шифровать блок открытого текста Р три раза с помощью двух ключей K₁ и К₂ (рис. 3.9). Процедура шифрования: C = E_K1(D_K2(E_K1(P))),

т.е. блок открытого текста Р сначала шифруется ключом K₁, затем расшифровывается ключом К₂ и окончательно зашифровывается ключом K₁

.

Рис. 3.9. Схемы трехкратного применения алгоритма DES
с двумя разными ключами

Этот режим иногда называют режимом EDE (encrypt-decrypt- encrypt). Введение в данную схему операции расшифрования D_K2 позволяет обеспечить совместимость этой схемы со схемой однократного использования алгоритма DES. Если в схеме трехкратного использования DES выбрать все ключи одинаковыми, то эта схема превращается в схему однократного использования DES. Процедура расшифрования выполняется в обратном порядке:

Р = D_K1(Е_K2(D_К1(С))),

т.е. блок шифртекста С сначала расшифровывается ключом K₁, затем зашифровывается ключом К₂ и окончательно расшифровывается ключом K₁.

Если исходный блочный алгоритм имеет n-битовый ключ, то схема трехкратного шифрования имеет 2n-битовый ключ. Чередование ключей K₁ и К₂ позволяет предотвратить криптоаналитическую атаку "встреча посредине". Данная схема приводится в стандартах Х9.17 и ISO 8732 в качестве средства улучшения характеристик алгоритма DES.

При трехкратном шифровании можно применить три различных ключа. При этом возрастает общая длина результирующего ключа. Процедуры шифрования и расшифрования описываются выражениями:

С = Е_K3(D_К2(Е_К1(Р))),

Р = D_К1(Е_К2(D_К3(С))).

Трехключевой вариант имеет еще большую стойкость. Очевидно, что если требуется повысить безопасность большого парка оборудования, использующего DES, то гораздо дешевле переключиться на схемы трехкратных DES, чем переходить на другой тип криптосхем.