Алгоритм MARS

был разработан коллективом криптологов из корпорации IBM. Именно IBM в свое время разработала семейство алгоритмов Lucifer, которое легло в основу предыдущего стандарта шифрования США— DES. Из авторов Lucifer в разработке алгоритма MARS принял участие Дон Коп- персмит, известный также и другими работами в области криптологии.

По правилам конкурса AES разрешалось вносить незначительные изменения в участвовавшие в конкурсе алгоритмы в течение первого раунда конкурса. Пользуясь этим правилом, авторы алгоритма MARS изменили процедуру расширения ключа, в результате чего существенно снизились требования, предъявляемые алгоритмом к энергонезависимой и оперативной памяти [284]. Рассмотрим здесь именно модифицированную версию алгоритма.

Структура алгоритма

При разработке алгоритма его авторы исходили из двух следующих предположений [111]:

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

?         Скорее всего, алгоритм с гетерогенной структурой будет лучше противостоять криптоаналитическим методам будущего, чем алгоритм, все раунды которого идентичны.

В результате разработчики алгоритма MARS придали ему сильно гетерогенную структуру — раунды алгоритма весьма различаются между собой. можно описать следующим образом (рис. 3.124):

1.     Выполняется предварительное наложение ключа: на 32-битные субблоки А, В, С, D накладываются 4 фрагмента расширенного ключа к0…к3 операцией сложения по модулю 2 .

2.     Выполняются 8 раундов прямого перемешивания (без участия ключа шифрования).

3.     Выполняются 8 раундов прямого криптопреобразования.

4.      Выполняются 8 раундов обратного криптопреобразования. Этапы 3 и 4 называются «криптографическим ядром» алгоритма MARS.

5.     Выполняются 8 раундов обратного перемешивания, также без участия ключа шифрования.

6.     Выполняется финальное наложение фрагментов расширенного ключа к36…к39 операцией вычитания по модулю 232 .

7.        Алгоритм представляет собой расширенную сеть Фейстеля. В каждом раунде выполняется обработка одного из субблоков и наложение результатов обработки на остальные субблоки, после чего субблоки меняются местами. Конкретные преобразования зависят от типа раунда и будут рассмотрены далее. Кроме того, между раундами могут выполняться различные дополнительные действия, которые также будут описаны далее.


Рис. 3.124. Структура алгоритма MARS

 


Раунд прямого перемешивания показан на рис. 3.125. Как видно из рисунка, в раунде выполняются следующие действия:

1.     Значение субблока Л «прогоняется» через таблицу замен 50 и накладывается на субблок В операцией XOR.

2.     Исходное значение субблока Л вращается на 8 битов вправо.

3.     Результат предыдущего шага обрабатывается таблицей замен и снова на- кладывается на субблок В операцией сложения по модулю 2 .

4.      Результат шага 2 вращается на 8 битов вправо.

5.     Результат предыдущего шага обрабатывается таблицей замен S0 и накла- дывается на субблок С операцией сложения по модулю 2 .

6.     Результат шага 4 вращается на 8 битов вправо.

7.      Результат предыдущего шага обрабатывается таблицей замен 5, и накладывается на субблок D операцией XOR.

8.     Субблоки меняются местами, как показано на рис. 3.125.

Кроме того, в некоторых раундах прямого перемешивания выполняются следующие дополнительные операции (не приведены на рис. 3.125):

?      в раундах №№ 0 и 4 после шага 7 выполняется наложение значения суб- блока D на субблок А операцией сложения по модулю 2 ;

?      в раундах №№ 1 и 5 субблок В аналогичным образом накладывается на субблок Л.

По словам авторов алгоритма, эти операции существенно усиливают алгоритм MARS против дифференциального криптоанализа [111].

Таблицы замен 50 и S{ приведены в Приложении. В качестве входного значения S0 (аналогично и Sx) принимает 8 младших битов входного слова. Таблица S0 меняет значение 0 на 09D0C479, значение 1 — на 28C8FFE0 ит. д.

Структура раунда прямого криптопреобразования приведена на рис. 3.126. Основой раунда является расширяющее криптопреобразование преобразующее 32-битное входное слово А в три выходных 32-битных значения, каждое из которых определенным образом накладывается на остальные субблоки (см. рис. 3.126). После этого субблок А вращается влево на 13 битов, затем субблоки меняются местами аналогично раунду прямого перемешивания.

Рис. 3.126. Раунд прямого криптопреобразования алгоритма MARS

 

Рис. 3.127. Операция Е алгоритма MARS

Преобразование Е показано на рис. 3.127. Из входного значения формируются три потока 0{…03, над которыми производятся следующие действия:  где:

Оу — номер итерации, начиная с 0; 0 / = 0…14 ;

•                 перемешивание массива Т:

где S — табличная замена, выполняемая по тем же правилам, что и в операции Е\

•                 заключительная перестановка: где п = 0…9.

3.     На вычисленные подключи накладываются дополнительные требования, состоящие в следующем:

•                 каждый подключ, используемый для умножения в операции Е (т. е. подключи с нечетными индексами от к5 до к35 включительно), должен

иметь нечетное значение; мало того, единичными должны быть два младших бита подключа, а не один;

•       те же подключи не должны содержать 10 нулевых или 10 единичных битов подряд.

Модификация подключей в соответствии с данными требованиями выполняется следующим образом.

•        2 младших бита обрабатываемого подключа устанавливаются в единичные значения; старое значение запоминается в переменной j (оно будет использовано впоследствии). Результирующее значение подключа обозначается как W.

•        Вычисляется 32-битная маска М, которая будет использована для модификации подключа— для обеспечения отсутствия в нем 10 подряд нулевых или единичных битов. Маска вычисляется следующим образом:

0 устанавливаются в 1 биты М, соответствующие тем битам обрабатываемого подключа, которые входят в последовательности из 10 нулевых или 10 единичных битов; остальные биты устанавливаются в 0;

0 обнуляются те единичные биты маски М, которые соответствуют любому из условий:

где / — номер бита, начиная с 0, a Wt — значение /-го бита.

•        Используется таблица корректирующих значений В, определенная следующим образом:

Элементы таблицы В эквивалентны элементам с 265-го по 268-й включительно объединенной таблицы 5; именно эти элементы используются для коррекции подключей благодаря их специфическим свойствам.

С помощью данной таблицы следующим образом вычисляется финальное значение подключа Kt:

где & — логическая побитовая операция «и», а вращение Bj определяется пятью младшими битами предыдущего подключа Kt_x.

Описанная процедура гарантирует требуемые свойства у подключей [111].

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

Сравнительный анализ достоинств и недостатков алгоритмов — финалистов конкурса AES приведен в разд. 2.1.

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