Алгоритм MARS, Шифрование данных. Структура алгоритма

Пользователям

Вебмастерам

Безминималки

Автовыплота

Карта сайта

 

Главная страница

Меню :

Главная страница +

Криптография -

Rijndael

ГОСТ №28147-89

Akelare

Anubis

Mars

RC6

Blowfish

Skipjack

Square

Статьи +

Документальные фильмы +

Экстракт здоровья +

 

      MARS.

      

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

 

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

 

      Исходя из двух следующих предположений:

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

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

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

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

 

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

      1. Предварительное наложение ключа: на 32-битные субблоки A, B, C, D накладываются 4 фрагмента расширенного ключа   k0...k3 операцией сложения по модулю .
      2. Выполняются 8 раундов прямого перемешивания (без участия ключа шифрования).
      3. Выполняются 8 раундов прямого криптопреобразования.
      4. Выполняются 8 раундов обратного криптопреобразования. Этапы 3 и 4 называются «криптографическим ядром» алгоритма MARS.
      5. Выполняются 8 раундов обратного перемешивания, также без участия ключа шифрования.
      6.Финальное наложение фрагментов расширенного ключа k36...k39 операцией вычитания по модулю .

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

 

      Раунд прямого перемешивания алгоритма MARS:

 

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

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

      1. Значение субблока A прогоняется через таблицу замен S0 и накладывается на субблок B операцией XOR.

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

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

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

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

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

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

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

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

      В раундах 0 и 4 после шага 7 выполняется наложение значения субблока D на субблок A операцией сложения по модулю .

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

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

 

      Таблицы замены:

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

 

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

 

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

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

 

      Операция E алгоритма MARS:

Рисунок. 4. Операция E алгоритма MARS.

Из входного значения формируются три потока O1...O3, над которыми производятся следующие действия:
O2 = I,
O3 = O2 <<< 13 (смещение на 13 бит влево),
O2 = O2 + k2r+4 mod (операция сложения O2 и k2r+4 по модулю ),
O3 = O3 * k2r+5 mod (операция умножения O3 и k2r+5 по модулю ),
O3 = O3 <<< 5 (смещение на 5 бит влево),
O1 = S(O2), (табличная замена)
O1 = O1 XOR O3, (операция XOR),
O2 = O2 <<< O3’, (сдвиг влево на значение младших пяти бит текущего значения O3)
O3 = O3 <<< 5 (смещение на 5 бит влево),
O1 = O1 XOR O3,(операция XOR),
O1 = O1 <<< O3’, (сдвиг влево на значение младших пяти бит текущего значения O3)

, где I — входное значение,
r — номер текущего раунда, считая с 0-го (при нумерации раундов в данном случае учитываются только раунды криптоядра алгоритма),
S — табличная замена для операции E, представляет собой объединение описанных выше таблиц S0 и S1; объединенная таблица содержит 512 значений, выходное значение выбирается по значению 9 младших бит входного слова.

Стоит обратить внимание на то, что в преобразовании E используются операции вращения на переменное число бит; в этом случае запись O3 обозначает, что число бит вращения определяется значением младших пяти бит текущего значения O3.

 

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

 

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

      От прямого криптораунда его отличает лишь измененный порядок наложения выходных значений преобразования E O1...O3 на слова B, C и D.

 

      Раунд обратного перемешивания алгоритма MARS:

 

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

Раунд обратного перемешивания (см. рис. 6) более существенно отличается от прямого. Фактически, обратное перемешивание выполняет обратные операции в обратной последовательности (см. рис. 2 и 6):

1. Значение субблока A прогоняется через таблицу замен S1 и накладывается на субблок B операцией XOR.

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

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

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

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

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

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

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

Аналогично прямому перемешиванию, в некоторых раундах выполняются следующие дополнительные операции, не показанные на рис. 6:
- В раундах 1 и 5 после шага 7 выполняется наложение значения субблока A на субблок B операцией вычитания по модулю .

- В раундах 2 и 6 субблок C аналогичным образом накладывается на субблок B.

 

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

 

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

 

      Ключ шифрования алгоритма MARS может иметь любой размер в диапазоне от 128 до 448 бит включительно, кратный 32 битам. Расширение ключа представляет собой формирование на основе ключа шифрования 40 подключей по 32 бита каждый (причем, подключи должны обладать определенными характеристиками, о которых будет сказано ниже), для чего выполняются следующие операции:

      1. Формируется временный массив T0...T14:

T0 = KI0,
T1 = KI1,
...
Tn-1 = KIn-1,
Tn = n,
Tn+1 = Tn+2 = ... = T14 = 0,

где KI0...KIn-1 — исходный ключ шифрования,
n — его размер в 32-битных словах — от 4 до 14 включительно.

 

      2. Данный шаг повторяется 4 раза (каждая итерация дает 10 вычисленных фрагментов расширенного ключа) и содержит следующие операции:


- линейное преобразование:

Ti = Ti XOR ((Ti-7 mod 15 XOR Ti-2 mod 15) <<< 3) XOR (4i + j),
где j — номер итерации, начиная с 0,
i = 0...14;

- перемешивание массива T:

 

Ti = (Ti XOR S(Ti-1 mod 15)) <<< 9,
где S — табличная замена, выполняемая по тем же правилам, что и в операции E;

 

- заключительная перестановка:

 

k10j+n = T4n mod15,
где n = 0...9.

 

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

а) Каждый подключ, используемый для умножения в операции E (то есть подключи с нечетными индексами от k5 до k35 включительно), должен иметь нечетное значение. Мало того, единичными должны быть два младших бита подключа, а не один.
б) Те же подключи не должны содержать 10 нулевых или 10 единичных бит подряд.

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

в) 2 младших бита обрабатываемого подключа устанавливаются в единичные значения; старое значение запоминается в переменной j (оно будет использовано впоследствии). Результирующее значение подключа обозначается как W.
г) Вычисляется 32-битная маска M, которая будет использована для модификации подключа — для обеспечения отсутствия в нем 10 подряд нулевых или единичных бит.
Маска M вычисляется следующим образом:
- Устанавливаются в 1 биты M, соответствующие тем битам обрабатываемого подключа, которые входят в последовательности из 10 нулевых или 10 единичных бит. Остальные биты устанавливаются в 0.
- Обнуляются те единичные биты маски M, которые соответствуют любому из условий:
i < 2,
i = 31,
Wi <> Wi-1,
Wi <> Wi+1,

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

д) Используется таблица корректирующих значений B, определенная следующим образом:
B0 = A4A8D57B,
B1 = 5B5D193B,
B2 = C8A8309B,
B3 = 73F9A978.

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

С помощью данной таблицы следующим образом вычисляется финальное значение подключа Ki:
Ki = W XOR ((Bj <<< Ki-1) & M),
где & — логическая побитовая операция «и», а вращение Bj определяется пятью младшими битами предыдущего подключа Ki-1.

 

О Сущности, Разуме и многом другом... – сайт академика Николая Левашова. Этот сайт содержит Знания. Уникальные Знания, которые, до сих пор, не были доступны всем желающим. Это Знания о загадках Жизни, о строении Вселенной, о Сущности, Разуме и многом другом...    ->

Яндекс.Метрика