AES (Advanced Encryption Standard)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 01:25, 12 июня 2016.
(перенаправлено с «AES»)

Advanced Encryption Standard- AES. Американский стандарт, опубликованный в 2001 году. В современный криптографических подуктах, наверно, не найдется таких, которые бы не использовали AES. Используется в WI-FI, WinRAR, PGP. DES- предшественник AES.

AES - симметричный алгоритм блочного шифрования (размер блока 128 бит, ключ 128/192/256 бит), принятый в качестве стандарта шифрования правительством США по результатам конкурса AES.

Структура алгоритма шифрования

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

Рис. 1 Схема раунда шифрования

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

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

Рис. 2 SubBytes

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

Рис. 3 ShiftRows

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

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

Рис. 4 MixColumns

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

Рис. 5 AddRoundKey

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

Размер ключа, бит R
128 10
192 12
256 14

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

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

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

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

1. Операция InvShiftRows выполняет циклический сдвиг вправо трех последних строк массива данных на то же количество байт, на которое выполнялся сдвиг операцией ShiftRows при зашифровании.
2. Операция InvSubBytes выполняет побайтно обратную табличную замену
3. Операция AddRoundKey, как и при зашифровании, выполняет наложение на обрабатываемые данные четырех слов расширенного ключа . Однако, нумерация раундов при расшифровании производится в обратную сторону – от до .
4. Операция InvMixColumns выполняет умножение каждого столбца массива данных аналогично прямой операции MixColumns, однако, умножение производится на полином , определенный следующим образом:
.
Аналогично зашифрованию, последний раунд расшифрования не содержит операцию InvMixColumns.

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

AES использует ключи шифрования трех фиксированных размеров: 128, 192, и 256 бит. В зависимости от размера ключа, конкретный вариант алгоритма AES может обозначаться как AES-128, AES-192 и AES-256 соответственно .
Задача процедуры расширения ключа состоит в формировании нужного количество слов расширенного ключа для их использования в операции AddRoundKey. Как было сказано выше, под «словом» здесь понимается 4-байтный фрагмент расширенного ключа, один из которых используется в первичном наложении материала ключа и по одному – в каждом раунде алгоритма. Таким образом, в процессе расширения ключа формируется слов.
Расширение ключа выполняется в два этапа, на первом из которых производится инициализация слов расширенного ключа (обозначаемых как ): первые ( – размер исходного ключа шифрования в словах, т.е. 4, 6 или 8) слов (т.е. ) формируются их последовательным заполнением байтами ключа (см. рис. 7).

Рис. 7 Инициализация расширенного ключа

Последующие слова формируются следующей последовательностью операций для каждого :
Шаг 1. Инициализируется временная переменная  :
.
Шаг 2. Данная переменная модифицируется следующим образом:
a. если кратно , то:
;
константы представляют собой слова, в которых все байты, кроме первого являются нулевыми, а первый байт имеет значение ;
b. если и , то:
;
c. в остальных случаях модификация переменной не выполняется.
Шаг 3. Формируется -е слово расширенного ключа:
.
Операция SubWord выполняет над каждым байтом входного значения табличную замену, которая была описана выше – см. операцию SubBytes.
Операция RotWord побайтно вращает входное слово на 1 байт влево.
Как видно, процедура расширения ключа является достаточно простой по сравнению со многими другими современными алгоритмами шифрования. Процедура расширения ключа имеет также несомненное достоинство в том, что расширение ключа может быть выполнено «на лету» (on-the-fly), т.е. параллельно с зашифрованием данных.

AES - История создания

В 1997 году был объявлен конкурс на алгоритм AES. Инициатор конкурса NIST(National Institute of Standarts). 1997г.-открытие;

1998г.- раунд 1(15 алгоритмов);

1999г.- раунд 2(5 алгоритмов);

2000г.- финал(1 алгоритм).

К кандидатам предъявлялись следующие требования:

  • должен быть блочный шифр;
  • размер блока 128 бит;
  • размер ключа 128 бит(затем 192/256);
  • эффективная програмная и аппаратная реализация;
  • возможность эффективной реализации на 32-х разрядных CPU;
  • простота архитектуры;
  • отсутствие ограничений на использование;

5 алгоритмов, дошедших до финала:

RC6, Twofish, Serpent, MARS, Rijndael. Все алгоитмы были достойными,но победил Rijndael.

Авторы: Vincent Rijmen, Joan Daemon.

AES первый алгоритм, не реализованный как Сеть Фейстеля.

Описание AES

  • block-последовательность бит(128),
  • key-ключ(128/196/256),
  • Key Expansion- процедура выработки подключей,
  • S-box- нелинейная таблица замен.

Шифрование производится за R раундов.

(R-1) раунды:

AddRoundKey(x,k)
SubBytes(x)
ShiftRows(x)
МixColumns(x)
AddRoundKey(x)

R-й раунд:

AddRoundKey(x,k)
SubBytes(x)
ShiftRows(x)
AddRoundKey(x)

В процедуре AddRoundKey ключ из каждого раунда, выработанный процедурой Key Expansion, объединяется с X.

Процедура SubBytes() обрабатывает каждый байт состояния, независимо производя нелинейную замену байтов используя таблицу замен(S-box).

ShiftRows работает со строками X. При этой трансформации строки состояния циклически сдвигаются влево на r байт по горизонтали, в зависимости от номера строки. Для нулевой строки r = 0, для первой строки r = 1Б и тд.

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

Определения и вспомогательные процедуры

Определения
Block последовательность бит, из которых состоит input, output, State и Round Key. Также под Block можно понимать последовательность байт
Cipher Key секретный, криптографический ключ, который используется Key Expansion процедурой, чтобы произвести набор ключей для раундов(Round Keys); может быть представлен как прямоугольный массив байтов, имеющий четыре строки и Nk колонок.
Ciphertext выходные данные алгоритма шифрования
Key Expansion процедура используемая для генерации Round Keys из Cipher Key
Round Key Round Keys получаются из Cipher Key используя процедуру Key Expansion. Они применяются к State при шифровании и расшифровании
State промежуточный результат шифрования, который может быть представлен как прямоугольный массив байтов имеющий 4 строки и Nb колонок
S-box нелинейная таблица замен, использующаяся в нескольких трансформациях замены байт и в процедуре Key Expansion для взаимнооднозначной замены значения байта
Nb число столбцов(32-ух битных слов), составляющих State. Для, AES Nb = 4
Nk число 32-ух битных слов, составляющих шифроключ. Для AES, Nk = 4,6, или 8
Nr число раундов, которое является функцией Nk и Nb. Для AES, Nr = 10, 12, 14
Rcon[] массив, который состоит из битов 32-х разрядного слова и является постоянным для данного раунда
Вспомогательные процедуры
AddRoundKey()  трансформация при шифровании и обратном шифровании, при которой Round Key XOR’ится c State. Длина RoundKey равна размеру State(те, если Nb = 4, то длина RoundKey равна 128 бит или 16 байт)
InvMixColumns() трансформация при расшифровании которая является обратной по отношению к MixColumns()
InvShiftRows() трансформация при расшифровании которая является обратной по отношению к ShiftRows()
InvSubBytes() трансформация при расшифровании которая является обратной по отношению к SubBytes()
MixColumns() трансформация при шифровании которая берет все столбцы State и смешивает их данные (независимо друг от друга), чтобы получить новые столбцы
RotWord() функция, использующаяся в процедуре Key Expansion, которая берет 4-х байтное слово и производит над ним циклическую перестановку
ShiftRows() трансформации при шифровании, которые обрабатывают State, циклически смещая последние три строки State на разные величины
SubBytes() трансформации при шифровании которые обрабатывают State используя нелинейную таблицу замещения байтов(S-box), применяя её независимо к каждому байту State
SubWord() функция, используемая в процедуре Key Expansion, которая берет на входе четырёх-байтное слово и применяя S-box к каждому из четырёх байтов выдаёт выходное слово

Шифрование

AES является стандартом, основанным на алгоритме Rijndael. Для AES длина input(блока входных данных) и State(состояния) постоянна и равна 128 бит, а длина шифроключа K составляет 128, 192, или 256 бит. При этом, исходный алгоритм Rijndael допускает длину ключа и размер блока от 128 до 256 бит с шагом в 32 бита. Для обозначения выбранных длин input, State и Cipher Key в байтах используется нотация Nb = 4 для input и State, Nk = 4, 6, 8 для Cipher Key соответственно для разных длин ключей.

В начале шифрования input копируется в массив State по правилу , для и . После этого к State применяется процедура AddRoundKey() и затем State проходит через процедуру трансформации(раунд) 10, 12, или 14 раз(в зависимости от длины ключа), при этом надо учесть, что последний раунд несколько отличается от предыдущих. В итоге, после завершения последнего раунда трансформации, State копируется в output по правилу , для и .

Отдельные трансформации SubBytes(), ShiftRows(), MixColumns(), и AddRoundKey() — обрабатывают State. Массив w[] — содержит key schedule.


Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
begin
    byte state[4,Nb]
    
    state = in

    AddRoundKey(state, w[0, Nb-1])

    for round = 1 step 1 to Nr-1
        SubBytes(state)
        ShiftRows(state)
        MixColumns(state)
        AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])
    end for

    SubBytes(state)
    ShiftRows(state)
    AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])

    out = state
end

Рис1. Псевдокод для Cipher

SubBytes()

Процедура SubBytes() обрабатывает каждый байт состояния, независимо производя нелинейную замену байтов используя таблицу замен(S-box). Такая операция обеспечивает нелинейность алгоритма шифрования. Построение S-box состоит из двух шагов. Во-первых, производится взятие обратного числа в . Во-вторых, к каждому байту b из которых состоит S-box применяется следующая операция: , где , и где bi есть i-ый бит b, а ci — i-ый бит c = {63} или {01100011}. Таким образом, обеспечивается защита от атак, основанных на простых алгебраических свойствах.

ShiftRows()

ShiftRows работает со строками State. При этой трансформации строки состояния циклически сдвигаются на r байт по горизонтали, в зависимости от номера строки. Для нулевой строки r = 0, для первой строки r = 1Б и тд.. Таким образом каждая колонка выходного состояния после применения процедуры ShiftRows состоит из байтов из каждой колонки начального состояния. Для алгоритма Rijndael паттерн смещения строк для 128 и 192-ух битных строк одинаков. Однако для блока размером 256 бит отличается от предыдущих тем, что 2, 3, и 4-е строки смещаются на 1, 3, и 4 байта соответственно.

MixColumns()

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

AddRoundKey()

В процедуре AddRoundKey, RoundKey каждого раунда объединяется со State. Для каждого раунда Roundkey получается из CipherKey используя процедуру KeyExpansion; каждый RoundKey такого же размера, что и State. Процедура производит побитовый XOR каждого байта State с каждым байтом RoundKey .

KeyExpansion()

AES алгоритм, используя процедуру KeyExpansion() и подавая в неё Cipher Key, K, получает ключи для всех раундов. Всего она получает Nb*(Nr + 1) слов: изначально для алгоритма требуется набор из Nb слов, и каждому из Nr раундов требуется Nb ключевых набора данных. Полученный массив ключей для раундов обозначается как , . Алгоритм KeyExpansion() показан в псевдо коде ниже.

Функция SubWord() берет четырёхбайтовое входное слово и применяет S-box к каждому из четырёх байтов то, что получилось подается на выход. На вход RotWord() подается слово которое она циклически переставляет и возвращает . Массив слов, слов постоянный для данного раунда, , содержит значения , где x = {02}, а является степенью в ( начинается с 1).

Первые слов расширенного ключа заполненны Cipher Key. В каждое последующее слово, , кладётся значение полученное при операции XOR и , те XOR’а предыдущего и на Nk позиций раньше слов. Для слов, позиция которых кратна Nk, перед XOR’ом к w[i-1] применяется трасформация, за которой следует XOR с константой раунда Rcon[i]. Указанная выше трансформация состоит из циклического сдвига байтов в слове(RotWord()), за которой следует процедура SubWord() — то же самое, что и SubBytes(), только входные и входные данные будут размером в слово.

Важно заметить, что процедура KeyExpansion() для 256 битного Cipher Key немного отличается от тех, которые применяются для 128 и 192 битных шифроключей. Если и кратно , то SubWord() применяется к до XOR’а.

KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk)
begin
    word temp
    i = 0;
    
    while ( i < Nk)
        w[i] = word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3])
        i = i+1
    end while
    
    i = Nk

    while ( i < Nb * (Nr+1))
        temp = w[i-1]
        if (i mod Nk = 0)
            temp = SubWord(RotWord(temp)) xor Rcon[i/Nk]
        else if (Nk > 6 and i mod Nk = 4)
            temp = SubWord(temp)
        end if
        w[i] = w[i-Nk] xor temp
        i = i + 1
    end while
end
Псевдокод для Key Expansion

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


InvCipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
begin
    byte state[4,Nb]
    
    state = in

    AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])

    for round = Nr-1 step -1 downto 1
        InvShiftRows(state)
        InvSubBytes(state)
        InvAddRoundKey(state, w[round*Nb, (round+1)*Nb-1])
        InvMixColumns(state)
    end for

    InvShiftRows(state)
    InvSubBytes(state)
    InvAddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])

    out = state
end

Псевдокод для Inverse Cipher

Варианты алгоритма

На базе алгоритма Rijndael, лежащего в основе AES, реализованы альтернативные криптоалгоритмы. Среди наиболее известных — участники конкурса Nessie: Anubis на инволюциях, автором которого является Винсент Рэймен и усиленный вариант шифра — Grand Cru Йохана Борста.