Алгоритм НРС

был разработан известным американским криптологом Ричардом Шреппелем (Richard Schroeppei) из Университета штата Аризона в 1998 г. Весьма необычно авторское название алгоритма (НРС, Hasty Pudding Cipher), первые два слова которого переводятся как «мучной заварной пудинг». Я не нашел где-либо объяснения такого «кулинарного» названия алгоритма; причем даже в спецификации алгоритма встречается множество кулинарных терминов, не используемых обычно в криптографии («spice» — специя, «stirring» — взбалтывание и т. д.), себя же, например, в [354] автор называет словом «puddingmeister», т. е. «изготовитель пудинга».

Основные характеристики алгоритма

Еще одна интересная особенность алгоритма— абсолютно произвольный размер шифруемого блока и ключа шифрования — алгоритм НРС не ограничивает эти величины ничем.

На самом деле то, что автор называет алгоритмом НРС, является совокупностью пяти различных (но взаимосвязанных) субалгоритмов, каждый из которых предназначен для шифрования блоков данных определенного размера [351,355]:

?     HPC-Tiny — для шифрования блоков размером от 0 до 35 битов включительно;

?      HPC-Short — от 36 до 64 битов;

?      HPC-Medium — от 65 до 128 битов;

?      HPC-Long — от 129 до 512 битов;

?      HPC-Extended — 513 битов и более.

Рассмотрим подробно субалгоритм HPC-Medium, поскольку именно в его диапазон действия попадает 128-битный размер блока данных, актуальный для конкурса AES (см. разд. 2.1), в котором алгоритм НРС участвовал.

Структура раунда

Шифрование выполняется в 8 раундов. Предварительно шифруемые данные записываются в 64-битные регистры S0 и , над содержимым которых в каждом раунде выполняется множество элементарных операций, приведенных на рис. 3.93, где использованы следующие обозначения:

?       © — операция побитового сложения по модулю 2;

?     знаками + и – обозначены операции, соответственно, сложения и вычитания 64-битных операндов по модулю 264;

?      «п — циклический сдвиг влево (или вправо) на указанное фиксированное число битов;

?      « — циклический сдвиг влево (или вправо) на переменное число битов, определяемое значением 6 младших битов «бокового» параметра;

?       t() — функция обнуления младшего байта 64-битного операнда;

?      Cj — константа, участвующая в вычислениях и определяемая следующим образом:

Достоинства и недостатки алгоритма

Раунд алгоритма НРС состоит из огромного количества операций. В сравнении, например, с раундом отечественного стандарта симметричного шифрования ГОСТ 28147-89 [4] (состоящим всего из четырех элементарных операций — см. разд. 3.1), алгоритм НРС выглядит чрезвычайно сложным. Тем не менее, поскольку подавляющее большинство действий выполняется с 64- битными операндами, на 64-битных платформах алгоритм НРС показал впечатляющую скорость шифрования [284, 352]: 128-битные блоки данных шифровались алгоритмом НРС быстрее всех алгоритмов — участников конкурса, за исключением алгоритма DFC (также ориентированного на 64-битные платформы), а 512- и 1024-битные блоки алгоритм НРС шифрует в 2 раза быстрее, чем ближайший конкурент по скорости — алгоритм DFC, и в 3 и более раза быстрее остальных алгоритмов, участвовавших в конкурсе. Однако стоит отметить, что на конкурсе AES «засчитывался» только 128-битный размер блока. Кроме того, на остальных платформах алгоритм НРС показывал заметно худшие результаты.

При проведении исследований в рамках конкурса AES были обнаружены и другие недостатки алгоритма НРС [284]:

?     каждый 256-й ключ алгоритма имеет 230 эквивалентных ключей; этот недостаток был оперативно исправлен автором алгоритма еще до подведения итогов первого раунда конкурса AES (здесь рассмотрена уже исправленная версия) [351, 354];

?     очень медленная процедура расширения ключа шифрования, которая не может выполняться параллельно с собственно шифрованием данных;

?     алгоритм предъявляет очень большие требования к энергонезависимой и оперативной памяти, что весьма затрудняет его применение в смарт- картах;

?     сложная структура алгоритма затрудняет его исследование с целью доказательства отсутствия уязвимостей.

не попал во второй этап конкурса. В своей статье [354] автор алгоритма обрушился с критикой на экспертов конкурса, которая сводилась к следующему утверждению: на конкурсе AES неправильно расставили приоритеты— алгоритм, выбираемый, фактически, в качестве мирового стандарта, должен быть оптимизирован именно под 64-битные платформы, за которыми уже ближайшее будущее. Кроме того, по словам разработчика алгоритма НРС, нельзя разработать алгоритм, одинаково хороший для 64- битных многопроцессорных серверов и дешевых 8-битных смарт-карт. На результаты конкурса AES эта позиция не повлияла, однако лично мне подобная критика кажется весьма обоснованной.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100