Блочный алгоритм MARS

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

УДМУРТСКИЙ  ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ 

Институт  права, социального управления и  безопасности

Кафедра информационной безопасности в управлении 
 
 

Контрольная работа

 по  дисциплине «Криптографическая защита информации »

на тему: «Блочный алгоритм MARS» 
 
 
 
 
 
 
 

Выполнил:                                                                                                                                                                                                                                                                                       

                                                                                                    Студент группы О-075300-01(к)

Специальности

“Организация  и технология защиты информации”

Алиев Эльнур Айдынович 
 

Проверил:

Бас Алексей  Анатольевич

  
 

Ижевск 2012

Содержание

Вступление..............................................................................................................................3

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

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

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

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

    Е-функция………………………………………………………………………………….9

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

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

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

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

Вступление

     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.

3.

4. // Затем 8 раундов  прямого перемешивания

5.   // используем D[0] для модифицирования D[1]; D[2]; D[3]

6. // обращаемся  к 4-ем S-блокам

7.

8.

9.

10.

11. // и вращаем  исходное слово вправо

12.

13. // также проделаем  дополнительные операции смешивания

14.

15.      // добавим D[3] к исходному слову

16.

17.    // добавим D[1] к исходному слову

18. // вращаем  массив D[ ]

19.

20.

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

     

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

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

          Псевдокод

1. // Проделаем  16 раундов шифрования при использовании  ключа

2.

3.

4.

5.

6. // сначала 8 раундов прямого преобразования

7.

8.

9. // потом 8 раундов обратного преобразования

10.

11.

12.