Алгоритм DES и его модификации
Американский стандарт криптографического закрытия данных DES
(Data Encryption Standard) является типичным представителем семейства блочных шифров. Этот шифр допускает эффективную аппаратную и программную реализацию, причем возможно достижение скоростей шифрования до нескольких мегабайт в секунду. Шифр DES представляет собой результат 33 отображений:
DES = IP-1ґ
где IP (Initial Permutation
– исходная перестановка) представляет собой проволочную коммутацию с инверсией IP?1;
композиция
перестановка местами половин блока не производится.
Подстановки
Шаг 1. На i-м цикле входной блок xi
длиной 64 символа
xi = (xi,0, xi,1 ..., xi,63)
делится на два блока по 32 символа X= (xi,0, xi,1 ..., xi,31) и X' = (x'i,0, x'i,1 ..., x'i,31).
Правый блок X' разбивается на восемь блоков по четыре символа:
| x'i,0 | x'i,1 | x'i,2 | x'i,3 | ||||
| x'i,4 | x'i,5 | x'i,6 | x'i,7 | ||||
| x'i,8 | x'i,9 | x'i,10 | x'i,11 | ||||
| x'i,12 | x'i,13 | x'i,14 | x'i,15 | ||||
| x'i,16 | x'i,17 | x'i,18 | x'i,19 | ||||
| x'i,20 | x'i,21 | x'i,22 | x'i,23 | ||||
| x'i,24 | x'i,25 | x'i,26 | x'i,29 | ||||
| x'i,28 | x'i,29 | x'i,30 | x'i,31 |
Эти восемь блоков путем копирования крайних элементов преобразуются в восемь блоков из шести символов:
| xi,31 | xi,0 | xi,1 | xi,2 | xi,3 | xi,4 | ||||||
| xi,3 | xi,4 | xi,5 | xi,6 | xi,7 | xi,8 | ||||||
| xi,7 | xi,8 | xi,9 | xi,10 | xi,11 | xi,12 | ||||||
| xi,11 | xi,12 | xi,13 | xi,14 | xi,15 | xi,16 | ||||||
| xi,15 | xi,16 | xi,17 | xi,18 | xi,19 | xi,20 | ||||||
| xi,19 | xi,20 | xi,21 | xi,22 | xi,23 | xi,24 | ||||||
| xi,23 | xi,24 | xi,25 | xi,26 | xi,27 | xi,28 | ||||||
| xi,27 | xi,28 | xi,29 | xi,30 | xi,31 | xi,0 |
Шаг 2. На i- циклической итерации 48 разрядов ключа
(ki,0, ki,1, ... , ki,47).
поразрядно суммируются (по модулю 2) с полученными выше 48 разрядами данных.
Шаг 3. j-й блок из шести символов (0Ј j <8) подается на вход блока подстановки (S-бокс) S[j] имеет шестиразрядный вход и четырехразрядный выход и представляет собой четыре преобразования из Z2,4
в Z2,4; два крайних разряда входного блока служат для выборки одного из этих преобразований. Каждая из восьми подстановок S[0], S[1],..., S[7] осуществляется с использованием четырех строк и 16 столбцов матрицы с элементами {0,1,...,15}. Каждый из массивов размерностью 4ґ16 определяет подстановку на множестве Z2,4
следующим образом. Если входом является блок из шести символов
(z0, z1, z2, z3, z4, z5),
то две крайние позиции (z0, z5) интерпретируются как двоичное представление целых чисел из набора {0,1,2,3}.
Эти целые определяют номер строки (от 0 до 3). Оставшиеся четыре символа (z1, z2, z3, z4) интерпретируются как двоичное представление целых чисел из набора {0,1,...,15} и служат для определения столбца в массиве (от 0 до 15). Таким образом, входной блок (0,0,1,0,1,1) соответствует строке 1 и столбцу 5.
Шаг 4. 32 разряда, составляющие выход S-бокса, подаются на вход блока проволочной коммутации (P-бокс).
Шаг 5. Компоненты правого входного 32-разрядного блока X', преобразованного в T(X'), поразрядно суммируются по модулю 2 с компонентами левого входного 32-разрядного блока X.
На каждой итерации используется 48-разрядный ключ (ki,0, ki,1 ..., ki,47). Поскольку входным ключом DES является 56-разрядный блок k
= = (ki,0, ki,1 ..., ki,55), то каждый его разряд используется многократно.
Какой именно из ключей используется на i-циклической итерации, определяется списком ключей. Для описания списка ключей введены дополнительные элементы.
Ключ определяется по следующему алгоритму:
производится начальная перестановка PC-1 ключа 56-разрядного ключа пользователя k = (ki,0, ki,1 ..., ki,55). Получаемый в результате 56-разрядный блок рассматривается как два 28-разрядных блока: левый – C0 и правый – D0;
производится левый циклический сдвиг блоков C0
и D0 s[1] раз для получения блоков C1
и D1;
из сцепления блоков (C1, D1) выбираются 48 разрядов с помощью перестановки PC-2. Эти разряды используются на первой итерации;
используемые на i-й циклической итерации разряды ключа определяются методом индукции. Для получения блоков Ci
и Di производим левый циклический сдвиг s[i] раз блоков Ci–1 и Di–1.
Инверсией DES (обеспечивающей расшифрование зашифрованных посредством DES данных) является
DES-1 = IP-1ґpT1ґp*ґ...ґp*ґ
pT16 ґIP, (2.2)
Расшифрование зашифрованного посредством DES текста осуществляется с использованием тех же блоков благодаря обратимости преобразования.
Таков общий алгоритм DES. Попробуем проанализировать его эффективность.
Поскольку длина блоков исходного текста равна 64, поддержка каталогов частот использования блоков является для злоумышленника задачей, выходящей за пределы современных технических возможностей.
Однако, данный алгоритм, являясь первым опытом стандарта шифрования имеет ряд недостатков. За время, прошедшее после создания DES, компьютерная техника развилась настолько быстро, что оказалось возможным осуществлять исчерпывающий перебор ключей и тем самым раскрывать шифр. Стоимость этой атаки постоянно снижается. В 1998 г. была построена машина стоимостью около 100000 долларов, способная по данной паре <исходный текст, шифрованный текст> восстановить ключ за среднее время в 3 суток. Таким образом, DES, при его использовании стандартным образом, уже стал далеко не оптимальным выбором для удовлетворения требованиям скрытности данных.
Было выдвинуто большое количество предложений по усовершенствованию DES, которые отчасти компенсируют указанные недостатки. Мы рассмотрим два из них.
Наиболее широко известным предложением по усилению DES является так называемый «тройной DES», одна из версий которого определяется формулой
То есть, ключ для EDE3 имеет длину 56 ґ 3 = 168 бит, и шифрование 64-битового блока осуществляется шифрованием с одним подключом, расшифрованием с другим и затем шифрованием с третьим. (Причина, по которой вторым шагом является
= DESk. Причина использования DES три раза вместо двух заключается в существовании атаки «встреча в середине» на двойной DES.)
Проблема с тройным DES состоит в том, что он гораздо медленнее, чем сам DES – его скорость составляет ровно одну треть исходной. При использовании EDE3 в режиме сцепления блоков это замедление скажется как на аппаратном, так и на программном (даже если попытаться компенсировать его дополнительной аппаратной частью) уровнях. Во многих случаях такое падение производительности неприемлемо.
В 1984 г. Рон Ривест предложил расширение DES, называемое DESX (DES eXtended), свободное от недостатков тройного DES.
DESX определяется как
То есть, ключ DESX K = k,k1,k2
состоит из 54+64+64=184 бит и включает три различных подключа: ключ «DES» k, предварительный «зашумляющий» ключ k1 и завершающий «зашумляющий» ключ k2.
Для шифрования блока сообщения мы складываем его поразрядно по модулю 2 с k1, шифруем его алгоритмом DES с ключом k и вновь поразрядно складываем его по модулю 2 с k2. Таким образом, затраты DESX на шифрование блока всего на две операции сложения по модулю 2 больше, чем затраты исходного алгоритма.
В отношении DESX
замечательно то, что эти две операции «исключающее ИЛИ» делают шифр гораздо менее уязвимым по отношению к перебору ключей. Укажем, что DESX
затрудняет получение даже одной пары <xi, DESXK(xi)> в том случае, когда злоумышленник организует атаку на шифр по выбранному исходному тексту, получая множество пар <Pj, DESK(Pj)>.
DESX предназначался для увеличения
защищенности DES против перебора ключей и сохранения его стойкости против других возможных атак. Но DESX в действительности также увеличивает стойкость против дифференциального и линейного криптоанализа, увеличивая требуемое количество проб с выбранным исходным текстом до величины, превышающей 260. Дальнейшее увеличение стойкости против этих атак может быть достигнуто заменой в DESX операции «исключающее ИЛИ» на сложение, как это было сделано в
+ x)
где сложение определяется следующим образом: L.R + L'.R' = (L а L').(R а R'), |L|=|R|=|L'|=|R'|= 32, а а обозначает сложение по модулю 232.
Сказанное не означает, что невозможно построить машину, раскрывающую DESX за приемлемое время. Но оно подразумевает, что такая машина должна использовать какую-либо радикально новую идею. Это не может быть машина, реализующая перебор ключей в общепринятом смысле.
Таким образом, практически во всех отношениях DESX
оказывается лучше DES. Этот алгоритм прост, совместим с DES, эффективно реализуем аппаратно, может использовать существующее аппаратное обеспечение DES и в его отношении было доказано, что он увеличивает стойкость к атакам, основанным на переборе ключей.
