Cтруктура алгоритма:

1. Предварительное наложение ключа: на [latex]32[/latex]-битные субблоки [latex]A, B, C, D[/latex] накладываются [latex]4[/latex] фрагмента расширенного ключа [latex]k_{0}…k_{3}[/latex] операцией сложения по модулю [latex]2^{32}[/latex];
2. Выполняются [latex]8[/latex] раундов прямого перемешивания (без участия ключа шифрования);
3. Выполняются [latex]8[/latex] раундов прямого криптопреобразования;
4. Выполняются [latex]8[/latex] раундов обратного криптопреобразования;
5. Выполняются [latex]8[/latex] раундов обратного перемешивания, также без участия ключа шифрования;
6. Финальное наложение фрагментов расширенного ключа [latex]k_{36}…k_{39}[/latex] операцией вычитания по модулю [latex]2^{32}[/latex].

Алгоритм уникален тем, что использовал практически все существующие технологии, применяемые в криптоалгоритмах, а именно:

• простейшие операции сложение, вычитание, исключающее или
• подстановки с использованием таблицы замен
• фиксированный циклический сдвиг
• зависимый от данных циклический сдвиг
• умножение по модулю [latex]2^{32}[/latex]
• ключевое забеливание

Аналогично реализуем метод циклического сдвига вправо:

Так же нам потребуется реализовать метод выделения [latex]n[/latex]-ого байта из субблока. Для этого мы будем сдвигать требуемый байт на место младшего байта и выделим его с помощью операции «логическое и» маской [latex]255[/latex] (в битовом представлении подряд идущих [latex]8[/latex] единиц, начиная с младшего бита) .

Осталось реализовать метод выделения последних [latex]n[/latex] бит из субблока. Для этого мы сначала сдвинем число влево на ([latex]32 — n[/latex]), чтобы на место старших бит встали искомые биты (таким образом стерев ненужные биты). А затем сдвинем их на место младших битов (то есть вправо с заполнением нулями на [latex]32 — n[/latex]).

Для работы алгоритма потребуется объявить некоторые элементы ([latex]S[/latex] и [latex]B[/latex] блоки) — они описаны в конце статьи.

Прямое перемешивание:

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

1. Значение субблока [latex]A[/latex] прогоняется через таблицу замен [latex]S0[/latex] и накладывается на субблок [latex]B[/latex] операцией [latex]XOR[/latex].
2. Исходное значение субблока [latex]A[/latex] вращается на [latex]8[/latex] бит вправо.
3. Результат предыдущего шага обрабатывается таблицей замен [latex]S1[/latex] и снова накладывается на субблок [latex]B[/latex] операцией сложения по модулю [latex]32[/latex].
4. Результат шага [latex]2[/latex] вращается на [latex]8[/latex] бит вправо.
5. Результат предыдущего шага обрабатывается таблицей замен [latex]S0[/latex] и накладывается на субблок [latex]С[/latex] операцией сложения по модулю [latex]32[/latex].
6. Результат шага [latex]4[/latex] вращается на [latex]8[/latex] бит вправо.
7. Результат предыдущего шага обрабатывается таблицей замен [latex]S1[/latex] и накладывается на субблок [latex]D[/latex] операцией [latex]XOR[/latex].
8. Субблоки меняются местами, как показано на рис. [latex]1[/latex].

Кроме того, в некоторых раундах прямого перемешивания выполняются следующие дополнительные операции (не приведены на рис. [latex]1[/latex]):
В раундах [latex]0[/latex] и [latex]4[/latex] после шага [latex]7[/latex] выполняется наложение значения субблока [latex]D[/latex] на субблок [latex]A[/latex] операцией сложения по модулю .
В раундах [latex]1[/latex] и [latex]5[/latex] субблок [latex]B[/latex] аналогичным образом накладывается на субблок [latex]A[/latex].

рис. 1.

Стоит заметить, что каждый раз, «прогоняя» [latex]i[/latex]-ий субблок через [latex]S[/latex] блоки мы берем последние [latex]8[/latex] бит, то есть байт субблока и его значение используем в качестве индексного обращения к блоку [latex]S[/latex]. (Понятно, что в блоках [latex]256[/latex]  элементов. О правилах их получения  рассказывается ниже).

Для простоты, мы будем возвращать для «прогона» каждый раз не последний байт, а младший, первый, второй и старший. Потом мы подвинем субблок вправо сразу на [latex]24[/latex] бита.

Заведем класс subblock, который будет содержать четыре [latex]32[/latex]-битные посылки и расширенный ключ (о его получении мы поговорим ниже).

Теперь добавим в него метод прямого перемешивания:

Процесс кодирования алгоритма Mars обратен процессу декодирования. По этому сразу добавим обратный метод. Назовем его backward pass, чтобы не менять порядок следования функции в методе дешифрования, и добавим, в начало названия префикс [latex]d[/latex], чтобы обозначить его принадлежность к методам декодирования. Стоит отметить, что перед этим стоит ознакомиться с понятием обратных операций.

Криптографическое преобразование:

Криптографическое ядро MARS — сеть Фейстеля 3-го типа, содержащая в себе [latex]16[/latex] раундов. [latex]8[/latex] раундов прямого (рис. 2) и [latex]8[/latex] раундов обратного криптопреобразования (рис. 3). В каждом раунде мы используем ключевую [latex]Е[/latex]-функцию, которая является комбинацией умножений, вращений, а также обращений к [latex]S[/latex]-блокам. Функция принимает на вход одно слово данных, а возвращает три слова, с которыми впоследствии будет осуществлена операция сложения или [latex]XOR[/latex] к другим трем словам данным. В дополнении исходное слово вращается на [latex]13[/latex] бит влево.

рис.2.

Для обеспечения, серьёзного сопротивления к криптоатакам, три выходных значения [latex]Е[/latex]-функции ([latex]O_{1}[/latex], [latex]O_{2}[/latex], [latex]O_{3}[/latex]) используются в первых восьми раундах и в последних восьми раундах в разных порядках. В первые восемь раундов мы добавляем [latex]O_{1}[/latex] и [latex]O_{2}[/latex] к первому и второму целевому слову, соответственно, и [latex]XOR[/latex] [latex]O_{3}[/latex] к третьему целевому слову. За последние восемь раундов, мы добавляем [latex]O_{1}[/latex] и [latex]O_{2}[/latex] к третьему и второму целевому слову, соответственно, и [latex]XOR[/latex] [latex]O_{3}[/latex] к первому целевому слову.

рис.3.

Для декодирования:

[latex]E[/latex]-функция

[latex]E[/latex]-функция принимает в качестве входных данных одно слово данных и использует ещё два слова расширенного ключа с индексами [latex]2*i + 4[/latex] и [latex]2*i + 5[/latex] , производя на выходе три слова. В этой функции мы используем три временные переменные, обозначаемые [latex]L[/latex], [latex]M[/latex] и [latex]R[/latex] (для левой, средней и правой).

<p\>Изначально мы устанавливаем в [latex]R[/latex] значение исходного слова смещенного на [latex]13[/latex] бит влево, а в [latex]M[/latex] — сумма исходных слов и первого ключевого слова. Затем мы используем первые девять битов [latex]M[/latex] как индекс к одной из [latex]512[/latex] [latex]S[/latex]-блоков (которое получается совмещением [latex]S0[/latex] и [latex]S1[/latex] смешиванием фазы), и сохраняем в [latex]L[/latex] значение соответствующего [latex]S[/latex]-блока.

Затем умножим второе ключевое слово на [latex]R[/latex], сохранив значение в [latex]R[/latex]. Затем вращаем [latex]R[/latex] на [latex]5[/latex] позиций влево (так, [latex]5[/latex] старших битов становятся [latex]5[/latex] нижними битами [latex]R[/latex] после вращения). Тогда мы делаем [latex]XOR[/latex] [latex]R[/latex] в [latex]L[/latex], а также просматриваем пять нижних бит [latex]R[/latex] для определения величины сдвига (от [latex]0[/latex] до [latex]31[/latex]), и вращаем [latex]M[/latex] влево на эту величину. Далее мы вращаем [latex]R[/latex] ещё на [latex]5[/latex] позиций влево и делаем [latex]XOR[/latex] в [latex]L[/latex]. В заключении, мы вновь смотрим на [latex]5[/latex] младших битов [latex]R[/latex], как на величину вращения и вращаем [latex]L[/latex] на эту величину влево. Таким образом результат работы [latex]E[/latex]-функции — [latex]3[/latex] слова (по порядку): [latex]L, M, R[/latex].

Обратное перемешивание:

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

1. Значение субблока [latex]A[/latex] прогоняется через таблицу замен [latex]S1[/latex] и накладывается на субблок [latex]B[/latex] операцией XOR.
2. Исходное значение субблока [latex]A[/latex] вращается на [latex]8[/latex] бит влево.
3. Результат предыдущего шага обрабатывается таблицей замен [latex]S0[/latex] и накладывается на субблок [latex]C[/latex] операцией вычитания по модулю [latex]2^{32}[/latex]/>.
4. Результат шага [latex]2[/latex] вращается на [latex]8[/latex] бит влево.
5. Результат предыдущего шага обрабатывается таблицей замен [latex]S1[/latex] и накладывается на субблок [latex]D[/latex] операцией вычитания по модулю [latex]2^{32}[/latex] />.
6. Результат шага [latex]4[/latex] вращается на [latex]8[/latex] бит влево.
7. Результат предыдущего шага обрабатывается таблицей замен [latex]S0[/latex] и накладывается на субблок [latex]D[/latex] операцией [latex]XOR[/latex].
8. Субблоки меняются местами, как показано на рис. 4.

Аналогично прямому перемешиванию, в некоторых раундах выполняются следующие дополнительные операции, не показанные на рис. 4:
— В раундах [latex]1[/latex] и [latex]5[/latex] после шага [latex]7[/latex] выполняется наложение значения субблока [latex]A[/latex] на субблок [latex]B[/latex] операцией вычитания по модулю [latex]2^{32}[/latex].

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

и для декодирования:

Финальная реализиция класса Block:

Добавив методы для сложения посылок с подключами мы получаем финальную реализацию класса Block.

Свойства [latex]S[/latex]-блоков:

Стоит отметить, что [latex]S[/latex]-блок — это конкатенация блоков [latex]S0[/latex] и [latex]S1[/latex].

1. [latex]S[/latex]-блок не должен содержать слова, состоящие все [latex]0[/latex] или [latex]1[/latex]
2. Каждые два [latex]S[/latex]-блока [latex]S0[/latex], [latex]S1[/latex] должны отличаться друг от друга как минимум в [latex]3[/latex] из [latex]4[/latex] байтах.(так как выполнение этого условия для псевдослучайных [latex]S[/latex]-блоков крайне маловероятно, то один из двух [latex]S[/latex]-блоков модифицируется)
3. S-блок не содержит двух элементов [latex]S[i],S[j](i\neq j)[/latex] таких, что [latex] S\left[i\right]=S\left[j\right][/latex]; [latex]S\left[i\right]=-S\left[j\right][/latex] или [latex] S\left[i\right]=-S\left[j\right][/latex]
4. В [latex]S[/latex]-блоке не существует двух пар элементов [latex]XOR[/latex]-отличия которых равны и двух пар элементов упорядоченная разность которых равна
5. Каждые два элемента [latex]S[/latex]-блока должны отличаться хотя бы [latex]4[/latex] битами

В данном программе будем использовать блок, предложенный в реализации IBM для AES.

Расширение ключа:

Процедура расширения ключа расширяет заданный массив ключей [latex]T[][/latex], состоящий из [latex]n[/latex] [latex]32[/latex]-битных слов (где [latex]n[/latex] целое число от [latex]4[/latex] до [latex]14[/latex]) в массив [latex]K[][/latex] из [latex]40[/latex] элементов. Исходный ключ не должен придерживаться какой-либо структуры. В дополнение, процедура расширения ключа гарантирует следующие свойства ключевого слова, используемого при перемножении в криптографическом ядре алгоритма:

• два младших бита ключевого слова будут всегда единицами
• ни одно из ключевых слов не будет содержать десять подряд идущих [latex]0[/latex] или [latex]1[/latex]

Опишем алгоритм расширения ключа.

Сначала массив [latex]T[][/latex] дополняется до 15 элементов следующим образом: [latex]T[n]=n[/latex];[latex]T[n+1\ldots 14]=0[/latex]

Далее данный процесс повторяется [latex]4[/latex] раза:

• • На каждой итерации генерируются [latex]10[/latex] слов расширенного ключа. [latex]j[/latex] переменная отображающая текущий номер итерации.(для первой итерации [latex]0[/latex], для второй [latex]1[/latex] и т. д.)
    Массив [latex]T[][/latex] преобразуется по следующему правилу: [latex]i=0\ldots 14,T[i]=T[i]\oplus ((T[i-7\mod 15]\oplus T[i-2\mod 15])\lll 3)\oplus (4i+j)[/latex]

• • Далее мы перемешиваем массив [latex]T[][/latex] при помощи [latex]4[/latex] раундов Сети Фейстеля 1-го типа. Повторяем четыре раза следующую операцию: [latex]T[i]=(T[i]+S[low~9~bits~of~T[i-1\mod 15]])\lll 9;i=0,1\ldots 14[/latex]

• Далее берем десять слов из массива [latex]T[][/latex] и вставляем их в качестве следующих десяти слов в массив [latex]K[][/latex] ещё раз перемешав: [latex]K[10j+i]=T[4i\mod 15];i=0,1\ldots 9[/latex]

Окончательно, мы пробегаемся по шестнадцати словам, используемыми для перемножения[latex](K[5],K[7]…K[35])[/latex] и модифицируем их для того, чтобы они соответствовали двум свойствам, описанным выше.
Записываем два младших бита [latex]K[i][/latex], по формуле [latex] j=K[i]\land 3[/latex] , а затем записываем вместо этих двух бит единицы, [latex] w=K[i]\lor 3[/latex] .
Собираем маску [latex]M[/latex] для битов [latex]w[/latex], которые принадлежат последовательностям из десяти и более нулей или единиц. К примеру, [latex] M_{l}=1[/latex] , тогда и только тогда, когда [latex]w_{l}[/latex] принадлежит последовательности из [latex]10[/latex] или более одинаковых элементов. Тогда мы сбрасываем (выставляем их в [latex]0[/latex]) значения тех единиц [latex]M[/latex], которые находятся на границах нулевых или единичных последовательностей, а также тех единиц, которые находятся в старшем и младшем битах. К примеру, пусть наше слово выглядит так: [latex] w=0^{3}1^{13}0^{12}1011[/latex] (выражение [latex]0^{i}[/latex] или же [latex] 1^{i}[/latex] обозначает, что [latex]0[/latex] или [latex]1[/latex] будут повторены в слове [latex]i[/latex] раз). Тогда маска [latex]M[/latex] будет выглядеть следующим образом: [latex] 0^{3}1^{25}0^{4}[/latex] . А значит мы сбрасываем биты в [latex]4, 15, 16, 28[/latex] позициях, то есть [latex]M=0^{4}1^{11}001^{10}0^{5}[/latex]
Далее, для исправления, мы используем таблицу из четырёх слов [latex]B[][/latex]. Все элементы таблицы [latex]B[/latex] подобраны так, что для них и для всех их цикличных сдвигов выполняется свойство, что в них нет семи подряд идущих [latex]0[/latex] или [latex]1[/latex]. В реализации IBM использовалась таблица [latex]B[]=\left\{0xa4a8d57b,0x5b5d193b,0xc8a8309b,0x73f9a978\right\}[/latex] . Далее используются два записанных бита [latex]j[/latex] для выбора слова из таблицы [latex]B[/latex], и используются младшие пять бит слова [latex]K[i-1][/latex] для вращения его элементов, [latex]p=B[j]\lll (lowest~5~bits~of~K[i-1])[/latex].
Окончательно, делается [latex]XOR[/latex] шаблона [latex]p[/latex] на исходное слово, при учете маски [latex]М[/latex]: [latex]K[i] = w\oplus (p\land M)[/latex] .

Сначала выделяем маской последовательность из [latex]10[/latex] нулей или единиц, и потом выставляем в маске [latex]1[/latex]-цы пока последовательность не прерывается.

Реализация класса Key: