Анализ эффективности алгоритма

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

Однако, данный алгоритм, являясь первым опытом стандарта шифрования имеет ряд недостатков. За время, прошедшее после создания DES, компьютерная техника развилась настолько быстро, что оказалось возможным осуществлять исчерпывающий перебор ключей и тем самым раскрывать шифр. Стоимость этой атаки постоянно снижается. В 1998 г. была построена машина стоимостью около 100000 долларов, способная по данной паре <исходный текст, шифрованный текст> восстановить ключ за среднее время в 3 суток. Таким образом, DES, при его использовании стандартным образом, уже стал далеко не оптимальным выбором для удовлетворения требованиям скрытности данных.

Было выдвинуто большое количество предложений по усовершенствованию DES, которые отчасти компенсируют указанные недостатки. Мы рассмотрим два из них.

Наиболее широко известным предложением по усилению DES является так называемый «тройной DES», одна из версий которого определяется формулой

То есть, ключ для EDE3 имеет длину 56 ґ 3 = 168 бит, и шифрование 64-битового блока осуществляется шифрованием с одним подключом, расшифрованием с другим и затем шифрованием с третьим. (Причина, по которой вторым шагом является , а не , является совместимость с DES: если выбрать K=k,k,k, то EDE3_K = DES_k. Причина использования DES три раза вместо двух заключается в существовании атаки «встреча в середине» на двойной DES.)

Проблема с тройным DES состоит в том, что он гораздо медленнее, чем сам DES – его скорость составляет ровно одну треть исходной. При использовании EDE3 в режиме сцепления блоков это замедление скажется как на аппаратном, так и на программном (даже если попытаться компенсировать его дополнительной аппаратной частью) уровнях. Во многих случаях такое падение производительности неприемлемо.

В 1984 г. Рон Ривест предложил расширение DES, называемое DESX (DES eXtended), свободное от недостатков тройного DES.

DESX определяется как

= k₂ Е DES_k(k₁ Е x)

То есть, ключ DESX K = k,k₁,k₂ состоит из 54+64+64=184 бит и включает три различных подключа: ключ «DES» k, предварительный «зашумляющий» ключ k₁ и завершающий «зашумляющий» ключ k₂.

Для шифрования блока сообщения мы складываем его поразрядно по модулю 2 с k₁, шифруем его алгоритмом DES с ключом k и вновь поразрядно складываем его по модулю 2 с k₂. Таким образом, затраты DESX на шифрование блока всего на две операции сложения по модулю 2 больше, чем затраты исходного алгоритма.

В отношении DESX замечательно то, что эти две операции «исключающее ИЛИ» делают шифр гораздо менее уязвимым по отношению к перебору ключей. Укажем, что DESX затрудняет получение даже одной пары <x_i, DESX_K(x_i)> в том случае, когда злоумышленник организует атаку на шифр по выбранному исходному тексту, получая множество пар <P_j, DES_K(P_j)>.

DESX предназначался для увеличения защищенности DES против перебора ключей и сохранения его стойкости против других возможных атак. Но DESX в действительности также увеличивает стойкость против дифференциального и линейного криптоанализа, увеличивая требуемое количество проб с выбранным исходным текстом до величины, превышающей 2⁶⁰. Дальнейшее увеличение стойкости против этих атак может быть достигнуто заменой в DESX операции «исключающее ИЛИ» на сложение, как это было сделано в

= k₂ + DES_k(k₁ + x),

где сложение определяется следующим образом: L.R + L'.R' = (L а L').(R а R'), |L|=|R|=|L'|=|R'|= 32, а а обозначает сложение по модулю 2³².

Сказанное не означает, что невозможно построить машину, раскрывающую DESX за приемлемое время. Но оно подразумевает, что такая машина должна использовать какую-либо радикально новую идею. Это не может быть машина, реализующая перебор ключей в общепринятом смысле.

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

Но практически употребляется лишь похожий на DES алгоритм IDEA – Improved Proposed Encryption Standard – улучшенный стандарт шифрования. Он отличается длиной ключа в 128 бит и смещением операций разных алгебраических групп для блоков длины 64 бита. Алгоритм IDEA разработан в Цюрихе Джеймсом Мэсси и опубликован в 1990 году. В отличие от алгоритмов FEAL, REDOC-II, LOKI, он выдержал множество атак критографов Англии, Германии, Израиля. Он считается более стойким, чем традиционный DES.

АЛГОРИТМ ШИФРОВАНИЯ ДАННЫХ IDEA

Алгоритм IDEA (International Data Encryption Algorithm) является блочным шифром. Он оперирует 64-биовыми блоками открытого текста. Несомненным достоинством алгоритма IDEA является то, что его ключ имеет длину 128 бит. Один и тот же алгоритм используется и для шифрования, и для расшифрования.

Первая версия алгоритма IDEA была предложена в 1990 г., ее авторы – х. Лей и Дж. Мэсси. Первоначальное название алгоритма PES (Proposed Encryption Standard). Улучшенный вариант этого алгоритма, разработанных в 1991 г., получил название IPES (Improved Proposed Encryption Standard). В 1992 г. IPES, изменил свое имя на IDEA. Как и большинство других блочных шифров, алгоритм IDEA использует при шифровании процессы смешивания и рассеивания, причем все процессы легко реализуются аппаратными и программными средствами.

В алгоритме IDEA используются следующие математические операции:

· Поразрядное сложение по модулю 2 (операция «исключающее ИЛИ»); обозначается как ;

· сложение беззнаковых целых по модулю 2¹⁶(модуль 65536): операция обозначается как ;

· умножение целых по модулю (2¹⁶-1) (модуль 65536), рассматриваемых как беззнаковые целые, за исключением того, что блок из нулей рассматривается как 2¹⁶; операция обозначается как .

Все операции выполняются над 16-битовыми субблоками.

Эти три операции несовместимы в том смысле, что:

· никакая пара из этих трех операций не удовлетворяет ассоциативному закону, например а (b c)≠(a b) c;

· никакая пара из этих трех операций не удовлетворяет дистрибутивному закону, например а (b c)≠(a b) (a c)

Комбинирование этих трех операций обеспечивает комплексное преобразование входа, существенно затрудняя криптоанализ IDEA по сравнению с DES, который базируется исключительно на операции «исключающее ИЛИ».

Общая схема алгоритма IDEA приведена на рис. 3.10. 64-битовый блок данных делится на четыре 16-битовых субблока. Эти четыре субблока становятся входом в первый цикл алгоритма. Всего выполняется восемь циклов. Между циклами второй и третий субблоки меняются местами. В каждом цикле имеет место следующая последовательность операций:

(1) - умножение субблока Х₁ и первого подключа.

(2) - сложение субблока Х₂ и второго подключа.

(3) - сложение субблока Х₃ и третьего подключа.

(4) - умножение субблока Х₄ и четвертого подлюча.

(5) - сложение результатов шагов (1) и (3).

(6) - сложение результатов шагов (2) и (4).

(7) - умножение результата шага (5) и пятого подключа.

(8) - сложение результатов шагов (6) и (7).

(9) - умножение результата шага (8) с шестым подлючом.

(10) - сложение результатов шагов (7) и (9).

(11) - сложение результатов шагов (1) и (9).

(12) - сложение результатов шагов (3) и (9).

(13) - сложение результатов шагов (2) и (10).

(14) - сложение результатов шагов (4) и (10).

Выходом цикла являются четыре субблока, которые получают как результаты выполнения шагов (11), (12), (13) и (14). В завершение цикла переставляют местами два внутренних субблока (за исключением последнего цикла), и в результате формируется выход для следующего цикла.

Обозначения:

X_i – 16-битовый субблок открытого текста, i=1…4

Y_j – 16-битовый субблок шифртекста, j=1…4

Z_j⁽^r⁾ – 16-битовый подключ (субблок ключа), j=1…6, r=1…8

– поразрядное суммирование по модулю 2 16-битовых субблоков

б – сложение по модулю 2¹⁶16-битовых целых

т – умножение по модулю 2¹⁶16-битовых целых (с нулевым субблоком, соответствующим 2¹⁶)

Рис. 3.10. Схема алгоритма IDEA (режим шифрования)

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

(1) - умножение субблока Х₁ и первого подлюча.

(2) - сложение субблока Х₂ и второго подключа.

(3) - сложение субблока Х₃ и третьего подключа.

(4) - умножение субблока Х₄ и четвертого подключа.

Наконец, эти результирующие четыре субблока Y₁…Y₄ вновь объединяют для получения блока шифртекста.

Создание подключей Z_j также относительно несложно. Алгоритм использует всего 52 подключа (по шесть для каждого из восьми циклов и еще четыре для преобразования выхода). Сначала 128-битовый ключ делят на восемь 16-битовых подключей. Это – первые восемь подключей для алгоритма (шесть подключей – для первого цикла и два подключа – для второго цикла). Затем 128-битовый ключ циклически сдвигается влево на 25 бит и снова делится на восемь подключей. Первые четыре из них используют во втором цикле; последние четыре – в третьем цикле. Ключ снова циклически сдвигается влево еще на 25 бит для получения следующих восьми подключей т.д., пока выполнение алгоритма не завершиться.

Расшифрование осуществляют аналогичным образом, за исключением того, что порядок использования подключей становится обратным, причем ряд значений подключей заменяется на обратные значения. Подключи расшифрования являются в основном либо аддитивными, либо мультипликативными обратными величинами подключей шифрования (табл. 3.10).

Таблица 3.10

Подключи шифрования и расшифрования алгоритма IDEA

Цикл	Подключи шифрования	Подключи расшифрования
	Z₁⁽¹⁾ Z₂⁽¹⁾ Z₃⁽¹⁾ Z₄⁽¹⁾ Z₅⁽¹⁾ Z₆⁽¹⁾	Z₁^(9)-1 -Z₂⁽⁹⁾ -Z₃⁽⁹⁾ Z₄^(9)-1 Z₅⁽⁸⁾ Z₆⁽⁸⁾
	Z₁⁽²⁾ Z₂⁽²⁾ Z₃⁽²⁾ Z₄⁽²⁾ Z₅⁽²⁾ Z₆⁽²⁾	Z₁^(8)-1 -Z₃⁽⁸⁾ -Z₂⁽⁸⁾ Z₄^(8)-1 Z₅⁽⁷⁾ Z₆⁽⁷⁾
	Z₁⁽³⁾ Z₂⁽³⁾ Z₃⁽³⁾ Z₄⁽³⁾ Z₅⁽³⁾ Z₆⁽³⁾	Z₁^(7)-1 -Z₃⁽⁷⁾ -Z₂⁽⁷⁾ Z₄^(7)-1 Z₅⁽⁶⁾ Z₆⁽⁶⁾
	Z₁⁽⁴⁾ Z₂⁽⁴⁾ Z₃⁽⁴⁾ Z₄⁽⁴⁾ Z₅⁽⁴⁾ Z₆⁽⁴⁾	Z₁^(6)-1 -Z₃⁽⁶⁾ -Z₂⁽⁶⁾ Z₄^(6)-1 Z₅⁽⁵⁾ Z₆⁽⁵⁾
	Z₁⁽⁵⁾ Z₂⁽⁵⁾ Z₃⁽⁵⁾ Z₄⁽⁵⁾ Z₅⁽⁵⁾ Z₆⁽⁵⁾	Z₁^(5)-1 -Z₃⁽⁵⁾ -Z₂⁽⁵⁾ Z₄^(5)-1 Z₅⁽⁴⁾ Z₆⁽⁴⁾
	Z₁⁽⁶⁾ Z₂⁽⁶⁾ Z₃⁽⁶⁾ Z₄⁽⁶⁾ Z₅⁽⁶⁾ Z₆⁽⁶⁾	Z₁^(4)-1 -Z₃⁽⁴⁾ -Z₂⁽⁴⁾ Z₄^(4)-1 Z₅⁽³⁾ Z₆⁽³⁾
	Z₁⁽⁷⁾ Z₂⁽⁷⁾ Z₃⁽⁷⁾ Z₄⁽⁷⁾ Z₅⁽⁷⁾ Z₆⁽⁷⁾	Z₁^(3)-1 -Z₃⁽³⁾ -Z₂⁽³⁾ Z₄^(3)-1 Z₅⁽²⁾ Z₆⁽²⁾
	Z₁⁽⁸⁾ Z₂⁽⁸⁾ Z₃⁽⁸⁾ Z₄⁽⁸⁾ Z₅⁽⁸⁾ Z₆⁽⁸⁾	Z₁^(2)-1 -Z₃⁽²⁾ -Z₂⁽²⁾ Z₄^(2)-1 Z₅⁽¹⁾ Z₆⁽¹⁾
Преобразование выхода	Z₁⁽⁹⁾ Z₂⁽⁹⁾ Z₃⁽⁹⁾ Z₄⁽⁹⁾	Z₁^(1)-1 -Z₃⁽¹⁾ -Z₂⁽¹⁾ Z₄^(1)-1

Для реализации алгоритма IDEA было принято предложение, что нулевой субблок равен 2¹⁶=-1; при этом мультипликативная обратная величина от 0 равна 0 [102]. Вычисление значений мультипликативных обратных величин требует некоторых затрат, но это приходиться делать только один раз для каждого ключа расшифрования

⇐ Предыдущая 4 5 6 7 8910 11 12 13 Следующая ⇒