Шрифт:
Закладка:
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 — режим электронной кодовой книги) по аналогии с традиционными кодовыми книгами, в которых содержались слова и соответствующие им шифры (обычно пятизначные десятичные числа).
На илл. 8.15 показано начало компьютерного файла; это список годовых премий сотрудников компании. Файл состоит из последовательных 32-разрядных записей (по одной на сотрудника) следующего формата: 16 байт на имя, 8 байт на должность и 8 байт на премию. Каждый из шестнадцати 8-байтных блоков (пронумерованных от 0 до 15) кодируется шифром DES.
Илл. 8.15. Открытый текст файла, зашифрованного в виде 16 DES-блоков
Лесли только что поругалась с начальством и не рассчитывает на большую премию. Ким, напротив, — любимица босса, и все это знают. Лесли может получить доступ к файлу после его зашифровки, но до его
