Как стать автором
Обновить

AES — американский стандарт шифрования. Часть III

Время на прочтение 7 мин
Количество просмотров 7.5K
image



Мотивом к публикации столь подробных текстов об 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 раундов используется свой заблаговременно сформированный, либо непосредственно вычисляемый, раундовый ключ {w[i]}.

Раундовые ключи формируются из ключа шифрования по специальному алгоритму, который включает в себя процедуру расширения ключа (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] = 2j-1 = 20 = 1) записывается значение 01 00 00 00 из 4-х байтовых слов, первый байт которого равен 20 = 1, т.е. 0000 00012, остальные байты этого 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)


Рассмотрим в подробностях процедуру формирования расширенного ключа (Expanded Key) из исходного ключа шифра. Формально расширенный ключ W будем описывать последовательностью содержащихся в последней колонке таблицы КК блоков W[i], i=0(1)Nk(Nr+1)-1, 4-байтовых слов (раундовых ключей), в которой первые Nk 32-разрядных слова представляют исходный ключ, т. е.
W = {W[0], W[1], W[2], W[3], W[4], …, W[K-1]}

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

.

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

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

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

SubWord( ) – побайтовая замена а( j ) на элементы S-блока функции SubBytes( ), например, байт (a f) заменяется на байт s(a, f) из S-блока; действие аналогичное как при обработке сообщения,
Rcon[j] – слагаемое XOR равно 2j-1.


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

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


Выбор раундового ключа (RoundKeySelection). Для текущего раунда с номером r. Раундовый ключ выбирается как {W[Nb( r)-1], …, W[Nb(r+1) – 1]},
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] = 2j-1 = 20 = 1) записывается значение 01 00 00 00 4-х байтового слова, первый байт которого равен 20 = 1, т.е. 0000 0001, остальные байты этого 32-разрядного слова – нулевые.

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

В двоичном представлении байта 0000 00012 = 0116 младшие разряды располагаются справа.

В графу 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] = 2j-1 = 1, 2, 4, 8, 16, ….
Удвоение значений допустимо до тех пор, пока Rcon[j] является элементом поля GF(28).

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

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


Этим можно завершить рассмотрение действий по формированию раундовых ключей шифра AES.
Теги:
Хабы:
+3
Комментарии 0
Комментарии Комментировать

Публикации

Истории

Работа

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн
PG Bootcamp 2024
Дата 16 апреля
Время 09:30 – 21:00
Место
Минск Онлайн
EvaConf 2024
Дата 16 апреля
Время 11:00 – 16:00
Место
Москва Онлайн