Алгоритм Райндал (Rijndael). Основные особенности шифра Райндал

Оглавление

Оглавление 1

Введение 2

Глава 1. Стандарт шифрования данных AES. 3

1.1 Алгоритм шифрования AES 3

1.2 Перспективный стандарт AES 8

1.3 Атака на алгоритм шифрования AES 12

Глава 2. Алгоритм Райндал (Rijndael). Основные особенности шифра Райндал. 14

2.1 Алгоритм Rijndael. Предварительные математические понятия 14

2.2 Сложение 14

2.3 Умножение 15

2.4 Умножение на Х 16

2.5 Обоснование разработки 17

2.6 Спецификация алгоритма 18

2.7 Состояние, ключ шифрования и число раундов 19

2.8 Преимущества алгоритма 20

2.9 Расширения 21

2.10 Другие возможности 22

2.11 Преимущества алгоритма шифрования Rijndael (AES) 23

Заключение 24

Литература 25

 

 

 

 

 

 

 

 

Введение

 

Цель  курсового проекта:  Рассмотреть алгоритм шифрования AES (Rijndael). Рассмотреть основные математические операции. Разобрать и реализовать процедуры AddRoundKey, SubBytes, ShiftRows, MixColumns.

Задачи:

1. Рассказать о шифровании AES.

2. Понять принцип построение стандарта шифрования.

3. Разобрать алгоритм  Rijndael.

4. Разобрать математическую  часть алгоритма. 

5. Сделать заключение

 

Целью проведения конкурса AES был поиск нового стандарта шифрования на замену таких алгоритмов как DES и IDEA, криптостойкость которых была подвергнута сомнению, а впоследствии и вовсем признали эти алгоритмы ненадежными. В результате проведения конкурса был выбран новый стандарт шифрования Advanced Encryption Standard (AES), также известный как Rijndael — симметричный алгоритм блочного шифрования с переменной длиной блока и переменной длиной ключа. Длина блока и длина ключа могут быть независимо установлены в 128, 192 или 256 бит. Обычно длина блока составляет 128 бит, поэтому в данной работе рассматривался именно этот размер. Алгоритм использует линейно-подстановочные преобразования и состоит из 10, 12 или 14 раундов в зависимости от длины ключа (соответственно 128, 192 и 256 бит). Блок данных, обрабатываемый с использованием алгоритма Rijndael, делится на массивы байтов, и каждая операция шифрования является байт-ориентированной.

Преобразование раунда алгоритма  Rijndael не имеет структуру сети Фейстеля, а использует структуру типа SP-сеть (Substitution-Permutation network, подстановочно-перестановочная сеть) — разновидность блочного шифра, предложенная в 1971 году Хорстом Фейстелем. Ппреобразование каждого раунда состоит из четырех различных преобразований, называемых слоями. Каждый слой разрабатывался с учетом противодействия линейному и дифференциальному криптоанализу. В основу каждого слоя положена своя собственная функция.

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

 

Глава 1. Стандарт шифрования данных AES.

1.1 Алгоритм шифрования AES

 

AES — в настоящее время  самый широко распространенный  алгоритм шифрования. AES уже более  10 лет является официальным стандартом  США для шифрования данных  и применяется в различных  сферах деятельности по всему  миру. Благодаря совокупности своих  положительных качеств и хорошему  запасу криптостойкости, в ближайшие годы AES вряд ли утратит свое лидерство. Алгоритм рекомендован для использования в приложениях и аппаратных решениях любой сложности в тех случаях, когда уместно применение блочных симметричных алгоритмов.

Преимущества алгоритма:

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

• Высокая криптостойкость. Алгоритм известен уже около 15 лет, в течение 10 из которых он является стандартом шифрования в США. За это время, AES был исследован вдоль и поперек криптоаналитиками со всего мира, и работа по поиску уязвимостей не прекращается до сих пор. На настоящий момент, не найдено сколько-нибудь серьезных уязвимостей, которые представляют практической опасности для криптостойкости алгоритма.

Недостатки алгоритма:

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

Алгоритм AES при использовании  сильных ключей и корректно реализованный, обеспечит очень высокий уровень  безопасности вашей информации. При  использовании алгоритма с ключами  длиной 128 бит, достигается достаточный  уровень защиты, при котором невозможно взломать алгоритм при помощи современных  технологий за разумное время. Применение же 192, 256-битных ключей сейчас обеспечивает избыточную защиту, которая имеет  хороших запас криптостойкости даже в случае развития в ближайшие годы технологии и науки.

AES имеет так же и  второе, менее известное название  — Rijndael, под которым он был впервые представлен общественности.

 В 1997 году Американский институт стандартизации NIST (National Institute of Standards & Technology ) объявил конкурс на новый стандарт симметричного криптоалгоритма, названного AES (Advanced Encryption Standard). К его разработке были подключены самые крупные центры криптологии со всего мира. К криптоалгоритмам - кандидатам на новый стандарт AES были предъявленыследующие требования:

− алгоритм должен быть симметричным;

− алгоритм должен быть блочным  шифром;

− алгоритм должен иметь  длину блока 128 бит и поддерживать три длины ключа: 128, 192 и 256 бит.

Дополнительно разработчикам  криптоалгоритмов рекомендовалось:

− использовать операции, легко  реализуемые как аппаратно (в  микрочипах), так и программно (на персональных компьютерах и серверах);

− ориентироваться на 32-разрядные  процессоры;

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

На этот конкурс было представлено 15 алгоритмов-претендентов, разработанных  как известными в области криптографии организациями (RSA Security, Counterpane и т.д.), так и частными лицами. Итоги конкурса были подведены в октябре 2000 года: победителем был объявлен алгоритм Rijndael, разработанный двумя криптографами из Бельгии, Винсентом Риджменом (Vincent Rijmen) и Джоан Даймен (Joan Daemen).

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

4 4 × , 4 6 × или 4 8 × в зависимости от установленной длины блока (допускается использование нескольких фиксированных размеров шифруемого блока информации). Далее на соответствующих этапах производятся преобразования либо над независимыми столбцами, либо над независимыми строками, либо вообще над отдельными байтами. Алгоритм AES состоит из определенного количества раундов (от 10 до 14 – это зависит от размера блока и длины ключа) и выполняет четыре преобразования:

− BS (ByteSub) - табличная замена каждого байта массива (рис. 1);

− SR (ShiftRow) - сдвиг строк массива (рис. 2).

При этой операции первая строка остается без изменений, а остальные  циклически побайтно сдвигаютсявлево на фиксированное число байтов, зависящее от размера массива. Например, для массива размером 4 4 × строки 2, 3 и 4 сдвигаются соответственно на 1, 2 и 3 байта; − MC (MixColumn) – операция над независимыми столбцами массива (рис. 3), когда каждый столбец по определенному правилу умножается на фиксированную матрицу c(x) ;

− AK (AddRoundKey) – добавление ключа. Каждый бит массива складывается «по модулю 2» с соответствующим битом ключа раунда, который, в свою очередь, определенным образом вычисляется из ключа шифрования (рис. 4). Эти преобразования воздействуют на массив State, который адресуется с помощью указателя 'state'. Преобразование AddRoundKey использует дополнительный указатель для адресации ключа раунда Round Key.

 

Рис. 1. Преобразование BS (ByteSub) использует таблицу замен (подстановок)

для обработки каждого  байта массива

 

Рис. 2 Преобразование SR (ShiftRow) циклически сдвигает три последние

строки в массиве

 

 Рис. 3. Преобразование MC (MixColumn) поочередно обрабатывает столбцы

Массива

 

Преобразование BS (ByteSub) является нелинейной байтовой подстановкой, которая воздействует независимо на каждый байт массива State, используя таблицу замен (подстановок) S-box. В каждом раунде (с некоторыми исключениями) над шифруемыми данными поочередно выполняются перечисленные преобразования (рис. 5). Исключения касаются первого и последнего раундов: перед первым раундом дополнительно выполняется операция AK, а в последнем раунде отсутствует MC. В результате последовательность операций при шифровании выглядит так:  AK BS SR MC AK ,{ , , , }(повторяется R −1 раз), BS SR AK , , . Количество раундов шифрования R в алгоритме AES переменное (10, 12 или 14 раундов) и зависит от размеров блока и ключа шифрования (для ключа также предусмотрено несколько фиксированных размеров).

Рис.4 Преобразование AK (AddRoundKey) производит сложение

 

 

 

Рис. 5 Раунд алгоритма AES

 

 

 

Дешифрование выполняется  с помощью следующих обратных операций:

1) Табличная замена BS обращается  применением другой таблицы, являющейся  инверсной относительно таблицы,  применяемой при шифровании.

2) Обратная операция к  SR – это циклический сдвиг  строк вправо, а не влево. 

3) Обратная операция для  MC – умножение по тем же  правилам на другую матрицу  d(x), удовлетворяющую условию c x d x ( ) ( ) 1. × =

4) Добавление ключа AK является  обратным самому себе, поскольку  в нем используется только  операция XOR. Эти обратные операции  применяются при дешифровании  в последовательности, обратной  той, что использовалась при  шифровании. Все преобразования  в шифре AES имеют строгое математическое  обоснование. Сама структура и  последовательность операций позволяют  выполнять данный алгоритм эффективно  как на 8-битовых так и на 32-битовых процессорах. В структуре алгоритма заложена возможность параллельного исполнения некоторых операций, что может поднять скорость шифрования на многопроцессорных рабочих станциях в несколько раз.

Алгоритм Rijndael стал новым стандартом шифрования данных AES благодаря целому ряду преимуществ перед другими алгоритмами. Прежде всего, он обеспечивает высокую скорость шифрования на всех платформах: как при программной, таки при аппаратной реализации. Кроме того, требования к ресурсам для его работы минимальны, что важно при его использовании в устройствах, обладающих ограниченными вычислительными возможностями. Недостатком же алгоритма AES можно считать лишь свойственную ему нетрадиционную схему. Дело в том, что свойства алгоритмов, основанных на сети Фейстеля, хорошо исследованы, а AES, в отличие от них, может содержать скрытые уязвимости, которые могут обнаружиться только по прошествии какого-то времени цс момента начала его широкого распространения.

 

 

 

 

1.2 Перспективный стандарт AES

 

Алгоритм шифрования DES давно  критикуют за целый ряд недостатков, в том числе, за слишком маленькую  длину ключа — всего 56 разрядов. Кроме того в январе 1999 года закодированное посредством DES сообщение было взломано с помощью связанных через  Internet в единую сеть 100 тыс. персональных компьютеров. И на это потребовалось менее 24-х часов. В связи с этим стало очевидным, что в ближайшие несколько лет, учитывая появление более дешевого и высокопроизводительного оборудования, алгоритм DES окажется несостоятельным.

Чтобы решить эту проблему, еще в 1997 году NIST выпустил запрос на комментарий RFC (Request For Comment), где описывался предполагаемый «Усовершенствованный стандарт шифрования» AES (Advanced Encryption Standard), который должен прийти на смену стандарту DES. В 1998 году NIST (National Institute of Standards and Technology), который был предшественником современного Национального института по стандартам и технологии, объявил конкурс на создание алгоритма, удовлетворяющего требованиям, выдвинутым институтом:

• применение одного или более открытых алгоритмов шифрования;
• общедоступность и отсутствие лицензионных отчислений;
• использование симметричного шифрования;
• поддержка минимального размера блока в 128 разрядов и размеров ключей в 128, 192 и 256 разрядов;
• бесплатное распространение по всему миру;
• приемлемая производительность для различных приложений.

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

В результате в качестве стандарта AES был выбран алгоритм Rijndael, разработанный двумя бельгийскими учеными, специалистами по криптографии. Правительство США объявило, что авторами наиболее перспективного алгоритма шифрования стали Джон Димен из компании Proton World International и Винсент Риджмен, сотрудник Католического университета.

Алгоритм Rijndael является нетрадиционным блочным шифром, поскольку в нем для криптопреобразований не используется сеть Фейштеля. Он представляет каждый блок кодируемых данных в виде таблицы двумерного массива байтов размером 4*4, 4*6 или 4*8 в зависимости от установленной длины блока. Далее, на соответствующих этапах, производятся преобразования либо независимых столбцов, либо независимых строк, либо вообще отдельных байтов в таблице.