Что такое aes 256

Как устроен 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 — американский стандарт шифрования. Часть III

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

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

Одно из основных старых (или даже старинных) требований к шифрам — это создавать открытый (доступный для изучения) алгоритм шифрования и накрутки вокруг него (режимы, протоколы и т. п.) всё, кроме ключа шифра. Ключ — это то, что должно сохраняться в строжайшей тайне от всех. При этом ключ не обязательно имеет гриф «Секретно». Предел такого условия — ключом владеет только получатель шифрграммы, он сам в принципе и должен его устанавливать.

Для симметричных систем шифрования это условие невыполнимо. И в этом принципиальное отличие асимметричных (двухключевых) систем от симметричных, в которых источник утечки информации о ключе может быть не единственным. Ранее отмечалось, что АЕS — упрощенная версия шифра RIJNDAEL, а здесь местами будем использовать полную версию.

Алгоритм формирование ключей шифра AES (Key Schedule). Общие положения и принцип

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

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

Выбранный двоичный вектор называют ключом шифра и его преобразуют в «квадрат» из 4×4=16 байтов. Далее из него формируют с применением двух спецпроцедур раундовые ключи, которые используются в процессах зашифрования/расшифрования, о которых подробно рассказывается здесь.

Одна процедура названа расширение ключа (Key Expansion), другая — выбор раундового ключа (Round Key Selection). Расширению подвергается выбранный случайный двоичный вектор с фиксированной длиной. Важно также внимательно отнестись к выбору датчика случайных чисел, провести его тестирование и апробацию.

Расширение ключа

Смысл расширения исходного (выбранного) ключа состоит в его разбиении не блоки (по 32 бита) и далее порождении из них множества новых блоков такой же длины для каждого раунда.
Итак, пусть выбран (128 бит) ключ шифра AES = 2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3c, для Nk = 4, который представлен блоками по 4 байта и его начальное раундовое расширение имеет вид w[0] = 2b7e1516; w[1] = 28aed2a6; w[2] = abf71588; w[3] = 09cf4f3c. Символом w[i] в таблице КК, i = 0(1)43, обозначен столбец из 4 байтов раундового ключа.

Сеанс шифрования представляет собой подготовку и алгоритмическое преобразование сообщения, например, письма. Текст письма в битовом представлении разбивается на блоки фиксированной длины Nb = 128, 192 или 256 бит. В стандарте AES длина блока только 128 бит.

Затем каждый блок представляется квадратом или (прямоугольником с 4-мя строками) и шифруется отдельно за фиксированное число раундов Nr = Nr (Nb, Nk), которое является, функцией двух переменных: длины блока Nb и длины ключа Nk, которые независимо могут принимать значения 128, 192, 256 бит.

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

Раундовые ключи формируются из ключа шифрования по специальному алгоритму, который включает в себя процедуру расширения ключа (Key Expansion) и процедуру выбора раундового ключа (Round Key Selection). Задание раундовых ключей непосредственно, минуя эти процедуры, недопустимо.

Сущность и цель первой процедуры — преобразовать заданный исходный ключ шифрования в более длинный, расширенный ключ (Expanded Key). Полное число бит расширенного ключа, из которого выбираются раундовые ключи, определяется произведением K = Nk (Nr + 1) – число бит блока ключа умножается на число раундов, увеличенное на единицу.

Пример 1. Пусть Nb = Nk = 4, заданы блоки длиной по 4×32 = 128 бит, тогда Nr = 10.
Длина К в битах для расширенного ключа K = 128∙11 = 1408 бит.

Вторая процедура (RoundKey Selection) представляет собой последовательную выборку 32Nk, т. е. 4-х 32-разрядных слов из расширенного ключа, т. е. первый раундовый ключ представлен начальными вновь сформированными Nk словами, второй раундовый ключ – следующими Nk словами и так до последнего раунда.

Пример 2. При тех же исходных данных (смотри предыдущий пример) полная длина расширенного ключа в байтах содержит Nk (Nr + 1) = 4∙11 = 44 четырехбайтовых слова W( i ),
i=0(1)Nk(Nr + 1) – 1. Строки таблицы КК нумеруются натуральными числами. Первая строка имеет номер 4, так как 4 строки (с номерами 0,1,2,3) с ключом шифра в таблицу КК не включаются.

Таблица Ключ шифра АЕS для всех 10 раундов (см. таблицу КК ниже).

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

Приведем пример заполнения первой с номером i = 4 строки таблицы КК. Левая колонка — текущие номера строк начинаются значением (4) так как первые 0,1,2,3 значения в таблицу не включены. Вообще индекс (номер строки) i пробегает значения i=0(1)Nk(Nr+1)-1 или i=0(1)43 всего 44 слова из 32 разрядов.

В колонку temp помещается значение w[i-1] = 09cf4f3c и вращением (циклическим сдвигом одного байта) RotWord() получим значение CF4F3C09, которое помещается в 3-ю колонку.В 4-ой колонке помещен результат 8А84ЕВ01 замены байтов SubBytes значений из 3-й колонки, т. е. СF→ 8А; 4F → 84; 3C →ЕВ; 09 → 01=>8А84ЕВ01.

Каждая 4-я строка таблицы в 5-й колонке заполняется значением Rcon[i/Nk], константой, вычисляемой по формуле Rcon(J)=01000000, j= [i/Nk] = 2 j-1 = 2 0 = 1) записывается значение 01 00 00 00 из 4-х байтовых слов, первый байт которого равен 2 0 = 1, т.е. 0000 0001₂, остальные байты этого 32-разрядного слова – нулевые.

Поле колонки 6 содержит сумму (XOR) полей 4-го и 5-го 8А84EB01+ 01000000 =8B84EB01;
Поле колонки 7 содержит W[i — Nk] =W[4 — 4] = W[0] =2B7E1516;
Поле колонки 8 содержит сумму полей колонок 6 и 7 W[i=4] =8А84EB01+2B7E1516 =A0FAFE17;
А теперь подробно и с деталями рассмотрим названные процедуры.

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

Последующие i-е слова образуются рекурсивно из предыдущих слов в соответствии с выражением, в котором суммирование есть XOR.

.

Для слов W[i] ключа, индекс которых кратен Nk, значения W[i-1] подвергаются перед выполнением операции XOR дополнительному преобразованию. Это преобразование описывается следующим образом.

Описание преобразования содержит функции:

RotWord() – побайтовый циклический сдвиг 32-разрядного слова a(0)a(1)a(2)a(3) по правилу
→ ;

Выделены позиции кратные Nb, значения в которых формируются с использованием функции SubWord( ), RotWord( ), Rcon( ). Позиции W[0] –W[3] заполняются по заданным исходным данным, все последующие – рассчитываются по соотношению для W[i].

Выбор раундового ключа (Round Key Selection)

Выбор раундового ключа (RoundKeySelection). Для текущего раунда с номером r. Раундовый ключ выбирается как ,
r = 1(1)Nr.

Здесь отметим, что общий алгоритм шифрования предусматривает разные варианты наборов переменных Nb, Nk, Nr. Для конкретной реализации фиксированного варианта она может быть существенно упрощена. Вычисление раундового ключа можно выполнять «на лету», что не требует большой памяти для хранения всей последовательности W. Можно ограничиться буфером из Nk слов.

Пример 3. Поясним приведенные теоретические положения числовым примером. Пусть, как и ранее, Nb = Nk = 4, Nr = 10. Ключ шифра задан в виде 16-ричной последовательности K = 2b7e1516 282ed2a6 abf71588 09cf4f3c

Архитектура «квадрат» и байт ориентированные вычисления определяют форму их представления следующей таблицей.

В таблице добавлена левая колонка — номер ( r) раунда
В первой строке r = 1, i = 4 в третью графу записывается предшествующий байт W[i-1] = W[3], т.е. последний байт из K ключа шифра. Так как индекс i = 4 кратен Nk= 4, то в графу 6 пишем (Rcon(J)=01000000, j= [i/Nk] = 2 j-1 = 2 0 = 1) записывается значение 01 00 00 00 4-х байтового слова, первый байт которого равен 2 0 = 1, т.е. 0000 0001, остальные байты этого 32-разрядного слова – нулевые.

В четвертую графу таблицы вписываем значения из предыдущей графы, но циклически сдвинутые на 1 байт влево (ротацию слова – RotWord). В пятую графу вписывается результат побайтной замены значений предыдущей графы на значения байтов из S – блока (функция SubWord – замены байтов). После этого выполняется сложение по mod2 (XOR) содержимого графы 5 и 6, 8a84eb01+ 0100 0000 = 8b84eb01, а результат суммирования заносится в графу 7.

В двоичном представлении байта 0000 0001₂ = 01₁₆ младшие разряды располагаются справа.

В графу 8 вписано значение слова W[i-Nk ] = W[0] (для первой строки это значение первого (левого байта) 4-х байтового слова ключа W[0] шифрования), которое операцией XOR суммируется 8b 84 eb 01+2b 7e 15 16 = a0 fa fe 17 с содержимым 7 графы. Результат суммирования (графа 9) как раз и является первым из четырех, 4-х байтовым словом раундового ключа первого раунда.

Другие три слова раундового ключа первого раунда формируются без использования функции циклического сдвига, замены и Rcon[j], так как их номера не кратны Nk. Содержимое графы 9 переносится в третью графу следующей строки таблицы.

Определение Rcon[j]. Эта процедура выполняется по специальному алгоритму, действия которого будем иллюстрировать примерами. Аргумент j функции Rcon[j] – целочисленный и определяется по текущему значению переменной i – номеру слова ключа. Очевидно
j = 1, 2, 3, … при i = Nk, 2Nk, 3Nk,….

Поскольку Nk в нашем примере равно 4, то целочисленные значения j имеем при i = 4, 8, 12. Далее для каждого целочисленного j Rcon[j] = 2 j-1 = 1, 2, 4, 8, 16, ….
Удвоение значений допустимо до тех пор, пока Rcon[j] является элементом поля GF(2 8 ).

При i > 32 получаем j > 8. Значения, выходящие за пределы поля, необходимо возвращать в поле. Это достигается приведением многочленного представления элементов поля Rcon [j](modφ(x)).

Пример 4. Пусть i = 32, 36, 40. Тогда j = 8, 9, 10. Эти значения выходят за пределы поля. Возвращаем их в поле путем редукции по модулю φ(x) и вычисляем требуемые значения.
Определим соответствующие значения Rcon [j]. Результаты вычислений сведем в таблицу.

Источник