Алгоритм DES: описание и пример

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

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

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

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

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

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

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

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

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

Для ясности изложения и описания алгоритма 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⁵⁶ вариантов. Так ли это много?

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

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

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

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

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

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

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

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