Лекции по криптологии / Y40_M01_L23

8

Лекция 23

Общая схема и криптопреобразования криптоалгоритма AES-128

Цель данной лекции – на примере нового американского стандарта шифрования AES изучить схему «квадрат» блочного шифра, отличную от схемы Фейстеля.

23.1. Стандарт AES основан на победившем в открытом международном конкурсе блочном шифре Rijndal (2001г.). Этот стандарт сменил морально устаревший сменивший DES, впрочем, последний до сих пор остается негласным стандартом в области финансовых технологий.

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

AES и Rijndal различаются диапазонами длин блоков и ключей шифрования. Длина блока в AES равна 128 битам. Допустимые длины ключей имеют значения: 128, 192 или 256 битов. Под AES-128 будем понимать алгоритм AES с длиной ключа в 128 битов. Этот ключ называется в стандарте ключом шифрования.

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

Вход в следующий цикл совпадает с выходом предыдущего цикла. Десятый цикл отличается от предыдущих. Прочие циклы построены однотипно.

Блок открытого текста является входом в первый цикл. Блоком шифртекста является выход из десятого цикла.

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

Размеры таблиц зависят от длин ключей (в битах). Эти длины должны быть кратны 32битам (четырем байтам). Количество строк в таблицах равно четырем. Количество столбцов зависит от длины ключей (равно длине ключа в битах, деленной на 32).

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

В типичном раунде AES-128 над состояниями последовательно выполняются следующие преобразования.

1. SubBytes. Побайтовая замена, с использованием фиксированной несекретной таблицы замены.

2. ShiftRows. Побайтовый циклический сдвиг строк состояния: i – я строка (i=0,1,2,3) сдвигается циклически на i байтов влево (это верно только для AES-128).

3. MixColumns. Смешивание колонок. Данная операция использует операции над над кольцом вычетов многочленов, коэффициенты которых принадлежат полю .

Приведение производится по модулю многочлена. Соответствующее кольцо не является полем, т.к. у многочлена существуют корни в .

4. AddRoundKey. Модификация состояния с помощью поразрядного сложения по модулю 2 (XOR) с раундовым ключом. Здесь каждый байт состояния рассматривается как строка битов.

В десятом раунде операция MixColumns пропускается. Это необходимо для обеспечения процедуры расшифрования данных.

5. До начала шифрования блока открытого текста производится процедура расширения ключа шифрования и формирование буфера раундовых ключей.

Кроме того, перед первым раундом выполняется операция AddRoundKey (начальная модификация состояния). Ключу, используемому на данном этапе, присвоен номер ноль.

Важной особенностью стандарта AES является то, что он построен с учетом возможной реализации на основе процессоров различных типов, например, 8-ми битовых, 32-х битовых.

В стандарте приведены процедуры, оптимально реализующие преобразования состояний.

Эти преобразования построены так, чтобы оптимизировать вычисления над 4-х мерными байтовыми векторами (колонками таблиц, представляющими состояния).

По этой причине параметры преобразований выбраны специфическим образом.

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

Все операции, кроме AddRoundKey, работают с байтами или 4-х мерными векторами, элементы которых являются байтами.

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

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

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

23.2. Преобразования состояний.

Преобразование SubBytes осуществляет простую побайтовую замену, с использованием фиксированной несекретной таблицы замены (S-box).

Эта таблица может быть построена следующим способом.

1. Исходный байт рассматривается как полином над и заменяется на байт коэффициентов полинома . Нулевой байт отображается в себя.

2. Байт , соответствующий a, преобразуется в байт с помощью обратимого аффинного преобразования над вида

Таким образом, S-box осуществляет преобразование байтов вида .

Преобразование ShiftRows осуществляет побайтовый циклический сдвиг строк состояния. В общем случае количество колонок таблицы состояния может быть больше четырех. При этом величина сдвига каждой строки выбирается из фиксированной несекретной таблицы. Для AES-128 состояние представляется квадратом 44. В случае квадрата i – я строка (i=0,1,2,3) сдвигается циклически на i байтов влево.

Очевидно, преобразование ShiftRows обратимо.

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

Например, вектор соответствует многочлену над полем вида

.

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

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

Вектор коэффициентов вычета является произведением соответствующих расширенных чисел. Произведение расширенных чисел а и b обозначим через , а произведение полиномов с расширенными коэффициентами – через .

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

, а полином

имеет расширенные коэффициенты, т.е. равен .

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

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

Обратным к является полином

.

Выбор модуля в виде полинома связан с тем, что при таком модуле очень просто получать вычеты полиномов вида . Оказывается, для этого достаточно показатель привести по модулю 4: .

Действительно, пусть , тогда разность делится на (сложение и вычитание по модулю 2 совпадают).

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

Напомним, что в этом случае достаточно рассматривать произведения полиномов степени не выше трех.

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

Пусть , и

.

Тогда

, , ,

, ,

, .

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

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

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

В итоге, выражения коэффициентов полинома таковы, что преобразование может быть записано в матричном виде (с операциями ).

Используя конкретный вид полинома , мы можем теперь описать преобразование колонки в виде

,

что и задает преобразование MixColumns колонки а.

Что касается преобразования AddRoundKey, то, как мы уже говорили, новое состояние равно состоянию, полученному с помощью поразрядного сложения по модулю 2 (XOR) исходного состояния и соответствующего раундового ключа. Здесь каждый байт состояния рассматривается как строка битов.

23.3. Управление ключами.

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

Длина в битах каждого раундового ключа равна одиннадцатикратной битовой длине блока. В рассматриваемом случае (AES-128) получим: 12811=1408.

Выбор раундовых ключей из буфера осуществляется просто: первые четыре слова (в каждом слове четыре байта) является ключом номер 0, следующие четыре слова – ключом номер 1 и т.д.

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

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

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

Первые четыре слова в буфере представляют собой ключ K. Столбцы последующей группы с номерами i=1,2,3 формируются по рекуррентному закону вида .

Здесь элементами рекурренты являются слова (столбцы) буфера, начальное состояние - ключ K, операция – поразрядное сложение слов по модулю два.

Нулевой столбец последующей группы (i кратно четырем) формируется по закону , где является модифицированным словом .

Модификация состоит в последовательном применении трех следующих функций, отображающих слово в слово.

1. Сдвиг байтов (RotByte): .

2. Замена байтов (SubByte): замена каждого байта слова по таблице замены SubBytes. В результате получаем слово .

3. Поразрядное сложение слова с « раундовой константой» - несекретным словом, Rcon[j] уникальным для каждого раундового ключа , j=1,2,…,10.

Здесь j является номером формируемого ключа (группы колонок).

В раундовой константе занят лишь первый байт RC[j], остальные байты – нулевые.

RC[1]=1, точнее, RC[1] является многочленом с вектором коэффициентов (0,0,0,0,0,0,0,1).

RC[2]=х, т.е. RC[2]= (0,0,0,0,0,0,1,0), и так далее,

RC[j] = RC[j-1] (операция в поле , с порождающим полиномом ).

23.4. Процессы зашифрования и расшифрования.

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

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

2. Производим начальную модификацию состояния с помощью ключа с номером 0.

3. Производим дальнейшее изменение состояний, выполняя раунды 1-9 (ключи 1-9).

4. модифицируем состояние с помощью финального раунда номер 10 (ключ 10).

В терминах операций над состояниями зашифрование и расшифрование выглядят так:

	1	2	3
	Зашифрование (прямой порядок ключей и операций)	Расшифрование (обратный порядок ключей и операций)	Расшифрование (обратный порядок инверсных ключей и прямой порядок операций)
Raund 0	AddRoundKey	invAddRoundKey	AddRoundKey
Raund 1 ……… ……… Raund 9	SubBytes	invShiftRows	invSubBytes
	ShiftRows	invSubBytes	invShiftRows
	MixColumns	invAddRoundKey	invMixColumns
	AddRoundKey	invMixColumns	AddRoundKey
Raund 10	SubBytes	invShiftRows	invSubBytes
	ShiftRows	invSubBytes	invShiftRows
	AddRoundKey	invAddRoundKey	AddRoundKey

В столбце таблицы с номером 1 записан порядок зашифрования. В столбце с номером 2 записана «естественная» последовательность шагов при расшифровании, где для операции F обратной считается операция invF. В третьем столбце записана эквивалентная последовательность шагов, выполняемая при расшифровании.

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

В данной последовательность операции выполняются в том же порядке, что и при зашифровании. При этом на каждом шаге используются соответствующие обратные операции и инверсные ключи. Эти ключи получаются при применении к каждой колонке таблицы состояния ключа операции invMixColumns. Указанному преобразованию подвергаются все раундовые ключи, кроме ключа с номером 0 и ключа с номером 10 (первого и последнего).

Очевидно, инверсные ключи легко получить из расширенного ключа заранее.