imrangadzhiev 17 апр 2020 в 08:55

Описание основ криптопреобразования AES

6 мин

15K

Туториал

Доброго времени суток, Хабр! Примерно 3 месяца назад проходил собеседование frontend разработчиком и самый первый вопрос, который мне задали: “Что такое AES?” Ну как бы аморфное представление я все же имел о симметрично блочном шифровании AES, было дело даже использовал в одном из проектов для шифрования персональных данных. Но чтобы знать алгоритм rijndael и еще уметь его реализовать на javascript, для меня на тот момент казалось задачей трудновыполнимой. Но! Мне был брошен вызов и я его принял.

Go в подкат!

За основу я взял спецификацию FIPS197 AES от 26 ноября 2011г.

В IT сфере одни из самых известных алгоритмов шифрования являются:

симметричные
асимметричные

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

В свою очередь симметричные алгоритмы делятся на два типа:

блочные
потоковые

Блочные имеют возможность шифровать данные блоками, то есть заведомо установленным конечным числом байтов. Отсюда вытекает возможность распараллеливанию шифровки блоков, то есть шифровать большие объемы данных одновременно, сокращая при это ресурс времени.

Потоковые шифруют посимвольно.

Преимуществами для асимметричных алгоритмов является его безопасное хранение ключей. Асимметричные — те алгоритмы, которые имеют два ключа:

publicKey
privateKey

publicKey — ключ для шифрования. Не подлежит для дешифровки, а значит необходимости в его передачи нет.
privateKey — ключ для дешифрования.

Недостатками асимметричных алгоритмов, является его относительно медленное выполнение шифрования.

Rijndael — симметричный алгоритм блочного шифрования с возможностью изменять размеры блоков и секретных ключей от 128 до 256 бит с разностью в 32 бита. Использует линейно-подстановочные преобразования и состоит из 10, 12 или 14 раундов в зависимости от длины ключа.
AES — rijndael с ключом в 128 бит и блоком данных в 16 байт.

Предположительно вы знакомы с теорией следующих терминов:

двоичная система счисления
десятичная система счисления
биты
байты
XOR (^)

Если все же нет, то не беда. Почитайте мою статью «Обработка изображений ReactJS — NodeJS» или посмотрите примеры снипеттов на reactjs.su

Математические понятия в rijndael:

Поле GF (2⁸) — конечное число элементов, результатом которого является n-ая натуральная степень простого числа. В рамках GF (2⁸) производятся произвольные операции сложения, вычитания, произведения, деления. Поле GF (2⁸) определенно.
Полиномиальное представление двоичных чисел. Rijndael работает с двоичными числами [00000000₂; 11111111₂]. Основание системы счисления заменяется некоторой фиктивной переменной, например x. Степень этой переменной будет соответствовать номеру разряда числа, а коэффициент значению самого разряда, полином принимает вид:

a(x)=a₇x⁷ +a₆x⁶ +a₅x⁵ +a₄x⁴ +a₃x³ +a₂x² +a₁x +a₀x;

Байт А, состоящий из битов a₇, a₆, a₅, a₄, a₃, a₂, a₁, a₀ можно записать в виде полинома с коэффициентами из {0, 1}, например:
87 = 01010111 (двоичный вид);
полиномиальный вид: x⁶ + x⁴ + x² + x + 1;
Неприводимый полином. Полином называется неприводимым, если он не имеет делителей, кроме 1 и самого себя. Для rijndael такой полином является m(x):
m(x)= x⁸ + x⁴ + x³ + x + 1;
Суммирование. Правилом выполнения сложения двух полиномов является побитовый XOR, то есть: 1 ^ 1 = 0 ^ 0 = 0; 1 ^ 0 = 0 ^ 1 = 1, например:

Байт А, состоящий из битов a₇, a₆, a₅, a₄, a₃, a₂, a₁, a₀;
Байт B, состоящий из битов b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀;

Сложение чисел A = 87 = 01010111; B = 131 = 10000011;
A ^ B = a₇, a₆, a₅, a₄, a₃, a₂, a₁, a₀ ^ b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀ = 11010100;
Произведение. В полиномиальном представлении умножение в GF(2⁸) соответствует умножению полиномов по модулю ( | -x | = x ) неприводимого двоичного полинома степени 8, например:

Произведение 87 x 131 будет выглядеть следующим образом:
(x⁶ + x⁴ + x² + x + 1)(x⁷ + x + 1) = x¹³ + x¹¹ + x⁹ + x⁸ + x⁷ + x⁷ + x⁵ + x³ + x² + x + x⁶ + x⁴ + x² + x + 1.
Раскрытие скобок происходит на основе элементарных математических правил. Далее сложение происходит по правилам суммирования указанных выше (п.4):

x⁷ + x⁷ = x⁷(1 + 1) = x⁷(1 ^ 1) = x⁷0 = 0;
(x⁶ + x⁴ + x² + x + 1)(x⁷ + x + 1) = x¹³ + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x³ + 1.

После производится деление на конкретно заданную функцию m(x) = x⁸ + x⁴ + x³ + x + 1 (неприводимый полином), которая по правилам rijndael гарантирует корректный результат, то есть на выходе мы получим двоичный полином степени меньше 8, а значит сможем представить его байтом для дальнейшего шифрования. Деление производится по модулю. Деление можно производить, как деление многочленов столбиком. Остаток от деления является результатом:

(x⁶ + x⁴ + x² + x + 1)(x⁷ + x + 1)/(x⁸ + x⁴ + x³ + x + 1) =
(x¹³ + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x³ + 1)/(x⁸ + x⁴ + x³ + x + 1) = |Result| = x⁷ + x⁶ + 1

Все вычислительные операции алгоритма проводятся с использованием вышеописанных правил

Функции алгоритма:

keyExpansion() — расширение ключа;
addRoundKey() — раундовый ключ;
subBytes() — замена state;
shiftRows() — циклическое смещение строк state;
mixColumns() — смешивание столбцов state;
invMixColumns() — обратная операция mixColumns;
invShiftRows() — обратная операция shiftRows;
invSubBytes() — обратная операция subBytes;

Шифрование в AES происходит в несколько этапов:

Формирование state
Допустим мы написали какое-то секретное сообщение конкретному лицу. Наше сообщение представляется числами [0; 255] (программно это выполняется кодированием по ASCII или Unicode). Сообщение делится на n-ое количество блоков данных в 16 байт. Блок данных называют state (программно можно представить в виде многомерного массива по 4 байта каждый подмассив = [ [], [], [], [] ] ), если сообщение не кратно 16 байтам, то оно дополняется до 16 байт:
keyExpansion();
Согласно принципам шифрования AES, ключ побайтно равен state. Операция расширения ключа генерирует из текущего ключа массив ключей для цикла раундов шифрования. В качестве сопоставления операции XOR используется фиксированный массив Rcon.

Rcon — постоянный массив для генерации ключей путем XOR. Иначе говоря функция keyExpansion() циклично XOR’ится с ключами фиксированного массива Rcon и возвращает массив ключей. Количество ключей составляет — 11. 10 из которых принадлежат раундам алгоритма.
```
let rCon = [
  [ 0x00, 0x00, 0x00, 0x00 ],
  [ 0x01, 0x00, 0x00, 0x00 ],
  [ 0x02, 0x00, 0x00, 0x00 ],
  [ 0x04, 0x00, 0x00, 0x00 ],
  [ 0x08, 0x00, 0x00, 0x00 ],
  [ 0x10, 0x00, 0x00, 0x00 ],
  [ 0x20, 0x00, 0x00, 0x00 ],
  [ 0x40, 0x00, 0x00, 0x00 ],
  [ 0x80, 0x00, 0x00, 0x00 ],
  [ 0x1b, 0x00, 0x00, 0x00 ],
  [ 0x36, 0x00, 0x00, 0x00 ],
];
```
addRoundKey();

Первый этап шифрования начинается с применения данной функции к state путем правила суммирования, указанного выше. Иначе говоря addRoundKey XOR’ится со state, точнее с каждым его байтом. Об’XOR’енный state попадает на следующий этап, а именно в систему раундов алгоритма:
Раунды алгоритма

В алгоритме есть 10 раундов, то есть 10 шагов криптопреобразования. Первые 9 раундов циклично выполняют 4 функции:
- subBytes();
- shiftRows();
- mixColumns();
- addRoundKey();
10-ый раунд выполняет:
- subBytes();
- shiftRows();
- addRoundKey();

subBytes();

Данная функция трансформирует state путем замены своих байтов на другие способом подставления в готовую фиксированную таблицу S-box:

State заведомо должен преобразоваться в hex формат, например: 01010011 -> 0101 | 0011 -> 53h

53h будет равен edh

программное представление S-box

const sBox = [
  0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
  0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
  0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
  0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
  0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
  0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
  0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
  0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
  0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
  0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
  0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
  0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
  0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
  0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
  0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
  0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16,
];

shiftRows();

Данная функция производит циклическое смещение 3-х последних строк влево следующим образом:
mixColumns();

Вычислительно самое сложное из функций. Тут происходит умножение на постоянную функцию a(x) = {03}x³ + {01}x² + {01}x + {02}. То есть произведение по указанному выше правилу конкретного столбца из state на функцию a(x). За исключением правила умножения алгоритма данный способ эквивалентен матричному умножению:

Дешифрование в AES также происходит в несколько этапов:

keyExpansion();
Раунды алгоритма

В алгоритме есть 10 раундов, то есть шаг криптопреобразования.

Первые 9 раундов циклично выполняют 4 функции, порядок обратный порядку шифрования, то есть:
- addRoundKey();
- invMixColumns();
- invShiftRows();
- invSubBytes();
10-раунд:
- addRoundKey();
- invShiftRows();
- invSubBytes();
addRoundKey();

Обратное суммирование по правилам алгоритма на самого себя, исключая массив Rcon
invMixColumns();

Функция invMixColumns выполняет мультипликативно обратную операцию умножения по правилам умножения алгоритма на постоянную функцию a⁻¹(x) конкретного столбца state:
invShiftRows();

Обратная трансформация shiftRows() — циклическое смещение вправо:
invSubBytes();

Инверсия subBytes() — обратная замена байт state заведомо представленную в hex в соответствии фиксированной таблицы inverse S-box: