Комбинирование блочных алгоритмов

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

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

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

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

не влияет на сложность криптоаналитической атаки полного перебора.

Рассмотрим эффективность двухкратного шифрования блока открытого текста с помощью двух разных ключей. Сначала шифруют блок Р ключом К₁, а затем получившийся шифртекст Е_К1(Р) шифруют ключом К₂. В результате двухкратного шифрования получают криптограмму

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

Расшифрование является обратным процессом:

Р = D_К1(D_К2(C)).

Если блочный алгоритм обладает свойствами группы, то всегда найдется такой ключ К₃, что

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

Если же блочный алгоритм не является группой, то результирующий двухкратно шифрованный блок текста окажется намного сложнее для взламывания методом полного перебора вариантов. Вместо 2ⁿ попыток, где n – длина ключа в битах, потребуется 2²ⁿ попыток. В частности, если n=64, то двухкратно зашифрованный блок текста потребует 2¹²⁸ попыток для нахожде-ния ключа.

Однако Р.Меркль и М.Хеллман показали на примере DES, что, используя метод "обмена времени на память" и криптоаналитическую атаку "встреча посредине", можно взломать такую схему двухкратного шифрования за 2ⁿ⁺¹ попыток. Хотя эта атака потребует очень большого объема памяти (для алгоритма с 56-битовым ключом потребуется 2⁵⁶ 64-битовых блоков или 10¹⁷ бит памяти).

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

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

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

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

Рисунок 5.4 – Схемы трехкратного применения алгоритма DES (3 DES)

с двумя разными ключами

Процедура расшифрования выполняется в обратном порядке:

Р = D_К1(Е_К2(D_К1(C))),

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

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

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

С = Е_К3(D_К2(E_К1(P))),

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

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

Поиск по сайту: