Что такое aes шифрование
Описание основ криптопреобразования AES
Доброго времени суток, Хабр! Примерно 3 месяца назад проходил собеседование frontend разработчиком и самый первый вопрос, который мне задали: “Что такое AES?” Ну как бы аморфное представление я все же имел о симметрично блочном шифровании AES, было дело даже использовал в одном из проектов для шифрования персональных данных. Но чтобы знать алгоритм rijndael и еще уметь его реализовать на javascript, для меня на тот момент казалось задачей трудновыполнимой. Но! Мне был брошен вызов и я его принял.
Go в подкат!
За основу я взял спецификацию FIPS197 AES от 26 ноября 2011г.
В IT сфере одни из самых известных алгоритмов шифрования являются:
В свою очередь симметричные алгоритмы делятся на два типа:
Потоковые шифруют посимвольно.
Преимуществами для асимметричных алгоритмов является его безопасное хранение ключей. Асимметричные — те алгоритмы, которые имеют два ключа:
Недостатками асимметричных алгоритмов, является его относительно медленное выполнение шифрования.
Rijndael — симметричный алгоритм блочного шифрования с возможностью изменять размеры блоков и секретных ключей от 128 до 256 бит с разностью в 32 бита. Использует линейно-подстановочные преобразования и состоит из 10, 12 или 14 раундов в зависимости от длины ключа.
AES — rijndael с ключом в 128 бит и блоком данных в 16 байт.
Предположительно вы знакомы с теорией следующих терминов:
Математические понятия в rijndael:
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₀;
Байт B, состоящий из битов b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀;
Произведение 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
Все вычислительные операции алгоритма проводятся с использованием вышеописанных правил
Функции алгоритма:
Шифрование в AES происходит в несколько этапов:
Rcon — постоянный массив для генерации ключей путем XOR. Иначе говоря функция keyExpansion() циклично XOR’ится с ключами фиксированного массива Rcon и возвращает массив ключей. Количество ключей составляет — 11. 10 из которых принадлежат раундам алгоритма.
Первый этап шифрования начинается с применения данной функции к state путем правила суммирования, указанного выше. Иначе говоря addRoundKey XOR’ится со state, точнее с каждым его байтом. Об’XOR’енный state попадает на следующий этап, а именно в систему раундов алгоритма:
В алгоритме есть 10 раундов, то есть 10 шагов криптопреобразования. Первые 9 раундов циклично выполняют 4 функции:
Данная функция трансформирует state путем замены своих байтов на другие способом подставления в готовую фиксированную таблицу S-box:
53h будет равен edh
Данная функция производит циклическое смещение 3-х последних строк влево следующим образом:
Вычислительно самое сложное из функций. Тут происходит умножение на постоянную функцию a(x) = <03>x³ + <01>x² + <01>x + <02>. То есть произведение по указанному выше правилу конкретного столбца из state на функцию a(x). За исключением правила умножения алгоритма данный способ эквивалентен матричному умножению:
Дешифрование в AES также происходит в несколько этапов:
В алгоритме есть 10 раундов, то есть шаг криптопреобразования.
Первые 9 раундов циклично выполняют 4 функции, порядок обратный порядку шифрования, то есть:
Функция invMixColumns выполняет мультипликативно обратную операцию умножения по правилам умножения алгоритма на постоянную функцию a⁻¹(x) конкретного столбца state:
Обратная трансформация shiftRows() — циклическое смещение вправо:
Инверсия subBytes() — обратная замена байт state заведомо представленную в hex в соответствии фиксированной таблицы inverse S-box:
Список литературы:
Как устроен AES
О чём эта статья
Долгое время я считал, что криптографические алгоритмы шифрования и хеширования, вроде AES и MD5, устроены очень сложно и написать их совсем не просто, даже имея под рукой полную документацию. Запутанные реализации этих алгоритмов на разных языках программирования только укрепляли это мнение. Но недавно у меня появилось много свободного времени и я решил разобраться в этих алгоритмах и написать их. Оказалось, что они очень просто устроены и для их реализации нужно совсем немного времени.
В этой статье я напишу как устроен алгоритм шифрования AES (которого иногда называют Rijndael) и напишу его на JavaScript. Почему на JavaScript? Чтобы запустить программу на этом языке, нужен только браузер в котором вы читаете эту статью. Чтобы запустить программу, скажем, на C, нужен компилятор и найдётся совсем мало желающих, готовых потратить время на компиляцию кода из какой то статьи. В конце есть ссылка по которой можно скачать архив с html страницей и несколькими js файлами — это пример реализации AES на JavaScript.
Как применить AES
Этот алгоритм преобразует один 128-битный блок в другой, используя секретный ключ который нужен для такого преобразования. Для расшифровки полученного 128-битного блока используют второе преобразование с тем же секретным ключом. Выглядит это так:
Размер блока всегда равен 128 бит. Размер ключа также имеет фиксированный размер. Чтобы зашифровать произвольный текст любым паролем можно поступить так:
Это можно записать так:
Чтобы расшифровать массив блоков cipher нужно применить к каждому блоку decrypt:
Конечно, длина текста может быть не кратна 128 битам. В таких случаях можно дополнить текст нулями до нужной длины, а в зашифрованные данные добавить несколько байт с зашифрованным размером оригинального текста. Функции aes.encrypt и aes.decrypt в файле aes.js в примере используют этот подход.
Поле GF(2 8 )
AES активно использует так называемое конечное поле GF(2 8 ). Чтобы написать AES на JavaScript не обязательно знать, что это за поле, но если вы хотите лучше понять AES, прочтите этот раздел.
Поле GF(2 8 ) это числа 0..255 для которых определили особое умножение и особое сложение. Возмём какое нибудь число из этого поля и представим его в виде восьми битов: a = a7a6a5a4a3a2a1a0. Точно также представим число b. Сложение a и b это известная побитовая операция xor:
У сложения есть простые свойства:
Умножение определяется сложнее. Запишем многочлены с коэффициентами из битов этих чисел:
Теперь перемножим эти два многочлена и найдём остаток от деления на m:
m = x 8 + x 4 + x 3 + x + 1
r = pq mod (m)
Почему выбран именно такой m? У этого многочлена есть только два делителя-многочлена на которых он делится без остатка: единица и он сам. По аналогии с простыми числами, многочлен m «простой». Находить остаток от деления можно также как для обычных чисел: для этого достаточно уметь умножать, складывать и вычитать многочлены, причём сложение и вычитание производят по правилам GF(2 8 ), т.е. сложение и вычитание многочленов это xor между каждой парой коэффициентов. Вот два примера:
Многочлен r представим в виде
Его 8 коэффициентов представляют собой 8-битовое число из поля GF(2 8 ) и это число называется произведением a•b. В отличие от сложения, умножение нельзя найти парой простых побитовых операций. Однако умножение на произвольный многочлен в поле GF(2 8 ) можно свести к умножению на многочлен x, а умножить на x можно несколькими побитовыми операциями, о чём пойдёт речь ниже.
Для обозначения многочленов в GF(2 8 ) используют 16-ричные цифры. Например
m = x 8 + x 4 + x 3 + x + 1 = 100011011 = 0x011b = <01><1b>
Умножить на многочлен x = <02>в поле GF(2 8 ) очень просто. Рассмотрим произведение:
Теперь нужно найти остаток от деления на m. Если бит a7 = 1, то нужно один раз вычесть m. Если a7 = 0 то вычитать ничего не нужно. Итак:
Умножение на x можно записать такой функцией:
Зная как умножать на x можно умножить на любой другой многочлен. Для примера найдём a•b где a = <3c>, b =
Таблица SBox
Эта таблица представляет собой 256-байтый массив и используется для замены одного байта другим. Не обязательно понимать как она получается, потому что в код можно просто скопировать этот массив. Чтобы узнать чему равен элемент SBox[b] нужно три действия:
В сумме эти три действия дают афинное преобразование:
Несложно понять как построена эта матрица из битов. Для умножения битов нужно применять «and», для сложения — «xor». Например:
Функцию sbox я написал так:
Построенная таблица выглядит так:
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 преобразования. В конце он записывает матрицу в виде массива и подаёт его на выход — это зашифрованный блок. Каждое из четырёх преобразований очень простое.
Для шифрования используют [a b c d] = [ <02><03><01><01>]. Можно проверить, что преобразование обратное к MixColumns[ <02><03><01><01>] это MixColumns[ <0e><0b><0d><09>].
Схематично шифрование можно изобразить так:
Расшифровка
Как видно, для шифрования блока данных AES последовательно применяет к нему много обратимых преобразований. Для расшифровки нужно применить обратные преобразования в обратном порядке.
Немного оптимизации
Функция sbox имеет всего 256 возможных входных значений и 256 возможных выходных значений. Чтобы не вычислять много раз sbox для одного аргумента, нужно кешировать результаты. На JavaScript это несложно сделать даже не меняя код написанный ранее. Для этого нужно всего лишь дописать ниже вот это:
Этот код заменяет sbox функцией которая кеширует результаты sbox. Тоже самое можно сделать для любой функции, например для invsbox и rcon. Этот же приём можно применить для функции gf.mul которая умножает два байта в поле GF(2 8 ), но в этом случае размер кеша будет равен 256×256 элементов, что довольно много.
Ссылки
Документация к AES на английском называется FIPS 197.
Advanced Encryption Standard
Винсент Риджмен, Джоан Даймон
10/12/14 (зависит от размера ключа)
Substitution permutation network
Содержание
История AES [ ]
Необходимость в принятии нового стандарта была вызвана небольшой длиной ключа DES (56 бит), что позволяло применить метод грубой силы (полный перебор ключей) против этого алгоритма. Кроме того, архитектура DES была ориентирована на аппаратную реализацию, и программная реализация алгоритма на платформах с ограниченными ресурсами не давала достаточного быстродействия. Модификация 3-DES обладала достаточной длиной ключа, но при этом была ещё медленнее.
Начало конкурса [ ]
2 января 1997 года NIST объявляет [1] о намерении выбрать преемника для DES, являвшегося американским стандартом с 1977 года. Однако, вместо опубликования алгоритма, NIST принял различные предложения от заинтересованных сторон о том, каким образом следует выбирать алгоритм. Бурный отклик со стороны открытого криптографического сообщества привёл к объявлению конкурса ( 12 сентября 1997 г.). Свой алгоритм могла предложить любая организация или группа исследователей. Требования к новому стандарту были следующими:
Кроме того, алгоритм, претендующий на то, чтобы стать стандартом, должен распространяться по всему миру на неэксклюзивных условиях и без платы за пользование патентом.
1-й и 2-й раунды [ ]
Третья конференция AES [ ]
Третья конференция AES прошла в Нью-Йорке 13 и 14 апреля 2000 года, незадолго до завершения второго этапа. На ней присутствовало 250 участников, многие из которых приехали из-за рубежа. Двухдневная конференция была разделена на восемь сессий, по четыре в день, плюс к тому состоялась неформальная дополнительная сессия, подводившая итоги первого дня. На сессиях первого дня обсуждались вопросы, связанные с программируемыми матрицами ( FPGA ), проводилась оценка реализации алгоритмов на различных платформах, в том числе PA-RISC, IA-64, Alpha, высокоуровневых смарт-картах и сигнальных процессорах, сравнивалась производительность претендентов на стандарт, анализировалось число раундов в алгоритмах-кандидатах. На сессиях второго дня был проанализирован Rijndael с сокращённым числом раундов и показана его слабость в этом случае, обсуждался вопрос об интегрировании в окончательный стандарт всех пяти алгоритмов-претендентов, ещё раз тестировались все алгоритмы. В конце второго дня была проведена презентация, на которой претенденты рассказывали о своих алгоритмах, их достоинствах и недостатках. О Rijndael рассказал Винсент Риджмен, заявивший о надёжности защиты, высокой общей производительности и простоте архитектуры своего кандидата.
Выбор победителя [ ]
Описание AES [ ]
Определения и вспомогательные процедуры [ ]
| 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 бит. Для обозначения выбранных длин 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() [ ]
Рис2.В процедуре SubBytes, каждый байт в state заменяется соответствующим элементом в фиксированной 8-битной таблице поиска, S; bij = S(aij).
ShiftRows() [ ]
Рис3.В процедуре ShiftRows, байты в каждой строке state циклически сдвигаются влево. Размер смещения байтов каждой строки зависит от ее номера.
ShiftRows работает со строками State. При этой трансформации строки состояния циклически сдвигаются на r байт по горизонтали, в зависимости от номера строки. Для нулевой строки r = 0, для первой строки r = 1б и тд.. Таким образом каждая колонка выходного состояния после применения процедуры ShiftRows состоит из байтов из каждой колонки начального состояния. Для алгоритма Rijndael паттерн смещения строк для 128 и 192-ух битных строк одинаков. Однако для блока размером 256 бит отличается от предыдущих тем, что 2, 3, и 4-ые строки смещаются на 1, 3, и 4 байта соответственно.
MixColumns() [ ]
Рис4.В процедуре MixColumns, каждай колонка состояния перемножается с фиксированным многочленом c(x).
AddRoundKey() [ ]
Рис5.В процедуре AddRoundKey, каждый байт состояния объединяется с RoundKey используя XOR operation (⊕).
KeyExpansion() [ ]
AES агоритм используя процедуру KeyExpansion() и подавая в нее Cipher Key, K, получает ключи для всех раундов. Всего она получает Nb*(Nr + 1) слов: изначально для алгоритма требуется набор из Nb слов, и каждому из Nr раундов требуется Nb ключевых набора данных. Полученный массив ключей для раундов обзначается как w[i], . Алгоритм KeyExpansion() показан в псевдо коде на рис.6
Функция SubWord() берет четырехбайтовое входное слово и применяет S-box к каждому из четырех байтов то, что получилось подается на выход. На вход RotWord() подается слово которое она циклически переставляет и возвращает . Массив слов, слов постоянный для данного раунда, Rcon[i], содержит значения , где x = <02>, а является степенью x в GF <2^8>( i начинается с 1).
Рис.6 Псевдокод для Key Expansion
Расшифрование [ ]
Рис.7 Псевдокод для Inverse Cipher