Алгоритм AES

Введение

Еще некоторое время назад самым распространенным в мире стандартом шифрования являлся DES (Data Encryption Standard). В 1997 году DES ознаменовал наступление новой эпохи в криптографии, получив официальный статус стандарта.
Однако по прошествии времени данный стандарт попал под критику в связи с целым рядом имевшихся недостатков. В первую очередь это было связано со слишком маленькой длиной ключа, которая составляла лишь 56 бит. Несмотря на все нарекания и утверждения о его уязвимости для хакерских атак, до недавнего времени DES выдерживал все нападки. В 1999 году с помощью компьютеров, объединенных в одну сеть, закодированное с помощью DES сообщение было раскрыто методом полного перебора по ключевому пространству. Причем это заняло менее суток.
Было очевидно, что в скором времени данный стандарт окажется несостоятельным. Чтобы решить эту проблему, еще в 1997 году Национальный институт стандартов и измерений NIST объявил конкурс на создание усовершенствованного стандарта шифрования Advanced Encryption Standard (AES), который бы заменил стандарт DES.
Таким образом, в данной работе будут рассмотрены ключевые моменты в истории появления нового стандарта AES, приведен алгоритм работы, а также будут выявлены особенности усовершенствованного стандарта.


1 Историческая справка
Для того алгоритм AES стал новым стандартом его архитектура должна была удовлетворять нескольким критериям: предлагать высокую степень защиты, обладать простой структурой и высокой производительностью.
Конечно, очевидно, что наивысшим приоритетом для нового алгоритма являлась защита. Уже на уровне внутренней архитектуры AES должен обладать надежностью, которой было бы достаточно, чтобы противостоять будущим попыткам хакерских атак. В то же время структура алгоритма должна была быть настолько простой, чтобы гарантировать эффективную процедуру шифрования.
Немаловажным в списке требований, которые предъявлялись к новому стандарту, являлась и его высокая производительность. Под хорошей производительностью предполагалась высокая скорость работы при шифровании и дешифровании, а также при реализации графика ключа [1].
B 1998 году, Национальный институт стандартов и измерений NIST объявил конкурс на создание алгоритма, который бы удовлетворял выдвинутым требованиям:
- Алгоритм должен представлять собой симметричный блочный шифр.
- AES должен быть легко реализуем как программно, так и аппаратно.
- Алгоритм должен работать со 128-разрядными блоками данных и ключами трех размеров (128, 192 и 256 разрядов).
- AES должен ориентироваться на 32-разрядные процессоры.
- Алгоритм должен быть открыто опубликован.
- AES должен распространяться бесплатно или быть общедоступным в рамках патентов ANSI.
К 15 июня 1998 года был заявлен 21 криптоалгоритм, но только 15 из них удовлетворяли всем выдвинутым требованиям. Были представлены следующие алгоритмы: LOKI97 (Australia), RIJNDAEL (Belgium), CAST-256 (Canada), DEAL (Canada), FROG(Costa Rica), DFC (France), MAGENTA (Germany), E2 (Japan), CRYPTON (Korea), HRC (USA), MARS (USA), RC6 (USA), SAFER+ (USA), TWOFISH (USA), SERPENT (UK, Israel, Norway).
В конце августа этого же года в Калифорнии прошла конференция AES1 для отбора кандидатов.
Основными критериями выбора были: криптографическая стойкость, стоимость, а также особенности алгоритма и его реализация.
B апреле 1999 прошла конференция в Риме AES2, в ходе которой проводились исследования предоставленных решений, в том числе связанных c дешифровкой и проверкой производительности, были получены экспертные оценки специалистов по криптографии [2]

.
9 августа 1999 года NIST выпустила пресс-релиз, в котором объявлялись пять финалистов, в число которых вошли MARS, RC6, Rijndael, Serpent, TwoFish. 2 октября 2000 года National Institute of Standards and Technology объявил о своем выборе в пользу стандарта Rijndael (Belgium). Спустя год, в ноябре 2001 года Rijndael стал стандартом США.
2 Advanced Encryption Standard
Advanced Encryption Standard, также известен как Rijndael, является симметричным алгоритмом с блочным шифром. Алгоритм оперирует блоками данных, равных 128 битам, и длиной ключа 128, 192 или 256 бит. Отсюда соответственно название стандарта - «AES-128», «AES-192» и «AES-256».
В рамках данной работы будет рассматриваться «AES-128», для него число 32-битных слов содержащихся во входном блоке (Nb) равняется 4; число 32-битных слов содержащихся в ключе шифрования (Nk) равняется 4, 6, 8; число раундов шифрования, как функция от Nb и Nk (Nr) равняется 10, 12, 14.
Входные (input), промежуточные (state) и выходные (output) результаты преобразований, которые выполняются в рамках криптографического алгоритма, называются состояниями (State). Состояние можно представить в виде матрицы 4x4, элементами которой являются байты. Такое представление носит название архитектуры «Квадрат» (рисунок 1).

Рисунок 1 - Пример представления блока в виде матрицы 4x4
На старте процессов шифрования и дешифрования массив входных данных in0 , in1 ,…, in15 преобразуется в массив State по правилу s[r, c] = in[r + 4c], где 0 ≤ r < 4 и 0 ≤ c < Nb. В конце действия алгоритма выполняется обратное преобразование out[r + 4c] = s[r, c] , где 0 ≤ r < 4 и 0 ≤ c < Nb - выходные данные получаются из байтов состояния в том же порядке [3].
Четыре байта в каждом столбце состояния представляют собой 32-битное слово, если r - номер строки в состоянии, то он одновременно является индексом каждого байта в этом слове. Таким образом, состояние можно представить как одномерный массив 32-битных слов w0 ,…, wNb , где номер столбца состояния c есть индекс в этом массиве. Тогда состояние можно представить следующим образом (рисунок 2).


w0 = s0,0 , s1,0 , s2,0 , s3,0
w2 = s0,2 , s1,2 , s2,2 , s3,2
w1 = s0,1 , s1,1 , s2,1 , s3,1
w3 = s0,3 , s1,3 , s2,3 , s3,3
Рисунок 2 - Состояние
Ключ шифрования также как и массив State представляется в виде прямоугольного массива с четырьмя строками и количеством столбцов равных Nk.
Для алгоритма AES число раундов Nr определяется на старте в зависимости от значения Nk (рисунок 3):


Nk
Nb
Nr
AES – 128
4
4
10
AES – 192
6
4
12
AES - 256
8
4
14
Рисунок 3 - Зависимость значения Nr от Nk и Nb

2.1 Зашифрование
Отдельные трансформации SubBytes(), ShiftRows(), MixColumns(), и AddRoundKey() - обрабатывают State.

Рисунок 4 - Операция зашифрования реализованная на псевдокоде
Операция «SubBytes» - это нелинейное замещение