<< Предыдущая

стр. 14
(из 39 стр.)

ОГЛАВЛЕНИЕ

Следующая >>


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

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

Во-вторых, в подписи должно использоваться не само сообщение, а его хэш.
Причина этого заключается в том, что без использования хэш-функции оказы-
вается возможным подобрать сообщение, соответствующее заданному значе-
нию подписи, вычисленному определенным образом. Данная атака также опи-
сана в книге "Handbook of Applied Cryptography". А если подписывается
значение хэша, то для отыскания подходящего сообщения придется обратить
еще и хэш, что при использовании стойкой криптографической хэш-функции
сделать почти невозможно.

Описанные выше недостатки в FGInt были обнаружены и успешно использова-
<ы представителями группы CORE, что позволило им выпустить генераторы
88 Часть II. Несколько слов о криптологии

регистрационных кодов к нескольким версиям программы SmartWhois, защи-
щенной с использованием цифровой подписи EIGamal с ключом длиной
960 бит, реализованной через библиотеку FGInt.


Подытоживая все написанное про алгоритмы и протоколы, можно сказать,
что хотя криптографическая часть любой защиты, возможно, поддается
формализации легче многих других элементов, это не делает ее гарантиро-
ванно стойкой. Существует множество способов из надежных составляющих ]
построить слабую систему. И только глубокие знания в криптогра-
фии, подкрепленные постоянной практикой, помогают снизить вероят-
ность неудачи.
Глава 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 года начался прием заявок на участие в конкурсе. К кан-
дидатам предъявлялись следующие обязательные требования:
П алгоритм должен относиться к симметричной криптографии (с секрет-
ным ключом);
П алгоритм должен являться блочным шифром;
О алгоритм должен поддерживать следующие комбинации размеров ключа
и блока шифрования: 128—128, 192—128 и 256—128.
90 Часть II. Несколько слов о криптологии

15 июня 1998 прием заявок закончился, и к участию в конкурсе оказа-
лись допущены 15 алгоритмов, разработанных криптографами из 12 стран.
В процессе сравнения конкурсантов оценивались следующие характеристики:
О криптостойкость — объем усилий, необходимых для успешного криптоа-
нализа. Эта характеристика является наиболее важной для алгоритма
шифрования и строится на основе следующих факторов:
• реальная криптостойкость алгоритма по сравнению с конкурентами
(при одинаковых размерах блока и ключа шифрования);
• насколько выход алгоритма неотличим от случайной перестановки
(пермутации) входного блока;
• серьезность математического обоснования стойкости алгоритма;
• другие факторы, проявившиеся во время открытого публичного изу-
чения свойств алгоритма;
• стоимость реализации — затраты, с которыми придется столкнуться при
использовании алгоритма. Стоимость определяется совокупностью сле-
дующих критериев:
• лицензионные требования. Предполагается, что AES должен получить
не меньшее распространение, чем имел DES, т. е. применяться массо-
во. Следовательно, предпочтение отдается алгоритмам, которые или
не покрываются патентами, или допускают неограниченное бесплат-
ное использование в любой точке мира;
• вычислительная эффективность (скорость алгоритма). Предполагается,
что алгоритм должен быть достаточно быстрым как при программной,
так и при аппаратной реализации;
• требования к памяти. Оценивается объем необходимой постоянной
' и оперативной памяти при программной реализации в разных средах,
а также число вентилей для аппаратной реализации;
• функциональные характеристики алгоритма, такие как:
• гибкость. Предпочтение отдается алгоритму, допускающему более ши-
рокое применение, т. к. он способен решить больше задач, стоящих
перед пользователями. Положительно характеризуют алгоритм сле-
дующие свойства:
О возможность оперировать блоками и ключами шифрования, отличны-
ми по размеру от описанных в обязательных требованиях к алгоритму;
О возможность надежной и эффективной реализации на большом ко-
личестве разных платформ: на восьмибитовых процессорах, в сетях
асинхронной передачи данных (Asynchronous Transfer Mode, ATM),
в голосовых и спутниковых коммуникациях, в телевидении высо-
кой четкости (High Definition Television, HDTV) и т. Д.;
Глава 8. Рекомендации по выбору алгоритмов gу

О возможность использования алгоритма для построения эффектив-
ного потокового шифра, генератора аутентификационных кодов,
хэш-функции, генератора псевдослучайных чисел и т. д.;
• удобство программной и аппаратной реализации. Алгоритм не должен
быть спроектирован с ориентацией только на аппаратную или только
на программную реализацию. Если алгоритм может быть реализован
как встроенная программа (firmware), это является его достоинством;
• простота. Чрезмерное усложнение алгоритма затрудняет его анализ и
реализацию, поэтому предпочтение отдается сравнительно простым
алгоритмам.
Вычислительной эффективности и требованиям к памяти имеет смысл уде-
лить чуть больше внимания.

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

Рассмотрим два алгоритма: RC4 и DES.

Программная реализация алгоритма шифрования RC4 очень проста
(см. разд. 7.2). Внутреннее состояние шифра описывается 256-байтовой табли-
цей перестановок state и двумя регистрами х и у. Для шифрования одного бай-
та необходимо произвести 3 операции чтения и 2 операции записи в таблицу
перестановок, а также выполнить 3 операции сложения по модулю 256.
И большая часть времени при шифровании тратится именно на обращение к
памяти. Аппаратная реализация RC4 не будет давать значительных преиму-
ществ перед программной, т. к. тормозящим фактором все равно останется об-
ращение к памяти, а на современных универсальных (неспециализированных)
компьютерах обмен с памятью сильно оптимизирован и производится на очень
высокой частоте.

С алгоритмом шифрования DES все иначе. Исходный текст DES на языке С за-
нимает десятки килобайт и весьма сложен для первичного восприятия.
В процессе работы DES оперирует не байтами или словами, а отдельными би-
тами. Но в процессорах архитектуры х86, к которым относятся Intel Pentium и
AMD Athlon, практически нет готовых команд для работы с битами — каждую
операцию DES приходится реализовывать посредством нескольких команд
процессора. То же самое, наверное, справедливо для большинства современ-
ных универсальных процессоров. А при аппаратной реализации такие опера-
ции, как, например, перестановки битов, можно реализовать на схемном уровне,
92_ Часть II. Несколько слов о криптологии

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

Одна из важных областей применения нового стандарта шифрования — смарт-
карты. Стоимость карты явным образом зависит от размеров доступной внутри
карты оперативной и постоянной памяти. Самые дешевые смарт-карты стоят
около 25 центов, но имеют всего 2 Кбайта постоянной памяти для хранения ал-
горитмов и констант и 64 байта оперативной памяти для хранения промежуточ-
ных значений и шифруемых данных. Разумеется, гораздо выгоднее иметь
в качестве стандарта те криптографические алгоритмы, которые смогут рабо-
тать в самых дешевых картах при минимальных ресурсах.


Вернемся к конкурсу AES. В 1999 году, после проведения второй конферен-
ции по выбору кандидата на AES, из 15 претенденте!* осталось только 5. Это
были алгоритмы RC6, Rijndael, MARS, Serpent и Twofish. Безусловного ли-
дера среди них не оказалось, но были явные кандидаты на выбывание. Так,
например, Seipent оказался медленней всех конкурентов в программной
реализации, 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 не просто ведется выбор симметричного блочного алгоритма,
Глава 8. Рекомендации по выбору алгоритмов 93_

но делается попытка подобрать коллекцию надежных и эффективных крип-
тографических алгоритмов. Рассматриваются такие криптографические
примитивы, как симметричные блочные и потоковые шифры, хэш-
функции, алгоритмы контроля целостности сообщений, схемы цифровой
подписи и шифрования с открытым ключом.
Проект 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.
Выбранные алгоритмы должны стать частью стандарта ISO/IEC 18033. Есть
основания полагать, что новый стандарт будет иметь много общего с реко-
мендациями NESSIE и существующими стандартами, такими как IEEE P1363.



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

8.2. Практические рекомендации
известных специалистов
Когда для решения конкретной задачи требуется выбрать алгоритм, устраи-
вать открытый конкурс — не самый быстрый путь. В большинстве случаев
достаточно выбрать его из уже существующих алгоритмов.
Авторы книги "Криптография. Официальное руководство RSA Security"
("RSA Security's Official Guide to Cryptography") Стив Бернет (Steve Burnett) и
Стивен Пэйн (Stephen Paine) для шифрования соединений между компью-
терами рекомендуют использовать потоковый алгоритм RC4, т. к. он обес-
печивает достаточно высокую скорость. Для таких приложений, как базы
данных, электронная почта и защищенное (зашифрованное) хранение фай-
лов, рекомендуется использовать блочные алгоритмы шифрования, в част-
ности AES (Rijndael).
Брюс Шнайер (Bruce Schneier) вместе с Нилсом Фергюсоном (Niels
Ferguson) в своей книге "Практическая криптография" ("Practical Cryptography")
считают, что с точки зрения безопасности карьеры лица, принимающего
решение, Rijndael — действительно самый приемлемый блочный алгоритм
шифрования. Он принят в качестве стандарта в США, и если в AES в буду-
щем будут обнаружены серьезные недостатки, наказывать за это, скорее
всего, никого не станут. Кроме того, AES уже достаточно широко распро-
странен и поддерживается большим числом библиотек. Так что AES — поч-
ти беспроигрышный выбор.
Если очень важно обеспечить максимальную стойкость шифрования, а ско-
рость играет малозначительную роль, рекомендуется обратить внимание на
другого финалиста конкурса AES — алгоритм Serpent, который большинство

<< Предыдущая

стр. 14
(из 39 стр.)

ОГЛАВЛЕНИЕ

Следующая >>