О чём эта статья
Долгое время я считал, что криптографические алгоритмы шифрования и хеширования, вроде AES и MD5, устроены очень сложно и написать их совсем не просто, даже имея под рукой полную документацию. Запутанные реализации этих алгоритмов на разных языках программирования только укрепляли это мнение. Но недавно у меня появилось много свободного времени и я решил разобраться в этих алгоритмах и написать их. Оказалось, что они очень просто устроены и для их реализации нужно совсем немного времени.
В этой статье я напишу как устроен алгоритм шифрования AES (которого иногда называют Rijndael) и напишу его на JavaScript. Почему на JavaScript? Чтобы запустить программу на этом языке, нужен только браузер в котором вы читаете эту статью. Чтобы запустить программу, скажем, на C, нужен компилятор и найдётся совсем мало желающих, готовых потратить время на компиляцию кода из какой то статьи. В конце есть ссылка по которой можно скачать архив с html страницей и несколькими js файлами — это пример реализации AES на JavaScript.
Как применить AES
Этот алгоритм преобразует один 128-битный блок в другой, используя секретный ключ который нужен для такого преобразования. Для расшифровки полученного 128-битного блока используют второе преобразование с тем же секретным ключом. Выглядит это так:
cipher = encrypt(block, key) // шифруем block с помощью key
block = decrypt(cipher, key) // расшифровываем cipher с помощью key
Размер блока всегда равен 128 бит. Размер ключа также имеет фиксированный размер. Чтобы зашифровать произвольный текст любым паролем можно поступить так:
- получить хеш от пароля
- преобразовать хеш в ключ по правилам описанным в стандарте AES
- разбить текст на блоки по 128 бит
- зашифровать каждый блок функцией cipher
Это можно записать так:
hash = md5(password) // MD5 хеш имеет длину 128 бит
key = keyexpansion(hash) // преобразуем хеш в ключ
blocks = split(text, 16) // разбить текст на блоки по 16 байт
for (i = 0; i < blocks.length; i++)
cipher[i] = encrypt(blocks[i], key)
Чтобы расшифровать массив блоков cipher нужно применить к каждому блоку decrypt:
hash = md5(password)
key = keyexpansion(hash)
for (i = 0; i < cipher.length; i++)
blocks[i] = decrypt(cipher[i], key)
text = merge(blocks) // соединить все блоки в одну строку
Конечно, длина текста может быть не кратна 128 битам. В таких случаях можно дополнить текст нулями до нужной длины, а в зашифрованные данные добавить несколько байт с зашифрованным размером оригинального текста. Функции aes.encrypt и aes.decrypt в файле aes.js в примере используют этот подход.
Поле GF(28)
AES активно использует так называемое конечное поле GF(28). Чтобы написать AES на JavaScript не обязательно знать, что это за поле, но если вы хотите лучше понять AES, прочтите этот раздел.
Поле GF(28) это числа 0..255 для которых определили особое умножение и особое сложение. Возмём какое нибудь число из этого поля и представим его в виде восьми битов: a = a7a6a5a4a3a2a1a0. Точно также представим число b. Сложение a и b это известная побитовая операция xor:
a + b = a xor b
У сложения есть простые свойства:
a + a = 0
-a = 0 - a = a
a - b = a + (-b) = a + b
Умножение определяется сложнее. Запишем многочлены с коэффициентами из битов этих чисел:
p = a7x7 + a6x6 + a5x5 + a4x4 + a3x3 + a2x2 + a1x + a0
q = b7x7 + b6x6 + b5x5 + b4x4 + b3x3 + b2x2 + b1x + b0
Теперь перемножим эти два многочлена и найдём остаток от деления на m:
m = x8 + x4 + x3 + x + 1
r = pq mod (m)
Почему выбран именно такой m? У этого многочлена есть только два делителя-многочлена на которых он делится без остатка: единица и он сам. По аналогии с простыми числами, многочлен m «простой». Находить остаток от деления можно также как для обычных чисел: для этого достаточно уметь умножать, складывать и вычитать многочлены, причём сложение и вычитание производят по правилам GF(28), т.е. сложение и вычитание многочленов это xor между каждой парой коэффициентов. Вот два примера:
x3 + x2 + 1 mod (x3 + 1) = x2 // нужно один раз отнять x3+1
x3 + x2 + 1 mod (x2 + 1) = (x3 + x2 + 1) - (x + 1)(x2 + 1) = -x
Многочлен r представим в виде
r = r7x7 + r6x6 + r5x5 + r4x4 + r3x3 + r2x2 + r1x + r0
Его 8 коэффициентов представляют собой 8-битовое число из поля GF(28) и это число называется произведением a•b. В отличие от сложения, умножение нельзя найти парой простых побитовых операций. Однако умножение на произвольный многочлен в поле GF(28) можно свести к умножению на многочлен x, а умножить на x можно несколькими побитовыми операциями, о чём пойдёт речь ниже.
Для обозначения многочленов в GF(28) используют 16-ричные цифры. Например
m = x8 + x4 + x3 + x + 1 = 100011011 = 0x011b = {01}{1b}
Умножить на многочлен x = {02} в поле GF(28) очень просто. Рассмотрим произведение:
xp = x(a7x7 + a6x6 + a5x5 + a4x4 + a3x3 + a2x2 + a1x + a0) =
a7x8 + a6x7 + a5x6 + a4x5 + a3x4 + a2x3 + a1x<2 + a0x
p = a7a6a5a4a3a2a1a0
xp = a7a6a5a4a3a2a1a00 // это сдвиг влево на один бит
Теперь нужно найти остаток от деления на m. Если бит a7 = 1, то нужно один раз вычесть m. Если a7 = 0 то вычитать ничего не нужно. Итак:
r = xp mod (m) = xp - m если a7 = 1
r = xp mod (m) = xp если a7 = 0
Умножение на x можно записать такой функцией:
gf.xtime = function(b)
{
var highbit = b & 0x80
var shl = (b << 1) & 0xff
return highbit == 0 ? shl : shl ^ 0x1b
}
Зная как умножать на x можно умножить на любой другой многочлен. Для примера найдём a•b где a = {3c}, b = {a1}:
b = {a1} = 10100001 = {80} + {20} + {01}
a•b = a•{80} + a•{20} + a•{01} = a•x7 + a•x5 + a =
a•{02}•{02}•{02}•{02}•{02}•{02}•{02} + a•{02}•{02}•{02}•{02}•{02} + a =
{29} + {c1} + {3c} = {d4}
Осталась одна простая операция в поле GF(28). У любого байта b, кроме нуля, есть обратный байт a = b-1 который обладает свойством a•b = {01}. Все три функции для работы с полем — умножение на x, умножение двух произвольных байтов и нахождение обратного — я собрал в маленькую библиотеку gf на JavaScript.
Таблица SBox
Эта таблица представляет собой 256-байтый массив и используется для замены одного байта другим. Не обязательно понимать как она получается, потому что в код можно просто скопировать этот массив. Чтобы узнать чему равен элемент SBox[b] нужно три действия:
- найти обратный байт к b в поле GF(28) (ноль оставить без изменений)
- умножить результат состоящий из восьми битов на матрицу 8×8 из 64 битов
- добавить {63}
В сумме эти три действия дают афинное преобразование:
Несложно понять как построена эта матрица из битов. Для умножения битов нужно применять «and», для сложения — «xor». Например:
r0 = b0 + b4 + b5 + b6 + b7 + 1
Функцию sbox я написал так:
aes.sbox = function(b)
{
var m = 0xf8
var r = 0
var q = gf.inv(b) || 0
for (var i = 0; i < 8; i++)
{
r = (r << 1) | bits.xorbits(q & m)
m = (m >> 1) | ((m & 1) << 7)
}
return r ^ 0x63
}
Построенная таблица выглядит так:
63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16
Её можно просто скопировать в код, как часто делают, а можно вычислять функцией sbox по мере надобности.
Таблица InvSBox
Для дешифрования текста AES использует таблицу обратную к SBox. Таблица InvSBox обладает одним свойством: InvSBox[SBox[i]] = i. InvSBox выглядит так:
52 09 6a d5 30 36 a5 38 bf 40 a3 9e 81 f3 d7 fb
7c e3 39 82 9b 2f ff 87 34 8e 43 44 c4 de e9 cb
54 7b 94 32 a6 c2 23 3d ee 4c 95 0b 42 fa c3 4e
08 2e a1 66 28 d9 24 b2 76 5b a2 49 6d 8b d1 25
72 f8 f6 64 86 68 98 16 d4 a4 5c cc 5d 65 b6 92
6c 70 48 50 fd ed b9 da 5e 15 46 57 a7 8d 9d 84
90 d8 ab 00 8c bc d3 0a f7 e4 58 05 b8 b3 45 06
d0 2c 1e 8f ca 3f 0f 02 c1 af bd 03 01 13 8a 6b
3a 91 11 41 4f 67 dc ea 97 f2 cf ce f0 b4 e6 73
96 ac 74 22 e7 ad 35 85 e2 f9 37 e8 1c 75 df 6e
47 f1 1a 71 1d 29 c5 89 6f b7 62 0e aa 18 be 1b
fc 56 3e 4b c6 d2 79 20 9a db c0 fe 78 cd 5a f4
1f dd a8 33 88 07 c7 31 b1 12 10 59 27 80 ec 5f
60 51 7f a9 19 b5 4a 0d 2d e5 7a 9f 93 c9 9c ef
a0 e0 3b 4d ae 2a f5 b0 c8 eb bb 3c 83 53 99 61
17 2b 04 7e ba 77 d6 26 e1 69 14 63 55 21 0c 7d
Виды AES
Алгоритм AES преобразует блок длиной 128 битов в другой блок той же длины. Для преобразования применяется расписание ключей w получаемое из ключа. 128-битный блок в AES представляется в виде матрицы 4×Nb. Стандарт допускает только одно значение Nb = 4, поэтому длина блока всегда 128 бит, хотя алгоритм может работать с любым Nb. Длина ключа равна 4Nk байт. Алгоритм шифрования блока состоит из Nr раундов — применений одной и той же группы преобразований к 128-битному блоку данных. Стандарт допускает следующие комбинации этих трёх параметров:
| Nk | Nb | Nr | |
| AES-128 | 4 | 4 | 10 |
| AES-192 | 6 | 4 | 12 |
| AES-256 | 8 | 4 | 14 |
Преобразование KeyExpansion
Для шифрования текста AES применяет не пароль или хеш от пароля, а так называемое «расписание ключей» получаемое из ключа. Это расписание можно представить как Nr + 1 матриц размера 4×Nb. Алгоритм шифрования делает Nr + 1 шагов и на каждом шаге он, помимо других действий, берёт одну матрицу 4×Nb из «расписания» и поэлементно добавляет её к блоку данных.
Шифрование блока данных
Алгоритм шифрования получает на вход 128-битный блок данных input и расписание ключей w, которое получается после KeyExpansion. 16-байтый input он записывает в виде матрицы s размера 4×Nb, которая называется состоянием AES, и затем Nr раз применяет к этой матрице 4 преобразования. В конце он записывает матрицу в виде массива и подаёт его на выход — это зашифрованный блок. Каждое из четырёх преобразований очень простое.
- AddRoundKey берёт из расписания ключей одну матрицу размера 4×Nb и поэлементно добавляет её к матрице состояния. Если два раза применить AddRoundKey, то ничего не изменится, поэтому преобразование обратное к AddRoundKey это оно само.
- SubBytes заменяет каждый элемент матрицы состояния соответвующим элементом таблицы SBox: sij = SBox[sij]. Преобразование SubBytes обратимо. Обратное к нему находится с помощью таблицы InvSBox.
- ShiftRows сдвигает i-ую строку матрицы s на i позиций влево, считая i с нуля. Обратное преобразование InvShiftRows сдвигает строки вправо.
- MixColumns умножает каждый столбец матрицы s слева на особую матрицу размера 4×4:
Для шифрования используют [a b c d] = [{02} {03} {01} {01}]. Можно проверить, что преобразование обратное к MixColumns[{02} {03} {01} {01}] это MixColumns[{0e} {0b} {0d} {09}].
Схематично шифрование можно изобразить так:
AddRoundKey(0)
for (var i = 1; i <= Nr - 1; i++)
{
SubBytes()
ShiftRows()
MixColumns([0x02, 003, 0x01, 0x01])
AddRoundKey(i)
}
SubBytes()
ShiftRows()
AddRoundKey(Nr)
Расшифровка
Как видно, для шифрования блока данных AES последовательно применяет к нему много обратимых преобразований. Для расшифровки нужно применить обратные преобразования в обратном порядке.
Немного оптимизации
Функция sbox имеет всего 256 возможных входных значений и 256 возможных выходных значений. Чтобы не вычислять много раз sbox для одного аргумента, нужно кешировать результаты. На JavaScript это несложно сделать даже не меняя код написанный ранее. Для этого нужно всего лишь дописать ниже вот это:
Function.prototype.cached = function()
{
var old = this
var cache = {}
return function(x)
{
if (cache[x] !== undefined)
return cache[x]
cache[x] = old(x)
return cache[x]
}
}
aes.sbox = aes.sbox.cached()
Этот код заменяет sbox функцией которая кеширует результаты sbox. Тоже самое можно сделать для любой функции, например для invsbox и rcon. Этот же приём можно применить для функции gf.mul которая умножает два байта в поле GF(28), но в этом случае размер кеша будет равен 256×256 элементов, что довольно много.
Ссылки
Документация к AES на английском называется FIPS 197.