Алгоритм MARS

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

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

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

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

В результате разработчики алгоритма MARS придали ему сильно гетерогенную структуру — раунды алгоритма весьма различаются между собой. Алгоритм MARS можно описать следующим образом:
Выполняется предварительное наложение ключа: на 32-битные субблоки А, В, С, D накладываются 4 фрагмента расширенного ключа операцией сложения по модулю 2.
Выполняются 8 раундов прямого перемешивания (без участия ключа шифрования).
Выполняются 8 раундов прямого криптопреобразования.
Выполняются 8 раундов обратного криптопреобразования. Этапы 3 и 4 называются «криптографическим ядром» алгоритма MARS.
Выполняются 8 раундов обратного перемешивания, также без участия ключа шифрования.
Выполняется финальное наложение фрагментов расширенного ключа операцией вычитания по модулю 232.

Алгоритм представляет собой расширенную сеть Фейстеля. В каждом раунде выполняется обработка одного из субблоков и наложение результатов обработки на остальные субблоки, после чего субблоки меняются местами. Конкретные преобразования зависят от типа раунда и будут рассмотрены далее. Кроме того, между раундами могут выполняться различные дополнительные действия, которые также будут описаны далее. Как видно из рисунка, в раунде выполняются следующие действия: Значение субблока Л «прогоняется» через таблицу замен 50 и накладывается на субблок В операцией XOR. Исходное значение субблока Л вращается на 8 битов вправо. Результат предыдущего шага обрабатывается таблицей замен Sj и снова накладывается на субблок В операцией сложения по модулю 2. Результат шага 2 вращается на 8 битов вправо. Результат предыдущего шага обрабатывается таблицей замен 50 и накла-дывается на субблок С операцией сложения по модулю 2. Результат шага 4 вращается на 8 битов вправо. Результат предыдущего шага обрабатывается таблицей замен 5, и накладывается на субблок D операцией XOR. Кроме того, в некоторых раундах прямого перемешивания выполняются следующие дополнительные операции: По словам авторов алгоритма, эти операции существенно усиливают алгоритм MARS против дифференциального криптоанализа. Стоит обратить внимание на то, что в преобразовании Е используются операции вращения на переменное число битов; в этом случае запись 03 обозначает, что число битов вращения определяется значением младших пяти битов текущего значения 03. От прямого криптораунда его отличает лишь измененный порядок наложения выходных значений преобразования Е Ох...03 на слова В, С и D. Раунд обратного перемешивания более существенно отличается от прямого. Фактически обратное перемешивание выполняет обратные операции в обратной последовательности. Исходное значение субблока А вращается на 8 битов влево. Результат предыдущего шага обрабатывается таблицей замен 50 и накла-дывается на субблок С операцией вычитания по модулю 2. Результат шага 2 вращается на 8 битов влево. Результат предыдущего шага обрабатывается таблицей замен S, и накладывается на субблок D операцией вычитания по модулю 2. Результат шага 4 вращается на 8 битов влево. Результат предыдущего шага обрабатывается таблицей замен 50 и накладывается на субблок D операцией XOR. Процедура расширения ключа Ключ шифрования алгоритма MARS может иметь любой размер в диапазоне от 128 до 448 битов включительно, кратный 32 битам. Расширение ключа представляет собой формирование на основе ключа шифрования 40 подключей по 32 бита каждый (причем подключи должны обладать определенными характеристиками, о которых будет сказано далее).