Алгоритм шифрування aes

Семенов Ю.А. (ІТЕФ-МФТІ)
Yu. Semenov (ITEP-MIPT)

Біти даних нумеруються з нуля, починаючи зі старших. В AES основним є поліноміальний поданням кодів. Так байт слід представляти як: x 6 + x 5 + x + 1.

Алгоритм AES виробляє операції над двовимірними масивами байт, званими структурами (state). Структура складається з 4 рядів по Nb байт. Nb дорівнює довжині блоку, поділеній на 32 (в даному стандарті Nb = 4). Це дозволяє позначати структуру як sr, c або s [r, c], де 0≤r<4 и 0≤с<4..

Вхідний код (in), який є послідовністю 16 байт можна уявити як:

При реалізації алгоритму AES використовуються операції додавання байт (по модулю 2 = XOR) і множення. В алгоритмі AES при множенні байтів використовується не приводиться многочлен:

m (x) = x 8 + x 4 + x 3 + x + 1

Обчислення твори М байтів на тут виконується відповідно до наступного алгоритму:

В цьому випадку зворотна величина байта дорівнює:

для множення напівбайтів (коди довжиною 4 біта) використовується не приводиться поліном:

Обчислення твори М напівбайтів на тут виконується наступним чином:

M являє собою напівбайт d. Операцію множення напівбайтів на можна записати в матричному вигляді:

Як було сказано вище довжини ключів Nk (довжина, виміряна в 32 бітових словах) можуть приймати значення 4, 6 або 8 (для AES-128, -192 і -256, відповідно). Число ітерацій Nr (round), що реалізуються в алгоритмі AES, становить відповідно 10, 12 і 14.

шифрування

При запуску алгоритму шифрування вхідний блок даних копіюється в масив state. Після початкового додавання до state ключа масив state перетворюється за допомогою функції циклічної обробки Nr раз (останній цикл дещо відрізняється від попередніх, див. Рис. 19.3). Результат перетворення заноситься в вихідний масив.

Опис алгоритму в С-подібному представленні відображено на рис. 1. Перетворення SubByte (), ShiftRows (), MixColumns () і AddRoundKey () здійснюють обробку масиву state. Масив w [i] описаний нижче.

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. Псевдокод, який реалізує процедуру шифрування

Перетворення SubByte ()

Перетворення SubByte () є нелінійної підстановкою байтів, яке працює незалежно для кожного байта State і використовує таблицю підстановок S. Ця заміна включає в себе дві операції:

Кожен байт замінюється на зворотний мультиплікативний (див. Формулу 3). Байт перетворюється сам у себе.
Для кожного байта здійснюється Афінний перетворення в поле GF (2), що задається формулою

Перетворення ShiftRows ()

У перетвореннях ShiftRows () байти в останніх трьох рядах State циклічно зсуваються на різну кількість байт. Перший ряд (r = 0) не зрушується. Перетворення ShiftRows () здійснюється наступним чином:

для 0

де величина зсуву shift (r, Nb) залежить від номера ряду r наступним чином:

shift (1,4) = 1; shift (2,4) = 2; shift (3,4) = 3

Перетворення MixColumns ()

Перетворення MixColumns () обробляє State колонка за колонкою, кожна з колонок є 4-бітний код. Колонки розглядаються як поліноми над полем GF (2 8). Колонка множиться на фіксований поліном = x 3 + x 2 + x + по модулю x 4 +1 (див. Формулу 2а).

Перетворення AddRoundKey ()

У перетворенні AddRoundKey () до State додається ключ ітерації (Round Key; побітова операція XOR). Операція проводиться для кожного байта State.

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

Ключі ітерації обчислюються на основі ключа шифрування за допомогою процедури перетворення ключа (Key expansion). Ця процедура формує Nb (Nr + 1) слів. Алгоритм вимагає Nb слів і кожна з Nr ітерацій вимагає Nb слів. В результаті виходить лінійний масив 4-байтових слів, який позначається [wi]. де i лежить в межах 0? i

KeyExpansion (byte key [4 * Nk], word w [Nb * (Nr + 1)], Nk)
begin
word temp
i = 0
while (i 6 and i mod Nk = 4)
temp = SubWord (temp)
end if
w [i] = w [i-Nk] xor temp
i = i + 1
end while
end
end

Мал. 2. Псевдокод реалізації процедури перетворення ключа

розшифровка

Всі процедури, описані в попередньому розділі, є оборотними. Метою дешифрування є обробка зашифрованого масиву даних з метою отримання вихідного блоку даних. Процедури дешифрування включають в себе функції InvShiftRows (), InvSubBytes (), InvMixColumns () і AddRoundKey (). Псевдокод для процедури дешифрування представлений на рис. 3.

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)
AddRoundKey (state, w [round * Nb, (round + 1) * Nb-1])
InvMixColumns (state)

end for
InvShiftRows (state)
InvSubBytes (state)
AddRoundKey (state, w [0, Nb-1])
out = state
end

Мал. 3. Псевдокод процедури дешифрування

Перетворення InvShiftRows ()

Процедура InvShiftRows () є зворотною по відношенню ShiftRows (). Байти в останніх трьох рядах State циклічно зсуваються на різну кількість байт. Перший ряд (r = 0) не зрушується.

Перетворення InvSubBytes ()

Перетворення InvSubBytes () є зворотною підстановкою байт, в якій S-таблиця послідовно застосовується для кожного з байтів State. Це досягається за рахунок зворотного афінної перетворення.

Перетворення InvMixColumns ()

Процедура InvMixColumns () є зворотною по відношенню MixColumns () (див. Розділ 1.3). Колонки розглядаються як поліноми над полем GF (2 8).

Зворотне перетворення AddRoundKey ()

Перетворення AddRoundKey (), описане в розділі 1.4 є оборотним, так як містить тільки операції XOR.

Еквівалентний код дешифрування

В алгоритмі дешифрування (рис. 3), послідовність перетворень відрізняється від порядку операцій шифрування, а форма ключів розширення для шифрування і дешифрування залишається незмінною (рис. 4). Однак ряд властивостей алгоритму AES допускають формування еквівалентного коду дешифрування, де послідовність операцій перетворення залишається тією ж самою (з заміною перетворень на зворотні).

EqInvCipher (byte in [4 * Nb], byte out [4 * Nb], word dw [Nb * (Nr + 1)])
begin
byte state [4, Nb]
state = in
AddRoundKey (state, dw [Nr * Nb, (Nr + 1) * Nb-1])
for round = Nr-1 step -1 downto 1
InvSubBytes (state)
InvShiftRows (state)
InvMixColumns (state)
AddRoundKey (state, dw [round * Nb, (round + 1) * Nb-1])
end for
InvSubBytes (state)
InvShiftRows (state)
AddRoundKey (state, dw [0, Nb-1])
out = state
end

Для еквівалентної програми дешифрування в кінець програми розширення ключа додається наступний псевдокод:

for i = 0 step 1 to (Nr + 1) * Nb-1
dw [i] = w [i]
end for
for round = 1 step 1 to Nr-1
InvMixColumns (dw [round * Nb, (round + 1) * Nb-1])

Мал. 4. Псевдокод для еквівалентного зворотного перетворення

Останнім часом з'явилася нова версія AES-NI (New Instructions) [2], яка дозволяє оптимізувати роботу алгоритму (знизити завантаження процесора на 50%). Ця версія може використовуватися і спільно з SSL. Компанія Intel розробила мікросхему, що реалізує цей алгоритм (серія X5600). Кількість клієнтів при роботі з версією AES-NI може бути збільшено на 13%.