Американский алгоритм шифрования DES был разработан в 1976 году Национальным институтом стандартов и технологий (NIST) и опубликован в 1977 году. Само это событие стало беспрецедентным в мировой практике, поскольку, хотя всегда и предполагается, что криптоаналитику известен алгоритм шифрования, они обычно никогда не публиковались и хранились в секрете. Американские разработчики применили новый подход, заявив, что криптоанализ созданного алгоритма по сложности сопоставим с перебором всех 256 возможных ключей, поэтому его публикация гарантированно не влечет ослабления криптосистемы, и все желающие могут попытаться выявить недостатки предложенной схемы. Таким образом, дополнительно они обеспечили себе всемирное тестирование.
Алгоритм DES официально действовал в качестве стандарта с 1980 по 1998 год, когда производительность вычислительной техники достигла такого уровня, что перебор всех возможных ключей стал возможен за короткое время (например, распределив диапазоны ключей по тысячам компьютеров в сети Internet, можно добиться дешифрования в течение суток).
В связи с этим в 1997 году NIST объявил конкурс на создание нового стандарта AES (Advanced Encryption Standard), который завершился в 2000 году принятием нового стандарта на базе алгоритма Rijndael. В течение же переходного периода применялся алгоритм 3-DES, который использует ключ в три раза длиннее (168 бит) и заключается в следующем:
1. Текст шифруется алгоритмом DES при помощи первых 56 бит ключа.
2. Полученная в п.1 комбинация расшифровывается по алгоритму DES с использованием следующих 56 бит ключа.
3. Полученная в п.2 комбинация шифруется алгоритмом DES при помощи последних 56 бит ключа.
4. Расшифрование шифртекста алгоритма 3-DES производится в обратном порядке.
Таким образом, базовая процедура осталась неизменной, она лишь удлинилась, что позволило увеличить ключ до неприемлемой, с точки зрения тотального перебора, длины.
Сам алгоритм DES, как и многие блочные шифры замены, имеет четыре модификации:
1. Electronic Code Book (ECB) – электронная кодовая книга, базовая версия алгоритма.
2. Cipher Block Chaining (CBC) – режим сцепления блоков, когда очередной блок шифртекста побитно складывается по модулю 2 со следующим блоком открытого текста, а первый блок складывается со специальным секретным инициирующим вектором. Этим достигается общая связанность всего шифруемого текста, усиливающая стойкость алгоритма. Данная модификация используется наиболее часто.
3. Output Feed Back (OFB) – режим обратной связи по выходу, здесь инициирующий вектор перед применением тоже шифруется, в отличие от предыдущего режима. Этот режим используется для генерации данных аутентификации.
4. Cipher Feed Back (CFB) – режим обратной связи по шифртексту, то же, что и OFB, только инициирующий вектор создается из самого открытого текста. Этот режим используется в основном для генерации псевдо случайных чисел (последовательностей).
В целом процесс шифрования включает следующие этапы:
1. Подготовка преобразующих комбинаций из ключа KEY.
2. Начальная перестановка блока открытого текста длиной 64 бита.
3. 16 проходов преобразования блока, полученного в п. 2.
4. Конечная перестановка блока, полученного в п. 3, который и является шифртекстом длиной также 64 бита.
Опишем их подробнее.
Подготовка преобразующих комбинаций.
1. В ключевой комбинации из 56 бит после каждых семи бит вставляется еще один, который дополняет предыдущие семь до нечетного количества единиц. Таким образом получается комбинация TK из 64 бит.
2. Комбинация TK подвергается перестановке для получения 56 бит:
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 64 53 45 37 29
21 13 5 28 20 12 4
3. В полученной перестановке первые 28 бит объявляются как C0, а следующие 28 бит как D0.
4. Путем циклического сдвига влево соответствующих комбинаций с предыдущим номером генерируется по 16 комбинаций Ci и Di (i = 1 … 16). Так для получения C1 и D1 производят сдвиг C0 и D0, для C2 и D2 – C1 и D1 и т.д. Количество сдвигаемых разрядов n зависит от номера комбинации и указано в табл. 9.2.
Таблица 9.2
i
n
5. На основе следующей перестановки соответствующих блоков CiDi генерируется 16 ключевых комбинаций Ki (i = 1 … 16) по 48 бит, которые и будут непосредственно использоваться при шифровании:
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
Начальная перестановка блока открытого текста.
1. Очередной шифруемый блок открытого текста W из 64 бит переставляется для получения комбинации W' следующим образом:
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
2. Полученная комбинация W' представляется как комбинация первых своих 32 бит, обозначаемых L0, и следующих 32 бит, обозначаемых R0.
16 проходов преобразования Фейстеля.
Последовательным образом вычисляется по 16 комбинаций Li и Ri (i = 1 … 16) исходя из следующих соотношений (здесь xor – побитное исключающее ИЛИ):
Li = Ri–1; Ri = Li–1 xor f(Ri–1, Ki)
Конечная перестановка.
Полученная комбинация из 64 бит R16L16 подвергается перестановке, которая является обратной к начальной перестановке (т.е. биты возвращаются на исходное место):
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25
Полученный таким образом блок из 64 бит и является шифртекстом.
Расшифрование шифртекста происходит по такому же алгоритму, только 16 обратных преобразований Фейстеля начинаются с комбинации R16L16 и выполняются по соотношениям:
Ri–1 = Li; Li–1 = Ri xor f(Li, Ki)
пока не будет получена комбинация L0R0, которая подвергается конечной перестановке, являющейся открытым текстом.
Саму суть алгоритма DES представляет функция шифрования f(X32, Y48). Рассмотрим алгоритм ее вычисления.
1. На вход функции поступает 32-битная комбинация данных X и 48‑битная ключевая комбинация Y.
2. Комбинация данных X расширяется до 48 бит по следующей схеме:
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
3. Над расширенной комбинацией X48 и ключевой комбинацией Y48 производится операция побитного исключающего ИЛИ:
B = X48 xor Y48
4. Комбинация B делится на 8 комбинаций по 6 бит:
B = B1B2B3B4B5B6B7B8
5. Для каждой комбинации Bi существует специальная таблица Si, состоящая из 4-х строк и 16-ти столбцов, пронумерованных, начиная с нуля. Каждый элемент представляет собой число от 0 до 15 (т.е. в двоичном виде 4 бита). На основе этих таблиц каждая комбинация Bi из 6-ти бит преобразуется в комбинацию B'i из 4-х бит, являющуюся каким-либо элементом таблицы Si. Элемент выбирается по следующему правилу: номер строки в таблице образуют крайние биты (левый и правый) комбинации Bi, а номер столбца – внутренние четыре бита.
Например, B7 = 110010. Крайние биты здесь 10 (110010), значит номер строки равен 2. Внутренние биты 1001 (110010), значит номер столбца 9. Элемент выбирается из таблицы S7.
6. В результате получается комбинация из 32-х бит:
B' = B'1B'2B'3B'4B'5B'6B'7B'8
7. Комбинация B' подвергается следующей перестановке:
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
Эта перестановка и является блоком в 32 бита, который представляет результат работы функции шифрования.
Ниже приводятся все 8 таблиц перекодировки, которые не подлежат изменению при реализации алгоритма, поскольку именно они обеспечивают его нелинейность и высокую криптографическую стойкость.
