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

Криптографические алгоритмы

Для начала обсудим, какие же типы криптографических алгоритмов используются для защиты информации. Криптоалгоритмы прежде всего делятся на три категории (см. схему ниже):

Классификация криптографических алгоритмов
  • Бесключевые, которые не используют каких-либо ключей в процессе криптографических преобразований.
  • Одноключевые, использующие в своих вычислениях некий секретный ключ.
  • Двухключевые, в которых на различных этапах вычислений применяются два вида ключей: секретные и открытые.

Рассмотрим вкратце основные виды криптоалгоритмов.

Хэш-функции. Выполняют «свертку» данных переменной длины в последовательность фиксированного размера — фактически это контрольное суммирование данных, которое может выполняться как с участием некоего ключа, так и без него. Такие функции имеют весьма широкое применение в области защиты компьютерной информации: без хэш-функций не обходятся программы электронной подписи (см., например, статью «Электронная цифровая подпись», «Мир ПК», № 3/02, с. 78), многие средства аутентификации (т.е. проверки личности пользователя компьютером) и контроля целостности любых видов информации.

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

Алгоритмы симметричного шифрования. Это такие алгоритмы, в которых для шифрования и расшифровки используется один и тот же ключ или ключ расшифровки легко вычисляется из ключа шифрования, и наоборот (см., например, статью «Защита информации в компьютерных сетях: шифрование», «Мир ПК», № 2/02, с. 70). Самая обширная категория криптоалгоритмов, подразделяющаяся на алгоритмы блочного (обрабатывают информацию, разбитую на блоки) и потокового (шифруют данные побитово) шифрования.

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

Алгоритмы аутентификации. Позволяют удостовериться в том, что пользователь (или удаленный компьютер) действительно является тем, за кого себя выдает. Простейшая схема аутентификации — парольная — не требует каких-либо криптографических ключей, но она слабая (и это доказано). А с помощью секретного ключа можно построить заметно более сильные схемы аутентификации (см. «Пример аутентификации пользователя сервером»).

Алгоритмы асимметричного шифрования. Применяют два вида ключей: открытый ключ для шифрования информации и секретный для расшифровки. Открытый ключ вычисляется из секретного таким образом, что обратное вычисление (получение секретного ключа из открытого) невозможно. То есть любая информация, зашифрованная общедоступным открытым ключом, может быть расшифрована только обладателем секретного ключа, из которого был вычислен данный открытый (см. «Асимметричное шифрование»).

Алгоритмы электронной подписи. Используют секретный ключ для вычисления электронной цифровой подписи (ЭЦП), а вычисляемый из него открытый — для проверки ЭЦП.

Выбор криптостандартов

В большинстве развитых стран использование различных средств защиты информации регулируется государством, а алгоритмы защиты стандартизованы. В России из перечисленных выше типов алгоритмов есть стандарты на симметричное шифрование (ГОСТ 28147—89), ЭЦП (ГОСТ Р 34.10—94 и ГОСТ Р 34.10—2001) и хэширование (ГОСТ Р 34.11—94).

Отечественные криптостандарты разрабатывались в недрах соответствующих спецслужб. Особенно показательна в этом смысле история алгоритма шифрования ГОСТ 28147—89, который разрабатывался еще в Советском Союзе. Несколько лет после разработки этот алгоритм имел статус секретного и только в начале 90-х годов был рассекречен и опубликован в открытой печати.

Абсолютно по-другому выбирались стандарты США и Европы, где считают, что никакая организация (в том числе спецслужбы, обладающие огромными ресурсами и научным потенциалом) в одиночку не способна провести полное исследование алгоритма — потенциального стандарта шифрования, необходимого для исключения в таком алгоритме уязвимых мест, воспользовавшись которыми гипотетические злоумышленники могли бы вскрыть его. Поэтому механизм утверждения криптостандартов США и Евросоюза таков.

Организаторы объявляют конкурс на выбор стандартов защиты информации, публикуют требования к алгоритмам-претендентам. В течение определенного срока математики и криптологи присылают свои алгоритмы для участия в конкурсе.

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

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

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

Конкурс AES

Американский стандарт симметричного шифрования DES (Data Encryption Standard — стандарт шифрования данных) разработан и принят в 1977 г. При разработке считалось, что стандарт выбирается на 10—15 лет, однако решение о смене стандарта было принято только в 1997 г., т.е. через 20 лет. Причем серьезных недостатков в архитектуре алгоритма найдено не было, за исключением одного — чересчур короткого ключа.

Ключ шифрования DES имеет размер 64 бита, из которых 56 бит являются значащими, а остальные используются для контроля четности. В 1997 г. такого размера хватало с запасом, но с тех пор компьютерная техника развивалась настолько быстро, что 56-битового ключа стало недостаточно уже сейчас. Немного посчитаем:

  • 56-битовый ключ означает наличие 256 вариантов ключа шифрования, т.е. примерно 7,2x1016.
  • Предположим, существует злоумышленник, который хочет найти нужный ему секретный ключ DES полным перебором (например, расшифровывает некий текст всеми 256 вариантами ключа, пока текст не расшифруется, — тогда ключ будет найден).
  • Предположим также, что у злоумышленника есть миллион компьютеров, каждый из которых перебирает миллион ключей DES в секунду.
  • Все компьютеры злоумышленника за секунду переберут 1012 ключей, а за час — 3,6x1015. Это означает, что на полный перебор всех ключей DES у злоумышленника уйдет около 20 ч (7,2x1016/3,6x1015 = 20). Соответственно средний поиск ключа займет всего 10 ч.

Компьютерные ресурсы, перебирающие триллион ключей в секунду, по нынешним временам не являются фантастическими. Их можно найти, например, в Интернете (путем подписки среди желающих предоставить ресурсы своего компьютера для участия в распределенных вычислениях или «зомбировав» незащищенные компьютеры специально подготовленным сетевым вирусом). А если злоумышленник — не частное лицо, а могущественная спецслужба недружественного государства? Тогда, возможно, вскрытие нужного ключа DES произойдет еще быстрее.

Таким образом, стандарт симметричного шифрования США 1977 г. сейчас является недостаточно сильным для шифрования какой-либо долговременной информации. Поэтому в 1997 г. было принято решение обновить стандарт, и с этой целью объявили о проведении конкурса AES (Advanced Encryption Standard — «продвинутый» стандарт шифрования) по выбору нового стандарта.

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

  • 128-битовый размер блока шифруемых данных;
  • поддержка 128-, 192- и 256-битовых ключей. 128-битовый ключ означает 9,5x1022 часов перебора всех вариантов ключа, что, исходя из описанных выше ресурсов, представляется достаточным на десяток лет вперед.

Дополнительных требований оказалось существенно больше:

  1. Алгоритмы не должны быть слабыми по современным меркам, т.е. уязвимыми для уже существующих видов атак.
  2. Алгоритмы не должны предъявлять слишком высокие требования к вычислительным ресурсам и объему оперативной и энергонезависимой памяти. В свое время DES был реализован как в серверах и персональных компьютерах, так и в различных устройствах, обладающих несравнимо меньшими ресурсами, например в смарт-картах и мобильных телефонах. Такая же популярность ожидала и AES.
  3. Алгоритмы должны обладать относительно высоким быстродействием на различных аппаратных платформах — от 8- до 64-битовых (исходя из потенциальной реализации в тех же смарт-картах).
  4. Алгоритмы должны поддерживать возможность параллельных вычислений на многопроцессорных архитектурах — это важно для быстрого шифрования информации на мощных серверах, обслуживающих миллионы клиентов.
  5. У алгоритмов не должно быть слабых или эквивалентных ключей. Слабым является ключ, результат шифрования на котором достаточно легко вскрыть. А эквивалентными называются ключи, которые, будучи различными, приводят к одному и тому же результату шифрования.
  6. Алгоритмы должны иметь относительно простую структуру — для лучшего анализа алгоритма и во избежание встроенных разработчиками алгоритма незадекларированных возможностей (в худшем, хотя и достаточно фантастическом случае — особого ключа, способного расшифровать любую зашифрованную информацию).

Конкурс проводил Национальный институт стандартов и технологий США NIST (National Institute of Standards and Technologies) — тот самый, который в свое время разработал алгоритм DES. NIST получил 15 алгоритмов в качестве претендентов на звание нового стандарта шифрования США. Присланы они были буквально со всего мира — например, алгоритм E2 был разработан в Японии, а SAFER+ (Secure And Fast Encryption Routine — «сильный и быстрый алгоритм шифрования») — совместная разработка ученых из Швейцарии и Армении.

На первом этапе конкурса отсеялись алгоритмы, не обеспечивающие качественного шифрования данных. Осталось пять алгоритмов без уязвимых мест и примерно с одинаковыми характеристиками, из которых по наилучшему соотношению «быстродействие/качество защиты» был выбран алгоритм Rijndael (см. «Алгоритм Rijndael — победитель конкурса AES»), разработанный двумя учеными-математиками из Бельгии — Винсентом Риджменом (V. Rijmen) и Джоан Деймен (J. Daemen).

Таким образом, в 2001 г. алгоритм Rijndael был выбран в качестве нового стандарта блочного симметричного шифрования США и получил название AES. В настоящее время этот алгоритм постепенно заменяет DES, который за 20 с лишним лет своего существования в качестве стандарта был реализован практически везде, где требовалось шифрование данных.

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

Конкурс NESSIE

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

Организаторы конкурса NESSIE поставили перед собой несравнимо более широкие цели, чем американский институт NIST. Конкурс NESSIE предполагал выбор стандартов сразу в нескольких областях обеспечения безопасности компьютерной информации:

  1. Блочное симметричное шифрование.
  2. Потоковое симметричное шифрование.
  3. Асимметричное шифрование.
  4. Хэширование.
  5. Электронная цифровая подпись.
  6. Двухключевая идентификация.

На конкурсе нашлось место даже для криптоаналитического алгоритма, т.е. алгоритма поиска слабых мест в алгоритмах шифрования.

Всего в конкурсе участвовало 40 алгоритмов с еще более широкой географией происхождения, чем на конкурсе AES.

Стоит сказать и о том, что организаторы конкурса не преследовали цель выбрать наилучший из алгоритмов в каждой из перечисленных категорий: здесь могло быть по нескольку победителей — «алгоритмов без недостатков» (а с потоковыми шифрами случилось наоборот — все шесть присланных на конкурс алгоритмов были отсеяны по причине недостаточной стойкости).

Формально конкурс проходил в несколько этапов, как и AES, и на каждом из них отсеивались алгоритмы с найденными к тому времени уязвимыми моментами.

Кроме алгоритмов, присланных на конкурс, рассматривались и известные криптографические стандарты и алгоритмы: те же участники конкурса AES — алгоритмы RC6 и Rijndael в категории алгоритмов блочного шифрования, стандарт хэширования США алгоритм SHA (Secure Hash Algorithm) и др.

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

* * *

Алгоритм AES стал новым стандартом США и де-факто — стандартом симметричного шифрования почти во всем мире.

Хуже с европейскими стандартами: в США выбором AES занимался уполномоченный государственный институт NIST, а в Европе — научные организации (например, Католический университет г. Лювен, Бельгия) и крупные корпорации (например, Siemens), причем выводы экспертов носили лишь рекомендательный характер. Кроме того, конкурс NESSIE был чересчур широк — возникло впечатление, что огромное количество алгоритмов эксперты просто не успели досконально изучить за три года его проведения. Даже простое перечисление результатов конкурса могло бы стать темой отдельной статьи .

Итог: несмотря на окончание конкурса NESSIE в феврале 2003 г., общеевропейских криптографических стандартов до сих пор нет.

Сергей Петрович Панасенко — начальник отдела разработки программного обеспечения фирмы «АНКАД», канд. техн. наук. С ним можно связаться по e-mail: develop@ancud.ru

Пример аутентификации пользователя сервером

Сервер проверяет «истинность» удаленного пользователя:

  1. Сервер генерирует случайное число.
  2. Отправляет его пользователю.
  3. Пользователь зашифровывает полученное число секретным ключом и отправляет результат серверу.
  4. Сервер расшифровывает полученные данные таким же секретным ключом.
  5. Сравнивает с исходным числом.

Равенство чисел означает, что пользователь обладает требуемым секретным ключом, т.е. ему удалось доказать свою легитимность.

Асимметричное шифрование

  1. Пользователь B зашифровывает сообщение на открытом ключе пользователя A (который когда-либо передал его пользователю B).
  2. Пользователь A расшифровывает сообщение своим секретным ключом.

Алгоритм Rijndael — победитель конкурса AES

Алгоритм разбивает входные данные на блоки, каждый из которых представляет собой двумерный массив размером 4x4, 4x6 или 4x8 байт (в зависимости от размера входного блока допускается несколько фиксированных размеров). Затем над этими данными выполняется от 10 до 14 раундов, в каждом из которых производятся следующие операции (с небольшими исключениями):

1. Байтовая замена: значение каждого байта массива заменяется другим согласно специальной таблице.
2. Побайтовый циклический сдвиг строк массива влево на различное число байт.
3. Умножение столбцов массива на константную матрицу.
4. Сложение с ключом раунда (определенным образом вычисляемый фрагмент ключа шифрования алгоритма).