Алгоритм AES (Rijndael)

Название AES присвоено алгоритму Rijndael — победителю конкурса AES.

 

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

 

Алгоритм AES представляет блок данных в виде двумерного байтового мас­сива размером 4×4. Все операции производятся над отдельными байтами массива, а также над независимыми столбцами и строками.

 

В каждом раунде алгоритма выполняются следующие преобразования (рис. 3.7) [132, 153]:

 

1. Операция SubBytes, представляющая собой табличную замену каждого байта массива данных согласно табл. 3.1 (рис. 3.8).

 

clip_image002

Таблица3.1

aes1

Таблица меняет входное значение 0 на 63 (шестнадцатеричное значение), 1 — на 7С, 2 на 77 и т. д.

 

Вместо данной табличной замены можно выполнить эквивалентную ей комбинацию двух операций:

 

• вычисление мультипликативной обратной величины от входного зна-

 

о

 

чения в конечном поле GF( 2 ); обратной величиной от 0 является 0;

 

• выходное значение Ъ вычисляется следующим образом:

 

Ъ{ =ai[+]ai+4m^[+]ai+5mo6S[+]ai+6mo6S[+]ai+7modS[+]ch

 

где:

 

0   niобозначает /-й бит величины п\

 

0 a— результат предыдущей операции;

 

0 с — шестнадцатеричная константа 63.

 

2. Операция ShiftRows, которая выполняет циклический сдвиг влево всех строк массива данных, за исключением нулевой (рис. 3.9). Сдвиг /-й стро­ки массива (дляi= 1,2,3) производится на / байтов.

 

clip_image004

Рис. 3.9. Операция ShiftRows

 

clip_image006

Рис. 3.10. Операция MixColumns

 

3. Операция MixColumns. Выполняет умножение каждого столбца массива данных (рис. 3.10), который рассматривается как полином в конечном поле GF(28), на фиксированный полином а(х):

 

а(х) = 3+ х2 + х + 2.

 

Умножение выполняется по модулю х4+ 1.

 

4. Операция AddRoundKey. Выполняет наложение на массив данных мате­риала ключа. А именно, на /-й столбец массива данных (/ = 0…3) побито­вой логической операцией «исключающее или» (XOR) накладывается оп­ределенное слово расширенного ключа W4r+i, где г— номер текущего раунда алгоритма, начиная с 1 (процедура расширения ключа будет опи­сана далее). Операция AddRoundKey представлена на рис. 3.11.

 

clip_image008

Рис. 3.11. Операция AddRoundKey

 

Зависимость количества раундов алгоритма Rот размера ключа приведена в табл. 3.2.

 

Таблица 3.2

 

Размер ключа в битах

 

Количество раундов

 

128

 

10

 

192

 

12

 

256

 

14

 

Перед первым раундом алгоритма выполняется предварительное наложение ма­териала ключа с помощью операции AddRoundKey, которая производит наложе­ние на открытый текст первых четырех слов расширенного ключа 1У0…1У3.

 

Последний же раунд отличается от предыдущих тем, что в нем не выполня­ется операция MixColumns.

 

Процедура расширения ключа

 

Алгоритм AES использует ключи шифрования трех фиксированных разме­ров: 128, 192 и 256 битов. В зависимости от размера ключа конкретный вари­ант алгоритма AES может обозначаться как AES-128, AES-192 и AES-256 соответственно [153].

 

Задача процедуры расширения ключа состоит в формировании нужного ко­личества слов расширенного ключа для их использования в операции AddRoundKey. Как было сказано выше, под «словом» здесь понимается 4-байтный фрагмент расширенного ключа, один из которых используется в первичном наложении материала ключа и по одному — в каждом раунде алгоритма. Таким образом, в процессе расширения ключа формируется 4*(/? + 1) слов.

 

Расширение ключа выполняется в два этапа, на первом из которых произво­дится инициализация слов расширенного ключа (обозначаемых как \У,): первые Nk(Nk— размер исходного ключа шифрования К в словах, т. е. 4, 6 или 8) слов W{, т.е. / = 0…(М; -1), формируются их последовательным за­полнением байтами ключа (рис. 3.12).

 

clip_image010

Рис. 3.12. Инициализация первых слов расширенного ключа

 

Последующие слова W(формируются такой последовательностью операций для каждого i= Nk…(A* (R+1) -1):

 

1. Инициализируется временная переменная Т:

 

T= Wi_i.

 

2. Эта переменная модифицируется таким образом: • если iкратно Nk, то:

 

Т = SubWord(RotWord(T)) [+] RCi/Nk;

 

операции SubWord и RotWord будут описаны далее, а константы RCnпредставляют собой слова, в которых все байты, кроме первого, являются нулевыми, а первый байт имеет значение 2n~xmod 256;

 

• если Nk= Sи (imodNk) = 4 , то:

 

Т = SubWord(T)\

 

• в остальных случаях модификация переменной Г не выполняется. 3. Формируется /-е слово расширенного ключа:

 

Операция SubWord выполняет над каждым байтом входного значения таб­личную замену, которая была описана выше — см. операцию SubBytes.

 

Операция RotWord побайтно вращает входное слово на 1 байт влево.

 

Как видно, процедура расширения ключа является достаточно простой по сравнению со многими другими современными алгоритмами шифрования. Процедура расширения ключа имеет также несомненное достоинство в том, что расширение ключа может быть выполнено «на лету» (onthefly), т. е. па­раллельно с зашифровыванием данных.

 

Авторы алгоритма в [132] пишут также, что не следует задавать напрямую расширенный ключ — программная или аппаратная реализация алгоритма должна именно получать исходный ключ шифрования К и выполнять про­цедуру расширения ключа. Здесь стоит снова вспомнить алгоритм DES — известно, что DES с независимо задаваемыми ключами раундов оказался слабее против некоторых атак, чем исходный алгоритм DES(см. разд. 3.15).

 

Расшифровывание

 

Расшифровывание выполняется применением обратных операций в обратной последовательности. Соответственно, перед первым раундом расшифровы­вания выполняется операция AddRoundKey (которая является обратной са­мой себе), накладывающая на шифртекст четыре последних слова расширен­ного ключа, т. е. W4RW4R+3.

 

Затем выполняется Rраундов расшифровывания, каждый из которых осуще­ствляет следующие преобразования (рис. 3.13):

 

1. Операция InvShiftRows производит циклический сдвиг вправо трех по­следних строк массива данных на то же количество байтов, на которое выполнялся сдвиг операцией ShiftRows при зашифровывании.

 

2. Операция InvSubBytes производит побайтно обратную табличную замену, которая приведена в табл. 3.3.

 

clip_image012

Рис. 3.13. Раунд расшифровывания

 

Таблица 3.3

 aes2

Такую табличную замену можно выполнить, применив к входному байту преобразование, обратное второму действию альтернативной операции SubBytes (см. описание SubBytes), после чего вычислить мультипликатив­ную обратную величину от результата предыдущей операции в конечном полеОР(28).

 

3. Операция AddRoundKey, как и при зашифровывании, выполняет наложе­ние на обрабатываемые данные четырех слов расширенного ключа W4rW4r+3. Однако нумерация раундов г при расшифровывании произво­дится в обратную сторону — от (R-1) до 0.

 

4. Операция InvMixColumns выполняет умножение каждого столбца массива данных аналогично прямой операции MixColumns, однако, умножение производится на полином a~l(x), определенный следующим образом:

 

а~] (х) = Вх3 + Dx2 +9х + Е.

 

Аналогично зашифровыванию, последний раунд расшифровывания не со­держит операцию InvMixColumns.

 

Отличия AES

 

от исходного алгоритма Rijndael

 

Алгоритм Rijndael позволяет шифровать данные не только 128-битными бло­ками, но и блоками по 192 или 256 битов. Таким образом, алгоритм AES, фактически, имеет лишь одно принципиальное отличие от Rijndael: он пре­дусматривает использование только 128-битных блоков данных. Рассмотрим изменения в приведенном выше описании алгоритма AES, связанные с дру­гими размерами блоков.

 

□ Обрабатываемые данные могут представляться не только в виде массива размером 4 х 4, но и 4 х 6 или 4×8 для 192- и 256-битных блоков соответ­ственно.

 

□ Количество раундов Rалгоритма Rijndael определяется табл. 3.4 в зависи­мости не только от размера ключа, но и от размера блока.

 

Таблица 3.4

 

<><>

 

</> </>

128

 

Размер ключа в битах

 

Размер блока в битах

 

192

 

256

 

128

 

10

 

12

 

14

 

192

 

12

 

12

 

14

 

256

 

14

 

14

 

14

 

□ Количество битов сдвига строк таблицы также зависит от размера блока (табл. 3.5).

[Более подробно об реализации алгоритма AES]

 

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

6 коммент. »

 
  • Сергей says:

    Чем дополняется последний блок файла до 128 битного значения?
    Существует ли стандарт “отбрасывания” лишних байтов, которые получаются при шифровании файлов, размер которых не кратен 128 битам?

  • Toma says:

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

  • Михаил says:

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

  • Михаил says:

    извиняюсь, предыдущий пост этот символ как раз не отобразил

    слэш ноль (\ 0)

  • Rasomaha says:

    Что-то я не догнал. То ли я дурак, то ли реально в статье ошибка. 1C в таблице что в 3.1 что в 3.3 повторяется 2 раза, а вот в самой статье оговаривается что 1 байт заменяется на 7C, а не 1C (по таблице 3.1).

  • Toma says:

    Все правильно в таблице “опечатка”, спасибо за внимательность. Таблицы заменил, в конце статьи ссылка на хорошее описание реализации AES. Извините за неудобства.

 

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100