Алгоритмы шифрования DES и AES

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

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

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

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

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

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

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

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

Шифрование

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

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

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

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

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

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

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

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

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

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

После выполнения перестановки с расширением для полученного 48-битного значения выполняется операция XOR с 48-битным подключом Ki. Затем полученное 48-битное значение подается на вход блока подстановки S (от англ. Substitution - подстановка), результатом которой является 32-битное значение. Подстановка выполняется в восьми блоках подстановки или восьми S-блоках (S-boxes). При выполнении этой операции 48 битов данных делятся на восемь 6-битовых подблоков, каждый из которых по своей таблице замен заменяется четырьмя битами. Подстановка с помощью S-блоков является одним из важнейших этапом DES. Таблицы замен для этой операции специально спроектированы специалистами так, чтобы обеспечивать максимальную безопасность. В результате выполнения этого этапа получаются восемь 4-битовых блоков, которые вновь объединяются в единое 32-битовое значение.

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

И, наконец, результат перестановки объединяется с помощью операции XOR с левой половиной первоначального 64-битового блока данных. Затем левая и правая половины меняются местами, и начинается следующий раунд.

После шестнадцати раундов шифрования выполняется конечная перестановка результата. Эта перестановка инверсна (обратна) начальной перестановке.

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

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

Расшифрование

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

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

Двухкратный DES и атака "встреча посередине"

В настоящее время основным недостатком DES считается маленькая длина ключа. Простейшим способом усложнения процесса криптоанализа является использование двухкратного шифрования с помощью одного и того же алгоритма с разными ключами. Если М – сообщение, К1, К2 – ключ, f – процесс шифрования по DES, а Е – зашифрованное сообщение, то можно записать

E=f(f(M,K1),K2),

то есть сначала блок шифруется одним ключом, затем получившийся шифротекст шифруется вторым ключом. Расшифрование проводится в обратном порядке ( f -1 – расшифрование по DES ):

E=f-1(f-1(M,K2),K1)

В этом случае длина ключа равна 56 * 2 = 112 бит, поэтому для обнаружения двойного ключа, которым зашифрован блок, потребуется в общем случае 2¹¹² попыток.

Исследовав эту проблему, американские ученые Меркл и Хеллман придумали способ проведения атаки по открытому тексту, который требует проведения не 2¹¹² попыток, а 2⁵⁷. (Меркл и Хеллман предложили эту схему против DES, но можно сделать обобщение на все блочные алгоритмы.)

Этот вариант атаки называется атака "встреча посередине". Он основан на следующем свойстве алгоритма. Мы имеем

E=f(f(M,K1),K2)

где М – сообщение, К1, К2 – ключ, f – процесс шифрования по DES, а Е – зашифрованное сообщение.

Тогда X=f(M,K1)=f-1(E,K2).

Атака состоит в следующем. Требуется, чтобы атакующий знал несколько пар "незашифрованный текст - соответствующий ему зашифрованный текст" (M, E). В этом случае вначале шифруется M для всех возможных 2⁵⁶ значений K1. Этот результат запоминается в памяти ЭВМ. Запомненные данные упорядочиваются по значению Х. Следующий шаг состоит в дешифровании E, с применением всех возможных 2⁵⁶ значений K2. Для каждого выполненного дешифрования ищется равное ему значение в первой таблице. Если такое значение найдено, то считается, что эти ключи могут быть правильными, и они проверяются для следующей известной пары "незашифрованный текст, зашифрованный текст". Максимальное количество попыток шифрования, которое, возможно, придется предпринять, равно 2*2n, или 2n+1 (где n – длина ключа в каждом из этапов шифрования; для DES n равно 56 ).

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

Для проведения атаки "встреча посередине" нужен большой объем памяти: 2ⁿ блоков (где n – длина ключа). Для DES, в котором используется 56-битовый ключ потребуется 2⁵⁶ 64-разрядных блоков памяти. Это составляет 2⁶² байт или 2²² Тбайт. Такой объем памяти достаточно трудно пока еще себе представить, кроме того, для проведения операций поиска в таком огромном массиве потребуется соответствующее время. Несмотря на это, двойное шифрование DES практически никогда не использовалась.

Трехкратный DES

В целях противодействия атаке "встреча посередине" было предложено использовать тройное шифрование с двумя ключами (рис 4.3).

В этом случае выполняется последовательность зашифрование-расшифрование-зашифрование ( EDE – от англ. Encrypt – Decrypt -Encrypt ). Этот процесс можно символически представить следующим образом:

E=f(f-1(f(M,K1),K2),K1)

Отправитель сначала шифрует сообщение первым ключом, затем расшифрует вторым и, наконец, окончательно шифрует первым. Получатель сначала расшифровывает первым ключом, затем шифрует вторым и снова расшифровывает первым. При этом длина ключа увеличивается вдвое и составляет 112 бит.

В качестве более надежной альтернативы предлагается метод трехкратного шифрования, использующий три разных ключа – на каждом из этапов свой. Общая длина ключа в таком методе возрастает ( 112+56=168 ), но хранение нескольких сотен бит обычно не является проблемой.

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

Алгоритм Rijndael

Алгоритм Rijndael (читается "Рейндал") разработан бельгийскими специалистами Joan Daemen (Proton World International) и Vincent Rijmen (Katholieke Universiteit Leuven). Этот шифр победил в проведенном Национальным институтом стандартов и техники (NIST) США конкурсе на звание AES (Advanced Encryption Standard) и в 2001 году был принят в качестве нового американского стандарта. Алгоритм Rijndael достаточно сложен для описания, поэтому рассмотрим только основные аспекты построения и особенности использования шифра.

Шифр Rijndael/AES (то есть рекомендуемый стандартом) характеризуется размером блока 128 бит, длиной ключа 128, 192 или 256 бит и количеством раундов 10, 12 или 14 в зависимости от длины ключа. В принципе, структуру Rijndael можно приспособить к любым размерам блока и ключа, кратным 32, а также изменить число раундов.

В отличие от шифров, предлагаемых DES и ГОСТ 28147-89, в основе Rijndael не лежит сеть Фейштеля. Основу Rijndael составляют так называемые линейно-подстановочные преобразования. Блок данных, обрабатываемый с использованием Rijndael, делится на массивы байтов, и каждая операция шифрования является байт-ориентированной. Каждый раунд состоит из трех различных обратимых преобразований, называемых слоями. Эти слои следующие.

Шифр начинается и заканчивается сложением с ключом. Это позволяет закрыть вход первого раунда при атаке по известному тексту и сделать криптографически значимым результат последнего раунда.

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

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

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

Режимы работы блочных алгоритмов

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

Пусть имеется некоторый блочный шифр, который выполняет преобразование f исходного блока данных Х с помощью ключа К в зашифрованный блок Y:

Y=f(X,K)

Рассмотрим некоторые возможные режимы выполнения преобразования f.

Простейшим режимом является режим простой поблочной замены. Специалистами этот режим называется ECB - Electronic CodeВook, что переводится как "электронная кодовая книга". В этом режиме каждый блок исходных данных шифруется независимо от остальных блоков, с применением одного и того же ключа шифрования. Если сообщение длиннее, чем длина блока соответствующего алгоритма, то оно разбивается на блоки Х1, Х2,..., Xn соответствующей длины, причем последний блок дополняется в случае необходимости фиксированными значениями. Каждый блок шифруется блочным шифром:

Y=f(Xi,K) для всех i от 1 до n

В результате шифрования всех блоков исходных данных Xi получается зашифрованное сообщение Y=Y1, Y2,..., Yn. Расшифрование выполняется по правилу

X=f-1(Yi,K) для всех i от 1 до n

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

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

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

Для устранения недостатков ECB при передаче нескольких блоков данных может использоваться режим CBC (Chipher Block Chaining) – режим сцепления блоков шифра.

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

То есть перед шифрованием очередного блока над открытым текстом и результатом шифрования предыдущего блока выполняется операция "сумма по модулю 2". Когда блок открытого текста зашифрован, он сохраняется в памяти шифрующего устройства, например, в регистре обратной связи. Перед шифрованием следующего блока данных, он подвергается операции "сумма по модулю 2" вместе с регистром обратной связи и только после этого шифруется. Полученный зашифрованный блок снова сохраняется в регистре обратной связи и используется при шифровании следующего блока входных данных и так далее до конца сообщения. Блок Y0 должен быть сформирован перед шифрованием первого блока исходных данных. Он называется вектором инициализации и используется для сложения по модулю 2 с первым блоком входных данных.

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

Зашифрованное сообщение можно расшифровать следующим образом:

Блок шифротекста сначала сохраняется в регистре обратной связи, а затем расшифровывается как обычно. Далее расшифровывается следующий блок и подвергается операции "сумма по модулю 2" с регистром обратной связи. И так выполняется до конца сообщения.

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

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

Ключевые термины

AES ( Advanced Encryption Standard ) – Алгоритм шифрования, действующий в качестве государственного стандарта в области шифрования данных в США с 2001 года. В основу стандарта положен шифр Rijndael. Шифр Rijndael/AES (то есть рекомендуемый стандартом) характеризуется размером блока 128 бит, длиной ключа 128, 192 или 256 бит и количеством раундов 10, 12 или 14 в зависимости от длины ключа. Основу Rijndael составляют так называемые линейно-подстановочные преобразования. В алгоритме широко используются табличные вычисления, причем все необходимые таблицы задаются константно, т.е. не зависят ни от ключа, ни от данных.

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

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

Режим ECB (Electronic CodeВook) – Один из режимов использования блочного алгоритма шифрования. Режим ECB (переводится как "электронная кодовая книга") – это режим простой поблочной замены. В этом режиме каждый блок исходных данных шифруется независимо от остальных блоков, с применением одного и того же ключа шифрования. Если сообщение длиннее, чем длина блока соответствующего алгоритма, то оно разбивается на блоки соответствующей длины, причем последний блок дополняется в случае необходимости фиксированными значениями. Режим ECB рекомендуется использовать для передачи одиночных коротких сообщений (например, криптографического ключа).

Режим CBC (Chipher Block Chaining) – режим сцепления блоков шифра. Один из режимов использования блочного алгоритма шифрования. Преобразование в режиме CBC выполняется следующим образом: каждый блок открытого текста складывается по модулю 2 с результатом шифрования предыдущего блока. Таким образом, результаты шифрования предыдущих блоков влияют на шифрование следующих блоков.

Краткие итоги

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

Одним из вариантов использования алгоритма DES является так называемый тройной DES: отправитель сначала шифрует сообщение первым ключом, затем расшифрует вторым и, наконец, окончательно шифрует первым. Получатель сначала расшифровывает первым ключом, затем шифрует вторым и снова расшифровывает первым. При этом длина ключа увеличивается вдвое и составляет 112 бит. В качестве альтернативы предлагается метод трехкратного шифрования, использующий три разных ключа – на каждом из этапов свой. Общая длина ключа в таком методе возрастает до 56x3=168 бит.

С 2001 года в США действует новый стандарт на блочный шифр ( AES ). В основу стандарта положен шифр Rijndael. Шифр Rijndael/AES (то есть рекомендуемый стандартом) характеризуется размером блока 128 бит, длиной ключа 128, 192 или 256 бит и количеством раундов 10, 12 или 14 в зависимости от длины ключа.

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

Режим ECB (Electronic CodeВook) – Один из режимов использования блочного алгоритма шифрования. Режим ECB (переводится как "электронная кодовая книга") – это режим простой поблочной замены. В этом режиме каждый блок исходных данных шифруется независимо от остальных блоков, с применением одного и того же ключа шифрования. Недостатком данного режима является то, что одинаковые блоки исходного текста преобразуются в одинаковый шифротекст. Режим ECB рекомендуется использовать для передачи одиночных коротких сообщений (например, криптографического ключа).

Режим CBC (Chipher Block Chaining) – режим сцепления блоков шифра. Один из режимов использования блочного алгоритма шифрования. Преобразование в режиме CBC выполняется следующим образом: каждый блок открытого текста складывается по модулю 2 с результатом шифрования предыдущего блока. Таким образом, результаты шифрования предыдущих блоков влияют на шифрование следующих блоков. Даже если все блоки исходных данных идентичны, шифротекст будет состоять из различных блоков. Этот режим предпочтителен при шифровании сообщений, размер которых превышает размер блока. Расшифровать сообщение, зашифрованное в режиме CBC, можно только последовательно, начиная с первого блока.

Набор для практики

Вопросы для самопроверки

Упражнения для самопроверки