Материал: Практическая реализация алгоритма симметричного шифрования AES

Практическая реализация алгоритма симметричного шифрования AES

Курсовая работа

Практическая реализация алгоритма симметричного шифрования AES

Введение

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

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

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

1. Описание симметричного алгоритма AES

.1 История возникновения AES (алгоритма симметричного шифрования)

В 1998 году NIST (National Institute of Standards and Technology) объявили конкурс по созданию алгоритма симметричного шифрования, под названием Advanced Encryption Standard сокращено AES. Этот алгоритм должен был стать новым стандартом USA на замену уже устаревшему стандарту Digital Encryption Standard сокращено DES, принятым в 1977 году. Причиной для смены стандарта являлась малая длина ключа DES которая составляла 56 бит, что позволяло злоумышленникам взламывать DES применяя простой метод перебора ключей. Так же проблему вызывала архитектура DES которая была направленна на аппаратную реализацию, что не позволяла программным реализациям получать достаточную скорость быстродействия в связи с нехватками ресурсов. Хотя и модификация TripleDES обладала достаточно большой длиной ключа, но была еще медленнее чем классический DES [1].

января 1997 года NIST объявляет о намерении выбрать новый алгоритм взамен устаревшей DES. 12 сентября 1997 г. был объявлен конкурс. Было разрешено представлять свой алгоритм любым организациям и группам исследователей. Все параметры для кандидатов были в свободном доступе, но NIST потребовало предварительного объявления основных принципов работы алгоритмов. В этот раз NIST решил не повторять ошибки, которые были при выборе DES, которые заключались в закрытии публикации данных об исследовании алгоритмов-кандидатов. Основные требования к кандидатам на стандарт AES:

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

длина обрабатываемого блока должна равняться 128 битам;

размерность ключей должна равняться 128, 192 или 256 битам.

Дополнительные рекомендации для конкурсантов:

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

должны использоваться только те операции, которые возможно было реализовать как программно, так и аппаратно на микрочипах.

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

Так же алгоритм, который станет новым стандартом должен будет распространяться бесплатно за пользование патентом. У алгоритма AES должна быть высокая степень защиты, простая структура и высокая производительность. Уже на внутреннем уровне своей архитектуры у него должна быть достаточная стойкость к попыткам его взлома.

октября 2000 объявили победителя конкурса, им стал алгоритм Rijndael. Сразу после завершения конкурса была начата процедура стандартизации и уже 28 февраля 2001 года был опубликован готовый проект, а 26 ноября 2001 года AES был принят как новый стандарт.не является чистым алгоритмом Rijndael, т.к. у классического алгоритма Rijndael поддерживается больший диапазон длин ключей и блоков. В AES же размер ключей фиксированный и равен 128 бит, а в Rijndael размер возможных ключей составляет промежуток - от 128 до 256 бит, с шагом 32 бита. В AES фиксированная длина блоков, которая составляет 16 байт, а в Rijndael дается возможность выбирать размер блока самостоятельно.- это компактный алгоритм с простой математической частью и высокой скоростью исполнения. Данный алгоритм показал хорошую стойкость к атакам, при которых пытались декодировать зашифрованные данные, анализируя внешние параметры алгоритма, куда входит время выполнения и уровень энергопотребления. В данном алгоритме возможно распараллеливание процессов, что позволяет с лёгкостью обеспечивать полное использование процессорных ресурсов. AES это алгоритм Rijndael с ключом в 128 бит и блоком данных 16 байт.

1.2 Шифрование

Принцип работы шифрования алгоритма AES и его основные функции

В алгоритме AES используются определенные функции как для шифрования, так и для дешифрования, основные функции алгоритма шифрования приведены в таблице 1.

При шифровании алгоритмом AES необходим секретный ключ размером 128 бит, ключ представляется как матрица размерностью 4x4 байта. В начале происходит разбитие текста на блоки размерность 128 бит, если в последнем блоке не хватает данных для его полного заполнения, то свободное место забивается нулями [2].

Двумерный массив размерность 16 байт в который заносят по очереди блоки с начальными данными обычно обозначается как state[a] [b]. Шифрование этих блоков происходит независимо друг от друга что позволяет распараллеливать эти процессы и конечный результат записывается в один массив.

Для шифрования каждого блока требуется как минимум 10 раундов, в каждый раунд входят следующие функции:

- KeyExpansion.

AddKey

SubBytes

ShiftRows

MixColumns

AddRoundKey

Сначала из основного ключа с помощью функции KeyExpansion генерируются раундовые ключи, каждый раундовый ключ используется один раз в одном раунде. После происходит суммирование данных с основным ключом в функции AddRoundKey. После выполнения функции AddRoundKey программа уходит в цикл пока счетчик не сравняется с заранее установленным количеством раундов для данного случая. В теле цикла вызывается функция замены байтов SubBytes, затем циклический сдвиг строк ShiftRows, перемешивание MixColumns, и суммирование с раундовым ключом AddRoundKey. В последнем 10 раунде функция MixColumns пропускается, наглядный пример работы алгоритма шифрования представлен в бок схеме Рисунок 1.

Таблица 1. Функции алгоритма AES

Рисунок 1. Блок схема алгоритма шифрования AES

Подробное описание функций алгоритма шифрования AES

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

Для создания, раундовых ключей, которые используются в функции AddRoundKey, алгоритм AES берет секретный ключ и производит расширение ключа [3].

Расширенный ключ состоит из 16 байт (четыре байта на слово), обозначаемых ниже как wi, где i находится в диапазоне [0..44]. Полная длина расширенного ключа для всех раундов программы составляет 1408 бит, на каждый раунд дается ключ длиной 128 бит. Для расширения базового ключа используется массив констант, который называется Rcon. Нумерация массива начинается от 1 до 256+3. Их значения определяются следующим образом:

Rcon1 = 1;

Rconk = 2 * Rconk-1 = 2^k-1, для k = 2, 3,… 255;

= 0, для k = 256, 257, 258;

Процедуру расширения ключа можно описать в виде последовательности следующих операций.

) Основной ключ шифрования копируются в первые четыре слова расширенного ключа.

) Для получения остальных частей ключа происходит их генерация следующим образом:

- если i кратно 4, то wi = SubBytes (RotByte(wi-1)) + Rcon (i/4);

- если i не кратно 4, то wi = wi-4 + wi-1.

Преобразование AddRoundKey и AddKey

В данной функции происходит добавление раундового ключа в обрабатываемый массив по средствам поразрядного суммирования с таблицей раундовых ключей, для AddKey с обычным ключом. Данное преобразование является обратным самим для себя.

state[j] [i] ^= RoundKey[j] [i]

Преобразование SubBytes

Функция SubBytes производит поочередную замену элементов матрицы с исходными данными на элементы из фиксированной матрицы S-BOX табл. 2. Основной целью этой замены является усложнение линейного дифференциального криптоанализа.

Таблица 2.Таблица подстановки S-Box

Преобразование ShiftRows

Функция ShiftRows производит побайтовый сдвиг строк влево по следующему алгоритму: первая строка не изменяется, вторая сдвигается на 1 байт влево, третья строка на 2 байта, а четвертая на 3 байта[4].

Преобразование MixColumns

При MixColumn столбцы Состояния рассматриваются как многочлены над GF(28) и умножаются по модулю x^4+1 на фиксированный многочлен a(x):

Этот многочлен - взаимно простой с x^4+1 и поэтому обратим.

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

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

Порядок обратного преобразования выглядит так: Производится расширение основного ключа KeyExpansion, после чего программа уходит в цикл до полного прохождения 9 раундов из 10. В которых выполняются следующие функции по порядку:

. AddRoundKey - в данной функции происходит суммирование обрабатываемых данных с раундовым ключом.

. InvMixColumns - в этой функции происходит перемешивание столбцов state обратная функции MixColumns.

. InvShiftRows - данная функция производит обратный функции ShiftRows циклический сдвиг строк state.

. InvSubBytes - в этой функции происходит замена байтов state по таблице замен для дешифрования.

После успешного прохождения девяти раундов программа выходит из цикла и исполняет оставшиеся функции для последнего раунда:

.1. AddRoundKey

.2. InvShiftRows

.3. InvSubBytes

Программа выполняет данные процедуры со всеми блоками исходных данных после чего объединяет их в выходном файле[5].

Подробное описание функций алгоритма дешифрования AES.

Преобразование InvMixColumns

Преобразование InvMixColumns является обратным для преобразования MixColumns и преобразование в этой функции подобно самой функции MixColumns, где каждый столбец умножается на особый многочлен d(x) который определяется:

('03'x^3+'01'x^2+'01'x+'02')Ä d(x)='01',

d(x)='0B'x^3+'0D'x^2+'09'x+'0E'

Преобразование InvShiftRows

Преобразование InvShiftRows является обратным для ShiftRows. В данном случае байты 2,3 и4 ряда сдвигаются в право. Вторая строка (нумерация строк начинается с 0) смещается на 1 байт, в третей строке - на 2 байта, а в четвертой - на 3 байта [6].

Преобразование InvSubBytes

Преобразование InvSubBytes тоже выполняет замену байт но уже с помощью обратной таблицы замен, называемой InvSbox. Обратная таблица замен приведена в Таблице 3.

Таблица 3. Таблица замен InvSbox

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

.1 Недостатки алгоритма DES?

Предшественником алгоритма AES являлся алгоритм DES который разработанный фирмой IBM и утверждённый правительством США в 1977 году как официальный стандарт. Проблемы алгоритма DES начались в 1973 г., когда Национальным бюро стандартов (National Bureau of Standards, NBS, предшественник NIST) были объявлены поиски алгоритма для стандарта DES. Предварительный стандарт было поручено проверить Агентству национальной безопасности (National Security Agency, NSA). Когда компания IBM предложила свой алгоритм шифрования под названием Lucifer в качестве стандарта DES. NSA рекомендовало внести два изменения, которые уже были одобрены NBS.

Одно из изменений, которые предлагали NSA заключалось в изменении размера ключа со 128 как было в Lucifer, до 56 бит. Проблема этого изменения заключалась в том, что в 1977 г. математики Уaйтфилд Диффи и Мapтин Хеллмaн, которыми был разработан алгоритм открытых ключей, который носил название Диффи-Хеллмaнa, объявили, что могут создать машину, которой под силу разгадать все ключи для данного алгоритма.

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

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

К сожалению, уже к 1990 г. Были сильно снижены затраты на машину для взлома DES. После чего в 1997 г. Группа добровольцев смогла взламывать DES в течении длительного времени. На следующий год уже была представлена полноценная машина с возможность взламывать один ключ каждые 5 дней. В итоге было решено заменить алгоритм DES.

2.2 Выбор AES

После демонстрации успешного взлома DES, NIST (Национальный институт стандартов и технологий США) решает заменить этот алгоритм и начинает поиски и анализ нового стандарта. Были опубликованы все данные o тестировании кандидатов на роль AES не относящиеся к секретным и выдвинуты требования авторам алгоритмов сообщить o базовых принципах построения, используемых в них констант, таблиц [2].

На роль AES был представлен 21 кандидат, из них шесть не соответствовали начальным требованиям, 10 были отсеяны уже после первого этапа проверки. В августе 1999 г. было объявлено пять финалистов конкурса на роль AES.

1. MARS

. RC6 (tm)

. Twofish

. Serpent

. Rijndael

Все пять алгоритмов являлись блоковыми шифраторы, у всех предусматривалось проведение нескольких раундов. Основными характеристиками при выборе являлись следующие девять параметров: две касались защиты (общий уровень защиты и защищённость реализации), гибкость, a остальные были направленны на эффективность реализации. В конце итогового тестирования NIST были присвоил оценки финалистам - «отлично», «хорошо» или «удовлетворительно» - по разным критериям. Эти оценки представлены на Рисунке 2 и Рисунке 3 различным числом, от одного до трёх, где один соответствует минимальной оценке, a три - максимальной.

Объективно сравнивать преимущества алгоритмов довольно сложно т.к. финалисты на роль алгоритма AES имеют много общих свойств. Для решения поставленной задачи, была разработана методика по которой проводились исследования алгоритмов шифрования. Один из методов предлагает анализ каждого алгоритма c минимальным числом раундов.

К примеру, при шифровании 128-битным ключом Rijndael выполняет 10 раундов. После проведения анализа уровня защиты Rijndael было выявлено что при выполнении количества раундов меньше восьми стойкость алгоритма была недостаточной. По этой методике так же были проверены остальные участники. По результатам проведенных опытов было обнаружено, что Rijndael для устойчивости к атакам хватает 8 раундов. Специалисты NIST решили, что данный алгоритм обладает достаточным запасом прочности, хотя другие кандидаты имеют даже больший запас прочности.

Для оценки производительности были проведены проверки реализаций как программными, так и аппаратными методами. При проверке реализаций программными методами были рассмотрены реализации на C, Java и смарт-карт на базе ARM, помимо 32 битных реализаций были и 64, так же проверки были проведены на как на 8 разрядных процессорах, так и на процессорах для обработки цифровых сигналов. На Рисунке 2 графически показаны оценки всех финалистов на уровне проверки по программной реализации. При анализе алгоритмов, предназначенных для устройств с ограниченными ресурсами, было использованы: смарт-карты c 8-paзpядным процессором и процессором Motorola 6805, чья оперативная память составляла всего 120 байт.