Конкурс NESSIE и алгоритм MISTY1

© Панасенко Сергей, 2004.

Не успел еще закончиться конкурс AES – конкурс по выбору нового стандарта шифрования США (см. статью «Неудачники конкурса AES: алгоритм шифрования E2» - «Банки и технологии» - № 6/2003, с. 82), как в Европе был объявлен весьма похожий конкурс по выбору криптостандартов Евросоюза.

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

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

На конкурсе даже нашлось место для криптоаналитического алгоритма, т.е. алгоритма, целью которого является поиск уязвимостей в криптоалгоритмах, однако, экспертами конкурса данный алгоритм был признан «бесполезным», поэтому в различных отчетах по конкурсу NESSIE криптоаналитических алгоритм отсутствует.
Мало того, эксперты не ставили целью выбрать именно лучший алгоритм в каждой из этих категорий – победителей могло быть много. Например, в категории алгоритмов электронной цифровой подписи было выбрано целых три победителя (RSA-PSS, ECDSA и SFLASH), а среди присланных алгоритмов потокового симметричного шифрования не нашлось ни одного, удовлетворившего экспертов.
На конкурс было прислано 42 алгоритма, к которым на более поздних этапах конкурса присоединились несколько известных криптоалгоритмов и стандартов других стран, например, победитель конкурса AES – алгоритм Rijndael, известное семейство функций хэширования SHA (Secure Hash Algorithm) и другие.

Алгоритмы блочного симметричного шифрования

Несомненно, наиболее интересной из всех категорий, в которых производилось исследование, являлась категория алгоритмов блочного симметричного шифрования. Именно в этой категории производился и выбор криптостандарта США на конкурсе AES. А на NESSIE в данную категорию было прислано наибольшее число алгоритмов – 17, которые были разделены на несколько подкатегорий по критерию размерности блока шифруемого текста:

1. 64 бита,
2. 128 бит,
3. 256 бит.

В ряде присланных на конкурс алгоритмов размер блока задавался параметрически, поэтому данные алгоритмы участвовали сразу в нескольких подкатегориях.
Из алгоритмов, шифрующих 64-битные блоки, победителем стал алгоритм MISTY1, который будет подробно рассмотрен ниже.
Кроме того, победителями среди блочных симметричных шифров стали алгоритмы Camellia (разработан известными японскими компаниями Mitsubishi Electric и Nippon Telegraph and Telephone), SHACAL-2 (разработка французской фирмы Gemplus) и AES/Rijndael.

Алгоритм MISTY1 разработан в 1996 году японской компанией Mitsubishi Electric.
Алгоритм имеет весьма интересную структуру – он основан на «вложенных» сетях Фейстеля (см. статью «Неудачники конкурса AES: алгоритм шифрования E2»). На рис. 1. представлена последовательность операций, выполняемых при зашифровании данных алгоритмом MISTY1. Как видно, алгоритм является сетью Фейстеля с различными четными и нечетными раундами. В нечетных раундах, по сравнению с четными, выполняется дополнительно операция FL, которая также выполняется и по завершении последнего раунда. Количество раундов строго не определено, но рекомендуется выполнять 8 раундов преобразований.
Операция FL (показана на рис. 2) является достаточно простой: 32-битное входное значение разбивается на два субблока по 16 бит, над которыми выполняются операции сложения по модулю 2 и побитные логические операции «и» (&) и «или» (|), причем в логических операциях участвуют определенные фрагменты расширенного ключа шифрования для операции FL: KL1 и KL2 (см. ниже).
Несравнимо более сложной является операция FO, схема которой показана на рис. 3. Она и представляет собой «второй уровень» сети Фейстеля внутри основной структуры алгоритма, показанной на рис. 1. В данной операции 32-битное входное значение также делится на два 16-битных фрагмента, один из которых обрабатывается операцией сложения по модулю 2 с определенным фрагментом ключа для операции FO (KOx) и операцией FI, после чего значения субблоков складываются по модулю 2 и меняются местами. Фактически, схема на рис. 3 является трехраундовой сетью Фейстеля с дополнительным сложением по модулю 2 после финального раунда.
В отличие от операций FL и FO, операция FI обрабатывает 16-битные блоки входных данных (см. рис. 4). И снова это «вложенная» 3-раундовая сеть Фейстеля, обрабатывающая 7-битный и 9-битный субблоки, над которыми выполняются следующие операции:

1. Табличные замены S7 и S9 над 7- и 9-битным субблоком соответственно.
2. Сложение субблоков между собой по модулю 2, причем в первом и третьем раундах 7-битный субблок дополняется нулями и результатом сложения является 9-битный субблок, а во втором раунде при сложении отбрасываются два левых бита 9-битного субблока и результатом сложения является 7-битный субблок.
3. Сложение по модулю 2 соответствующих субблоков с 7- и 9-битным фрагментами расширенного ключа шифрования KI1 и KI2, выполняемое во втором раунде.

Размерность ключа алгоритма MISTY1 – 128 бит. Перед началом работы алгоритма или параллельно с описанными выше операциями выполняется процедура расширения ключа шифрования, в которой вычисляются фрагменты ключа, используемые в операциях FL, FO и FI. Процедура расширения ключа не является сложной, кроме того, в ней используется фрагмент самого алгоритма – функция FI, поэтому на расширение ключа шифрования не требуются дополнительные ресурсы (в отличие от многих других алгоритмов шифрования, в которых расширение ключа может быть достаточно ресурсоемкой операцией, – например, данный недостаток есть у алгоритма MARS – одного из финалистов конкурса AES).
В результате исследований алгоритма MISTY1 эксперты не обнаружили каких-либо слабостей у данного алгоритма при достаточно высокой скорости шифрования, что также является немаловажной характеристикой криптоалгоритмов. Стоит сказать и о том, что вариант алгоритма MISTY1 – алгоритм KASUMI – в 2000 году стал стандартом шифрования мобильной связи W-CDMA.

Несмотря на сходство целей конкурсов AES и NESSIE, между ними есть немало различий, в частности:

1. Конкурс AES проводил государственный институт США NIST (National Institute of Standards and Technology – Национальный институт стандартов и технологий), имеющий все полномочия на выбор нового стандарта шифрования США (и опыт стандартизации криптоалгоритмов). А организаторы конкурса NESSIE – научные организации и крупные корпорации (например, Католический университет г. Лювен, Бельгия, университет г. Берген, Норвегия, корпорация Siemens и другие), выбор которых носит лишь рекомендательный характер. Соответственно, есть сомнения, что у Евросоюза в ближайшее время появятся криптостандарты, основанные на алгоритмах – победителях конкурса NESSIE.
2. В отличие от конкурса AES, NESSIE преследовал несравнимо более широкие цели – выбирались, фактически, алгоритмы для решения большей части проблем защиты информации. Было впечатление, что за три года проведения конкурса эксперты просто не успели провести полномасштабное исследование всех присланных на конкурс алгоритмов. Видимо, не зря скептики считали конкурс NESSIE весьма «расфокусированным» по сравнению с конкурсом AES.

Кроме того, в отличие от сугубо технического конкурса AES, конкурс NESSIE изначально был весьма политизирован – многие эксперты считали, что в качестве стандарта шифрования США (а фактически – общемирового стандарта, судя по широчайшей распространенности предыдущего американского стандарта шифрования DES) NIST ни в коем случае не выберет алгоритм, разработанный за пределами США. Поэтому конкурс NESSIE в различных публикациях именно противопоставлялся конкурсу AES – как «наш (единой Европы) ответ США». Выбор институтом NIST алгоритма Rijndael (разработанного в Бельгии), похоже, даже несколько разочаровал тех европейских экспертов, которые предпочитали видеть в NESSIE большую политическую составляющую. И хотя один из разработчиков алгоритма Rijndael – Винсент Риджмен (Vincent Rijmen) – после победы в конкурсе AES не сомневался, что Rijndael станет стандартом Евросоюза, эксперты предпочли «не рекомендовать к стандартизации» алгоритм Rijndael, несмотря на отсутствие в данном алгоритме недостатков

Рисунки:

1. Структура алгоритма MISTY1.
2. Операция FL.
3. Операция FO.
4. Операция FI .

Перейти на главную страницу Карта сайта Список статей