128 битное шифрование что это

Как устроен 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 = a₇a₆a₅a₄a₃a₂a₁a₀. Точно также представим число 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. Если бит a₇ = 1, то нужно один раз вычесть m. Если a₇ = 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×N_b. Стандарт допускает только одно значение N_b = 4, поэтому длина блока всегда 128 бит, хотя алгоритм может работать с любым N_b. Длина ключа равна 4N_k байт. Алгоритм шифрования блока состоит из N_r раундов — применений одной и той же группы преобразований к 128-битному блоку данных. Стандарт допускает следующие комбинации этих трёх параметров:

Преобразование KeyExpansion

Для шифрования текста AES применяет не пароль или хеш от пароля, а так называемое «расписание ключей» получаемое из ключа. Это расписание можно представить как N_r + 1 матриц размера 4×N_b. Алгоритм шифрования делает N_r + 1 шагов и на каждом шаге он, помимо других действий, берёт одну матрицу 4×N_b из «расписания» и поэлементно добавляет её к блоку данных.

Шифрование блока данных

Алгоритм шифрования получает на вход 128-битный блок данных input и расписание ключей w, которое получается после KeyExpansion. 16-байтый input он записывает в виде матрицы s размера 4×N_b, которая называется состоянием AES, и затем N_r раз применяет к этой матрице 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.

Источник

Алгоритм шифрования DES (Data Encryption Standard) [9] c 1977 года является стандартом симметричного шифрования США (кроме информации повышенной степени секретности). В течение последующих 20 лет «DES стойко выдержал 20 лет массового всемирного криптоанализа» [7] — десятилетия криптоанализа (т.е. науки, посвященной поиску уязвимостей и, соответственно, взлому криптографических алгоритмов защиты информации) не привели к обнаружению серьезных уязвимостей в алгоритме (подробно о криптоанализе DES см. [18]).

Фактически, DES дал невиданный доселе толчок развитию криптоанализа. Вышли сотни трудов, посвященных различным методам криптоанализа именно в приложении к алгоритму DES, а также деталям самого алгоритма и их влиянию на криптостойкость DES. Можно утверждать, что именно благодаря DES появились целые направления криптоанализа. DES до сих пор считается сильным алгоритмом шифрования во всем, кроме размера ключа шифрования. 56-битный ключ DES явно недостаточен и при современных вычислительных ресурсах может быть вскрыт методом «грубой силы», т.е. перебором всех возможных вариантов ключа шифрования. Причем многие криптографы понимали это еще до принятия DES в качестве стандарта [22], а первые попытки увеличения размера ключа DES без изменения самого алгоритма начались уже в 1978 году (см. [18]). Однако, DES продолжал активно использоваться в качестве стандарта США.

Эти требования оказались достаточно жесткими и частично противоречащими друг другу; каждый конкретный алгоритм из участвовавших в конкурсе представлял собой некий найденный авторами компромисс между соответствиями данным требованиям.

Заявки от участников конкурса NIST принимал в течение полутора лет, после чего все присланные на конкурс алгоритмы изучались и обсуждались как в самом институте NIST, так и всеми желающими. Стоит сказать, что в NIST пришло немало отзывов, все они находятся в открытом доступе и их можно посмотреть на web-сайте института (см. выше).

Всего в конкурсе приняли участие 15 алгоритмов шифрования [1, 13]:

В результате первого этапа конкурса были выбраны 5 алгоритмов без явно выраженных недостатков: MARS, RC6, Rijndael, Serpent и Twofish. Началось детальное изучение именно этих алгоритмов (что называлось «вторым этапом» или «финалом» конкурса AES), продолжавшееся еще год с небольшим. В результате победителем конкурса стал алгоритм Rijndael; ему было присвоено название AES, под именем которого он уже достаточно широко реализован и, видимо, по широте распространения обойдет своего предшественника — алгоритм DES.

Стоит сказать, что алгоритму Rijndael посвящено уже множество статей и разделов книг (например, [20, 21]), поэтому рассмотрим здесь подробно другие алгоритмы, вышедшие в финал, а к алгоритму Rijndael, возможно, вернемся в одной из следующих статей.Алгоритм Serpent

Как было сказано выше, алгоритм Serpent разработан тремя известнейшими криптологами: Россом Андерсоном, Эли Бихамом и Ларсом Кнудсеном. Каждый из них знаменит своими криптоаналитическими работами, а также разработанными ранее алгоритмами шифрования (например, широкую известность получили алгоритмы Bear и Leon, разработанные Андерсоном и Бихамом [2]; не менее известен алгоритм Square, разработанный авторами алгоритма Rijndael Джоан Деймен (Joan Daemen) и Винсентом Риджменом (Vincent Rijmen) при участии Ларса Кнудсена [8]). Именно Эли Бихама без преувеличения можно назвать величайшим криптоаналитиком современности — его авторству (часто в соавторстве с другими специалистами) принадлежит множество работ, посвященных методам вскрытия различных известных алгоритмов шифрования.

Еще до конкурса AES появился алгоритм Serpent-0, отличающийся от присланного на конкурс алгоритма Serpent-1 (или просто Serpent) только тем, что в нем были использованы таблицы замен алгоритма DES (в незначительно модифицированном виде). В Serpent используются уже оригинальные таблицы замен, которые, по словам авторов [3], вкупе с незначительным изменением процедуры расширения ключа усилили алгоритм против дифференциального и линейного криптоанализа.

Рассмотрим здесь именно тот алгоритм Serpent, который был прислан на конкурс AES и стал одним из его финалистов.

Структура алгоритма

Serpent представляет собой SP-сеть, в которой блок данных в процессе шифрования разбивается на 4 субблока по 32 бита (см. рис. 1) [3].

Алгоритм выполняет 32 раунда преобразований; перед первым раундом выполняется начальная перестановка IP, после заключительного раунда — финальная перестановка FP. Начальная перестановка определена следующим образом:

Это означает, что бит 0 остается на своем месте, бит 32 входного значения становится битом 1, бит 64 — битом 2 и т.д.

Финальная перестановка является инверсной начальной перестановке и выглядит так:

В каждом раунде используется одна и та же таблица; всего же в алгоритме определены 8 таблиц замен S₀. S₇, которые циклически используются в 32 раундах шифрования:

Ячейки таблицы содержат выходные значения; входное значение определяет требуемый номер столбца. Например, таблица S₀ меняет 0 на 3, 1 на 8 и т.д.

Каждая ячейка таблицы соответствует биту выходного значения (от 0 до 127); в ячейке перечислены входные биты, XOR которых дает выходное значение. Например:

Линейное преобразование может быть реализовано как в виде приведенной таблицы, так и с помощью следующих вычислений (см. рис. 2):

Операция g() обрабатывает 32-битных входной субблок выполнением перечисленных ниже шагов (см. рис. 4):

где g₀. g₃ — байты выходного значения функции g().
Умножение выполняется в конечном поле GF(2 8 ) с образующим полиномом x 8 + x 6 + x 5 + x 3 + 1.
Матрица M₁ определена следующим образом (здесь и далее в таблицах указаны шестнадцатеричные значения):

В конце каждого раунда, за исключением последнего, субблоки A (значение до описанной выше обработки) и C меняются местами; субблоки B (значение до обработки) и D также меняются местами.

Перед первым раундом выполняется входное отбеливание — наложение операцией XOR на обрабатываемые субблоки четырех фрагментов расширенного ключа K₀. K₃. Аналогично выполняется выходное отбеливание — после последнего раунда с использованием подключей K₄. K₇.

Как видно, алгоритм Twofish имеет существенно более сложную структуру, чем Serpent, что компенсируется вдвое меньшим количеством раундов.

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

Процедура расширения ключа формирует 40 32-битных подключей для использования в 16 раундах алгоритма и для выполнения операций отбеливания. Кроме того, на основе ключа шифрования вычисляются таблицы замен S₀. S₃.

Аналогично алгоритму Serpent, Twofish использует ключи шифрования любого размера до 256 бит включительно. Однако, дополнение ключа выполняется несколько иначе: исходный ключ, при необходимости, дополняется нулевыми битами до ближайшего стандартного размера, т.е. до 128, 192 или 256 бит. Процедура расширения ключа обрабатывает дополненный таким образом ключ.

Сначала выполняется предварительная обработка ключа, включающая в себя следующие шаги:

Матрица M₂ определена следующим образом:

Генерация подключей k₀. k₃₉ производится на основе вычисленных на предварительном этапе массивов M_e и M_o следующим образом:

а функция h() заслуживает подробного описания.

Данная функция схематично представлена на рис. 5.

Она выполняется в несколько шагов, состав которых зависит от размера дополненного ключа в 64-битных фрагментах, т.е. от описанного выше значения k. В качестве параметров функция h() принимает 32-битное слово и массив 32-битных слов размерностью k. Последовательность выполнения такова:

где x — входное значение,
y — выходное значение,
>>>₄ — операция циклического вращения вправо 4-битных величин, т.е. раздельное вращение каждого нибла обрабатываемого байта;
t_i — табличные замены, различные для q₀ и q₁; для q₀ таблицы выглядят так:

Выходное значение таблицы берется из позиции, соответствующей входному значению; например, t₁ заменяет 0 на E, 1 на C и т.д.

Таблицы для q₁ определены следующим образом:

Осталось описать зависимость от ключа таблиц замен S₀. S₃. Фактически, в алгоритме шифрования вместо описанной выше функции g() используется функция h(), использующая в качестве входного значения 32-битный субблок A или B, а в качестве входного массива — описанный ранее массив V. Таким образом, замена выполняется на основе тех же таблиц t₀. t₃, которые используются в процедуре расширения ключа.

Видно, что процедура расширения ключа является сложной и занимает несравнимо больше времени, чем шифрование одного блока данных. Авторы алгоритма в его спецификации [16] описали несколько возможных вариантов оптимизации процедуры расширения ключа, один из которых можно выбрать в конкретной реализации алгоритма, исходя из следующих параметров:

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

Twofish-FK

Помимо описанного выше «стандартного» варианта алгоритма Twofish, авторы предложили еще и Twofish Family Key (или Twofish-FK) — шаблон для формирования на основе Twofish вариантов алгоритма, несовместимых между собой и предназначенных, таким образом, для ограниченных применений, например, в рамках конкретных организаций для защиты внутреннего документооборота.

Несовместимость вариантов достигается путем применения дополнительного ключа (FK), константного для всех субъектов, применяющих конкретный из вариантов алгоритма Twofish-FK. Т.е. конкретное значение используемого FK формирует некий «контур совместимости» криптосредств, реализующих Twofish-FK.

где E_FK(N) — результат зашифрования алгоритмом Twofish на ключе FK 128-битного блока, первый байт которого содержит значение N, а остальные байты обнулены,
| — операция конкатенации.

Источник