Алгоритм симметричного шифрования des. Стандарты блочного шифрования

Самым распространенным и наиболее известным алгоритмом симметричного шифрования является DES (Data Encryption Standard). Алгоритм был разработан в 1977 году, в 1980 году был принят NIST (National Institute of Standards and Technology, США) в качестве стандарта.

DES является классической сетью Фейштеля с двумя ветвями. Данные шифруются 64-битными блоками, используя 56-битный ключ. Алгоритм преобразует за несколько раундов 64-битный вход в 64-битный выход. Длина ключа равна 56 битам. Процесс шифрования состоит из четырех этапов. На первом этапе выполняется начальная перестановка (IP) 64-битного исходного текста (забеливание), во время которой биты переупорядочиваются в соответствии со стандартной таблицей. Следующий этап состоит из 16 раундов одной и той же функции, которая использует операции сдвига и подстановки. На третьем этапе левая и правая половины выхода последней (16-й) итерации меняются местами. Наконец, на четвертом этапе выполняется перестановка IP-1 результата, полученного на третьем этапе. Перестановка IP-1 инверсна начальной перестановке.

Рис.4. Алгоритм DES

На рисунке показан способ, в котором используется 56-битный ключ. Первоначально ключ подается на вход функции перестановки. Затем для каждого из 16 раундов подключ K i является комбинацией левого циклического сдвига и перестановки. Функция перестановки одна и та же для каждого раунда, но подключи K i для каждого раунда получаются разные вследствие повторяющегося сдвига битов ключа.

Начальная перестановка и ее инверсия определяются стандартной таблицей. Если М - это произвольные 64 бита, то X = IP (M) - переставленные 64 бита. Если применить обратную функцию перестановки Y = IP-1 (X) = IP-1 (IP(M)), то получится первоначальная последовательность битов.

Описание раунда des

Рассмотрим последовательность преобразований, используемую в каждом раунде.

Рис.5. Иллюстрация раунда алгоритма DES

64-битный входной блок проходит через 16 раундов , при этом на каждой итерации получается промежуточное 64-битное значение. Левая и правая части каждого промежуточного значения трактуются как отдельные 32-битные значения, обозначенные L и R. Каждую итерацию можно описать следующим образом:

R i = L i -1 F(R i -1 , K i)

Таким образом, выход левой половины L i равен входу правой половины R i-1 . Выход правой половины R i является результатом применения операции XOR к L i-1 и функции F, зависящей от R i-1 и K i .

Рассмотрим функцию F более подробно. R i , которое подается на вход функции F, имеет длину 32 бита. Вначале R i расширяется до 48 битов, используя таблицу, которая определяет перестановку плюс расширение на 16 битов. Расширение происходит следующим образом. 32 бита разбиваются на группы по 4 бита и затем расширяются до 6 битов, присоединяя крайние биты из двух соседних групп. Например, если часть входного сообщения

Efgh ijkl mnop . . .

то в результате расширения получается сообщение

Defghi hijklm lmnopq . . .

После этого для полученного 48-битного значения выполняется операция XOR с 48-битным подключом K i . Затем полученное 48-битное значение подается на вход функции подстановки, результатом которой является 32-битное значение.

Подстановка состоит из восьми S-boxes, каждый из которых на входе получает 6 бит, а на выходе создает 4 бита. Эти преобразования определяются специальными таблицами. Первый и последний биты входного значения S-box определяют номер строки в таблице, средние 4 бита определяют номер столбца. Пересечение строки и столбца определяет 4-битный выход. Например, если входом является 011011, то номер строки равен 01 (строка 1) и номер столбца равен 1101 (столбец 13). Значение в строке 1 и столбце 13 равно 5, т.е. выходом является 0101.

Далее полученное 32-битное значение обрабатывается с помощью перестановки Р, целью которой является максимальное переупорядочивание битов, чтобы в следующем раунде шифрования с большой вероятностью каждый бит обрабатывался другим S-box.

Ключ для отдельного раунда K i состоит из 48 битов. Ключи K i получаются по следующему алгоритму. Для 56-битного ключа, используемого на входе алгоритма, вначале выполняется перестановка в соответствии с таблицей Permuted Choice 1 (РС-1). Полученный 56-битный ключ разделяется на две 28-битные части, обозначаемые как C0 и D0 соответственно. На каждом раунде C i и D i независимо циклически сдвигаются влево на 1 или 2 бита, в зависимости от номера раунда. Полученные значения являются входом следующего раунда. Они также представляют собой вход в Permuted Choice 2 (РС-2), который создает 48-битное выходное значение, являющееся входом функции F(R i-1 , K i).

Процесс дешифрования аналогичен процессу шифрования. На входе алгоритма используется зашифрованный текст, но ключи K i используются в обратной последовательности. K 16 используется на первом раунде, K 1 используется на последнем раунде. Пусть выходом i-ого раунда шифрования будет L i ||R i . Тогда соответствующий вход (16-i)-ого раунда дешифрования будет R i ||L i .

После последнего раунда процесса расшифрования две половины выхода меняются местами так, чтобы вход заключительной перестановки IP-1 был R 16 ||L 16 . Выходом этой стадии является незашифрованный текст.

Прошло уже белее 30 лет с даты принятия алгоритма DES в качестве стандарта шифрования США. DES - алгоритм шифрования с наиболее богатой и интересной историей.

История создания алгоритма

Один из наиболее известных в мире криптологов Брюс Шнайер в своей знаменитой книге «Прикладная криптография» так описал проблемы пользователей средств защиты информации в начале 70-х гг. XX века (естественно, речь идет о пользователях по ту сторону «железного занавеса»):

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

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

Данной проблемой озаботилось Национальное Бюро Стандартов (National Bureau of Standards, NBS) США. В результате в 1973 г. был объявлен первый в истории открытый конкурс на стандарт шифрования. NBS было готово исследовать с целью выбора стандарта алгоритмы-претенденты, удовлетворяющие следующим критериям:

Алгоритм должен быть криптографически стойким;

Алгоритм должен быть быстрым;

П структура алгоритма должна быть четкой и ясной;

Стойкость шифрования должна зависеть только от ключа, сам алгоритм не должен быть секретным;

Алгоритм должен быть легко применим для различных целей;

Алгоритм должен легко реализовываться аппаратно на существующей элементной базе.

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

Фактически алгоритм-претендент оказался всего один: это был разработанный фирмой ШМ алгоритм шифрования Lucifer {см. разд. 3.31). В течение двух лет проводилась доработка алгоритма:

Во-первых, NBS совместно с Агентством Национальной Безопасности (АНБ, NSA - National Security Agency) США был проведен тщательный анализ алгоритма, результатом которого явилась его достаточно существенная переработка;

Во-вторых, принимались к рассмотрению комментарии и критические замечания от всех заинтересованных организаций и частных лиц.

В результате совместной деятельности IBM, NBS и АНБ в январе 1977 г. DES был опубликован как стандарт США (последняя версия этого стандарта - в документе ) на алгоритм шифрования данных (кроме информации повышенной степени секретности). Алгоритм DES был запатентован фирмой ЮМ, однако NBS получило, фактически, бесплатную и неограниченную лицензию на использование данного алгоритма . Альтернативное, но реже используемое название алгоритма - DEA (Data Encryption Algorithm).

Основные характеристики и структура алгоритма

Алгоритм DES шифрует информацию блоками по 64 бита с помощью 64- битного ключа шифрования, в котором используется только 56 битов (процедура расширения ключа подробно описана далее).

Шифрование информации выполняется следующим образом (рис. 3.56):

1. Над 64-битным блоком данных производится начальная перестановка согласно табл. 3.16.

Таблица 3.16

Таблица трактуется следующим образом: значение входного бита 58 (здесь и далее все биты нумеруются слева направо, начиная с 1-го) помещается в выходной бит 1, значение 50-го бита - в бит 2 и т. д.

2. Результат предыдущей операции делится на 2 субблока по 32 бита (на

рис. 3.56 обозначены А 0 и В 0), над которыми производятся 16 раундов

следующих преобразований:

Как было сказано выше, из 64-битного ключа шифрования алгоритм DES использует только 56 битов. Каждый 8-й бит отбрасывается и никак не применяется в алгоритме, причем использование оставшихся битов ключа шифрования в реализациях алгоритма DES никак не лимитировано стандартом . Процедура извлечения 56 значащих битов 64-битного ключа на рис. 3.59 обозначена как Е. Помимо извлечения, данная процедура выполняет еще и перестановку битов ключа согласно табл. 3.19 и 3.20.

Таблица 3.19

Таблица 3.20

В результате перестановки формируются два 28-битных значения С и D. Таблица 3.19 определяет выборку битов ключа для С, табл. 3.20 - для D.

Затем выполняются 16 раундов преобразований, каждый из которых дает один из ключей раундов K t . В каждом раунде процедуры расширения ключа производятся следующие действия:

1. Текущие значения С и D циклически сдвигаются влево на переменное число битов п. Для раундов 1, 2, 9 и 16 п = 1, в остальных раундах выполняется циклический сдвиг на 2 бита.

2. С и D объединяются в 56-битное значение, к которому применяется сжимающая перестановка CP, результатом которой является 48-битный ключ раунда К (. Сжимающая перестановка выполняется согласно табл. 3.21.

Таблица 3.21

При расшифровании данных можно использовать ту же процедуру расширения ключа, но применять ключи раундов в обратном порядке. Есть и другой вариант: в каждом раунде процедуры расширения ключа вместо циклического сдвига влево выполнять циклический сдвиг вправо на п битов, где гс’ = 0 для первого раунда, и’=1 для раундов 2, 9, 16 и п= 2 для остальных раундов. Такая процедура расширения ключа сразу даст нужные для расшифровывания ключи раундов.

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

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

Преобразования Сетью Фейстеля

Это преобразование над векторами (блоками) представляющими собой левую и правую половины регистра сдвига. В алгоритме DES используются прямое преобразование сетью Фейстеля в шифровании (см. Рис.1) и обратное преобразование сетью Фейстеля в расшифрование (см. Рис.2).

Схема шифрования алгоритма DES

Исходный текст - блок 64 бит.
Шифрованный текст - блок 64 бит.

Процесс шифрования состоит в начальной перестановке, 16 циклах шифрования и конечной перестановке.
Рассмотрим подробную схему алгоритма DES:
L i R i =1,2\ldots.левая и правая половины 64-битового блока L i R i
k i - 48 битовые ключи
f - функция шифрования
IP - начальная перестановка
IP -1 - конечная перестановка. По таблице первые 3 бита результирующего блока IP(T) после начальной перестановки IP являются битами 58, 50, 42 входного блока Т, а его 3 последние бита являются битами 23, 15, 7 входного блока. Дальше 64-битовой блок IP(T) участвует в 16-циклах преобразования Фейстеля.

16 циклов преобразования Фейстеля:

Разбить IP(T) на две части L 0 ,R 0 , где L 0 ,R 0 - соответствено 32 старших битов и 32 младших битов блока T0 IP(T)= L 0 R 0

Пусть T i -1 = L i -1 R i -1 результат (i-1) итерации, тогда результат i-ой интерации T i = L i R i определяется:

L i = R i - 1 Левая половина L i равна правой половине предыдущего вектора L i - 1 R i - 1 . А правая половина R i - это битовое сложение L i - 1 и f(R i - 1 , k i) по модулю 2.

В 16-циклх преобразования Фейстеля функция f играет роль шифрования. Рассмотрим подробно функцию f.

Аргументы функции f являются 32 битовой вектор R i - 1 , 48 битовой ключ k i , которые являются результатом преобразования 56 битового исходного ключа шифра k.

Для вычисления функции f используются фукция расширения Е, преобразование S, состоящее из 8 преобразований S-блоков , и перестановка P.

Функция Е расширяется 32 битовой вектор R i - 1 до 48 битовой вектор E(R i - 1) путем дублирования некоторых битов из R i - 1 при этом порядок битов вектора E(R i - 1) указан в таблице 2. Первые три бита вектора E(R i - 1) являются битами 32, 1, 2 вектора R i -1 . По таблице 2 видно что биты 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 дублируются. Последние 3 биты вектора E(Ri - 1) - это биты 31, 32, 1 вектора R i - 1 . Полученный после перестановки блок E(R i -1) складывается по модулю 2 с ключами k i и затем представляются в виде восьми последовательных блоков B 1 ,B 2 ,...B 8 .
E(R i - 1) = B 1 B 2 ...B 8
Каждый B j является 6-битовым блоком. Далее каждый из блоков B j трансформируется в 4 битовой блок B" j с помощью преобразований S j . Преобразования S j определяется таблицей 3. Предположим что B 3 = 101111 и мы хотим найти B" 3 . Первый и последний разряды B 3 являются двоичной записью числа а, 0Значение функции f(R i - 1 ,k i) (32 бит) получается перестановкой Р, применяемой к 32 битовому блоку B" 1 B" 2 ...B" 8 . Перестановка Р задана таблицей 4.
f(R i - 1 ,k i) = P(B" 1 B" 2 ...B" 8)
Согласно таблице 4, первые четыре бита результирующего вектора после действия функции f - это бита 16, 7, 20, 21 вектора B" 1 B" 2 ...B" 8

Генерирование ключей k i .
Ключи k i получаются из начального ключа k (56 бит = 7 байтов или 7 символов в АSCII) таким образом. Восемь битов, находящих в позициях 8, 16, 24, 32, 40, 48, 56, 64 добавляются в ключ k таким образом чтобы каждый байт содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. Затем делают перестановку для расширенного ключа (кроме добавляемых битов 8, 16, 24, 32, 40, 48, 56, 64). Такая перестановка определенна как в таблице 5.

Эта перестановка определяется двумя блоками C 0 и D 0 по 28 бит каждый. Первые 3 бита C 0 есть биты 57, 49, 41 расширенного ключа. А первые три бита D 0 есть биты 63, 55, 47 расширенного ключа. C i ,D i i=1,2,3…получаются из C i - 1 ,D i - 1 одним или двумя левыми циклическими сдвигами согласно таблице 6.

Ключ k i , i=1,…16 состоит из 48 бит, выбранных из битов вектора C i D i (56 бит) согласно таблице 7. Первый и второй биты k i есть биты 14, 17 вектора C i D i

Конечная перестановка IP - 1 действует на T 16 и используется для востановления позиции. Она является обратной к перестановке IP. Конечная перестановка определяется таблицей 8.
Режимы использования DES DES может используется в четырех режимах.

Режим электронной кодовой книги (ЕСВ - Electronic Code Book): обычное использование DES как блочного шифра (см. Рис.7).

Режим сцепления блоков (СВС - Cipher Block Chaining) (см. Рис.8). Каждый очередной блок C i i>=1, перед зашифровыванием складывается по модулю 2 со следующим блоком открытого текста M i + 1 . Вектор C 0 - начальный вектор, он меняется ежедневно и хранится в секрете.

Режим обратной связи по шифротексту (CFB - Cipher Feed Back) (см. Рис.9). В режиме СFB вырабатывается блочная «гамма» Z 0 ,Z 1 ,...Z i = DESk(C i - 1) . Начальный вектор C 0 сохраняется в секрете.

Режим обратной связи по выходу (OFB - Output Feed Back) (см. Рис.10). В режиме OFB вырабатывается блочная «гамма» Z 0 ,Z 1 ,... , i>=1

Data Encryption Standard (DES) - это стандарт шифрования данных, изобретенный в США в 80-х годах ХХ века. Среди шифров он по праву считается "пенсионером", при этом оставаясь рабочей лошадкой криптографии. DES перестал быть пригодным в условиях сверхбыстрой техники и больших объемов данных из-за ограничений в 56 бит на ключ и 64 бит на данные. Однако он все еще используется.

Что такое блочные шифры?

DES - алгоритм блочного шифрования. За последние 20-30 лет было создано множество блочных шифров, но создать хороший шифр, который был бы безопасным, задача достаточно сложная. Важно, чтобы шифр обладал характеристиками, которые позволят ему функционировать во многих сферах и отраслях.

Блочные шифры состоят из нескольких итераций поочередного использования некоторого шифра. Каждая итерация называется раундом. Как показывает практика, даже некоторые из примитивных алгоритмов при последовательном использовании способны создавать надежные шифры. Алгоритм DES - пример, который оставался надежным и несокрушимым 20 лет.

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

Использование DES

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

Официально алгоритм шифра DES был стандартом в США до 1998 года. В 1997 году началось создание нового стандарта, который был назван System), и хотя криптоанализ показывает, что попытка взломать DES приводит к множеству систем нелинейных уравнений, аналитические методы не способны помочь решить задачу - его слабым местом является малое множество возможных ключей. Их количество равно 2 56 и все варианты можно перебрать при помощи современных технологий за относительно короткий срок.

Один раунд в алгоритме

Для ясности изложения и описания алгоритма DES используем рисунок (линейную диаграмму вычислений) 4.1, показывающий структуру одного раунда.

Каждый прямоугольник в линейной диаграмме представляет собой некие вычисления, а исходящая из него стрелка указывает, куда будут переданы результаты работы блока. Знаком плюс, обведенным в кружок, обозначается операция "исключающего или", называемая в программирование XOR. Операция еще носит имя "побитовое сложение" или "сложение без переноса". В сети можно найти алгоритм DES на C и изучить его для лучшего понимания.

DES принимает текстовый блок, размером 64 бита. Он проходит через начальную перестановку по определенному принципу. При анализе алгоритма выяснилось, что смысла в этой перестановке мало, т. к. она не дает какого-либо криптографического эффекта. Текстовый блок разбивается на 2 равные части: правая (R) и левая (L). Затем шифрованные части меняются местами и объединяются, а в конце раунда получается 64-битовый блок данных, только зашифрованный.

Общий алгоритм

Алгоритм DES включает в себя 16 раундов, совершаемых по схеме, описанной выше. Все раунды пронумерованы через i, где i = (1; 16). Каждый i-ый раунд из пары (Li-1, Ri-1) получает новую пару (Li, Ri), используя ключ Ki. Основные преобразования происходят внутри функции F.

Алгоритм работы функции F

Как видно из рисунка 4.1, R проходит через операцию "Расширение". Данный блок дублирует ряд битов из R и дополняет его ими, получая 48-битное значение. Полученный результат проходит через побитовое сложение с 48-битным ключом Ki. И результат этой операции передается в блок S. Блок S содержит 8 маленьких матриц-подстановок, которые подобраны особым образом.

Каждая матрица получает на входе 6 битов информации и выдает 4-битовое значение. В итоге на входе блок S получает данные размером 48 бит, а на выходе представляет результат в виде 32-битового значения.

Данное 32-битное значение проходит через еще одну операцию перестановки, после чего суммируется операцией xor с L. Наконец правая и левая часть меняются местами и раунд завершается. Как уже говорилось ранее, таких раундов алгоритм совершает 16 штук.

Здесь мы не будем перегружать статью примерами, которые занимают много места. Работу DES и примеры можно посмотреть в сети.

Шифр Фейстеля

Алгоритм DES основан на шифре Фейстеля. Его идея весьма изящна. На каждом раунде часть L складывается со значением F(R, Ki) и L меняется позицией с R. Ключевой особенностью алгоритма Фейстеля является то, что дешифрирование и шифрование состоят из одинаковых шагов: части L и R меняются местами, а затем выполняется операция сложения L и F (R, Ki). Это позволяет сделать процедуры шифрования и расшифровки простыми и понятными.

В шифрах Фейстеля зачастую вводится одно интересное изменение - отмена перестановки L и R в последней итерации. Это делает алгоритмы шифрования и дешифрирования полностью симметричными. Разница заключается только в порядке использования ключей Ki. Этот принцип оказался крайне удобным для использования на программном уровне, так как шифрование и расшифровка происходит средствами одной функции. Например, лаконичная реализация алгоритма шифрования DES на C.

Ключи шифрования

Для шифрования данных в DES используется шестнадцать 48-битовых ключей. По одному ключу на раунд. Каждый ключ создается выборкой 48 бит из 56-битового основного ключа. Создание ключей для того или иного раунда определяется механизмом, подробно описанным в документации DES.

Вкратце алгоритм выборки i ключа выглядит следующим образом. В основной ключ на позиции 8, 16, 24, 32, 40, 48, 56, 64 добавляются биты. Делается это таким образом, чтобы каждый байт содержал нечетное количество единиц. Соблюдение правила помогает обнаруживать ошибки при обмене ключей. После этого, используя специальные таблицы, дополненный ключ подвергается перестановке и сдвигам, за исключением битов, которые были добавлены. Таким образом получается требуемый ключ.

Компоненты DES

Каждый компонент алгоритма DES решает определенную задачу:

1. Алгоритм Фейстеля упрощает шифрование и расшифровку, гарантируя при этом смешивание обеих половин текста.
2. Побитовое суммирование частей текста с ключами перемешивает открытые данные с ключом и шифрует их.
3. S-блок и таблицы соответствий делают алгоритм нелинейным, повышая его устойчивость к различным атакам.
4. Расширение, S-блок и перестановки обеспечивают диффузию алгоритма - лавинный эффект. Другими словами, если во входных данных функции F изменится хоть 1 бит, то это вызовет изменение сразу множества битов. Если лавинный эффект в шифре не наблюдается, то изменения открытых данных будут приводить к равноценным изменениям в шифрованном виде, которые можно отследить и использовать для взлома. В криптографии существует критерий лавинного эффекта. Алгоритм удовлетворяет ему, если при изменении 1 бита открытых данных изменяется не менее половины шифрованных данных. Алгоритм DES удовлетворяет ему, начиная с 4 раунда. Итог - при изменении 1 бита открытых данных в шифре DES изменятся 29 битов.

Проблемы безопасности в DES

Очевидной проблемой DES является выборка ключей шифрования из общего ключа. Что будет, если в качестве ключа выбрать нулевое значение (все биты ключа равны 0)? Это приведет к тому, что выборка всех ключей для шифрования на каждом раунде будет одинаковой, а все ключи будут равны нулю. Мало того, что 16 шифрований пройдут с одним ключом, так из-за того, что алгоритмы шифрования и расшифровки DES отличаются только порядком применения ключей, они будут абсолютно одинаковыми. Потеряется весь смысл шифрования.

DES обладает 4 ключами, которые называются слабыми, приводящими к описанному эффекту. В DES есть 12 полуслабых и 48 псевдослабых ключей, которые приводят к ограничению вариаций генерируемых ключей в раундах. Иными словами, есть вероятность, что в ходе шифрования в 16 раундах будет использовано не 16 различных ключей, а 8, 4 или даже 2.

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

Проблема ключа шифрования

Является основополагающей для DES и считается главной причиной, почему стоит отказаться от этого алгоритма. Так как размер ключа в DES составляет 56 бит, то для перебора всех ключей понадобится просмотреть 2 56 вариантов. Так ли это много?

Если осуществлять по 10 миллионов проверок ключей в секунду, то на проверку уйдет порядка 2000 лет. Кажется, что алгоритм весьма устойчив. Он был таковым в прошлом веке, когда создание компьютера подобной мощности было почти невозможной задачей как с технической, так и с финансовой точки зрения.

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

Криптоанализ и DES

Можно без преувеличения заявить, что DES стал причиной появления прикладной науки под названием "Криптографический анализ". С самого начала появления DES предпринимались попытки его взломать, проводились научные работы по его изучению. Все это привело к зарождению таких областей математики, как:

• линейный криптоанализ - изучение и выявление зависимости между открытым текстом и шифрованным;
• дифференциальный криптоанализ - изучение и анализ зависимостей между несколькими открытыми текстами и их шифрованными версиями;
• криптоанализ на связанных ключах - изучение зависимостей между шифрованными текстами, полученными на первичном ключе, и ключах, связанных с первичным каким-либо образом.

DES выдержал 20 лет всемирного криптоанализа и атак, но остался стойким шифром. Но кто ищет - тот всегда найдет...

1. Бихам и Шамир, ученые из Израиля, в 1991 году показали при помощи дифференциального криптоанализа, что на DES можно совершить атаку, при которой ключ вычислялся при условии, что у атакующего имеется 2 47 специально подобранных пар открытого и шифрованного текстов.
2. Японский ученый Митсуру Мацуи в 1993 году показал, что вычислить ключ можно при помощи линейного криптоанализа. Для этого всего лишь нужно знать 2 47 пар открытого текста и соответствующего шифрованного варианта.

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

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

Чтобы воспользоваться алгоритмом DES для решения разнообразных криптографических задач, разработаны четыре рабочих режима:

· электронная кодовая книга ECB(Electronic Code Book);

· сцепление блоков шифра CBC (Cipher Block Chaining);

· обратная связь по шифртексту CFB (Cipher Feed Back);

· обратная связь по выходу OFB (Output Feed Back).

Режим "Электронная кодовая книга"

Длинный файл разбивают на 64-битовые отрезки (блоки) по 8 байтов. Каждый из этих блоков шифруют независимо с использованием одного и того же ключа шифрования (рис.3.6).

Основное достоинство – простота реализации. Недостаток – относительно слабая устойчивость против квалифицированных криптоаналитиков. Из-за фиксированного характера шифрования при ограниченной длине блока 64 бита возможно проведение криптоанализа "со словарем". Блок такого размера может повториться в сообщении вследствие большой избыточности в тексте на естественном языке.

Рисунок 3.6 – Схема алгоритма DES в режиме электронной кодовой книги

Это приводит к тому, что идентичные блоки открытого текста в сообщении будут представлены идентичными блоками шифртекста, что дает криптоаналитику некоторую информацию о содержании сообщения.

Режим "Сцепление блоков шифра"

В этом режиме исходный файл М разбивается на 64-битовые блоки: М = М 1 М 2 ...М n . Первый блок М 1 складывается по модулю 2 с 64‑битовым начальным вектором IV, который меняется ежедневно и держится в секрете (рис.3.7). Полученная сумма затем шифруется с использованием ключа DES, известного и отправителю, и получателю информации. Полученный 64-битовый шифр С 1 складывается по модулю 2 со вторым блоком текста, результат шифруется и получается второй 64‑битовый шифр С 2 , и т.д. Процедура повторяется до тех пор, пока не будут обработаны все блоки текста.

Таким образом, для всех i = 1…n (n – число блоков) результат шифрования С i определяется следующим образом: С i =

DES (М i  C i –1), где С 0 = IV – начальное значение шифра, равное начальному вектору (вектору инициализации).

Очевидно, что последний 64-битовый блок шифртекста является функцией секретного ключа, начального вектора и каждого бита

Рисунок 3.7 – Схема алгоритма DES в режиме сцепления блоков шифра

открытого текста независимо от его длины. Этот блок шифртекста называют кодом аутентификации сообщения (КАС).

Код КАС может быть легко проверен получателем, владеющим секретным ключом и начальным вектором, путем повторения процедуры, выполненной отправителем. Посторонний, однако, не может осуществить генерацию КАС, который воспринялся бы получателем как подлинный, чтобы добавить его к ложному сообщению, либо отделить КАС от истинного сообщения для использования его с измененным или ложным сообщением.

Достоинство данного режима в том, что он не позволяет накапливаться ошибкам при передаче.

Блок М i является функцией только С i –1 и С i . Поэтому ошибка при передаче приведет к потере только двух блоков исходно-го текста.

Режим "Обратная связь по шифру"

В этом режиме размер блока может отличаться от 64 бит (рис.3.8). Файл, подлежащий шифрованию (расшифрованию), считывается последовательными блоками длиной k битов (k=1…64).

Входной блок (64-битовый регистр сдвига) вначале содержит вектор инициализации, выровненный по правому краю.

Предположим, что в результате разбиения на блоки мы получили n блоков длинойk битов каждый (остаток дописывается нулями или пробелами). Тогда для любого i=1…n блок шифр-текста

С i = M i  P i –1 ,

где Р i–1 обозначает k старших битов предыдущего зашифрованного блока.

Обновление сдвигового регистра осуществляется путем удаления его старших k битов и записи С i в регистр. Восстановление зашифрованных данных также выполняется относительно просто: Р i –1 и С i вычисляются аналогичным образом и

М i = С i  Р i –1 .

Рисунок 3.8 – Схема алгоритма DES в режиме обратной связи по шифртексту

Режим "Обратная связь по выходу"

Этот режим тоже использует переменный размер блока и сдвиговый регистр, инициализируемый так же, как в режиме СFB, а именно – входной блок вначале содержит вектор инициализации IV, выровненный по правому краю (рис.3.9). При этом для каждого сеанса шифрования данных необходимо использовать новое начальное состояние регистра, которое должно пересылаться по каналу открытым текстом.

М = М 1 М 2 ... M n .

Для всех i = 1… n

С i = M i  P i ,

где Р i – старшие k битов операции DES (С i –1).

Отличие от режима обратной связи по шифртексту состоит в методе обновления сдвигового регистра.

Это осуществляется путем отбрасывания старших k битов и дописывания справа Р i .

Рисунок 3.9 – Схема алгоритма DES в режиме обратной связи по выходу

3.3. ОбластипримененияалгоритмаDES

Каждому из рассмотренных режимов (ЕСВ, СВС, CFB, OFB) свойственны свои достоинства и недостатки, что обусловливает области их применения.

Режим ЕСВ хорошо подходит для шифрования ключей: режим CFB, как правило, предназначается для шифрования отдельных символов, а режим OFB нередко применяется для шифрования в спутниковых системах связи.

Режимы СВС и CFB пригодны для аутентификации данных. Эти режимы позволяют использовать алгоритм DES для:

· интерактивного шифрования при обмене данными между терминалом и главной ЭВМ;

· шифрования криптографического ключа в практике автоматизированного распространения ключей;

· шифрования файлов, почтовых отправлений, данных спутников и других практических задач.

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

В системах автоматической обработки данных человек не в состоянии просмотреть данные, чтобы установить, не внесены ли в них какие-либо изменения. При огромных объемах данных, проходящих в современных системах обработки, просмотр занял бы слишком много времени. К тому же избыточность данных может оказаться недостаточной для обнаружения ошибок. Даже в тех случаях, когда просмотр человеком возможен, данные могут быть изменены таким образом, что обнаружить эти изменения человеку очень трудно. Например, "do" может быть заменено на "do not", "$1900" – на "$9100". Без дополнительной информации человек при просмотре может легко принять измененные данные за подлинные. Такие опасности могут существовать даже при использовании шифрования данных. Поэтому желательно иметь автоматическое средство обнаружения преднамеренных и непреднамеренных изменений данных.

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

Этот процесс описывает стандарт для аутентификации данных ЭВМ (FIPS 113). Суть стандарта состоит в том, что данные зашифровываются в режиме обратной связи по шифртексту (режим CFB) или в режиме сцепления блоков шифра (режим СВС), в результате чего получается окончательный блок шифра, представляющий собой функцию всех разрядов открытого текста. После этого сообщение, которое содержит открытый текст, может быть передано с использованием вычисленного окончательного блока шифра, служащего в качестве криптографической контрольной суммы.

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

му тексту.

Шифрование и аутентификацию используют для защиты данных, хранящихся в ЭВМ. Во многих ЭВМ пароли зашифровывают необратимым образом и хранят в памяти машины. Когда пользователь обращается к ЭВМ и вводит пароль, последний зашифровывается и сравнивается с хранящимся значением. Если обе зашифрованные величины одинаковы, пользователь получает доступ к машине, в противном случае следует отказ.

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

С помощью алгоритма DES можно также зашифровать файлы ЭВМ для их хранения.

Одним из наиболее важных применений алгоритма DES является защита сообщений электронной системы платежей (ЭСП) при операциях с широкой клиентурой и между банками .

Алгоритм DES реализуется в банковских автоматах, терминалах в торговых точках, автоматизированных рабочих местах и главных ЭВМ. Диапазон защищаемых им данных весьма широк – от оплат $50 до переводов на многие миллионы долларов. Гибкость основного алгоритма DES позволяет использовать его в самых разнообразных областях применения электронной системы платежей.