Государственный стандарты шифрования des

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

DES

В начале 1970-х годов правительство США под давлением промышленных и финансовых кругов согласилось официально допустить использование криптографических методов для защиты конфиденциальных данных от несанкционированного доступа. Национальное бюро стандартов объявило открытый конкурс на создание общедоступного алгоритма шифрования с гарантированной надежностью. Оценку представленных кандидатов осуществляло Агентство национальной безопасности США. В январе 1977 года предложенный фирмой IBM и оказавшийся победителем конкурса, «Алгоритм шифрования для защиты данных ЭВМ» был зарегистрирован в качестве государственного стандарта США: Data Encryption Standard (Стандарт шифрования данных, DES).

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

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

Входной блок подвергается начальной перестановке, и ее результат разбивается на два 32-разрядных блока L0 и R0. После этого следуют 16 раундов шифрования с использованием секретного ключа K. Над финальным блоком L16R16 осуществляется перестановка, обратная по отношению к начальной, и результат выдается в качестве блока криптограммы.

При дешифровании все действия производятся в обратном порядке.

Центральной операцией алгоритма DES, обеспечивающей стойкость шифра, является подстановка с использованием шифраторов, так называемых S-боксов (substitution boxes).

S-бокс представляет собой таблицу размерности 4×6 с нумерацией строк 0, 1, 2, 3 и столбцов от 0 до 15. В каждой строке стоит своя перестановка столбцовых номеров. На вход S-бокса подается 6-разрядный двоичный блок a0a1a2a3a4a5. Первый и последний его символы a0a5 определяют строку S-бокса, средние a1a2a3a4 – его столбец. Стоящее на пересечении строки и столбца число дает в двоичной записи 4-разрядный выходной блок. Переработка 6-буквенных двоичных блоков в 4-буквенные и является функцией S-бокса.

В качестве примера покажем, как это делает S-бокс 5:

2	12	4	1	7	10	11	6	8	5	3	15	13	0	14	9
14	11	2	12	4	7	13	1	5	0	15	10	3	9	8	6
4	2	1	11	10	13	7	8	15	9	12	5	6	3	0	14
11	8	12	7	1	14	2	13	6	15	0	9	10	4	5	3

Пусть на вход подается двоичное слово 111010. Оно выделяет в таблице строку с номером 2 (т.е. 10) и столбец с номером 13 (т.е. 1101). На их пересечении стоит число 3. Его двоичная запись 0011 и появляется на выходе.

Все используемые в DES перестановки и подстановки известны. Неизвестен только секретный 56-разрядный ключ K, принадлежащий пользователю. Таким образом, в DES реализован идеал Керкхофса: о шифре известно все, кроме ключа. Для прямого взлома DES нужно перебрать %%2^{56}=72 057 594 037 927 936%% (72 квадриллиона 57 триллионов 594 миллиарда 37 миллионов 927 тысяч 936) возможных ключей. DES стал наиболее широко признанным механизмом криптографической защиты данных, не составляющих государственной тайны.

При регистрации DES в качестве государственного стандарта США рекомендовалось пересматривать его на предмет стойкости каждые пять лет. Последние испытания были проведены в 1997 году, и шифр в очередной раз был признан надежным. В июле 1998 года, затратив более 250 000 долларов, компания EFF (Electronic Frontier Foundation, Фонд электронного рубежа) предъявила суперкомпьютер «DES-взломщик», изготовленный с использованием 1536 чипов, обеспечивавших проверку 28 миллиардов ключей в секунду. С его помощью контрольная DES-криптограмма была дешифрована за 56 часов. В январе 1999 года, присоединив еще 100 000 объединенных в сеть персональных компьютеров, EFF справилась с этой задачей уже за 22 часа, – DES был окончательно скомпрометирован.

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