Стандарт шифрования данных DES (Data Encryption Standart) опубликован Национальным бюро стандартов США в 1977 г. В 1980 г. этот алгоритм был принят Национальным институтом стандартов и технологий США (НИСТ) в качестве стандарта шифрования данных для защиты от несанкционированного доступа к важной, но несекретной информации в государственных и коммерческих организациях США.
К достоинствам DES можно отнести простоту ключевой системы, высокую скорость аппаратной и программной реализации, достаточно высокую криптографическую стойкость алгоритма шифрования при заданной длине ключа.
Алгоритм DES, используя комбинацию ряда подстановок и перестановок, осуществляет шифрование 64-битовых блоков данных с помощью 56-битового ключа k.
Процесс шифрования состоит в начальной перестановке битов входного блока, шестнадцати циклах шифрования и, наконец, конечной перестановке битов.
Отметим, что все приводимые ниже таблицы являются стандартными и должны использоваться при реализации алгоритма DES в неизменном виде. Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс вскрытия шифра путем подбора ключа.
В приводимом ниже описании алгоритма DES использованы следующие обозначения:
Li и Ri– левая и правая половины 64-битного i-го исходного блока;
Å – операция побитового сложения векторов-блоков по модулю 2;
ki – 48-битовые ключи;
f – функция шифрования;
IP – начальная перестановка степени 64.
При зашифровании очередного блока Т его биты подвергаются начальной перестановке IP согласно табл. 9.
Таблица 9.Начальная перестановка IP
При этом бит 58 блока Т становится битом 1, бит 50 битом 2 и т. д. Полученный после перестановки блок IP(Т) разделяется на две половины: L0, состоящую из 32 старит бит, и R0, состоящую из 32 младших бит.
Затем выполняется итеративный процесс шифрования, состоящий из 16 циклов преобразования Фейстеля. Результат i-й итерации Тi=LiRiопределяется формулами (5.1), где Y1 =Li a Y2 =Ri
Результатом последней итерации является блок Т16=L16R16. По окончании шифрования осуществляется восстановление позиций битов применением к Т16 обратной перестановки IP -1.
При расшифровании данных все действия выполняются в обратном порядке.
Для вычисления значения функции f используются:
функция расширения Е; преобразование S, составленное из восьми преобразований S-блоков S1,S2,...,S8; перестановка Р. Аргументами функции f являются вектор Ri-1 (32 бита) и вектор ki (48 бит). Функция Е "расширяет" 32-битовый вектор Ri-1 до 48-битового вектора Е(Ri-1) путем дублирования некоторых битов вектора Ri-1, при этом порядок следования битов в Е(Ri-1) указан в табл. 10.
Таблица 10
Первые три бита в Е(Ri-1) – это соответственно биты 32, 1 и 2 вектора Ri-1, а последние три бита – это соответственно биты 31, 32, 1 вектора Ri-1.
Полученный результат складывается побитно по модулю 2 с текущим значением ключа ki и затем представляется в виде восьми последовательных 6-битовых блоков В1,..., В8.
Далее каждый из блоков Вj трансформируется в 4-битовый блок Вj¢ с помощью подходящей таблицы S-блока Sj , список которых приведен в табл. 11. Преобразование блока Вj в Вj¢ осуществляется следующим образом. Пусть, например, В2 равен 111010. Первый и последний разряды (10) являются двоичной записью числа a. Аналогично средние 4 разряда (1101) представляют число b. В нашем примере a =2, b = 13. Таким образом, пара (a, b) однозначно определяет число, находящееся в таблице S2 на пересечении строки с номером а и столбца с номером b. В данном случае это число равно 3. Записывая его в двоичной форме, получаем В2, равный 0011.
Значение f(Ri-1 , ki) теперь получается применением перестановки битов Р, заданной таблицей 12 к результирующему 32-битовому блоку В1¢В2¢…В8¢.
На каждой итерации используется текущее значение ключа ki (48 бит), получаемое из исходного ключа k следующим образом.
Сначала пользователи выбирают сам ключ k, содержащий 56 случайных значащих битов. Восемь битов, находящихся в позициях 8,16,...,64, добавляются в ключ таким образом, чтобы каждый байт содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. Значащие 56 бит ключа подвергаются перестановке, приведенной в табл. 13.
Таблица 13
Эта перестановка определяется двумя блоками С0и D0 по 28 бит в каждом (они занимают соответственно верхнюю и нижнюю половины таблицы). Так, первые три бита в С0 есть соответственно 57, 49, 41 биты ключа. Затем индуктивно определяются блоки Сiи Di, i = 1,…,16.
Если уже определены C i-1 и Di-1, тo Сi, и Di получаются из них одним или двумя левыми циклическими сдвигами согласно табл. 14.
Таблица 14
i
Число сдвигов
Теперь определим ключи ki, 1 £ i £ 16. Ключ ki состоит из 48 битов, выбираемых из битов блока СiDiсогласно таблице 15. Первыми тремя битами в ki являются биты 14, 17, 11 из блока СiDi. Отметим, что 8 из 56 бит (с номерами 9, 18, 22, 25, 35, 38, 43, 54) из СiDiотсутствуют в ki.
Таблица 15
Сделаем несколько замечаний.
Нелинейность преобразований, осуществляемых DES, определяется только S-блоками. Их выбор не имеет достаточно обстоятельного обоснования. Высказывались мнения о том, что S-блоки имеют некоторую "лазейку", позволяющую осуществлять контроль за шифрованной перепиской. Официальная же версия такова. В 1976 г. АНБ заявило, что выбор S-блоков определен следующими требованиями:
– каждая строка табличного задания каждого S-блока должна являться перестановкой множества {0,1,...,15};
– S-блоки не должны являться линейными или аффинными функциями своих входов;
– изменение одного бита входа S-блока должно приводить к изменению, по крайней мере, двух битов выхода;
– для каждого S-блока и любого входа х значение S(x) и S(xÅ(0,0,1,1,0,0)) должны различаться, по крайней мере, двумя битами.
Криптоанализ DES приводит ко многим нелинейным системам уравнений. Дело в том, что каждый бит блока шифртекста является функцией от всех битов блока открытого текста и ключа. Известные аналитические методы вскрытия DES не дают существенного выигрыша по сравнению с полным перебором всего множества из 256 ключей. К недостаткам алгоритма DES относится небольшое (по современным меркам) число ключей, что дает возможность их полного перебора на быстродействующей вычислительной технике за реальное время.
Официально DES являлся стандартом шифрования данных до 31 декабря 1998 г. В 1997 г. был объявлен конкурс на новый стандарт, который был назван AES (Advanced Encryption Standard). 2 октября 2000 г. Национальный институт стандартов и технологий (НИСТ) США объявил победителя "конкуpca AES". Однако для того, чтобы этот алгоритм завоевал мировое признание, необходимы серьезные исследования его свойств специалистами различных стран.
