MARS (криптография)

MARS
Создатель:	Кэролин Барвик, Дон Копперсмит
Создан:	1998 г.
Опубликован:	1998 г.
Размер ключа:	128 - 448 бит
Размер блока:	128 бит
Число раундов:	32
Тип:	Сеть Фейстеля

MARS — шифр-кандидат в AES, разработанный корпорацией IBM, создавшей в своё время DES. По заявлению IBM, в алгоритм MARS вложен 25-летний криптоаналитический опыт фирмы, и наряду с высокой криптографической стойкостью шифр допускает эффективную реализацию даже в таких ограниченных рамках, какие характерны для смарт-карт.

В разработке шифра принял участие Дон Копперсмит, один из авторов шифра Lucifer (DES), известный рядом статей по криптологии: улучшение структуры S-блоков против дифференциального криптоанализа, метод быстрого перемножения матриц(алгоритм Копперсмита — Винограда), криптоанализ RSA. Кроме него в разработке алгоритма приняли участие: Кэролин Барвик, Эдвард Д’Эвиньон, Росарио Женаро, Шай Халеви, Чаранжит Джутла, Стивен M. Матьяс Мл., Люк О'Коннор, Мохамед Перьевян, Дэвид Саффорд, Невенко Зунич.

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

По результатам конкурса AES, MARS вышел в финал, но уступил Rijndael. После объявления результатов (19 Мая 2000 года) группа разработчиков составила своё собственное мнение о конкурсе AES, где дала комментарии на претензии к своему детищу.

Сейчас MARS распространяется по всему миру под лицензией Royalty-free.

Краткое описание алгоритма

MARS является блочно-симметричным шифром с секретным ключом. Размер блока при шифровании 128 бита, размер ключа может варьироваться от 128 до 448 бит включительно (кратные 32 битам). Создатели стремились совместить в своём алгоритме быстроту кодирования и стойкость шифра. В результате получился один из самых криптостойких алгоритмов, участвовавших в конкурсе AES.

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

• простейшие операции (сложение, вычитание, исключающее или)
• подстановки с использованием таблицы замен
• фиксированный циклический сдвиг
• зависимый от данных циклический сдвиг
• умножение по модулю 2³²
• ключевое забеливание

Использование двойного перемешивания представляет сложность для криптоанализа, что некоторые относят к недостаткам алгоритма. В то же время на данный момент не существует каких-либо эффективных атак на алгоритм, хотя некоторые ключи могут генерировать слабые подключи.

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

Авторы шифра исходили из следующих предположений:

1. Выбор операций. MARS был спроектирован для использования на самых современных компьютерах того времени. Для достижения лучших защитных характеристик в него были включены самые «сильные операции» поддерживаемые в них. Это позволило добиться большего отношения securityper-instruction для различных реализации шифра.
2. Структура шифра. Двадцатилетний опыт работы в области криптографии подтолкнул создателей алгоритмак мысли, что каждый раунд шифрования играет свою роль в обеспечении безопасности шифра. В частности, мы можем видеть, что первый и последний раунды обычно сильно отличаются от промежуточных(«центральных») раундов алгоритма в плане защиты от криптоаналитических атак. Таким образом, при создании MARSa использовалась смешанная структура, где первый и последний раунды шифрования существенно отличаются от промежуточных.
3. Анализ. Скорее всего, алгоритм с гетерогенной структурой будет лучше противостоять криптоаналитическим методам будущего, чем алгоритм, все раунды которого идентичны. Разработчики алгоритма MARS придали ему сильно гетерогенную структуру — раунды алгоритма весьма различаются между собой.

В шифре MARS использовались следующие методы шифрования:

1. Работа с 32-х битными словами. Все операции применяются к 32-битным словам. то есть вся исходная информация разбивается на блоки по 32 бита. (если же блок оказывался меньшей длины, то он дополнялся до 32 бит)
2. Сеть Фейстеля. Создатели шифра считали, что это лучший вариант совмещения скорости шифрования и криптостойкости. В MARS использована сеть Фейстеля 3-го типа.
3. Симметричность алгоритма. Для стойкости шифра к различным атакам все его раунды были сделаны полностью симметричными, то есть вторая часть раунда есть зеркальное повторение первой его части.

Структуру алгоритма MARS можно описать следующим образом:

1. Предварительное наложение ключа: на 32-битные субблоки A, B, C, D накладываются 4 фрагмента расширенного ключа k₀…k₃ операцией сложения по модулю 2³²;
2. Выполняются 8 раундов прямого перемешивания (без участия ключа шифрования);
3. Выполняются 8 раундов прямого криптопреобразования;
4. Выполняются 8 раундов обратного криптопреобразования;
5. Выполняются 8 раундов обратного перемешивания, также без участия ключа шифрования;
6. Финальное наложение фрагментов расширенного ключа k₃₆…k₃₉ операцией вычитания по модулю 2³².

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

В первой фазе на каждое слово данных накладывается слово ключа, а затем происходит восемь раундов смешивания согласно сети Фейстеля третьего типа совместно с некоторыми дополнительными смешиваниями. В каждом раунде мы используем одно слово данных (называемое, исходным словом) для модификации трёх других слов(называемые, целевыми словами). Мы рассматриваем четыре байта исходного слова в качестве индексов на двух S-блоков, S₀ и S₁, каждый, состоящий из 256 32-разрядных слов, а далее проводим операции XOR или добавления данных соответствующего S-блока в три других слова.

Если четыре байта исходного слова b₀, b₁, b₂, b₃ (где b₀ является первым байтом, а b₃ является старшим байтом), то мы используем b₀, b₂, как индексы в блока S₀ и байты b₁, b₃, как индексы в S-блоке S₁. Сначала сделаем XOR S₀ к первому целевому слову, а затем прибавим S₁ к тому же слову. Мы также добавляем S₀ ко второму целевому слову и XOR блока-S₁ к третьему целевому слову. В заключении, мы вращаем исходное слово на 24 бита вправо.

В следующем раунде мы вращаем имеющиеся у нас четыре слова: таким образом, нынешнее первое целевое слово становится следующим исходным словом, текущее второе целевое слово становится новым первым целевым словом, третье целевое слово становится следующую вторым целевым словом, и текущее исходное слово становится третьим целевым словом.

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

Псевдокод

1. // Первое наложение ключа на данные
2. <math>for ~i ~= ~0 ~to ~3 ~do</math>
3. <math> D \left [ i \right ] = D[i] + K[i] </math>
4. // Затем 8 раундов прямого перемешивания
5. <math>for ~i = ~0 ~to ~7 ~do</math>  // используем D[0] для модифицирования D[1]; D[2]; D[3]
6. // обращаемся к 4-ем S-блокам
7.<math> D \left [1 \right ] = D[1] \oplus S0[ ~low ~byte ~of ~D[0] ]</math>
8.<math> D \left [ 1 \right ] = D[1] + S1[ ~2nd ~byte ~of ~D[0] ]</math>
9.<math> D \left [ 2 \right ] = D[2] + S0[ ~3rd ~byte ~of ~D[0] ]</math>
10.<math> D[3] = D[3] \oplus S1[ ~high ~byte ~of ~D[0] ]</math>
11. // и вращаем исходное слово вправо
12.<math> D[0] = D[0] \ggg 24 </math>
13. // также проделаем дополнительные операции смешивания
14. <math>if ~i ~= ~0 ~or ~4 ~then </math>
15.     <math>D \left [ 0 \right ] = D[0] + D[3]</math> // добавим D[3] к исходному слову
16. <math>if ~i ~= ~1 ~or ~5 ~then</math>
17.     <math>D \left [0 \right ] = D[0] + D[1]</math> // добавим D[1] к исходному слову
18. // вращаем массив D[ ]
19.<math>(D[3]; D[2]; D[1]; D[0]) \leftarrow  (D[0]; D[3]; D[2]; D[1]) </math>
20.<math>end-for</math>

Криптографическое ядро

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

Для обеспечения, серьёзного сопротивления к криптоатакам, три выходных значения Е-функции(O₁, O₂, O₃) используются в первых восьми раундах и в последних восьми раундах в разных порядках. В первые восемь раундов мы добавляем O₁ и O₂ к первому и второму целевому слову, соответственно, и XOR O₃ к третьему целевому слову. За последние восемь раундов, мы добавляем O₁ и O₂ к третьему и второму целевому слову, соответственно, и XOR O₃ к первому целевому слову.

Псевдокод

1. // Проделаем 16 раундов шифрования при использовании ключа
2.<math>for ~i ~= ~0 ~to ~15 ~do</math>
3.<math>(out1; ~out2; ~out3) ~= ~E-function(D[0]; ~K[2i + 4]; ~K[2i + 5])</math>
4.<math>D[0] = D[0] \lll 13</math>
5.<math>D[2] = D \left [ 2 \right ] + out2</math>
6.<math>if ~i ~< ~8 ~then</math> // сначала 8 раундов прямого преобразования
7.     <math>D[1] = D \left [ 1 \right ] + out1</math>
8.     <math>D[3] = D[3] \oplus out3 </math>
9.<math>else</math> // потом 8 раундов обратного преобразования
10.    <math>D[3] = D \left [ 3 \right ] + out1</math>
11.    <math>D[1] = D[1] \oplus out3</math>
12.<math>end-if</math>
13. // вращаем массив D[ ]
14.<math>(D[3]; ~D[2]; ~D[1]; ~D[0]) \leftarrow (D[0]; ~D[3]; ~D[2]; ~D[1])</math>
15.<math>end-for</math>

Е-функция

E-функция принимает в качестве входных данных одно слово данных и использует ещё два ключевых слов, производя на выходе три слова. В этой функции мы используем три временные переменные, обозначаемые L, M и R (для левой, средней и правой).

Изначально мы устанавливаем в R значение исходного слова смещенного на 13 бит влево, а в M — сумма исходных слов и первого ключевого слова. Затем мы используем первые девять битов M как индекс к одной из 512 S-блоков (которое получается совмещением S₀ и S₁ смешиванием фазы), и сохраняем в L значение соответствующего S-блока.

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

Псевдокод

1. // используем 3 временные переменные L; M; R
2.<math>M = ~in + ~key1</math> //добавляем первое ключевое слово
3.<math>R = (in \lll 13) \otimes key2</math> // умножаем на второе ключевое слово, которое должно быть четным
4.<math>i = ~lowest ~9 ~bits ~of ~M</math>
5.<math>L = S \left [ i \right ]</math> // взятие S-блока
6.<math>R = R \lll 5</math>
7.<math>r = ~lowest ~5 ~bits ~of ~R</math> // эти биты описывают величину последующего вращения
8.<math>M = M \lll r</math> // первое вращение на переменную величину
9.<math>L = L \oplus R </math>
10.<math>R = R \lll 5</math>
11.<math>L = L \oplus R</math>
12.<math>r = ~lowest ~5 ~bits ~of ~R</math> // эти биты описывают величину последующего вращения
13.<math>L = L \lll r </math> // второе вращение на переменную величину
14.<math>output(L; ~M; ~R)</math>

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

Обратное перемешивание практически совпадает с прямым перемешиванием, за исключением того факта, что данные обрабатываются в обратном порядке. То есть, если бы мы совместили прямое и обратное перемешивание так, чтобы их выходы и входы были бы соединены в обратном порядке (D[0] прямого и D[3] обратного, D[1] прямого и D[2] обратного), то не увидели бы результата перемешивания. Как и в прямом смешивание, здесь мы тоже используем одно исходное слово и три целевых. Рассмотрим четыре первых байта исходного слова: b₀, b₁, b₂, b₃. Будем использовать b₀, b₂ как индекс к S-блоку — S₁, а b₁b₃ для S₀. Сделаем XOR S₁[b₀] в первое целевое слово, вычтем S₀[b₃] из второго слова, вычтем S₁[b₂] из третьего целевого слов и затем проделаем XOR S₀[b₁] также к третьему целевому слову. Наконец, мы поворачиваем исходное слово на 24 позиций влево. Для следующего раунда мы вращаем имеющиеся слова так, чтобы нынешнее первое целевое слово стало следующим исходным словом, текущее второе целевое слово стало первым целевым словом, текущее третье целевое слово стало вторым целевым словом, и текущее исходное слово стало третьим целевым словом. Кроме того, перед одним из четырёх «особенных» раундов мы вычитаем одно из целевых слов из исходного слова: перед четвёртым и восьмым раундами мы вычитаем первое целевое слово, перед третьем и седьмым раундами мы вычтем третье целевое слово из исходного.

Псевдокод

1. // Проводим 8 раундов обратного перемешивания
2.<math> for ~i ~= ~0 ~to ~7 ~do</math>
3. // дополнительные операции смешивания
4. <math>if ~i ~= ~2 ~or ~6 ~then</math>
5.      <math>D[0] = D[0] - ~D[3]</math> //вычитаем D[3] из исходного слова
6. <math>if ~i ~= ~3 ~or ~7 ~then</math>
7.     <math>D[0] = D[0] - ~D[1]</math> // вычитаем D[1] из исходного слова
8. // обращаемся к четырём элементам S-блоков
9.<math>D[1] = D[1] \oplus S1[ ~low ~byte ~of ~D[0] ]</math>
10.<math>D[2] = D[2] - ~S0[ ~high ~byte ~of ~D[0] ]</math>
11.<math>D[3] = D[3] \oplus S1[ ~3rd ~byte ~of ~D[0] ]</math>
12.<math>D[3] = D[3] - ~S0[ ~2nd ~byte ~of ~D[0] ]</math>
13. // и вращаем исходное слово влево
14.<math>D[0] = D[0] \lll 24</math>
15. // вращаем массив D[]
16.<math>(D[3]; D[2]; D[1]; D[0]) \leftarrow  (D[0]; D[3]; D[2]; D[1])</math>
17.<math>end-for</math>
18. // Вычитаем ключевое слово
19.<math>for ~i ~= ~0 ~to ~3 ~do</math>
20.        <math>D[i] = D[i] - ~K[36 + i]</math>

Дешифрование

Процесс декодирования обратен процессу кодирвоания. Код дешифрования похож (но не идентичен) на код шифрования.

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

1. // Начальное наложение ключа 
2.<math>for ~i ~= ~0 ~to ~3 ~do</math>
3.<math>D\left [ i \right ] = D[i] + K[36 + i]</math>
4. // Затем проводим 8 раундов прямого перемешивания
5.<math>for ~i ~= ~7 ~down ~to ~0 ~do</math>
6. // вращаем массив D[]
7.<math>(D[3]; ~D[2]; ~D[1]; ~D[0]) \leftarrow (D[2]; ~D[1]; ~D[0]; ~D[3])</math>
8. // и вращаем исходное слово вправо
9.<math>D[0] = D[0] \ggg 24</math>
10. // обращаемся к 4-ем элементам S-блоков
11.<math>D[3] = D[3] \oplus S0[ ~2nd ~byte ~of ~D[0] ]</math>
12.<math>D[3] = D[3] + S1[ ~3rd ~byte ~of ~D[0] ]</math>
13.<math>D[2] = D[2] + S0[ ~high ~byte ~of ~D[0] ]</math>
14.<math>D[1] = D[1] \oplus S1[ ~low ~byte ~of ~D[0] ]</math>
15. // дополнительное смешивание
16.<math>if ~i ~= ~2 ~or ~6 ~then</math>
17.      <math>D[0] = D\left [ 0 \right ] + D[3]</math> // добавляем D[3] к исходному слову
18.<math>if ~i ~= ~3 ~or ~7 ~then</math>
29.      <math>D[0] = D\left [ 0 \right ] + D[1]</math> // добавляем D[1] к исходному слову
20.<math>end-for</math>

Криптографическое ядро

1. // Проведем 16 раундов при использование наложения ключа
2.<math>for ~i ~= ~15 ~down ~to ~0 ~do</math>
3. // вращаем массив D[]
4.<math>(D[3]; ~D[2]; ~D[1]; ~D[0]) \leftarrow (D[2]; ~D[1]; ~D[0]; ~D[3])</math>
5.<math>D[0] = D[0] \ggg 13</math>
6.<math>(out1; ~out2; ~out3) = E-function(D[0]; ~K[2i + 4]; ~K[2i + 5])</math>
7.<math>D[2] = D \left [ 2 \right ] - out2</math>
8.<math>if ~i ~< ~8 ~then</math> // последние 8 раундов в прямом порядке
9.      <math>D[1] = D\left [ 1 \right ] - out1</math>
10.     <math>D[3] = D[3] \oplus out3</math>
11.<math>else</math> // первые 8 раундов в обратном порядке
12.     <math>D[3] = D\left [ 3 \right ] - out1</math>
13.     <math>D[1] = D[1] \oplus out3</math>
14.<math>end-if</math>
15.<math>end-for</math>

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

1. // Проводим 8 раундов обратного перемешивания
2. <math>for ~i ~= ~7 ~down ~to ~0 ~do</math>
3. // Вращаем массив D[]
4.<math>(D[3]; ~D[2]; ~D[1]; ~D[0]) \leftarrow (D[2]; ~D[1]; ~D[0]; ~D[3])</math>
5. // дополнительные операции переммешивания
6.<math>if ~i ~= ~0 ~or ~4 ~then</math>
7.      <math>D[0] = D\left [ 0\right ] - D[3]</math> // вычитаем D[3] из исходного слова
8.<math>if ~i ~= ~1 ~or ~5 ~then</math>
9.      <math>D[0] = D\left [ 0 \right ] - D[1]</math> // вычитаем D[1] из исходного слова
10. // вращаем исходное слово влево
11.<math>D[0] = D[0] \lll 24</math>
12. // обращаемся к четырём элементами S-блоков
13.<math>D[3] = D[3] \oplus S1[ ~high ~byte ~of ~D[0] ]</math>
14.<math>D[2] = D[2] - S0[ ~3rd ~byte ~of ~D[0] ]</math>
15.<math>D[1] = D[1] - S1[ ~2nd ~byte ~of ~D[0] ]</math>
16.<math>D[1] = D[1] \oplus S0[ ~low ~byte ~of ~D[0] ]</math>
17.<math>end-for</math>
18. // вычитание подключа из данных
19.<math>for ~i ~= ~0 ~to ~3 ~do</math>
20.     <math>D[i] = D\left [ i\right ] - K[i]</math>

Особенности алгоритма

S-блоки

При создании S-блока S, его элементы генерировались псевдослучайным генератором, после чего тестировались на различные линейные и диффиренциальные свойства. Псевдослучайные S-блоки были сгенерированы при следующих параметрах:

<math>i = 0\ldots102; j = 0\ldots4, S[5i+j] = \mathrm{SHA-1}(5i \vert c1 \vert c2 \vert c3)</math>

(где <math>SHA-1(j)</math> — есть j-ое слово на выходе SHA-1) Здесь считается, что i — 32-битное без знаковое, целое число, а c1, c2, c3 есть некоторые константы. В реализации IBM: c1 = 0xb7e15162; c2 = 0x243f6a88 (которые являются двоичной записью дробной части <math>e</math> и <math>\pi</math> соответственно). c3 изменялось пока не были подобраны S-блоки с подходящими свойствами. SHA-1 работает над потоками данных и использует прямой порядок байт.

Свойства S-блоков

Дифференциальные свойства.

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

Требование №4 не выполнялось в реализации IBM для AES, но было поправлено сразу после финала.
Было замечено, что в S-блоках присутствуют следующие элементы, противоречащие этому требованию:  

XOR	Вычитание
<math>S[27] \oplus S[101] = S[292] \oplus S[360] = 0x117f1a43</math>	<math>S \left [ 13 \right ] - S[138] = S[364]-S[297] = 0x75082c89 </math>
<math>S[27] \oplus S[292] = S[101] \oplus S[360] = 0x2b05b22a</math>	<math>S \left [ 19 \right ] -S[168] = S[509]-S[335] = 0x0b7fc4bd </math>
<math> S[27] \oplus S[360] = S[101] \oplus S[292] = 0x3a7aa869 </math>	<math> S \left [ 49 \right ] -S[97] = S[142]-S[392] = 0x725ca4be </math>
	<math>S \left [ 131 \right ] -S[333] = S[348]-S[211]= 0xc73689fe</math>
	<math>S \left [ 13 \right ] -S[364] = S[138]-S[297] = 0x86dedc7c</math>
	<math>S \left [ 131 \right ] -S[348] = S[333]-S[211]= 0x22492124</math>
	<math>S \left [ 19 \right ] -S[509] = S[168]-S[335] = 0x9ce0ed93</math>
	<math>S \left [ 49 \right ] -S[142] = S[97]-S[392] = 0x5d91f03a</math>

Линейные свойства

1. Соотношение смещения: <math>\left | Pr_x[parity(S[x]) = 0] - 1/2 \right |</math>. Необходимо, чтобы это выражение было больше хотя бы <math>1/32</math>
2. Однобитовое смещение: <math> \forall j \left | Pr_x[S[x]_j = 0] - 1/2 \right |</math> Необходимо, чтобы это выражение было больше хотя бы <math>1/30</math>
3. Двухбитовое смещение: <math> \forall j \left | Pr_x[S[x]_j \oplus S[x]_{j+1} = 0] - 1/2 \right |</math>. Необходимо, чтобы это выражение было больше хотя бы <math>1/30</math>
4. Однобитовая корреляция:<math> \forall i,j \left | Pr_x [S[x]_j = x_i] - 1/2 \right |</math>. Необходимо минимизировать это выражение среди всех возможных S-блоков, которые удовлетворяют предыдущим пунктам

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

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

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

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

1. Сначала массив <math>k[]</math> полностью переписывается в промежуточный массив <math>T[]</math>, состоящий из 15 элементов. <math>T[0 \ldots n-1] = k[0 \ldots n-1]; T[n] = n; T[n + 1 \ldots 14] = 0</math>
2. Далее данный процесс повторяется 4 раза. На каждой итерации генерируются 10 слов расширенного ключа. <math>j</math> переменная отображающая текущий номер итерации.(для первой итерации 0, для второй 1 и т. д.)
   1. Массив T[] преобразуется по следующему правилу:<math> 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)</math>
   2. Далее мы перемешиваем массив <math>T[]</math> при помощи 4 раундов Сети Фейстеля 1-го типа. Повторяем четыре раза следующую операцию: <math>T[i] = (T[i] + S[low ~9 ~bits ~of ~T[i - 1 \mod 15]]) \lll 9; i = 0,1\ldots14</math>
   3. Далее берем десять слов из массива T[] и вставляем их в качестве следующих десяти слов в массив K[] ещё раз перемешав: <math>K[10j + i] = T[4i \mod 15]; i = 0,1 \ldots 9</math>
3. Окончательно, мы пробегаемся по шестнадцати словам, используемыми для перемножения(K[5],K[7]…K[35]) и модифицируем их для того, чтобы они соответствовали двум свойствам, описанным выше.
   1. Записываем два младших бита K[i], по формуле <math> j = K[i] \land 3 </math>, а затем записываем вместо этих двух бит единицы, <math>w = K[i] \lor 3</math>.
   2. Собираем маску M для битов w, которые принадлежат последовательностям из десяти и более нулей или единиц. К примеру, <math>M_l=1</math>, тогда и только тогда, когда <math>w_l</math> принадлежит последовательности из 10 или более одинаковых элементов. Тогда мы сбрасываем (выставляем их в 0) значения тех единиц M, которые находятся в концах нулевых или единичных последовательностей, а также тех единиц, которые находятся в старшем и младшем битах. К примеру, пусть наше слово выглядит так: <math>w = 0^{3}1^{13}0^{12}1011</math> (выражение <math>0^i</math> или же <math>1^i</math> обозначает, что 0 или 1 будут повторены в слове i раз). Тогда маска M будет выглядеть следующим образом: <math>0^{3}1^{25}0^{4}</math>. А значит мы сбрасываем биты в 4, 15, 16, 28 позициях, то есть <math> M = 0^{4}1^{11}001^{10}0^{5}</math>
   3. Далее, для исправления, мы используем таблицу из четырёх слов B[]. Все элементы таблицы B подобраны так, что для них и для всех их цикличных сдвигов выполняется свойство, что в них нет семи подряд идущих 0 или 1. В реализации IBM использовалась таблица <math> B[] = \left \{ 0xa4a8d57b,0x5b5d193b, 0xc8a8309b, 0x73f9a978 \right \} </math>. Далее используются два записанных бита j для выбора слова из таблицы B, и используются младшие пять бит слова K[i-1] для вращения его элементов, <math> p = B[j] \lll (lowest ~5 ~bits ~of ~K[i-1]). </math>
   4. Окончательно, делается XOR шаблона p на исходное слово, при учете маски М: <math> K[i] = w \oplus (p \land M)</math>. Стоит заметить, то что 2 младших бита М являются 0, то два младших бита итогового слова будут единицами, а использование таблицы B позволяет гарантировать, что в слове не будет 10 подряд идущих 0 или 1

Преимущества и недостатки алгоритма

Шифр был кандидатом AES, после небольших изменений в ходе первого раунда конкурса, связанных с изменением процедуры расширения ключа, MARS успешно прошёл в финал.

В финале конкурса у MARS был выделен целый ряд недостатков:

1. Сложная структура. Сложная гетерогенная структура алгоритма затрудняла не только его анализ, но и реализацию.
2. Реализация. Возникали проблемы при реализации шифра на платформах, которые не поддерживали операции 32-битного умножения и вращения на произвольное число бит.
3. Ограниченность ресурсов. Невозможность аппаратно реализовать алгоритм при малых ресурсах оперативной или же энергонезависимой памяти.
4. Защита. MARS оказался плохо защищен от атак по времени выполнения и потребляемой мощности.
5. Расширение ключа. MARS хуже других финалистов AES поддерживал расширение ключа «на лету».
6. Распараллеливаемость. Можно распараллелить лишь небольшую часть алгоритма.

На все эти недостатки экспертная комиссия выделила одно крупное достоинство данного алгоритма — его симметричность. Исходя из выделенных недостатков, MARS ожидаемо не стал победителем AES.

Ответ аналитикам AES

После оглашения результатов конкурса AES, группа создателей MARS выпустила свою рецензию на весь конкурс. В ней были поставлены под сомнение критерии оценки конкурса. Они считали, что главной характеристикой шифра должна быть именно надёжность и его стойкость (к примеру, к brute-force атакам) Кроме того они ответили на каждую претензию со стороны жюри к своему алгоритму.

1. MARS не подходит для аппаратной реализации Среди претензий к шифру были его трудная аппаратная реализация, которая могла повлечь за собой утяжеление работы Интернета, а также внедрение больших, по своим размерам, схем.

Разработчики утверждают, что их реализация способна работать со скоростью 1,28Гбит/сек, что является приемлемым для интернета, а стоимость их чипов может быть и высокая (13$ за 12Гбит/сек чип или 1$ за 1Гбит/сек чип), но в будущем их цена значительно упадет.

2. MARS не подходит для реализации на устройствах с малой памятью Для реализации на SMART картах есть у алгоритмов есть всего 128 байт памяти. Для процедуры расширения ключа MARS требует 512 байт.

Разработчики считают, что нет причины, по которой нужно реализовывать AES на таком уязвимом ресурсе с малой памятью, как смарт-карты, так как все эти ресурсы можно просто и быстро переделать их на системы с открытым ключом.

3. MARS не подходит для реализации на ППВМ MARS не подходит для реализации на платформах, где не разрешено вращение(зависящих от сторонних факторов).

Разработчики отмечают, что эта проблема не является фатальной, а требует немного времени, для адаптации алгоритма к этой платформе

4. Расширение ключа MARS является очень тяжёлой операцией

Разработчики утверждают, что это смешное утверждение. Они утверждают, что у них соблюдена «идеальная» пропорция между дополнительной памятью на ключ и пропускной способностью(25 байт на ключ)

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

Анализ безопасности алгоритма

В настоящее время нет эффективных атак на данный алгоритм. Хотя у него есть несколько слабых сторон:

1. Подключи с большим количеством повторяющихся нулей или единиц могут привести к эффективным атакам на MARS, так как на их основании будут сгенерированны слабые подключи.
2. Два младших бита, используемых при перемножении всегда единицы. Таким образом всегда есть два входных бита, которые неизменны в ходе процесса умножения на ключ, а также два выходных бита, независимых от ключа.

Литература

• Сергей Панасенко. Алгоритмы шифрования. — Санкт-Петербург: БХВ-Петербург, 2009. — P. 65-68, 219-228. — 576 стр p. — ISBN 978-5-9775-0319-8.

Ссылки

• [www.research.ibm.com/security/mars.pdf Спецификация алгоритма(AES версия)]
• [cartman-cipher.narod.ru/mirror/mars1248.zip Исходные тексты MARS-1248 на языке C]
• [domino.research.ibm.com/comm/research_projects.nsf/pages/security.mars.html Официальная страница шифра]
• [www.research.ibm.com/security/sbox-diffs.txt Описание проблемы сгенерированных S-блоков]
• [www.research.ibm.com/security/final-comments.pdf Комментарии создателей шифра]

Отрывок, характеризующий MARS (криптография)

– Да, постой, – сказал Денисов, оглянулся на офицеров и, достав из под подушки свои бумаги, пошел к окну, на котором у него стояла чернильница, и сел писать.
– Видно плетью обуха не пег'ешибешь, – сказал он, отходя от окна и подавая Ростову большой конверт. – Это была просьба на имя государя, составленная аудитором, в которой Денисов, ничего не упоминая о винах провиантского ведомства, просил только о помиловании.
– Передай, видно… – Он не договорил и улыбнулся болезненно фальшивой улыбкой.


Вернувшись в полк и передав командиру, в каком положении находилось дело Денисова, Ростов с письмом к государю поехал в Тильзит.
13 го июня, французский и русский императоры съехались в Тильзите. Борис Друбецкой просил важное лицо, при котором он состоял, о том, чтобы быть причислену к свите, назначенной состоять в Тильзите.
– Je voudrais voir le grand homme, [Я желал бы видеть великого человека,] – сказал он, говоря про Наполеона, которого он до сих пор всегда, как и все, называл Буонапарте.
– Vous parlez de Buonaparte? [Вы говорите про Буонапарта?] – сказал ему улыбаясь генерал.
Борис вопросительно посмотрел на своего генерала и тотчас же понял, что это было шуточное испытание.
– Mon prince, je parle de l'empereur Napoleon, [Князь, я говорю об императоре Наполеоне,] – отвечал он. Генерал с улыбкой потрепал его по плечу.
– Ты далеко пойдешь, – сказал он ему и взял с собою.
Борис в числе немногих был на Немане в день свидания императоров; он видел плоты с вензелями, проезд Наполеона по тому берегу мимо французской гвардии, видел задумчивое лицо императора Александра, в то время как он молча сидел в корчме на берегу Немана, ожидая прибытия Наполеона; видел, как оба императора сели в лодки и как Наполеон, приставши прежде к плоту, быстрыми шагами пошел вперед и, встречая Александра, подал ему руку, и как оба скрылись в павильоне. Со времени своего вступления в высшие миры, Борис сделал себе привычку внимательно наблюдать то, что происходило вокруг него и записывать. Во время свидания в Тильзите он расспрашивал об именах тех лиц, которые приехали с Наполеоном, о мундирах, которые были на них надеты, и внимательно прислушивался к словам, которые были сказаны важными лицами. В то самое время, как императоры вошли в павильон, он посмотрел на часы и не забыл посмотреть опять в то время, когда Александр вышел из павильона. Свидание продолжалось час и пятьдесят три минуты: он так и записал это в тот вечер в числе других фактов, которые, он полагал, имели историческое значение. Так как свита императора была очень небольшая, то для человека, дорожащего успехом по службе, находиться в Тильзите во время свидания императоров было делом очень важным, и Борис, попав в Тильзит, чувствовал, что с этого времени положение его совершенно утвердилось. Его не только знали, но к нему пригляделись и привыкли. Два раза он исполнял поручения к самому государю, так что государь знал его в лицо, и все приближенные не только не дичились его, как прежде, считая за новое лицо, но удивились бы, ежели бы его не было.
Борис жил с другим адъютантом, польским графом Жилинским. Жилинский, воспитанный в Париже поляк, был богат, страстно любил французов, и почти каждый день во время пребывания в Тильзите, к Жилинскому и Борису собирались на обеды и завтраки французские офицеры из гвардии и главного французского штаба.
24 го июня вечером, граф Жилинский, сожитель Бориса, устроил для своих знакомых французов ужин. На ужине этом был почетный гость, один адъютант Наполеона, несколько офицеров французской гвардии и молодой мальчик старой аристократической французской фамилии, паж Наполеона. В этот самый день Ростов, пользуясь темнотой, чтобы не быть узнанным, в статском платье, приехал в Тильзит и вошел в квартиру Жилинского и Бориса.
В Ростове, также как и во всей армии, из которой он приехал, еще далеко не совершился в отношении Наполеона и французов, из врагов сделавшихся друзьями, тот переворот, который произошел в главной квартире и в Борисе. Все еще продолжали в армии испытывать прежнее смешанное чувство злобы, презрения и страха к Бонапарте и французам. Еще недавно Ростов, разговаривая с Платовским казачьим офицером, спорил о том, что ежели бы Наполеон был взят в плен, с ним обратились бы не как с государем, а как с преступником. Еще недавно на дороге, встретившись с французским раненым полковником, Ростов разгорячился, доказывая ему, что не может быть мира между законным государем и преступником Бонапарте. Поэтому Ростова странно поразил в квартире Бориса вид французских офицеров в тех самых мундирах, на которые он привык совсем иначе смотреть из фланкерской цепи. Как только он увидал высунувшегося из двери французского офицера, это чувство войны, враждебности, которое он всегда испытывал при виде неприятеля, вдруг обхватило его. Он остановился на пороге и по русски спросил, тут ли живет Друбецкой. Борис, заслышав чужой голос в передней, вышел к нему навстречу. Лицо его в первую минуту, когда он узнал Ростова, выразило досаду.
– Ах это ты, очень рад, очень рад тебя видеть, – сказал он однако, улыбаясь и подвигаясь к нему. Но Ростов заметил первое его движение.
– Я не во время кажется, – сказал он, – я бы не приехал, но мне дело есть, – сказал он холодно…
– Нет, я только удивляюсь, как ты из полка приехал. – «Dans un moment je suis a vous», [Сию минуту я к твоим услугам,] – обратился он на голос звавшего его.
– Я вижу, что я не во время, – повторил Ростов.
Выражение досады уже исчезло на лице Бориса; видимо обдумав и решив, что ему делать, он с особенным спокойствием взял его за обе руки и повел в соседнюю комнату. Глаза Бориса, спокойно и твердо глядевшие на Ростова, были как будто застланы чем то, как будто какая то заслонка – синие очки общежития – были надеты на них. Так казалось Ростову.
– Ах полно, пожалуйста, можешь ли ты быть не во время, – сказал Борис. – Борис ввел его в комнату, где был накрыт ужин, познакомил с гостями, назвав его и объяснив, что он был не статский, но гусарский офицер, его старый приятель. – Граф Жилинский, le comte N.N., le capitaine S.S., [граф Н.Н., капитан С.С.] – называл он гостей. Ростов нахмуренно глядел на французов, неохотно раскланивался и молчал.
Жилинский, видимо, не радостно принял это новое русское лицо в свой кружок и ничего не сказал Ростову. Борис, казалось, не замечал происшедшего стеснения от нового лица и с тем же приятным спокойствием и застланностью в глазах, с которыми он встретил Ростова, старался оживить разговор. Один из французов обратился с обыкновенной французской учтивостью к упорно молчавшему Ростову и сказал ему, что вероятно для того, чтобы увидать императора, он приехал в Тильзит.
– Нет, у меня есть дело, – коротко ответил Ростов.
Ростов сделался не в духе тотчас же после того, как он заметил неудовольствие на лице Бориса, и, как всегда бывает с людьми, которые не в духе, ему казалось, что все неприязненно смотрят на него и что всем он мешает. И действительно он мешал всем и один оставался вне вновь завязавшегося общего разговора. «И зачем он сидит тут?» говорили взгляды, которые бросали на него гости. Он встал и подошел к Борису.
– Однако я тебя стесняю, – сказал он ему тихо, – пойдем, поговорим о деле, и я уйду.
– Да нет, нисколько, сказал Борис. А ежели ты устал, пойдем в мою комнатку и ложись отдохни.
– И в самом деле…
Они вошли в маленькую комнатку, где спал Борис. Ростов, не садясь, тотчас же с раздраженьем – как будто Борис был в чем нибудь виноват перед ним – начал ему рассказывать дело Денисова, спрашивая, хочет ли и может ли он просить о Денисове через своего генерала у государя и через него передать письмо. Когда они остались вдвоем, Ростов в первый раз убедился, что ему неловко было смотреть в глаза Борису. Борис заложив ногу на ногу и поглаживая левой рукой тонкие пальцы правой руки, слушал Ростова, как слушает генерал доклад подчиненного, то глядя в сторону, то с тою же застланностию во взгляде прямо глядя в глаза Ростову. Ростову всякий раз при этом становилось неловко и он опускал глаза.
– Я слыхал про такого рода дела и знаю, что Государь очень строг в этих случаях. Я думаю, надо бы не доводить до Его Величества. По моему, лучше бы прямо просить корпусного командира… Но вообще я думаю…
– Так ты ничего не хочешь сделать, так и скажи! – закричал почти Ростов, не глядя в глаза Борису.
Борис улыбнулся: – Напротив, я сделаю, что могу, только я думал…
В это время в двери послышался голос Жилинского, звавший Бориса.
– Ну иди, иди, иди… – сказал Ростов и отказавшись от ужина, и оставшись один в маленькой комнатке, он долго ходил в ней взад и вперед, и слушал веселый французский говор из соседней комнаты.


Ростов приехал в Тильзит в день, менее всего удобный для ходатайства за Денисова. Самому ему нельзя было итти к дежурному генералу, так как он был во фраке и без разрешения начальства приехал в Тильзит, а Борис, ежели даже и хотел, не мог сделать этого на другой день после приезда Ростова. В этот день, 27 го июня, были подписаны первые условия мира. Императоры поменялись орденами: Александр получил Почетного легиона, а Наполеон Андрея 1 й степени, и в этот день был назначен обед Преображенскому батальону, который давал ему батальон французской гвардии. Государи должны были присутствовать на этом банкете.
Ростову было так неловко и неприятно с Борисом, что, когда после ужина Борис заглянул к нему, он притворился спящим и на другой день рано утром, стараясь не видеть его, ушел из дома. Во фраке и круглой шляпе Николай бродил по городу, разглядывая французов и их мундиры, разглядывая улицы и дома, где жили русский и французский императоры. На площади он видел расставляемые столы и приготовления к обеду, на улицах видел перекинутые драпировки с знаменами русских и французских цветов и огромные вензеля А. и N. В окнах домов были тоже знамена и вензеля.
«Борис не хочет помочь мне, да и я не хочу обращаться к нему. Это дело решенное – думал Николай – между нами всё кончено, но я не уеду отсюда, не сделав всё, что могу для Денисова и главное не передав письма государю. Государю?!… Он тут!» думал Ростов, подходя невольно опять к дому, занимаемому Александром.
У дома этого стояли верховые лошади и съезжалась свита, видимо приготовляясь к выезду государя.
«Всякую минуту я могу увидать его, – думал Ростов. Если бы только я мог прямо передать ему письмо и сказать всё, неужели меня бы арестовали за фрак? Не может быть! Он бы понял, на чьей стороне справедливость. Он всё понимает, всё знает. Кто же может быть справедливее и великодушнее его? Ну, да ежели бы меня и арестовали бы за то, что я здесь, что ж за беда?» думал он, глядя на офицера, всходившего в дом, занимаемый государем. «Ведь вот всходят же. – Э! всё вздор. Пойду и подам сам письмо государю: тем хуже будет для Друбецкого, который довел меня до этого». И вдруг, с решительностью, которой он сам не ждал от себя, Ростов, ощупав письмо в кармане, пошел прямо к дому, занимаемому государем.
«Нет, теперь уже не упущу случая, как после Аустерлица, думал он, ожидая всякую секунду встретить государя и чувствуя прилив крови к сердцу при этой мысли. Упаду в ноги и буду просить его. Он поднимет, выслушает и еще поблагодарит меня». «Я счастлив, когда могу сделать добро, но исправить несправедливость есть величайшее счастье», воображал Ростов слова, которые скажет ему государь. И он пошел мимо любопытно смотревших на него, на крыльцо занимаемого государем дома.
С крыльца широкая лестница вела прямо наверх; направо видна была затворенная дверь. Внизу под лестницей была дверь в нижний этаж.
– Кого вам? – спросил кто то.
– Подать письмо, просьбу его величеству, – сказал Николай с дрожанием голоса.
– Просьба – к дежурному, пожалуйте сюда (ему указали на дверь внизу). Только не примут.
Услыхав этот равнодушный голос, Ростов испугался того, что он делал; мысль встретить всякую минуту государя так соблазнительна и оттого так страшна была для него, что он готов был бежать, но камер фурьер, встретивший его, отворил ему дверь в дежурную и Ростов вошел.
Невысокий полный человек лет 30, в белых панталонах, ботфортах и в одной, видно только что надетой, батистовой рубашке, стоял в этой комнате; камердинер застегивал ему сзади шитые шелком прекрасные новые помочи, которые почему то заметил Ростов. Человек этот разговаривал с кем то бывшим в другой комнате.
– Bien faite et la beaute du diable, [Хорошо сложена и красота молодости,] – говорил этот человек и увидав Ростова перестал говорить и нахмурился.
– Что вам угодно? Просьба?…
– Qu'est ce que c'est? [Что это?] – спросил кто то из другой комнаты.
– Encore un petitionnaire, [Еще один проситель,] – отвечал человек в помочах.
– Скажите ему, что после. Сейчас выйдет, надо ехать.
– После, после, завтра. Поздно…
Ростов повернулся и хотел выйти, но человек в помочах остановил его.
– От кого? Вы кто?
– От майора Денисова, – отвечал Ростов.
– Вы кто? офицер?
– Поручик, граф Ростов.
– Какая смелость! По команде подайте. А сами идите, идите… – И он стал надевать подаваемый камердинером мундир.
Ростов вышел опять в сени и заметил, что на крыльце было уже много офицеров и генералов в полной парадной форме, мимо которых ему надо было пройти.
Проклиная свою смелость, замирая от мысли, что всякую минуту он может встретить государя и при нем быть осрамлен и выслан под арест, понимая вполне всю неприличность своего поступка и раскаиваясь в нем, Ростов, опустив глаза, пробирался вон из дома, окруженного толпой блестящей свиты, когда чей то знакомый голос окликнул его и чья то рука остановила его.
– Вы, батюшка, что тут делаете во фраке? – спросил его басистый голос.
Это был кавалерийский генерал, в эту кампанию заслуживший особенную милость государя, бывший начальник дивизии, в которой служил Ростов.
Ростов испуганно начал оправдываться, но увидав добродушно шутливое лицо генерала, отойдя к стороне, взволнованным голосом передал ему всё дело, прося заступиться за известного генералу Денисова. Генерал выслушав Ростова серьезно покачал головой.
– Жалко, жалко молодца; давай письмо.
Едва Ростов успел передать письмо и рассказать всё дело Денисова, как с лестницы застучали быстрые шаги со шпорами и генерал, отойдя от него, подвинулся к крыльцу. Господа свиты государя сбежали с лестницы и пошли к лошадям. Берейтор Эне, тот самый, который был в Аустерлице, подвел лошадь государя, и на лестнице послышался легкий скрип шагов, которые сейчас узнал Ростов. Забыв опасность быть узнанным, Ростов подвинулся с несколькими любопытными из жителей к самому крыльцу и опять, после двух лет, он увидал те же обожаемые им черты, то же лицо, тот же взгляд, ту же походку, то же соединение величия и кротости… И чувство восторга и любви к государю с прежнею силою воскресло в душе Ростова. Государь в Преображенском мундире, в белых лосинах и высоких ботфортах, с звездой, которую не знал Ростов (это была legion d'honneur) [звезда почетного легиона] вышел на крыльцо, держа шляпу под рукой и надевая перчатку. Он остановился, оглядываясь и всё освещая вокруг себя своим взглядом. Кое кому из генералов он сказал несколько слов. Он узнал тоже бывшего начальника дивизии Ростова, улыбнулся ему и подозвал его к себе.
Вся свита отступила, и Ростов видел, как генерал этот что то довольно долго говорил государю.
Государь сказал ему несколько слов и сделал шаг, чтобы подойти к лошади. Опять толпа свиты и толпа улицы, в которой был Ростов, придвинулись к государю. Остановившись у лошади и взявшись рукою за седло, государь обратился к кавалерийскому генералу и сказал громко, очевидно с желанием, чтобы все слышали его.
– Не могу, генерал, и потому не могу, что закон сильнее меня, – сказал государь и занес ногу в стремя. Генерал почтительно наклонил голову, государь сел и поехал галопом по улице. Ростов, не помня себя от восторга, с толпою побежал за ним.


На площади куда поехал государь, стояли лицом к лицу справа батальон преображенцев, слева батальон французской гвардии в медвежьих шапках.
В то время как государь подъезжал к одному флангу баталионов, сделавших на караул, к противоположному флангу подскакивала другая толпа всадников и впереди их Ростов узнал Наполеона. Это не мог быть никто другой. Он ехал галопом в маленькой шляпе, с Андреевской лентой через плечо, в раскрытом над белым камзолом синем мундире, на необыкновенно породистой арабской серой лошади, на малиновом, золотом шитом, чепраке. Подъехав к Александру, он приподнял шляпу и при этом движении кавалерийский глаз Ростова не мог не заметить, что Наполеон дурно и не твердо сидел на лошади. Батальоны закричали: Ура и Vive l'Empereur! [Да здравствует Император!] Наполеон что то сказал Александру. Оба императора слезли с лошадей и взяли друг друга за руки. На лице Наполеона была неприятно притворная улыбка. Александр с ласковым выражением что то говорил ему.
Ростов не спуская глаз, несмотря на топтание лошадьми французских жандармов, осаживавших толпу, следил за каждым движением императора Александра и Бонапарте. Его, как неожиданность, поразило то, что Александр держал себя как равный с Бонапарте, и что Бонапарте совершенно свободно, как будто эта близость с государем естественна и привычна ему, как равный, обращался с русским царем.
Александр и Наполеон с длинным хвостом свиты подошли к правому флангу Преображенского батальона, прямо на толпу, которая стояла тут. Толпа очутилась неожиданно так близко к императорам, что Ростову, стоявшему в передних рядах ее, стало страшно, как бы его не узнали.
– Sire, je vous demande la permission de donner la legion d'honneur au plus brave de vos soldats, [Государь, я прошу у вас позволенья дать орден Почетного легиона храбрейшему из ваших солдат,] – сказал резкий, точный голос, договаривающий каждую букву. Это говорил малый ростом Бонапарте, снизу прямо глядя в глаза Александру. Александр внимательно слушал то, что ему говорили, и наклонив голову, приятно улыбнулся.
– A celui qui s'est le plus vaillament conduit dans cette derieniere guerre, [Тому, кто храбрее всех показал себя во время войны,] – прибавил Наполеон, отчеканивая каждый слог, с возмутительным для Ростова спокойствием и уверенностью оглядывая ряды русских, вытянувшихся перед ним солдат, всё держащих на караул и неподвижно глядящих в лицо своего императора.
– Votre majeste me permettra t elle de demander l'avis du colonel? [Ваше Величество позволит ли мне спросить мнение полковника?] – сказал Александр и сделал несколько поспешных шагов к князю Козловскому, командиру батальона. Бонапарте стал между тем снимать перчатку с белой, маленькой руки и разорвав ее, бросил. Адъютант, сзади торопливо бросившись вперед, поднял ее.
– Кому дать? – не громко, по русски спросил император Александр у Козловского.
– Кому прикажете, ваше величество? – Государь недовольно поморщился и, оглянувшись, сказал:
– Да ведь надобно же отвечать ему.
Козловский с решительным видом оглянулся на ряды и в этом взгляде захватил и Ростова.
«Уж не меня ли?» подумал Ростов.
– Лазарев! – нахмурившись прокомандовал полковник; и первый по ранжиру солдат, Лазарев, бойко вышел вперед.
– Куда же ты? Тут стой! – зашептали голоса на Лазарева, не знавшего куда ему итти. Лазарев остановился, испуганно покосившись на полковника, и лицо его дрогнуло, как это бывает с солдатами, вызываемыми перед фронт.
Наполеон чуть поворотил голову назад и отвел назад свою маленькую пухлую ручку, как будто желая взять что то. Лица его свиты, догадавшись в ту же секунду в чем дело, засуетились, зашептались, передавая что то один другому, и паж, тот самый, которого вчера видел Ростов у Бориса, выбежал вперед и почтительно наклонившись над протянутой рукой и не заставив ее дожидаться ни одной секунды, вложил в нее орден на красной ленте. Наполеон, не глядя, сжал два пальца. Орден очутился между ними. Наполеон подошел к Лазареву, который, выкатывая глаза, упорно продолжал смотреть только на своего государя, и оглянулся на императора Александра, показывая этим, что то, что он делал теперь, он делал для своего союзника. Маленькая белая рука с орденом дотронулась до пуговицы солдата Лазарева. Как будто Наполеон знал, что для того, чтобы навсегда этот солдат был счастлив, награжден и отличен от всех в мире, нужно было только, чтобы его, Наполеонова рука, удостоила дотронуться до груди солдата. Наполеон только прило жил крест к груди Лазарева и, пустив руку, обратился к Александру, как будто он знал, что крест должен прилипнуть к груди Лазарева. Крест действительно прилип.
Русские и французские услужливые руки, мгновенно подхватив крест, прицепили его к мундиру. Лазарев мрачно взглянул на маленького человечка, с белыми руками, который что то сделал над ним, и продолжая неподвижно держать на караул, опять прямо стал глядеть в глаза Александру, как будто он спрашивал Александра: всё ли еще ему стоять, или не прикажут ли ему пройтись теперь, или может быть еще что нибудь сделать? Но ему ничего не приказывали, и он довольно долго оставался в этом неподвижном состоянии.
Государи сели верхами и уехали. Преображенцы, расстроивая ряды, перемешались с французскими гвардейцами и сели за столы, приготовленные для них.
Лазарев сидел на почетном месте; его обнимали, поздравляли и жали ему руки русские и французские офицеры. Толпы офицеров и народа подходили, чтобы только посмотреть на Лазарева. Гул говора русского французского и хохота стоял на площади вокруг столов. Два офицера с раскрасневшимися лицами, веселые и счастливые прошли мимо Ростова.
– Каково, брат, угощенье? Всё на серебре, – сказал один. – Лазарева видел?
– Видел.
– Завтра, говорят, преображенцы их угащивать будут.
– Нет, Лазареву то какое счастье! 10 франков пожизненного пенсиона.
– Вот так шапка, ребята! – кричал преображенец, надевая мохнатую шапку француза.
– Чудо как хорошо, прелесть!
– Ты слышал отзыв? – сказал гвардейский офицер другому. Третьего дня было Napoleon, France, bravoure; [Наполеон, Франция, храбрость;] вчера Alexandre, Russie, grandeur; [Александр, Россия, величие;] один день наш государь дает отзыв, а другой день Наполеон. Завтра государь пошлет Георгия самому храброму из французских гвардейцев. Нельзя же! Должен ответить тем же.
Борис с своим товарищем Жилинским тоже пришел посмотреть на банкет преображенцев. Возвращаясь назад, Борис заметил Ростова, который стоял у угла дома.
– Ростов! здравствуй; мы и не видались, – сказал он ему, и не мог удержаться, чтобы не спросить у него, что с ним сделалось: так странно мрачно и расстроено было лицо Ростова.
– Ничего, ничего, – отвечал Ростов.
– Ты зайдешь?
– Да, зайду.
Ростов долго стоял у угла, издалека глядя на пирующих. В уме его происходила мучительная работа, которую он никак не мог довести до конца. В душе поднимались страшные сомнения. То ему вспоминался Денисов с своим изменившимся выражением, с своей покорностью и весь госпиталь с этими оторванными руками и ногами, с этой грязью и болезнями. Ему так живо казалось, что он теперь чувствует этот больничный запах мертвого тела, что он оглядывался, чтобы понять, откуда мог происходить этот запах. То ему вспоминался этот самодовольный Бонапарте с своей белой ручкой, который был теперь император, которого любит и уважает император Александр. Для чего же оторванные руки, ноги, убитые люди? То вспоминался ему награжденный Лазарев и Денисов, наказанный и непрощенный. Он заставал себя на таких странных мыслях, что пугался их.
Запах еды преображенцев и голод вызвали его из этого состояния: надо было поесть что нибудь, прежде чем уехать. Он пошел к гостинице, которую видел утром. В гостинице он застал так много народу, офицеров, так же как и он приехавших в статских платьях, что он насилу добился обеда. Два офицера одной с ним дивизии присоединились к нему. Разговор естественно зашел о мире. Офицеры, товарищи Ростова, как и большая часть армии, были недовольны миром, заключенным после Фридланда. Говорили, что еще бы подержаться, Наполеон бы пропал, что у него в войсках ни сухарей, ни зарядов уж не было. Николай молча ел и преимущественно пил. Он выпил один две бутылки вина. Внутренняя поднявшаяся в нем работа, не разрешаясь, всё также томила его. Он боялся предаваться своим мыслям и не мог отстать от них. Вдруг на слова одного из офицеров, что обидно смотреть на французов, Ростов начал кричать с горячностью, ничем не оправданною, и потому очень удивившею офицеров.