Самым распространенным и наиболее известным алгоритмом симметричного шифрования является 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 . Выходом этой стадии является незашифрованный текст.

симметричными ключами .

Предложенная IBM модификация проекта, названная Lucifer, была принята как DES . DES были изданы в эскизном виде в Федеральном Регистре в марте 1975 года как Федеральный Стандарт Обработки Информации (FIPS – Federal Information Processing Standard) .

После публикации эскиз строго критиковался по двум причинам. Первая: критиковалась сомнительно маленькая длина ключа (только 56 битов), что могло сделать шифр уязвимым к атаке "грубой силой". Вторая причина: критики были обеспокоены некоторым скрытым построением внутренней структуры DES .

Они подозревали, что некоторая часть структуры (S -блоки) может иметь скрытую лазейку, которая позволит расшифровывать сообщения без ключа. Впоследствии проектировщики IBM сообщили, что внутренняя структура была доработана, чтобы предотвратить криптоанализ .

DES был наконец издан как FIPS 46 в Федеральном Регистре в январе 1977 года. Однако FIPS объявил DES как стандарт для использования в неофициальных приложениях. DES был наиболее широко используемым блочным шифром с симметричными ключами , начиная с его публикации. Позже NIST предложил новый стандарт ( FIPS 46-3), который рекомендует использование тройного DES (трехкратно повторенный шифр DES ) для будущих приложений. Как мы увидим далее, в лекциях 9-10, предполагается, что более новый стандарт AES заменит DES .

Общие положения

Как показано на рис. 8.1. , DES - блочный шифр .

Рис. 8.1.

На стороне шифрования DES принимает 64 -битовый исходный текст и порождает 64 -битовый зашифрованный текст; на стороне дешифрования DES принимает 64 -битовый зашифрованный текст и порождает 64 -битовый исходный текст. На обеих сторонах для шифрования и дешифрования применяется один и тот же 56 -битовый ключ.

8.2. Структура DES

Рассмотрим сначала шифрование , а потом дешифрование . Процесс шифрования состоит из двух перестановок (P -блоки) - они называются начальные и конечные перестановки, - и шестнадцати раундов Файстеля. Каждый раунд использует различные сгенерированные 48 -битовые ключи. Алгоритм генерации будет рассмотрен в этой лекции позднее. Рисунок 8.2 показывает элементы шифра DES на стороне шифрования.

Начальные и конечные перестановки

Рисунок 8.3 показывает начальные и конечные перестановки (P -блоки). Каждая из перестановок принимает 64 -битовый вход и переставляет его элементы по заданному правилу. Мы показали только небольшое число входных портов и соответствующих выходных портов. Эти перестановки - прямые перестановки без ключей, которые инверсны друг другу. Например, в начальной перестановке 58 -й бит на входе переходит в первый бит на выходе. Аналогично, в конечной перестановке первый входной бит переходит в 58 -й бит на выходе. Другими словами, если между этими двумя перестановками не существует раунда, 58 -й бит, поступивший на вход устройства начальной перестановки, будет доставлен на 58 -й выход финальной перестановкой.

Рис. 8.2.

Рис. 8.3.

Правила перестановки для этого P -блока показаны в таблице 8.1 . Таблицу можно представить как 64 -элементный массив. Заметим, что работу с таблицей мы обсуждали, значение каждого элемента определяет номер входного порта, а порядковый номер (индекс) элемента определяет номер выходного порта.

Таблица 8.1. Таблица начальных и конечных перестановок

Начальные перестановки								Конечные перестановки
58	50	42	34	26	18	10	02	40	08	48	16	56	24	64	32
60	52	44	36	28	20	12	04	39	07	47	15	55	23	63	31
62	54	46	38	30	22	14	06	38	06	46	14	54	22	62	30
64	56	48	40	32	24	16	08	37	05	45	13	53	21	61	29
57	49	41	33	25	17	09	01	36	04	44	12	52	20	60	28
59	51	43	35	27	19	11	03	35	03	43	11	51	19	59	27
61	53	45	37	29	21	13	05	34	02	42	10	50	18	58	26
63	55	47	39	31	23	15	07	33	01	41	09	49	17	57	25

Эти две перестановки не имеют никакого значения для криптографии в

Который ANSI называет алгоритмом шифрования данных DEA (Data Encryption Algorithm) , a ISO — DEA-1, за 20 лет стал мировым стандартом. За годы своего существования он выдержал натиск различных атак и при известных ограничениях все еще считается криптостойким.

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

Криптостойкость полностью определяется ключом. Фундаментальным строительным блоком DES является комбинация подстановок и перестановок. DES состоит из 16 циклов.

Oбщий вид цикла преобразования:

Если L i и R i — левая и правая половины, полученные в результате i -й итерации, K i — 48-битный ключ для цикла i , а f — функция, выполняющая все подстановки, перестановки и XOR с ключом, то один цикл преобразования можно представить как:

Учитывая подстановку F i (*) и перестановку Т (*), цикл преобразования можно представить так, как это сделано на рис.

Видно, что каждый цикл DES представляет собой композиционный шифр с двумя последовательными преобразованиями — подстановкой F i (*) и перестановкой Т (*) (за исключением последнего, шестнадцатого цикла, где перестановка опускается).

Подстановка:

(L i , R i) = (R i −1 , L i −1) ⊕ f (R i −1 , K)

является инволюцией, так как

F i (F i (L i −1 , R i −1)) = F i (R i −1 , L i −1) ⊕ (f (R i −1 , K i))) = (R i −1 , L i −1 ⊕(f (R i −1 , K i)) ⊕ (f (R i −1 , K i))) = (L i −1 , R i −1)

А подстановка

T (L i ′, R i ′) = (R i ′, L i ′),

так же является инволюцией, так как

T (T (L i ′, R i ′)) = T (R i ′, L i ′) = L i ′, R i ′

Если обозначить начальную и завершающую перестановки как (IP) и (IР) − 1 , то прямое DES-преобразование (шифрование) реализует функцию:

DES = (IP) F 1 TF 2 T … F 15 TF 16 (IP) − 1 ,

а обратное DES-преобразование (дешифрование) реализует функцию:

DES − 1 = (IP) −1 F 16 TF 15 T … F 2 TF 1 (IP).

Таким образом, DES является шифром Фейстеля и сконструирован так, чтобы выполнялось полезное свойство: для шифрования и дешифрования используется один и тот же алгоритм. Единственное отличие состоит в том, что ключи должны использоваться в обратном порядке.

То есть если при шифровании использовались ключи K 1 , K 2 , K 3 , …, K 16 , то ключами дешифрования будут K 16 , K 15 , K 14 , …, K 1 . Алгоритм использует только стандартную арифметику 64-битовых чисел и логические операции, поэтому легко реализуется на аппаратном уровне.

DES работает с 64-битовым блоком открытого текста. После первоначальной перестановки блок разбивается на правую и левую половины длиной по 32 бита. Затем выполняется 16 преобразований (функция f), в которых данные объединяются с ключом. После шестнадцатого цикла правая и левая половины объединяются, и алгоритм завершается заключительной перестановкой (обратной по отношению к первоначальной). На каждом цикле (см. рис.) биты ключа сдвигаются, и затем из 56 битов ключа выбираются 48 битов. Правая половина данных увеличивается до 48 битов с помощью перестановки с расширением, объединяется посредством XOR с 48 битами смещенного и переставленного ключа, проходит через 8 S-блоков, образуя 32 новых бита, и переставляется снова. Эти четыре операции и выполняются функцией f .

Затем результат функции f объединяется с левой половиной с помощью другого XOR. В итоге этих действий появляется новая правая половина, а старая правая становится новой левой половиной. Эти действия повторяются 16 раз, образуя 16 циклов DES.

Стандарт России — ГОСТ 28147-89

ГОСТ 28147-89 — это блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. В криптоалгоритме также используется дополнительный ключ, который рассматривается ниже. Для шифрования открытый текст сначала разбивается на левую и правую половины L и R . На i -м цикле используется подключ К i:

L i = R i −1 ,
R i = L i −1 ⊕ (f (R i −1 , K i)).

Функция f реализована следующим образом. Сначала правая половина и i -й подключ складываются по модулю 2 32 . Результат разбивается на восемь 4-битовых подпоследовательностей, каждая из которых поступает на вход своего S-блока. ГОСТ использует восемь различных S-блоков, первые 4 бита попадают в первый S-блок, вторые 4 бита — во второй S-блок и т. д. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Например, S-блок может выглядеть как: 7,10,2,4,15,9,0,3,6,12,5,13,1,8,11. В этом случае, если на входе S-блока 0, то на выходе 7. Если на входе 1, на выходе 10 и т. д. Все восемь S-блоков различны, они фактически являются дополнительным ключевым материалом. Выходы всех восьми S-блоков объединяются в 32-битовое слово, затем все слово циклически сдвигается влево на 11 битов. Наконец, результат объединяется с помощью операции XOR с левой половиной, и получается новая правая половина, а правая половина становится новой левой половиной. Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: k 1 , k 2 , …, k 8 . На каждом цикле используется свой подключ. Дешифрование выполняется так же, как и шифрование, но инвертируется порядок подключей k i . Стандарт не определяет способ генерации S-блоков.

Основные различия между DES и ГОСТом

Главные различия между DES и ГОСТом заключаются в следующем:

• DES использует сложную процедуру для генерации подключей из ключей. В ГОСТе эта процедура очень проста;
• в DES 56-битный ключ, а в ГОСТе — 256-битный. Если добавить секретные перестановки S-блоков, то полный объем секретной информации ГОСТа составит примерно 610 бит;
• у S-блоков DES 6-битные входы и 4-битные выходы, а у S-блоков ГОСТа 4-битные входы и выходы. В обоих алгоритмах используется по восемь S-блоков, но размер S-блока ГОСТа равен четверти размера S-блока DES;
• в DES используются нерегулярные перестановки, названные Р-блоком, а в ГОСТе используется 11-битный циклический сдвиг влево;
• в DES 16 циклов, а в ГОСТе — 32.

Силовая атака на ГОСТ абсолютно бесперспективна. ГОСТ использует 256-битовый ключ, а если учитывать секретные S-блоки, то длина ключа будет еще больше. ГОСТ, по-видимому, более устойчив к дифференциальному и линейному криптоанализу, чем DES. Хотя случайные S-блоки ГОСТа при некотором выборе не гарантируют высокой криптостойкости по сравнению с фиксированными S-блоками DES, их секретность увеличивает устойчивость ГОСТа к дифференциальному и линейному криптоанализу. К тому же эффективность этих криптоаналитических методов зависит от количества циклов преобразования — чем больше циклов, тем труднее криптоанализ. ГОСТ использует в два раза больше циклов, чем DES, что, возможно, приводит к несостоятельности дифференциального и линейного криптоанализа.

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

Основным различием представляется использование в ГОСТе циклического сдвига вместо перестановки. Перестановка DES увеличивает лавинный эффект. В ГОСТе изменение одного входного бита влияет на один S-блок одного цикла преобразования, который затем влияет на два S-блока следующего цикла, затем на три блока следующего цикла и т.д. Потребуется восемь циклов, прежде чем изменение одного входного бита повлияет на каждый бит результата; в DES для этого нужно только пять циклов. Однако ГОСТ состоит из 32 циклов, a DES только из 16.

Разработчики ГОСТа пытались достигнуть равновесия между криптостойкостью и эффективностью. Взяв за основу конструкцию Фейстеля, они разработали криптоалгоритм, который лучше, чем DES, подходит для программной реализации. Для повышения криптостойкости введен сверхдлинный ключ и удвоено количество циклов. Однако вопрос, увенчались ли усилия разработчиков созданием более криптостойкого, чем DES, криптоалгоритма, остается открытым.

Воробьева Е., Лукьянова А.

Аннотация: Одной из наиболее известных криптографических систем с закрытым ключом является DES – Data Encryption Standard. Эта система первой получила статус государственного стандарта в области шифрования данных. И хотя старый американский стандарт DES в настоящее время утратил свой официальный статус, этот алгоритм все же заслуживает внимания при изучении криптографии. Кроме того в этой лекции объясняется, что такое "двухкратный DES", атака "встреча посередине" и способы ее устранения. В этой же лекции кратко рассматривается новый стандарт США на блочный шифр – алгоритм Rijndael.

Цель лекции : познакомить студента с основными сведениями об алгоритме шифрования DES .

Основные сведения

Одной из наиболее известных криптографических систем с закрытым ключом является DES – Data Encryption Standard . Эта система первой получила статус государственного стандарта в области шифрования данных. Она разработана специалистами фирмы IBM и вступила в действие в США 1977 году. Алгоритм DES широко использовался при хранении и передаче данных между различными вычислительными системами; в почтовых системах, в электронных системах чертежей и при электронном обмене коммерческой информацией . Стандарт DES реализовывался как программно, так и аппаратно. Предприятиями разных стран был налажен массовый выпуск цифровых устройств, использующих DES для шифрования данных. Все устройства проходили обязательную сертификацию на соответствие стандарту.

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

Длина ключа в алгоритме DES составляет 56 бит . Именно с этим фактом связана основная полемика относительно способности DES противостоять различным атакам. Как известно, любой блочный шифр с закрытым ключом можно взломать, перебрав все возможные комбинации ключей. При длине ключа 56 бит возможны 2 56 разных ключей. Если компьютер перебирает за одну секунду 1 000 000 ключей (что примерно равно 2 20), то на перебор всех 2 56 ключей потребуется 2 36 секунд или чуть более двух тысяч лет, что, конечно, является неприемлемым для злоумышленников.

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

Вместе с этим можно отметить, что систему DES вполне можно использовать в небольших и средних приложениях для шифрования данных, имеющих небольшую ценность. Для шифрования данных государственной важности или имеющих значительную коммерческую стоимость система DES в настоящее время, конечно, не должна использоваться. В 2001 году после специально объявленного конкурса в США был принят новый стандарт на блочный шифр , названный AES (Advanced Encryption Standard) , в основу которого был положен шифр Rijndael , разработанный бельгийскими специалистами. Этот шифр рассматривается в конце лекции.

Основные параметры DES : размер блока 64 бита, длина ключа 56 бит , количество раундов – 16. DES является классической сетью Фейштеля с двумя ветвями. Алгоритм преобразует за несколько раундов 64-битный входной блок данных в 64-битный выходной блок. Стандарт DES построен на комбинированном использовании перестановки, замены и гаммирования. Шифруемые данные должны быть представлены в двоичном виде.

Шифрование

Общая структура DES представлена на рис. 4.1 . Процесс шифрования каждого 64-битового блока исходных данных можно разделить на три этапа:

1. начальная подготовка блока данных;
2. 16 раундов "основного цикла";
3. конечная обработка блока данных.

На первом этапе выполняется начальная перестановка 64-битного исходного блока текста, во время которой биты определенным образом переупорядочиваются.

На следующем (основном) этапе блок делится на две части (ветви) по 32 бита каждая. Правая ветвь преобразуется с использованием некоторой функции F и соответствующего частичного ключа , получаемого из основного ключа шифрования по специальному алгоритму преобразования ключей. Затем производится обмен данными между левой и правой ветвями блока. Это повторяется в цикле 16 раз.

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

Рис. 4.1.

Рассмотрим более подробно все этапы криптографического преобразования по стандарту DES .

На первом этапе 64-разрядный блок исходных данных подвергается начальной перестановке. В литературе эта операция иногда называется "забеливание" – whitening . При начальной перестановке биты блока данных определенным образом переупорядочиваются. Эта операция придает некоторую "хаотичность" исходному сообщению, снижая возможность использования криптоанализа статистическими методами.

Одновременно с начальной перестановкой блока данных выполняется начальная перестановка 56 бит ключа. Из рис. 4.1 . видно, что в каждом из раундов используется соответствующий 48-битный частичный ключ K i . Ключи K i получаются по определенному алгоритму, используя каждый из битов начального ключа по нескольку раз. В каждом раунде 56-битный ключ делится на две 28-битовые половинки. Затем половинки сдвигаются влево на один или два бита в зависимости от номера раунда. После сдвига определенным образом выбирается 48 из 56 битов. Так как при этом не только выбирается подмножество битов, но и изменяется их порядок, то эта операция называется " перестановка со сжатием". Ее результатом является набор из 48 битов. В среднем каждый бит исходного 56-битного ключа используется в 14 из 16 подключей, хотя не все биты используются одинаковое количество раз.

Далее выполняется основной цикл преобразования, организованный по сети Фейштеля и состоящий из 16 одинаковых раундов. При этом в каждом раунде ( рис. 4.2) получается промежуточное 64-битное значение , которое затем обрабатывается в следующем раунде.

Рис. 4.2.

Левая и правая ветви каждого промежуточного значения обрабатываются как отдельные 32-битные значения, обозначенные L и R .

Вначале правая часть блока R i расширяется до 48 битов, используя таблицу, которая определяет перестановку плюс расширение на 16 битов. Эта операция приводит размер правой половины в соответствие с размером ключа для выполнения операции XOR . Кроме того, за счет выполнения этой операции быстрее возрастает зависимость всех битов результата от битов исходных данных и ключа (это называется "лавинным эффектом"). Чем сильнее проявляется лавинный эффект при использовании того или иного алгоритма шифрования, тем лучше.

После выполнения перестановки с расширением для полученного 48-битного значения выполняется операция XOR с 48-битным подключом K i . Затем полученное 48-битное значение подается на вход блока подстановки S (от англ. Substitution - подстановка), результатом которой является 32-битное значение . Подстановка выполняется в восьми блоках подстановки или восьми S-блоках (S-boxes). При выполнении этой DES на бумаге выглядит достаточно сложным, что уж говорить про его программную реализацию! Разработать правильно и оптимально функционирующую программу полностью в соответствии с DES , наверно, под силу только опытным программистам. Некоторые трудности возникают при программной реализации, например, начальной перестановки или перестановки с расширением. Эти сложности связаны с тем, что первоначально планировалось реализовывать DES только аппаратно. Все используемые в стандарте операции легко выполняются аппаратными блоками, и никаких трудностей с реализацией не возникает. Однако через некоторое время после публикации стандарта разработчики программного обеспечения решили не стоять в стороне и тоже взяться за создание систем шифрования. В дальнейшем DES реализовывался и аппаратно, и программно.

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.