Глава 8. Рекомендации по выбору алгоритмов

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

8.1. Конкурсы по выбору стандартов шифрования

Хорошим примером того, как стоит подходить к выбору алгоритма шифрования, может послужить описание процесса выбора алгоритма Advanced Encryption Standard (AES) — нового стандарта шифрования США, пришедшего на смену DES.

8.1.1. Стандарт шифрования США

В 1996 году национальный институт стандартов и технологий США (National Institute of Standards and Technology, NIST) начал работу над организацией конкурса по выбору лучшего алгоритма для нового стандарта.

2 января 1997 года NIST официально объявил о запуске программы по разработке нового федерального стандарта обработки информации (Federal Information Processing Standard, FIPS).

12 сентября 1997 года начался прием заявок на участие в конкурсе. К кандидатам предъявлялись следующие обязательные требования:

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

- криптостойкость — объем усилий, необходимых для успешного криптоанализа. Эта характеристика является наиболее важной для алгоритма шифрования и строится на основе следующих факторов:
- реальная криптостойкость алгоритма по сравнению с конкурентами (при одинаковых размерах блока и ключа шифрования);
- насколько выход алгоритма неотличим от случайной перестановки (пермутации) входного блока;
- серьезность математического обоснования стойкости алгоритма;
- другие факторы, проявившиеся во время открытого публичного изучения свойств алгоритма;
- стоимость реализации — затраты, с которыми придется столкнуться при использовании алгоритма.
Стоимость определяется совокупностью следующих критериев:
- лицензионные требования. Предполагается, что AES должен получить не меньшее распространение, чем имел DES, т. е. применяться массово. Следовательно, предпочтение отдается алгоритмам, которые или не покрываются патентами, или допускают неограниченное бесплатное использование в любой точке мира;
- вычислительная эффективность (скорость алгоритма). Предполагается, что алгоритм должен быть достаточно быстрым как при программной, так и при аппаратной реализации;
- требования к памяти. Оценивается объем необходимой постоянной и оперативной памяти при программной реализации в разных средах, а также число вентилей для аппаратной реализации;
- функциональные характеристики алгоритма, такие как:
гибкость. Предпочтение отдается алгоритму, допускающему более широкое применение, т. к. он способен решить больше задач, стоящих перед пользователями. Положительно характеризуют алгоритм следующие свойства:
- возможность оперировать блоками и ключами шифрования, отличными по размеру от описанных в обязательных требованиях к алгоритму;
- возможность надежной и эффективной реализации на большом количестве разных платформ: на восьмибитовых процессорах, в сетях асинхронной передачи данных (Asynchronous Transfer Mode, ATM), в голосовых и спутниковых коммуникациях, в телевидении высокой четкости (High Definition Television, HDTV) и т. Д.;
- возможность использования алгоритма для построения эффективного потокового шифра, генератора аутентификационных кодов, хэш-функции, генератора псевдослучайных чисел и т. д.;
- удобство программной и аппаратной реализации. Алгоритм не должен быть спроектирован с ориентацией только на аппаратную или только на программную реализацию. Если алгоритм может быть реализован как встроенная программа (firmware), это является его достоинством;
- простота. Чрезмерное усложнение алгоритма затрудняет его анализ и реализацию, поэтому предпочтение отдается сравнительно простым алгоритмам.

Вычислительной эффективности и требованиям к памяти имеет смысл уделить чуть больше внимания.

Особенности программной и аппаратной реализации алгоритмов
Разумеется, и программно, и аппаратно можно реализовать практически любой алгоритм. Но при этом очень важно, как быстро будет работать программная реализация и насколько будет дешева и эффективна аппаратная.
Рассмотрим два алгоритма: RC4 и DES.
Программная реализация алгоритма шифрования RC4 очень проста (см. разд. 7.2). Внутреннее состояние шифра описывается 256-байтовой таблицей перестановок stateи двумя регистрами х и у. Для шифрования одного байта необходимо произвести 3 операции чтения и 2 операции записи в таблицу перестановок, а также выполнить 3 операции сложения по модулю 256. И большая часть времени при шифровании тратится именно на обращение к памяти. Аппаратная реализация RC4 не будет давать значительных преимуществ перед программной, т. к. тормозящим фактором все равно останется обращение к памяти, а на современных универсальных (неспециализированных) компьютерах обмен с памятью сильно оптимизирован и производится на очень высокой частоте.
С алгоритмом шифрования DES все иначе. Исходный текст DES на языке С занимает десятки килобайт и весьма сложен для первичного восприятия. В процессе работы DES оперирует не байтами или словами, а отдельными битами. Но в процессорах архитектуры х86, к которым относятся Intel Pentium и AMD Athlon, практически нет готовых команд для работы с битами — каждую операцию DES приходится реализовывать посредством нескольких команд процессора. То же самое, наверное, справедливо для большинства современных универсальных процессоров. А при аппаратной реализации такие операции, как, например, перестановки битов, можно реализовать на схемном уровне,и они будут выполняться за один такт. И аппаратная реализация DES оказывается значительно быстрее, чем программная, даже несмотря на тактовые частоты современных универсальных процессоров, уже давно измеряемые в гигагерцах.
Одна из важных областей применения нового стандарта шифрования — смарт-карты. Стоимость карты явным образом зависит от размеров доступной внутри карты оперативной и постоянной памяти. Самые дешевые смарт-карты стоят около 25 центов, но имеют всего 2 Кбайта постоянной памяти для хранения алгоритмов и констант и 64 байта оперативной памяти для хранения промежуточных значений и шифруемых данных. Разумеется, гораздо выгоднее иметь в качестве стандарта те криптографические алгоритмы, которые смогут работать в самых дешевых картах при минимальных ресурсах.

Вернемся к конкурсу AES. В 1999 году, после проведения второй конференции по выбору кандидата на AES, из 15 претендентов осталось только 5. Это были алгоритмы RC6, Rijndael, MARS, Serpent и Twofish. Безусловного лидера среди них не оказалось, но были явные кандидаты на выбывание. Так, например, Serpent оказался медленней всех конкурентов в программной реализации, a MARS — в аппаратной. Ни для одного из пяти финалистов не было предложено метода криптоанализа, позволяющего взломать алгоритм быстрее, чем полным перебором, но для RC6 был разработан способ взлома 15 из 20 используемых циклов шифрования.

В итоге, 2 октября 2000 года победителем конкурса был объявлен алгоритм шифрования Rijndael, разработанный бельгийцами Винсентом Райменом (Vincent Rijmen) и Йоханом Дайменом (Joan Daemen). Название алгоритма было образовано из начальных букв их фамилий.

26 ноября 2001 года NIST объявил о том, что в США Rijndael получил статус федерального стандарта обработки информации — нового стандарта шифрования данных.

8.1.2. Европейскиекриптографическиесхемы

AES — не единственный открытый конкурс по выбору стандарта шифрования. Аналогичный конкурс проводится также еврокомиссией и носит название NESSIE (New European Schemes for Signature, Integrity and Encryption, новые европейские схемы для цифровой подписи, контроля целостности и шифрования).

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

Проект NESSIE был начат в январе 2000 года. Предполагается, что после выработки рекомендаций по алгоритмам в отдельных категориях, NESSIE окажет существенное влияние на применение криптографии в Европе.

8.1.3. Стандарт ISO/IEC 18033

Параллельно с проектом NESSIE работы по стандартизации криптографических алгоритмов проводит и 27-ой подкомитет первого объединенного технического комитета международной электротехнической комиссии при международной организации по стандартизации (International Organization for Standardization / International Electrotechnical Commission, Joint Technical Committee 1 / Subcommittee 27, ISO/IEC JTC 1/SC 27). Указанный подкомитет самостоятельно не проводит сравнительного тестирования криптографических алгоритмов, но принимает решения, основываясь на информации, полученной в рамках таких открытых проектов, как NESSIE.

Выбранные алгоритмы должны стать частью стандарта КОДЕС 18033. Есть основания полагать, что новый стандарт будет иметь много общего с рекомендациями NESSIE и существующими стандартами, такими как IEEE P1363.

8.1.4. Стандарт шифрования Японии

Агентство развития информационных технологий Японии (Information technology Promotion Agency, I PA), субсидируемое японским министерством международной торговли и индустрии, проводит оценку различных криптографических технологий в рамках проекта CRYPTREC. Целью проекта является формирование набора криптографических алгоритмов, которые будут использоваться в рамках программы электронного правительства Японии, инфраструктура которого должна быть сформирована в 2003 году. CRYPTREC оценивает асимметричные криптографические технологии, пригодные для шифрования, аутентификации, цифровой подписи и распределения ключей, а также симметричные потоковые и блочные шифры, генераторы псевдослучайных чисел и хэш-функции.