Эффективность этих базовых элементов становится очевидной, если расположить каскадом целый ряд блоков (илл. 8.13 (в)), создав продукционный шифр (product cipher). В нашем примере на первом этапе (P1) 12 входных линий меняются местами. На второй ступени вход разбивается на четыре группы из 3 бит, с каждой из которых операция замены выполняется независимо (S1–S4). Такое расположение позволяет составить большой S-блок из множества мелких. Это хороший способ, так как небольшие S-блоки удобны при аппаратной реализации (к примеру, восьмиразрядный S-блок можно представить в виде 256-разрядной таблицы перекодировки), однако большие S-блоки довольно трудно построить (например, 12-разрядный S-блок потребует минимум 212 = 4096 перекрещенных проводов в средней стадии). Хотя этот метод является лишь частным случаем, он достаточно эффективный. Выход продукционного шифра можно сделать сложной функцией входа, используя достаточно большое количество дополнительных ступеней.
Продукционные шифры, работающие с k-битными входами и производящие k-битные последовательности, широко распространены. В частности, часто применяются шифры с k, равным 256. Аппаратная реализация обычно имеет не семь, как на илл. 8.13 (в), а по крайней мере 20 физических этапов. Программная реализация совершает минимум восемь циклических итераций, каждая из которых производит S-блочные подстановки в подблоках блока данных длиной от 64 до 256 бит, после чего производится перестановка, которая перемешивает результаты S-блоков. Часто также производятся две дополнительные перестановки в начале и в конце. В литературе эти итерации называются раундами.
8.5.1. Стандарт шифрования данных DES
В январе 1977 года правительство США приняло продукционный шифр, разработанный IBM, в качестве официального стандарта для незасекреченной информации. Этот шифр, получивший название DES (Data Encryption Standard — стандарт шифрования данных), широко применялся в промышленности для защиты информации. Хотя в своем исходном виде он уже небезопасен, его модифицированная версия по-прежнему изредка используется. Эффективность исходной версии сомнительна: изначально длина ключа равнялась 128 бит, но после консультаций с АНБ компания IBM «добровольно» уменьшила ее до 56 бит, что, по мнению криптографов, было слишком мало даже для того времени. Алгоритм DES действует практически так же, как показано на илл. 8.13 (в), но использует блоки большего размера. Открытый текст (в двоичном виде) разбивается на 64-битные блоки, каждый из которых шифруется по отдельности путем выполнения перестановок и подстановок, параметризованных 56-битным ключом в каждом из 16 последовательных раундов. По сути, это очень большой моноалфавитный подстановочный шифр на базе алфавита с 64-битными символами (о которых мы поговорим чуть позже).
Уже в 1979 году стало ясно, что 56-битный ключ слишком короткий, и IBM разработала обратно совместимую схему увеличения длины ключа за счет одновременного использования двух 56-битных ключей, что в совокупности давало 112-битный ключ (Такман; Tuchman, 1979). Эта новая схема, названная тройным DES (Triple DES), используется до сих пор (илл. 8.14).
Илл. 8.14. (а) Тройное шифрование с помощью DES. (б) Дешифрование
Возникает два резонных вопроса. Первый: почему здесь используется два, а не три ключа? Второй: для чего выполняется шифрование, дешифрование и затем снова шифрование? Ответ следующий. В случае, когда компьютеру, использующему тройной DES, необходимо связаться с компьютером, на котором реализован одинарный DES, он может применить тройной DES, взяв в качестве обоих ключей одно и то же значение. Это даст тот же результат, что и применение одинарного DES. Такой подход упростил поэтапное внедрение тройного DES. Сегодня этот алгоритм можно считать устаревшим, но он по-прежнему используется в некоторых областях применения, которые трудно поддаются изменениям.
8.5.2. Улучшенный стандарт шифрования AES
Когда стало понятно, что DES (даже с тройным шифрованием) устаревает, Национальный институт стандартов и технологий (National Institute of Standards and Technology, NIST) — агентство Министерства торговли, занимающееся разработкой стандартов для Федерального правительства США, — решил создать новый криптографический стандарт для несекретных данных. Специалисты NIST ясно осознавали противоречия, связанные с DES. Они прекрасно понимали, что, услышав о новом стандарте, все, кто хоть что-то смыслит в криптографии, решат, что и здесь есть лазейка, с помощью которой АНБ получит доступ к данным. Вряд ли в таких условиях люди согласятся применять новую технологию, и она, скорее всего, канет в Лету.
Исходя из этого, NIST выбрал неожиданное для правительственной бюрократии решение и организовал криптографический конкурс. В январе 1997 года ученые со всего мира были приглашены для представления своих разработок нового стандарта, который назвали AES (Advanced Encryption Standard — продвинутый стандарт шифрования). Ниже перечислены требования к разработкам конкурсантов:
1. Алгоритм использует симметричный блочный шифр.
2. Все детали разработки общедоступны.
3. Поддерживаются длины ключей 128, 192 и 256 бит.
4. Возможна как программная, так и аппаратная реализация.
5. Алгоритм общедоступен или лицензирован на недискриминационных условиях.
Было рассмотрено 15 серьезных предложений. На открытых конференциях разработчики представляли свои проекты, а оппоненты должны были приложить максимум усилий, чтобы найти в них недостатки. В августе 1998 года NIST выбрал пять финалистов, руководствуясь критериями безопасности, эффективности, простоты, гибкости, а также требований к памяти (это важно для встроенных систем). Затем были проведены конференции, на которых высказывались дополнительные критические замечания.
В октябре 2000 года NIST объявил победителей конкурса — Йоана Дамена (Joan Daemen) и Винсента Рэймена (Vincent Rijmen), предложивших метод Rijndael. Название Rijndael (произносится примерно как «Райн-дол») представляет собой сокращение фамилий авторов разработки. В ноябре 2001 года Rijndael был объявлен стандартом правительства США и опубликован как FIPS 19742. Благодаря абсолютной открытости конкурса, техническим возможностям метода и тому факту, что победившая команда состояла из двух молодых бельгийских криптографов (которые вряд ли стали бы сотрудничать с NSA, предоставляя какие-то лазейки), Rijndael стал главным мировым криптографическим стандартом. AES в настоящее время является частью набора инструкций для некоторых процессоров.
Rhindael поддерживает длины ключей и размеры блоков от 128 до 256 бит с шагом в 32 бита. Длины ключей и блоков могут выбираться независимо друг от друга. При этом AES задает размер блока в 128 бит, а длину ключа — в 128, 192 или 256 бит. Вряд ли кто-то будет использовать 192-битные ключи, поэтому фактически есть два варианта AES: 128-битный блок с 128-битным ключом и 128-битный блок с 256-битным ключом.
Ниже мы рассмотрим только один вариант алгоритма — 128/128, поскольку это стандарт для коммерческих приложений. При использовании 128-битного ключа размер ключевого пространства составляет 2128 ≈ 3 × 1038 ключей. Даже если АНБ удастся собрать компьютер с миллионом параллельных процессоров, каждый из которых способен вычислять один ключ в пикосекунду, на перебор всех значений потребуется около 1010 лет. К тому времени Солнце уже давно потухнет, и нашим потомкам придется читать распечатку ключа при свечах.
Rijndael
С математической точки зрения Rijndael основан на теории полей Галуа, благодаря чему можно строго доказать некоторые его свойства, касающиеся секретности. Также можно рассмотреть его как код на языке С, не вдаваясь в математические подробности.
Как и в DES, в Rijndael применяются подстановки и перестановки. И там и там используется несколько итераций, число которых зависит от размера ключа и блока и равно 10 для 128-разрядного ключа и 128-битных блоков (при максимальном размере ключа и блоков число итераций равно 14). Однако, в отличие от DES, все операции выполняются над целым количеством байтов, что позволяет создавать эффективные реализации как в аппаратном, так и в программном исполнении. Из-за того что DES ориентирован на использование битов, его программные реализации работают медленно.
Алгоритм Rijndael обеспечивает не только высокую степень безопасности, но и отличную скорость. Хорошая программная реализация на компьютере с частотой 2 ГГц может шифровать данные со скоростью 700 Мбит/с. Этого достаточно для шифрования более десяти видеофайлов в формате 4K в режиме реального времени. Аппаратные реализации работают еще быстрее.
8.5.3. Режимы шифрования
Несмотря на всю эту сложность, по сути, AES (а также DES и любой другой блочный код) является моноалфавитным подстановочным шифром с большими длинами символов (128-битные символы в AES, 64-битные — в DES). Для любого отрывка открытого текста шифр при прогоне через один и тот же шифрующий блок будет всегда одинаковым. Скажем, если вы 100 раз зашифруете открытый текст abcdefgh, используя алгоритмы DES или AES с одним и тем же ключом, то вы 100 раз получите на выходе одинаковый зашифрованный текст. Взломщик может попытаться использовать это свойство при попытке расшифровки текста.
Режим электронной кодовой книги
Чтобы понять, как использовать это свойство моноалфавитного подстановочного шифра для частичного взлома шифра, мы рассмотрим кодирование (тройное) по стандарту DES (поскольку изображать 64-разрядные блоки проще, чем 128-разрядные). Имейте в виду, что AES сталкивается с такими же проблемами. Самый очевидный способ кодирования длинного сообщения заключается в разбиении его на отдельные блоки по 8 байт (64 бита) и кодировании этих блоков одним и тем же ключом по очереди. Последний блок при необходимости можно дополнить до 64 бит. Этот метод назван режимом ECB (Electronic Code Book mode — режим электронной кодовой книги) по аналогии с традиционными кодовыми книгами, в которых содержались слова и соответствующие им шифры (обычно пятизначные десятичные числа).