что такое 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.

Источник

Лучший в своем классе: история появления стандарта шифрования AES

C мая 2020 года в России стартовали официальные продажи внешних винчестеров WD My Book, поддерживающих аппаратное шифрование AES с 256-битным ключом. В силу законодательных ограничений, ранее подобные устройства можно было приобрести лишь в зарубежных интернет-магазинах электроники либо на «сером» рынке, однако теперь обзавестись защищенным накопителем с фирменной 3-летней гарантией от Western Digital может любой желающий. В честь этого знаменательного события мы решили сделать небольшой экскурс в историю и разобраться, как появился Advanced Encryption Standard и чем же он так хорош по сравнению с конкурирующими решениями.

Долгое время официальным стандартом симметричного шифрования в США являлся DES (Data Encryption Standard — стандарт шифрования данных), разработанный компанией IBM и внесенный в перечень Федеральных стандартов обработки информации в 1977 году (FIPS 46-3). В основу алгоритма легли наработки, полученные в ходе исследовательского проекта под кодовым названием Lucifer. Когда 15 мая 1973 года Национальное бюро стандартов США объявило о проведении конкурса, целью которого стало создание стандарта шифрования для госучреждений, американская корпорация включилась в криптографическую гонку с третьей версией Люцифера, использовавшей обновленную сеть Фейстеля. И наряду с другими конкурсантами потерпела фиаско: ни один из алгоритмов, представленных на первый конкурс, не соответствовал строгим требованиям, сформулированным экспертами НБС.

Разумеется, в IBM не могли просто так смириться с поражением: когда 27 августа 1974 года конкурс был перезапущен, американская корпорация вновь подала заявку, представив улучшенную версию Lucifer. На сей раз у жюри не оказалось ровным счетом ни одной претензии: проведя грамотную работу над ошибками, IBM успешно устранила все недочеты, так что придраться оказалось не к чему. Одержав убедительную победу, Люцифер сменил имя на DES и уже 17 марта 1975 года был издан в Федеральном реестре.

Однако в ходе открытых симпозиумов, организованных в 1976 году с целью обсуждения нового криптографического стандарта, DES подвергся жесткой критике со стороны экспертного сообщества. Причиной этого стали изменения, внесенные в алгоритм специалистами АНБ: в частности, была уменьшена длина ключа до 56 бит (изначально Lucifer поддерживал работу с 64- и 128-битными ключами), а также изменена логика работы блоков перестановки. По мнению криптографов, «улучшения» не имели смысла и единственное, к чему стремилось Агентство национальной безопасности, внедряя модификации, — получить возможность беспрепятственно просматривать зашифрованные документы.

В связи с перечисленными обвинениями, при Сенате США была создана специальная комиссия, целью работы которой стала проверка обоснованности действий АНБ. В 1978 году по итогам расследования был опубликован доклад, в котором сообщалось следующее:

В то же время ограничение на длину ключа оказалось проблемой, и притом весьма серьезной, что в 1998 году убедительно доказала общественная организация Electronic Frontier Foundation (EFF) в рамках эксперимента DES Challenge II, проведенного под эгидой RSA Laboratory. Специально для взлома DES был построен суперкомпьютер, получивший кодовое название EFF DES Cracker, над созданием которого трудились Джон Гилмор, сооснователь EFF и руководитель проекта DES Challenge, и Пол Кочер, основатель компании Cryptography Research.

Процессор EFF DES Cracker

Разработанная ими система смогла успешно подобрать ключ к зашифрованному образцу методом простого перебора всего за 56 часов, то есть менее чем за трое суток. Для этого DES Cracker потребовалось проверить около четверти всех возможных комбинаций, а это значит, что даже при самом неблагоприятном стечении обстоятельств на взлом уйдет около 224 часов, то есть не более 10 суток. При этом стоимость суперкомпьютера, с учетом затраченных на его проектирование средств, составила всего 250 тысяч долларов. Нетрудно догадаться, что сегодня взломать подобный шифр еще проще и дешевле: мало того, что железо стало куда мощнее, так еще и благодаря развитию интернет-технологий хакеру вовсе не обязательно покупать или арендовать необходимое оборудование — вполне достаточно создать ботнет из зараженных вирусом ПК.

Данный эксперимент наглядно продемонстрировал, насколько DES морально устарел. А поскольку на тот момент алгоритм использовался в составе практически 50% решений в области шифрования данных (по оценке все той же EFF), вопрос о поиске альтернативы встал как никогда остро.

Новые вызовы — новый конкурс

Справедливости ради стоит сказать, что поиски замены для Data Encryption Standard начались практически одновременно с подготовкой EFF DES Cracker: Национальный институт стандартов и технологий (NIST) США еще в 1997 году объявил о запуске конкурса алгоритмов шифрования, призванного выявить новый «золотой стандарт» криптобезопасности. И если в былые времена аналогичное мероприятие проводилось исключительно «для своих», то, памятуя о неудачном опыте 30-летней давности, в NIST решили сделать конкурс полностью открытым: в нем могли принять участие любая компания и любое частное лицо, независимо от места дислокации или гражданства.

Такой подход оправдал себя еще на этапе отбора претендентов: среди авторов, подавших заявку на участие в конкурсе Advanced Encryption Standard, оказались и всемирно известные криптологи (Росс Андерсон, Эли Бихам, Ларс Кнудсен), и небольшие IT-компании, специализирующиеся на кибербезопасности (Counterpane), и крупные корпорации (немецкая Deutsche Telekom), и образовательные учреждения (Лёвенский католический университет, Бельгия), а также стартапы и небольшие фирмы, о которых мало кто слышал за пределами их стран (например, Tecnologia Apropriada Internacional из Коста-Рики).

Интересно, что в этот раз в NIST утвердили всего два основных требования к алгоритмам-участникам:

Прием заявок на конкурс Advanced Encryption Standard продлился полтора года. Всего в нем приняли участие 15 алгоритмов:

В случае с «богом войны» эксперты отметили идентичность процедуры шифрования и дешифровки данных, однако этим его преимущества и ограничились. Алгоритм IBM вышел на удивление прожорливым, что делало его неподходящим для работы в условиях ограниченных ресурсов. Наблюдались проблемы и с распараллеливанием вычислений. Для эффективной работы MARS нуждался в аппаратной поддержке 32-битного умножения и вращения на переменное число бит, что опять же накладывало ограничения на перечень поддерживаемых платформ.

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

Алгоритм унаследовал часть преобразований от своего предшественника, RC5, тщательно исследованного ранее, что в сочетании с простой и наглядной структурой делало его полностью прозрачным для экспертов и исключало наличие «закладок». К тому же RC6 демонстрировал рекордные скорости обработки данных на 32-битных платформах, а процедуры шифрования и дешифровки были реализованы в нем абсолютно идентично.

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

Twofish

Twofish оказался довольно шустрым и хорошо оптимизированным для работы на маломощных устройствах, отлично справлялся с расширением ключей и предполагал несколько вариантов реализации, что позволяло тонко адаптировать его под конкретные задачи. В то же время «две рыбки» оказались уязвимы к атакам по сторонним каналам (в частности, по времени и потребляемой мощности), не особо дружили с многопроцессорными системами и отличались чрезмерной сложностью, что, кстати, сказалось и на скорости расширения ключа.

Serpent

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

Источник

Описание основ криптопреобразования 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 (Advanced Encryption Standard)

Однажды я проверял за переводчиком проект по СХД, и там было такое предложение:

Data can be automatically encrypted inside disk storage systems using high-security 128-bit AES technology …

Переводчик ничтоже сумняшеся выдал перевод, в котором значилось следующее:

Удалось найти достойное видео на английском, где работа алгоритма разложена по полкам — некоторые вещи опущены, но по крайней мере после его изучения, переводчик уже не будет задумываться о том, разряды там или биты.

Мы его транскрибировали и перевели, оно ниже, с незначительными купюрами. Желаю приятного чтения.

1. Предисловие

— … ты слышал название Rijndael?

— Нет? Возможно, такая подача материала может кого-то раздражать, но мне удалось в предыдущем видео про историю AES ни слова не сказать о том, как этот алгоритм работает.

Что ж… Давай начнем с некоторых чисел, которые мы вскользь упомянули в последнем видео. AES – это симметричный алгоритм блочного шифрования, который оперирует блоками по 128 бит.

Это значит, что AES берет 128 бит исходного сообщения и превращает их с помощью некоего ключа в 128-битный шифротекст. Размер ключа может быть 128, 192 или 256 бит.

Поэтому уровень безопасности разнится от надежного до, как мне кажется, чрезмерно надежного.

Если вы обнаружите, что ваш браузер использует 128 бит, это нормально. Ключ такого размера был указан как часть AES, поэтому алгоритму Rjjndael этого должно быть достаточно. Просто представьте: у нас есть 16 байтов, или 128 бит, мы что-то с ними делаем и получаем шифротекст. И поскольку все происходит в SP-сети, то есть подстановочно-перестановочной, мы что-нибудь подставим, или применим метод конфузии, и что-нибудь переставим, переместим элементы, чтобы также использовать метод диффузии. Вы же не хотите, чтобы у вас было как в Энигме — один байт на входе и один на выходе, ибо это очень легко поддается криптоанализу, и история это подтверждала неоднократно.

2. Деление на блоки.

Итак, вместо длинных рядов бит или байтов, как в большинстве алгоритмов шифрования, в AES элементы организованы в матрицы 4 на 4 по 128 бит. Получается, нас есть сообщение размером 128 бит или 16 байтов в виде матрицы 4 на 4.

Каждый раз, когда я рисую матрицу, получается как-то так.

В первой ячейке будет байт 0, здесь байт 1, байт 2, байт 3, затем 4, 5, 6, 7, то есть байты размещаются по столбцам сверху вниз.

Иными словами, мы берем 128 бит нашего сообщения и расписываем его в таком порядке.

Затем мы начнем применять к ним функции SP-сети: переставлять элементы и подставлять байты на место других, то есть мы собираемся трансформировать исходное сообщение таким образом, чтобы взломщики не могли его прочитать.

В алгоритме AES происходит несколько разных операций, но запомните, что все они совершаются в матрице 4 на 4. Так что же мы будем делать? Мы работаем с SP-сетью, поэтому мы совершим подстановки и перестановки элементов с помощью разных команд и потом в определенный момент добавим наш ключ.

3. Наложение фрагмента ключа через XOR

Итак, это наш открытый текст и, в первую очередь, мы берем часть нашего ключа и совершаем сложение по модулю 2, или функцию XOR.

Как вы помните, мы используем наш ключ между раундами. Именно он обеспечивает секретность, так как остальная часть алгоритма есть в открытом доступе. Давайте рассмотрим раунд шифрования.

Всё это и есть один раунд.

Единственное, что стоит упомянуть, MixColumns применяется на всех раундах кроме последнего, потому что на последний раунд эта функция уже не влияет. Эта команда просто переставляет элементы выходных данных, но к этому моменту байты уже достаточно перемешаны. То есть в каждом раунде повторяются все этапы, и только на последнем пропускается MixColumns.

Если размер вашего ключа 128 бит, у вас 10 таких раундов, если 192 бита – 12 раундов, если 256 бит – 14 раундов.

Но имейте в виду, что алгоритм раундов один и тот же, так же между раундами применяется функция XOR в AddRoundKey. Мы не используем каждый раз один и тот же ключ. Как я объяснял в видео про SP-сеть, мы берем исходный ключ, расширяем его с помощью так называемого расписания ключей (key schedule) и создаем разные раундовые ключи.

Таким образом, у нас получится ключ 0, затем ключ 1, ключ 2 и так далее, в зависимости от того, какой раунд мы рассматриваем, то есть в каждом раунде используется часть расширенного ключа.

Мы не будем подробно говорить о расписании ключей, это довольно простой процесс и, подразумевается, что, прежде всего, он должен быть быстрым. KeyExpansion берет ваш исходный ключ и расширяет его настолько, чтобы его можно было использовать в разных раундах. Итак, это был очень коротенький обзор алгоритма AES.

4. О сложении: XOR и поля Галуа

Развернутое описание намного лучше этой простой схемы. Я даже не могу выразить, насколько настоящий алгоритм лучше того варианта, который я изобразил в своем видео про SP-сеть. Вот мы подставили, переставили, перемешали элементы, и далее мы собираемся делать это снова и снова, пока не получим шифротекст.

Полагаю, возникает вопрос: что происходит на каждом из этих этапов? Для меня алгоритм AES изящен именно потому, что он не использует операции, которых можно было бы от него ожидать.

Конечно, XOR повсеместно применяется в криптографии, но на самом деле все операции в AES по сути своей математические и производятся над так называемым конечным полем.

Мы уже немного рассказывали о конечных полях или полях Галуа в своем видео про кодирование с помощью кода Рида – Соломона (Reed Solomon encoding).

Смысл заключается в использовании теории поля Галуа для конечных полей и выполнении множества длинных делений и сложений чисел в пределах этого поля.

Например, у вас есть некоторое количество элементов, скажем, все числа от 0 до 10, например, и у вас есть различные операции, которые можно выполнять в пределах этого поля. Таким образом, в Rjjndael у нас поле Галуа из 2’8 элементов.

А затем в этом поле можно производить сложение, вычитание, умножение и деление или вычисление мультипликативного обратного X’-1.

Важно помнить о конечном поле, если мы не будем углубляться в математику, что 2’8 элементов – это 16 байтов, так что каждый из элементов в этом поле Галуа – это байт. Так что мы начинаем с 00000000 и движемся к 11111111. Таким образом, в этом конкретном конечном поле 256 таких элементов.

Если мы берем наше изначальное сообщение, нужно знать, даже если вы не взглянете на него снова, что какую бы операцию мы с ним не проводили, мы получим другой элемент их этого поля. Мы никогда не выходим за пределы поля, ни за верхнюю, ни за нижнюю границу, знаете ли, и не уходим в отрицательные числа или что-то в этом роде, здесь нет чисел с плавающей запятой и ничего подобного. Если мы берем одно из чисел и добавляем его к другому, то находим третье в пределах поля. Точно также, если мы умножаем или наоборот вычисляем мультипликативный обратный, или делим, мы переходим к другому числу. Поле Галуа довольно удобно для построения шифра на его основе, потому что большинство действий имеют свою противоположность, например, сложение и вычитание отменяют друг друга, так же как умножение и вычисление мультипликативного обратного или деление, и мы можем перемещаться по этому полю. Но мы всегда остаемся в пределах наших байтов. Если мы представляем путь данных в AES в виде матрицы 4 на 4, это наш 128-битный блок, и мы можем совершать операции в пределах этого конечного поля, и после всех действий мы всё еще будем в нем.

Количество бит не увеличится до 130 или 140, и никакой подобной катастрофы не произойдет.

Так вот, вернемся к схеме, и, держа ее в голове, поговорим о том, что делает каждая функция.

5. Внутри раунда. Операция 1: SubBytes

SubBytes – наш блок подстановки, это буквально таблица преобразования, причем хитро разработанная. Создатели просто ее придумали. Каждый байт связан с другим байтом из S-блока в зависимости от их функции в этом поле. Но гораздо важнее, что с помощью некоторых свойств ее постарались сделать как можно более сложной. Так что она очень нелинейная, и трудно представить в виде математической функции ее саму и ее действие. В общем, давайте просто попробуем, и тогда мы сможем ее обсудить.

Итак, у нас есть наша матрица, давайте пока отложим нашу схему… у нас есть наша матрица (нам нужно было бы нарисовать ее много раз). Пишем байт 0, байт 1, и так до байта 15.

Теперь мы берем первый байт, ищем ему замену в нашей таблице и подставляем эту замену на его место. Теперь наш подставленный байт выглядит вот так.

И мы собираемся проделать это с каждым байтом по отдельности. Чтобы сделать эту функцию еще более запутанной, ее разработали таким образом, чтобы не было фиксированных точек, то есть ни один байт не остается на месте. Если мы берем байт 15, мы не можем подставить его на то же место.

Точно также нет никаких фиксированных точек с противоположным значением, то есть биты заменяются по другому принципу. Например, противоположное число для 1010 – это 0101, и так для всего байта.

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

6. Внутри раунда. Операция 2: ShiftRows

Мы взяли наш открытый текст, применили часть нашего раундового ключа, то есть наш первоначальный ключ, и затем в начале раунда мы сделали подстановку, используя S-блок. После этого мы собираемся сдвинуть строки с помощью функции ShiftRows.

На самом деле это просто. С первым рядом мы ничего не делаем.

Второй ряд мы передвинем на один шаг влево. Тогда байт 1 пройдет весь путь в конец строки, потому что элементы движутся по кругу. Этот байт движется сюда, этот – сюда, а этот – сюда. А первый, очевидно, движется в конец строки.

Этот ряд тоже движется, но уже на два шага влево. Так что этот байт движется сюда, этот – сюда, этот – в конец ряда и так далее, а четвертый ряд сдвигается на три шага влево, результат такой же, как если бы этот ряд сдвигался вправо на один шаг.

Так что этот байт движется вот сюда, этот – сюда и так далее.

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

Итак, мы просто берем байты и переставляем их в другое место в пределах матрицы. Теперь мы подходим к функции MixColumns, которая следует за SubBytes.

7. Внутри раунда. Операция 3: MixColumns

Когда мы переставили байты из одних столбцов в другие, мы собираемся взять каждый из столбцов и смешать все их элементы.

Мы возьмем первый столбец и смешаем байты в нем, а потом отдельно второй, третий и так далее. Так что это операция производится в пределах столбца. Этот байт переместился сюда, а затем перемешался с другими элементами в этом столбце. Этот передвинулся сюда и перемешался с другими элементами в этом столбце. Таким образом, эти две операции в тандеме хорошенько всё перемешивают, если представить это с технической точки зрения. Здесь используется матричное умножение.

Давай просто оторвем еще один листочек. Нам сегодня нужно много бумаги. Возьмем один столбец с элементами, например, С0, С1, С2, С3 и умножим его как вектор на матрицу.

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

Эти числа достаточно велики и настолько перемешаны, что здесь происходят довольно интересные процессы, но одновременно эти числа и достаточно малы, чтобы процессы происходили быстро, как в более сложных реализациях и тому подобное. Если бы в матрице вместо 2 было бы 50, все происходило бы медленнее.

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

Мы повторяем этот процесс, чтобы получить все остальные значения.

В конце концов после всех перемешиваний, перемещений и переставлений мы получаем новый столбец с битами и байтами.

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

Наша операция сложения – это XOR, а умножение – это умножение внутри конечного поля по модулю многочлена. Остальные подробности мы обсудим как-нибудь в другой раз.

8. Заключение

А сейчас, давайте еще раз проговорим весь алгоритм сначала:

Мы подставим некоторые байты на место других, используя хорошо продуманный S-блок. Затем мы сдвинем элементы в строке и после этого смешаем элементы в столбцах.

Мы подставим, а затем переставим наши данные в матрице, причем после каждого раунда будем добавлять раундовый ключ, который в данном случае выполняет функцию XOR, а затем будем повторять весь процесс, кроме последнего раунда, где мы не тратим время на смешивание столбцов, потому что это уже не нужно. В конце мы добавляем наш последний раундовый ключ, и на этом все.

В результате мы получаем 128-битный блок полной неразберихи. Этот алгоритм можно описать как некую случайную перестановку. AES как будто берет блок входных данных и в случайном порядке производит выходные данные, но, на самом деле, очевидно, что порядок преобразований во многом зависит от ключа. Если у вас есть ключ, вы можете также расшифровать текст. Для каждой функции алгоритма существует противоположная, которую мы можем применить, чтобы запустить обратный процесс.

9. Post Scriptum

— Скажи, а этот алгоритм когда-нибудь дает сбои?

— Просто кажется, что в нем так много этапов и так много составляющих.

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

Одна из главных особенностей AES как стандарта заключается в эффективности использования ЦП. Существуют расширенные инструкции AES по выполнению одного раунда, последнего раунда и т. д. для микропроцессоров Intel и других производителей. Эти процессоры невосприимчивы к такого рода атакам, и они невероятно быстрые. Если использовать AES на процессоре, который оптимизирован под такие задачи, с помощью правильных инструкций, то можно рассчитывать на шифрование со скоростью гигабит в секунду, что весьма быстро. Поэтому в BitLocker или в каком-нибудь шифровании диска вы даже глазом не успеете моргнуть. Вы кликнули файл, и процессор тут же расшифровал его и показал вам, прежде чем вы смогли осознать, что произошло. Это всё благодаря скорости процессов.

Может быть, мы еще немного поговорим о полях Галуа, потому что, мне нравится, когда говорят… Прежде всего, пожалуйста, поищите Галуа, Эвариста Галуа в Википедии, потому что он очарователен.

— Разве он не погиб на дуэли?

Да, в 20 лет он погиб на дуэли. Он опубликовал три знаковые работы по конечным полям, многочленам и прочим вещам. Я не математик и не знаю всей истории. Но дело в том, что этот парень…

На этом загадочном моменте видео обрывается, и мы заканчиваем свою историю про неряшливый перевод.

Полагаем, из этих объяснений стало понятно, что ни о каких разрядах там речь не идет, а речь исключительно о перемешивании битов в несколько раундов.

Надеемся, было познавательно.

Ирина Мирошникова (транскрибация), Светлана Дугинова (перевод), Евгений Бартов (выбор сюжета, вступление, редактура), Галина Таранова (оформление)

Источник