Алгоритм шифрования AES (Advanced Encryption Standard – улучшенный стандарт шифрования) в настоящее время является стандартом блочного симметричного шифрования США. Данная статья посвящена истории появления стандарта AES, описанию алгоритма шифрования, лежащего в его основе, а также различным криптоаналитическим исследованиям этого алгоритма.

Конкурс AES

В отличие от многих других криптографических стандартов (например, предыдущего стандарта шифрования США DES [4] или отечественного стандарта ГОСТ 28147-89 [9]), AES не был разработан «в недрах спецслужб», а выбран на открытом конкурсе из относительно большого числа алгоритмов-претендентов.
До принятия в качестве стандарта алгоритма AES в данном качестве использовался алгоритм DES (Data Encryption Standard – стандарт шифрования данных). Несмотря на множество найденных криптоаналитических методов, применимых к DES (подробно о алгоритме DES и его криптоанализе см. [10]), фактически, не было обнаружено каких-либо серьезных уязвимостей в данном алгоритме, за исключением одного, но весьма принципиального недостатка: весьма короткого ключа, реальный размер которого составляет всего 56 бит. Насколько это мало, можно судить из следующей весьма распространенной оценки: для полного перебора ключей DES достаточно примерно 20 часов работы миллиона процессоров, каждый из которых перебирает миллион ключей DES в секунду [8]. Ясно, что такой стойкости против вскрытия алгоритма методом «грубой силы» (см. часть 2 статьи «Современные методы вскрытия алгоритмов шифрования»)  категорически недостаточно. Тем не менее, DES оставался стандартом шифрования до начала XXI века.

В 1997 году Институт Стандартов и Технологий США (NIST – National Institute of Standards and Technology) объявил о проведении конкурса по замене стандарта DES. На конкурс могли быть присланы алгоритмы шифрования, разработанные как организациями, так и частными лицами в любой стране. Алгоритм-победитель этого конкурса должен был стать новым стандартом блочного симметричного шифрования США.

Для участия в конкурсе (которому было присвоено название AES) алгоритм шифрования должен был соответствовать всего двум обязательным требованиям [2]:

·         128-битный размер блока шифруемых данных,

·         не менее трех поддерживаемых алгоритмом размеров ключей шифрования: 128, 192 и 256 бит.

Кроме того, NIST в [2] предъявил большое число требований, носивших рекомендательный характер. Именно по соответствию этим требованиям, фактически, и был выбран алгоритм-победитель конкурса. Рекомендации NIST были таковы:

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

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

3.     Должны отсутствовать слабые и эквивалентные ключи (т.е. ключи, являющиеся различными, но приводящие к одному и тому же результату шифрования).

4.     Скорость шифрования данных должна быть высокой на всех потенциальных аппаратных платформах – от 8-битных до 64-битных.

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

6.     Алгоритм должен предъявлять минимальные требования к оперативной и энергонезависимой памяти.

7.     Не должно быть ограничений для использования алгоритма; в частности, алгоритм не должен ограничивать свое использование в различных стандартных режимах работы (см. [5]), в качестве основы для построения хэш-функций, генераторов псевдослучайных последовательностей и т.д.

В конкурсе AES приняли участие 15 алгоритмов шифрования [1, 7]:

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

·         всемирно известных криптологов, например, «звездный» коллектив авторов алгоритма Twofish;

·         организации, давно работающие в данной области и обладающие как богатым опытом разработки криптоалгоритмов, так и сильнейшими специалистами в данной области, например, американская фирма RSA – автор алгоритма RC6;

·         всемирно известные корпорации, обладающие большим научным потенциалом, например японский телекоммуникационный гигант NTT с алгоритмом E2;

·         образовательные учреждения, известные своими достижениями в области криптографии, например Ecole Normale Superieure (Париж, Франция) с алгоритмом DFC;

·         и наоборот, организации, весьма малоизвестные до проведения конкурса AES, например, фирма Tecnologia Apropriada (автор алгоритма FROG) из латиноамериканского государства Коста-Рика.

Анализ алгоритмов-претендентов проводился как специалистами института NIST, так и различными независимыми экспертами – на конкурс было прислано множество материалов, посвященных участвовавшим в конкурсе алгоритмам; все эти материалы можно найти на сайте института NIST http://csrc.nist.gov. По результатам анализа, как видно из приведенной выше таблицы, во второй раунд конкурса вышли следующие 5 алгоритмов: MARS, RC6, Rijndael, Serpent и Twofish.

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

Подробное описание алгоритмов MARS, RC6, Serpent и Twofish можно найти в статье [11]. Здесь же подробно рассмотрим алгоритм шифрования Rijndael, которому (как победителю конкурса) было присвоено название AES.

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

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

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

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

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

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

Рис. 2.        Операция SubBytes.

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

1.1.      Вычисление мультипликативной обратной величины от входного значения в конечном поле GF(2⁸); обратной величиной от 0 является 0.

1.2.      Выходное значение b вычисляется следующим образом:

b_i = a_i Å a_{i + 4 mod 8} Å a_{i+5 mod 8} Å a_{i+6 mod 8} Å a_{i+7 mod 8} Å c_i,

где n_i обозначает i-й бит величины n,

a – результат предыдущей операции,

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

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

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

a(x) = 3x³ + x² + x + 2.

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

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

Количество раундов алгоритма R зависит от размера ключа следующим образом:

Перед первым раундом алгоритма выполняется предварительное наложение материала ключа с помощью операции AddRoundKey, которая выполняет наложение на открытый текст первых четырех слов расширенного ключа W₀…W₃.

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

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

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

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

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

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

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

Расширение ключа выполняется в два этапа, на первом из которых производится инициализация слов расширенного ключа (обозначаемых как W_i): первые Nk (Nk – размер исходного ключа шифрования K в словах, т.е. 4, 6 или 8) слов W_i (т.е. i = 0…Nk-1) формируются их последовательным заполнением байтами ключа (см. рис. 6).

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

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

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

T = W_i-1.

Шаг 2.           Данная переменная модифицируется следующим образом:

a.     если i кратно Nk, то:

T = SubWord(RotWord(T)) Å RC_ëi/Nkû;

операции SubWord, RotWord будут описаны ниже, а константы RC_n представляют собой слова, в которых все байты, кроме первого являются нулевыми, а первый байт имеет значение 2^n-1 mod 256;

b.     если Nk = 8 и (i mod Nk) = 4, то:

T = SubWord(T);

c.     в остальных случаях модификация переменной T не выполняется.

Шаг 3.           Формируется i-е слово расширенного ключа:

W_i = W_i-Nk Å T.

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

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

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

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

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

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

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

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

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

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

Данную табличную замену можно выполнить, применив к входному байту преобразование, обратное операции 1.2 (см. описание операции SubBytes), после чего вычислить мультипликативную обратную величину от результата предыдущей операции в конечном поле GF(2⁸).

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

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

a^-1(x) = Bx³ + Dx² + 9x + E.

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

Отличия AES от исходного алгоритма Rijndael

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

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

2.     Количество раундов R алгоритма Rijndael определяется следующей таблицей в зависимости не только от размера ключа, но и от размера блока:

3.     Количество бит сдвига строк таблицы также зависит от размера блока:

4.     Поскольку для 192- и 256-битного блоков увеличивается количество столбцов массива данных до 6 и 8 соответственно, в операции AddRoundKey участвуют уже 6 или 8 слов расширенного ключа вместо четырех. Следовательно, в r-м раунде алгоритма выполняется наложение слов расширенного ключа W_Nb*r…W_Nb*r+3, где Nb – количество столбцов массива данных.

5.     В связи с вышесказанным, изменяется и процедура расширения ключа, однако, изменение состоит лишь в том, что данная процедура должна выработать Nb*(R+1)-1 слов расширенного ключа, а не 4*(R+1)-1 (что, впрочем, остается справедливым для 128-битного блока).

Вторая часть статьи будет посвящена криптоаналитическим исследованиям алгоритма AES.

1.          AES Round 1 Information. // http://csrc.nist.gov – January 26, 2001.

2.          Announcing Request for Candidate Algorithm Nominations for the Advanced Encryption Standard (AES). // http://csrc.nist.gov – Department of Commerce – National Institute of Standards and Technology – Federal Register: September 12, 1997.

3.          Daemen J., Rijmen V. AES Proposal: Rijndael. // http://csrc.nist.gov – Document version 2 – 03/09/99.

4.          FIPS 46-3. Data Encryption Standard (DES). // http://csrc.nist.gov – Reaffirmed 1999 October 25.

5.          FIPS 81. DES Modes of Operation. // http://csrc.nist.gov – 1980 December 2.

6.          FIPS Publication 197. Specification for the Advanced Encryption Standard. // http://csrc.nist.gov – November 26, 2001.

7.          Nechvatal J., Barker E., Dodson D., Dworkin M., Foti J., Roback E. Status report on the first round of the development of the advanced encryption standard. // http://csrc.nist.gov – National Institute of Standards and Technology.

8.          Брассар Ж. Современная криптология. – Пер. с англ.: М.: Полимед, 1999 – 176 с.

9.          ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. – М.: Госстандарт СССР, 1989.

10.       Панасенко С. Алгоритм шифрования DES и его варианты. // Connect! Мир связи. – 2006 - №№ 3-6.

11.       Панасенко С. Алгоритмы шифрования – финалисты конкурса AES. // iXBT – http://www.ixbt.com – 2006.

Об авторе:

Панасенко Сергей Петрович, нач. отдела разработки программного обеспечения фирмы АНКАД, кандидат технических наук.

С автором можно связаться:      по телефонам (495)532-1313, (495)531-0000

или по E-mail develop@ancud.ru

http://www.panasenko.ru