Перспективный стандарт AES

Алгоритм шифрования DES давно критикуют за целый ряд недостатков, в том чис­ле, за слишком маленькую длину ключа — всего 56 разрядов. Кроме того, в январе 1999 года закодированное посредством DES сообщение было взломано с помощью связанных через Internet в единую сеть 100 тыс. персональных компьютеров. И на это потребовалось менее 24-х часов. В связи с этим стало очевидным, что в ближайшие несколько лет, учитывая появление более дешевого и высокопроизводительного обо* рудования, алгоритм DES окажется несостоятельным.

Чтобы решить эту проблему, еще в 1997 году NIST выпустил запрос на коммента­рий RFC (Request For Comment), где описывался предполагаемый «Усовершенство­ванный стандарт шифрования» AES (Advanced Encryption Standard), который должен прийти на смену стандарту DES. В 1998 году NIST (National Institute of Standards and Technology), который был предшественником современного Национального институ-

та по стандартам и технологии, объявил конкурс на создание алгоритма, удовлетворя­ющего требованиям, выдвинутым институтом:

Q применение одного или более открытых алгоритмов шифрования;

О общедоступность и отсутствие лицензионных отчислений;

Q использование симметричного шифрования;

Q поддержка минимального размера блока в 128 разрядов и размеров ключей в 128,192 и 256 разрядов;

G бесплатное распространение по всему миру;

Q приемлемая производительность для различных приложений.

Перед проведением первого тура конкурса в NIST поступило 21 предложение, из которых 15 удовлетворяли выдвинутым критериям. Затем были проведены исследова­ния этих решений, в том числе связанные с дешифровкой и проверкой производитель­ности, и получены экспертные оценки специалистов по криптографии.

В результате в качестве стандарта AES был выбран алгоритм Rijndael, разработан­ный двумя бельгийскими учеными, специалистами по криптографии. Правительство США объявило, что авторами наиболее перспективного алгоритма шифрования стали Джон Димен из компании Proton World International и Винсент Риджмен, сотрудник Католического университета.

Алгоритм Rijndael является нетрадиционным блочным шифром, поскольку в нем для криптопреобразований не используется сеть Фейштеля. Он представляет каждый блок кодируемых данных в виде таблицы двумерного массива байтов размером 4*4, 4*6 или 4*8 в зависимости от установленной длины блока. Далее, на соответствую­щих этапах, производятся преобразования либо независимых столбцов, либо незави­симых строк, либо вообще отдельных байтов в таблице.

Все преобразования в шифре имеют строгое математическое обоснование. Сама структура и последовательность операций позволяют выполнять данный алгоритм эффективно как на 8-битных, так и на 32-битных процессорах. Это позволяет достичь приемлемой производительности при работе на самых разных платформах: от смарт-карт до крупных серверов. В структуре алгоритма заложена возможность параллель­ного выполнения некоторых операций, что на многопроцессорных рабочих станциях может поднять скорость шифрования еще в 4 раза.

Rijndael представляет собой итеративный блочный шифр, имеющий блоки пере­менной длины и ключи различной длины. Длина ключа и длина блока может быть 128, 192 или 256 бит независимо друг от друга. Согласно структуре шифра разнообразные преобразования взаимодействуют с промежуточным результатом шифрования, назы­ваемым состоянием (state).

Это состояние можно представить в виде прямоугольного массива байтов, ко­торый имеет 4 строки, а число столбцов Nb равно длине блока, деленной на 32. Ключ шифрования также представлен в виде прямоугольного массива с четырьмя строками. В этом массиве число столбцов Nk равно длине ключа, деленной на 32. Пример представления состояния и ключа шифрования в виде массивов представ­лен на рис. 4.9.

В некоторых случаях ключ шифрования показан как линейный массив 4-байтовых
слов. Слова состоят из 4-х байт, которые находятся в одном столбце (при представле­
нии в виде прямоугольного массива). *"

Входные данные для шифра, например, открытый текст, обозначаются как байты состояния в порядке аО,0, al,0, аЗ,0, аОД, al,l, аЗД,а4,1... После завершения дей­ствия шифра выходные данные получаются из байтов состояния в том же порядке.

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

Q замена байт — ByteSub;

Q сдвиг строк — ShiftRow;

Q замешивание столбцов — MixColumn;

Q добавление циклового ключа — AddRoundKey.

Число циклов обозначается Nr и зависит от значений Nb и Nk (рис. 4.10).

Преобразование ByteSub представляет собой нелинейную замену байт, выполняе­мую независимо с Каждым байтом состояния. Порядок замены определяется инверти­руемыми S-блоками (таблицами замены), которые построены как композиции двух преобразований:

О получение обратного элемента относительно умножения в поле GF(28);

Q применение афинного преобразования (над GF(2)).

Применение преобразования ByteSub к состоянию представлено на рис. 4.11.

Преобразование сдвига строк ShiftRow заключается в том, что последние три строки состояния циклически сдвигаются на различное число байт. При этом первая строка состояния остается без изменения, вторая—сдвигается на С1 байт, третья строка сдви­гается на С2 байт, а четвертая — на СЗ байт. Значения сдвигов С1, С2 и СЗ различны и зависят от длины блока Nb. Величины этих сдвигов в байтах представлены в'табл. 4.3

Таблица 4.3. Величина сдвига строк для разной длины блоков

Длина блока, байт	Значение сдвига, байт
	С,	Сг	С3

Пример операции сдвига последних трех строк состояния на определенную вели­чину представлен на рис. 4.12.

Преобразование эамешивания столбцов MixColumn (рис. 4.13) основано на мате­матическом преобразовании, перемещающем данные внутри каждого столбца. В этом преобразовании столбцы состояния рассматриваются как многочлены над GF(28) и умножаются по модулю х4+1 на многочлен С(х).

Операция AddRoundKey—добавление к состоянию циклового ключа посредством простого EXOR. Сам цикловой ключ вырабатывается из ключа шифрования посред­ством алгоритма выработки ключей (key schedule). Его длина равна длине блока Nb. Преобразование AddRoundKey представлено на рис. 4Л 4.

Алгоритм выработки ключей содержит два этапа:

Q расширение ключа (key expansion);

Q выбор циклового ключа (round key selection).

В основе алгоритма лежат следующее: общее число бит цикловых ключей равно длине блока, умноженной на число циклов плюс 1. Например, для длины блока 128 бит и 10-и циклов потребуется 1408 бит циклового ключа. Ключ шифрования превращается в расши­ренный ключ (expanded key). Цикловые ключи выбирают из расширенного ключа так: первый цикловой ключ содержит первые Nb слов, второй — следующие Nb слов и т. д.

Расширенный ключ представляет собой линейный массив 4-битных слов. Первые Nk слов содержат ключ шифрования. Все остальные слова определяются рекурсив­но из слов с меньшими индексами, то есть каждое последующее слово получается посредством EXOR предыдущего слова и слова на Nk позиций ранее. Для слов, по­зиция которых кратна Nk, перед EXOR применяется преобразование к предыдуще­му слову, а затем еще прибавляется цикловая константа. Преобразование содержит циклический сдвиг байтов в слове, обозначаемый rotl, затем следует применение таблицы замены байт — SubByte. Алгоритм выработки ключей зависит от величины Nk. Расширенный ключ всегда должен получаться из ключа шифрования и никогда не указываться напрямую. При этом нет ограничений на выбор ключа шифрования.

Выбор циклового ключа заключается в том, что каждый цикловой ключ получается из слов массива циклового ключа, как показано для Nb = 6 и Nk = 4 на рис. 4.15.

Выработка ключей может быть сделана и без использования массива. Это характерно для реализаций, в которых критично требование к занимаемой памяти. В этом случае цик­ловые ключи можно вычислить «на лету» посредством использования буфера из Nk слов.

Теперь рассмотрим особенности реализации алгоритма Rijndael. Этот алгоритм является байт-ориентированным, т. е. полностью может быть сформулирован в терми­нах операций с байтами. В алгоритме широко используются алгебраические операции в конечных полях, наиболее сложно реализуемо умножение в поле GF(28). Непосред­ственное выполнение этих операций привело бы к крайне неэффективной реализации алгоритма. Однако байтовая структура шифра открывает широкие возможности для программной реализации. Замена байта по таблице и последующее умножение на кон­станту в конечном поле GF(28) могут быть представлены как одна замена по таблице. Поскольку в прямом шифре используются три константы (01,02,03), то понадобятся три такие таблицы, в обратном шифре, соответственно, — четыре (ОБ, OD, 0В, 09). При надлежащей организации процесса шифрования построчный байтовый сдвиг мат­рицы данных можно не выполнять. При реализации на 32-битных платформах воз­можно реализовать байтовую замену и умножение элемента матрицы данных на стол­бец матрицы М как одну замену 8-и бит на 32 бита.

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

Для процессоров Intel Pentium с недостаточным количеством регистров сюда надо добавить еще 4 команды выгрузки содержимого регистров в память, тогда на указан­ных процессорах раунд шифрования по алгоритму Rijndael можно выполнить за 40 команд или за 20 тактов процессора с учетом возможности параллельного выполне-

ния команд этим процессором. Для 14 раундов получаем 280 тактов процессора на цикл шифрования плюс несколько дополнительных тактов на «лишнее» прибавление ключа. Добавив несколько тактов на внутрипроцессорные задержки, получим оценку 300 тактов на цикл шифрования. На процессоре Pentium Pro-200 это теоретически позволяет достичь быстродействия примерно 0,67 млн блоков в секунду, или, с уче­том размера блока в 128 бит, примерно 8,5 Мбайт/с. Для меньшего числа раундов скорость пропорционально возрастет.

Указанная выше оптимизация потребует, однако, определенных расходов опера­тивной памяти. Для каждого столбца матрицы М строится свой вектор замены одного байта на 4-байтное слово. Кроме того, для последнего раунда, в котором отсутствует умножение на матрицу М, необходим отдельный вектор замен такого же размера. Это требует использования 5*28*4=5 кбайт памяти для хранения узлов замен для зашиф­рования и столько же для узлов замен расшифрования — всего 10 кбайт. Для совре­менных компьютеров на базе Intel Pentium под управлением ОС Windows 9x/NT/2000 это не выглядит чрезмерным требованием.

Байт-ориентированная архитектура алгоритма Rijndael позволяет весьма эффек­тивно реализовать его на 8-битных микроконтроллерах, используя только операции загрузки/выгрузки регистров, индексированного извлечения байта из памяти и поби­тового суммирования по модулю 2. Указанная особенность позволит также выпол­нить эффективную программную реализацию алгоритма. Раунд шифрования требует выполнения 16-байтных замен плюс четырех операций побитового «исключающего или» над 128-битными блоками, которые можно выполнить в три этапа. В итоге полу­чаем 4 операдии на раунд, или 57 операций на 14-раундовый цикл шифрования с уче­том «лишней» операции побитового прибавления ключа по модулю 2.

Дата добавления: 2014-01-07