Алгоритм НРС

Алгоритм НРС был разработан известным американским криптологом Ри­чардом Шреппелем (Richard Schroeppel) из Университета штата Аризона в 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-битные регистры 50 и S,, над содержимым которых в каждом раунде выполняется множество элементарных операций, приведен­ных на рис. 3.93, где использованы следующие обозначения:

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

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

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

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

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

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

где Ъ— размер шифруемого блока в битах, а Р/19— «псевдослучайная» константа:clip_image004

происхождение которой прозрачно — это запись первых 19 знаков числа л, игнорируя запятую;

clip_image006

Хп — значения, определяющие количество битов циклического сдвига в соответствующей операции:

clip_image008

где:

• < 50 > — текущее на момент выполнения операции значение регистра S0;

• & — операция побитового логического «и»;

• / — номер текущего раунда (начиная с 0);

□ кп — фрагмент расширенного ключа (процедура расширения ключа шифрования описана далее):

clip_image010

где К — расширенный ключ — массив, состоящий из 256 64-битных слов;

Spn — фрагмент дополнительного ключа, участвующего в операции шифрования (spice):

clip_image012

где Spice — массив дополнительного ключа, состоящий из 8 64-битных слов.

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

По завершении 8 раундов преобразований выполняются 2 дополнитель­ные операции: значение 50‘ (т. е. значение регистра S0 после выполнения приведенных на рис. 3.93 действий) складывается по модулю 264 с К[Ь + 8], a Si —с К[Ъ + 9\.

1 Между вычислениями к\ и к2 значение < 50 >. в общем случае, изменилось, поэтому кх Фк2*

Как написано автором в спецификации алгоритма, «его структура является сетью Фейстеля, однако измененной настолько, что не факт, что Фейстель распознал бы ее». Эксперты конкурса AES также не узнали в структуре алго­ритма сеть Фейстеля [284].

Расшифровывание производится выполнением обратных операций в обрат­ной последовательности.

Процедура расширения ключа

Задача процедуры расширения ключа— формирование расширенного клю­ча, представляющего собой массив из 256 64-битных слов. Причем для каж­дого из субалгоритмов должен быть отдельный массив расширенного ключа (процесс расширения ключа для каждого из субалгоритмов различен). Стоит сказать, что знание одного из массивов расширенного ключа не позволяет вычислить значения других расширенных ключей, а также исходный ключ шифрования. Однако если используется фиксированный размер блока шиф­руемых данных, достаточно сформировать расширенный ключ только для субалгоритма, соответствующего используемому размеру блока.

Опишем процедуру расширения ключа:

1. Массив расширенного ключа инициализируется так:

clip_image014

где:

Nc — номер субалгоритма (например, 3 для наиболее актуального суб­алгоритма HPC-Medium);

L — размер ключа шифрования в битах;

• £19 и /?220 — аналогичные /719 «псевдослучайные» константы:

clip_image016

Остальные 253 слова массива инициализируются следующим образом: K[i] = K[i -1] + (K[i 2] ®(K[i – 3]» 23) 0 (k[i – 3]« 41)) mod264

2. Производится побитовое сложение по модулю 2 ключа шифрования и проинициализированного массива расширенного ключа (но не более 128 слов — вспомним про переменный и неограниченный размер ключа).

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

• Выполняется инициализация регистров S0…S7 следующим образом:

clip_image018

• Для каждого слова расширенного ключа производятся вычисления, приведенные на рис. 3.94. Причем для усиления эффекта перемешива­ния этот этап может выполняться в несколько раундов; автор алгорит­ма рекомендует 3 раунда перемешивания.

На рис. 3.94 использованы следующие обозначения:

• | — операция побитового логического «или»;

• / — номер вычисляемого слова расширенного ключа;

j — номер раунда выполнения этапа 3;

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

clip_image020

4. Если размер ключа шифрования превышает 128 64-битных слов (т. е. 8192 битов— что является более, чем достаточным размером ключа по современным меркам), то для каждого 128-словного фрагмента ключа по­вторяются шаги 2 и 3 — т. е. фрагмент ключа добавляется к расширенно­му ключу и перемешивается.

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

Стоит сказать несколько слов и про дополнительный ключ. Его назначе­ние— модифицировать результат шифрования при одинаковых значениях входных данных и ключа шифрования. Таким образом, Spice играет роль вектора инициализации в режиме шифрования со сцеплением блоков шифра. Автор алгоритма считает возможность использования такого «внутреннего» по отношению к алгоритму вектора инициализации большим преимуществом алгоритма и рекомендует модифицировать значение Spice перед шифровани­ем каждого блока данных [351].

Дополнительный ключ может быть секретным, что увеличивает фактический объем ключевой информации, однако в алгоритме с неограниченным разме-

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

clip_image022

Рис. 3.94. Раунд функции перемешивания процедуры расширения ключа

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

Раунд алгоритма НРС состоит из огромного количества операций. В сравне­нии, например, с раундом отечественного стандарта симметричного шифро­вания ГОСТ 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 эта позиция не повлияла, однако лично мне по­добная критика кажется весьма обоснованной.

Оригинальные тесты. Виртуальные техника – NewsTex и статьи о науке гипотезы

Вы можете следить за любыми ответами на эту запись через 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