Стандарт шифрования данных и расширенный стандарт шифрования

В 1973 году Национальное бюро стандартов США (НБС; ныне Национальный институт стандартов и технологий) опубликовало публичный запрос на предложения по криптоалгоритму для рассмотрения в качестве нового криптографического стандарта. Не было получено ни одного приемлемого предложения. Второй запрос был опубликован в 1974 году, и компания International Business Machines (IBM) представила запатентованный алгоритм Lucifer, разработанный одним из исследователей компании, Хорстом Фейстелем, несколькими годами ранее. Алгоритм Lucifer был оценен в ходе секретных консультаций между NBS и Агентством национальной безопасности (АНБ). После некоторых изменений внутренних функций и сокращения размера ключа со 112 бит до 56 бит, в 1975 году в Федеральном реестре были опубликованы полные детали алгоритма, который должен был стать стандартом шифрования данных (DES). После почти двух лет общественной оценки и комментариев сам стандарт был принят в конце 1976 года и опубликован в начале 1977 года. В результате сертификации стандарта НБС и его обязательств по оценке и сертификации реализаций, было предписано использовать DES в несекретных приложениях правительства США для защиты двоично-кодированных данных при передаче и хранении в компьютерных системах и сетях, а также в отдельных случаях для защиты секретной информации.

Использование алгоритма DES стало обязательным для всех финансовых операций правительства США, связанных с электронным переводом средств, включая операции, проводимые банками-членами Федеральной резервной системы. Последующее принятие DES организациями по стандартизации во всем мире привело к тому, что DES стал де-факто международным стандартом безопасности данных в бизнесе и коммерции.

DES - это продукционный блочный шифр, в котором 16 итераций, или раундов, процесса подстановки и транспонирования (перестановки) соединены в каскад. Размер блока составляет 64 бита. Ключ, управляющий преобразованием, также состоит из 64 бит, однако только 56 из них могут быть выбраны пользователем и являются собственно ключевыми битами. Остальные восемь являются битами проверки четности и, следовательно, полностью избыточны. Рисунок представляет собой функциональную схему последовательности событий, происходящих за один раунд шифрования (или дешифрования) преобразования DES. На каждом промежуточном этапе процесса преобразования выходной шифр предыдущего этапа разделяется на 32 крайних левых бита Li и 32 крайних правых бита Ri. Ri транспонируется, чтобы стать левой частью следующего более высокого промежуточного шифра, Li + 1. Правая половина следующего шифра, Ri + 1, является сложной функцией, Li + f(Ri, Ki + 1), от подмножества ключевых битов, Ki + 1, и от всего предыдущего промежуточного шифра. Существенной особенностью для безопасности DES является то, что f включает очень специальную нелинейную подстановку - т.е. f(A) + f(B) ≠ f(A + B)- определенную Бюро стандартов в табличных функциях, известных как S-боксы. Этот процесс повторяется 16 раз. Эта базовая структура, в которой на каждой итерации выход шифра с предыдущего шага делится пополам, половинки транспонируются с помощью сложной функции, управляемой ключом, выполняемой на правой половине, и результат объединяется с левой половиной с помощью логического "исключающего-или" (истина или "1" только тогда, когда истинен ровно один из случаев) для формирования новой правой половины, называется шифром Фейстеля и широко используется - и не только в DES. Одна из привлекательных особенностей шифров Фейстеля - помимо их безопасности - заключается в том, что если подмножества ключей используются в обратном порядке, повторение "шифрования" расшифровывает шифротекст для восстановления открытого текста.

Безопасность DES не больше, чем его рабочий фактор - усилие грубой силы, необходимое для перебора 256 ключей. Это поиск иголки в стоге сена из 72 квадриллионов соломинок. В 1977 году это считалось невыполнимой вычислительной задачей. В 1999 году специализированная поисковая система DES в сочетании со 100 000 персональных компьютеров в Интернете нашла ключ DES за 22 часа. Более ранний ключ был найден распределенными компьютерами Интернета за 39 дней, а только специализированной поисковой системой - за 3 дня. В течение некоторого времени было очевидно, что DES, хотя и не был взломан в обычном криптоаналитическом смысле, больше не является безопасным. Был придуман способ, который фактически давал DES 112-битный ключ - по иронии судьбы, размер ключа алгоритма Lucifer, первоначально предложенного IBM в 1974 году. Этот способ известен как "тройной DES" и предполагает использование двух обычных ключей DES. Как предложил Уолтер Такман из корпорации Amperif, операция шифрования будет E1D2E1, а расшифровка - D1E2D1. Поскольку EkDk = DkEk = I для всех ключей k, это тройное шифрование использует обратную пару операций. Существует много способов выбрать три операции так, чтобы в результате получилась такая пара; Такман предложил эту схему, поскольку если оба ключа одинаковы, то получается обычный одноключевой DES. Таким образом, оборудование с тройным DES могло быть совместимо с оборудованием, которое использовало только старый одинарный DES. Банковские стандарты приняли эту схему для обеспечения безопасности.

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

В январе 1997 года Национальный институт стандартов и технологий (NIST) опубликовал публичный запрос на представление кандидатов для замены устаревшего DES. На этот раз было получено 15 приемлемых предложений из 12 стран. В октябре 2000 года NIST объявил, что Rijndael, программа, созданная двумя бельгийскими криптографами, Джоаном Деменом и Винсентом Риджменом, была принята в качестве нового стандарта, или Advanced Encryption Standard (AES). NBS ожидала, что DES будет реализован на специализированном оборудовании, и поэтому практически не рассматривала возможность его эффективной реализации в программном обеспечении, т.е. с использованием микропроцессоров общего назначения. В результате DES не смог воспользоваться преимуществами быстрого развития микропроцессоров, которое произошло в последние два десятилетия 20-го века. Спецификации AES, с другой стороны, в равной степени подчеркивали аппаратную и программную реализацию. Отчасти это учитывало потребности смарт-карт и другого оборудования точек продаж, которые обычно имеют очень ограниченные вычислительные возможности, но более важным было признание растущих потребностей Интернета и электронной коммерции. Основываясь на опыте работы с DES, где усовершенствования в вычислениях просто превысили рабочий коэффициент фиксированного 56-битного ключа, спецификации NIST для AES также требовали, чтобы алгоритм был способен увеличивать длину ключа при необходимости. Rijndael оказался достаточно компактным для реализации на смарт-картах (менее 10 000 байт кода) и достаточно гибким, чтобы позволить увеличить длину ключа.

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