Алгоритм Райндал (Rijndael). Основные особенности шифра Райндал

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

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

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

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

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

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

• замена байт - ByteSub;
• сдвиг строк — ShiftRow;
• замешивание столбцов - MixColumn;
• добавление циклового ключа AddRoundKey.
• Число циклов обозначается Nr и зависит от значений Nb и Nk.

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

• получение обратного элемента относительно умножения в поле GF(28);
• применение афинного преобразования (над GF(2)).

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

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

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

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

• расширение ключа (key expansion);
• выбор циклового ключа (round key selection).

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

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

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

Выработка ключей может быть сделана и без использования  массива. Это характерно для реализаций, в которых критично требование к  занимаемой памяти. В этом случае цикловые ключи можно вычислить «на  лету» посредством использования  буфера из 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.

1.3 Атака на алгоритм шифрования AES

Специалисты по криптографии обнаружили слабость в широко используемом алгоритме  шифрования AES (также известном как  Rijndael), которая свидетельствует о более низкой стойкости шифра, чем было принято считать до сих пор. В ожидающейся к публикации статье исследователи Алекс Бирюков (Alex Biryukov), Орр Данклман (Orr Dunkelman), Натан Келлер (Nathan Keller), Дмитрий Ховратович (Dmitry Khovratovich) и Ади Шамир (Adi Shamir) показали, что 256-битная версия AES восприимчива к серии так называемых related-key атак (атак со связанными ключами), существенно снижающих требуемое для поиска ключа время. Одна из техник, используемая против 11-раундовой версии алгоритма, может быть завершена за 2^70 операций. Другая техника использует только два связанных ключа для взлома полного ключа 9-раундовой версии за 2^39 операций, что значительно быстрее по сравнению с показателем 2^120 для лучшего предыдущего механизма атаки. Третья техника взламывает 10-раундовую версию за время выполнения 2^45 операций.

Как и предыдущие техники атак на ключ, последние предложенные методики по большей части непрактичны для быстрого вскрытия нужных данных. Тем не менее, ценность исследований стойкости алгоритма определяется его широким распространением в шифровании чувствительной к раскрытию информации и каналов ее передачи. AES лежит в основе нескольких алгоритмов-кандидатов на новый алгоритм хэширования SHA-3, который должен быть принят американским Национальным институтом стандартов и технологий (US National Institute of Standards and Technology).

"Кода вы занимаетесь созданием  системы с длительным периодом  эксплуатации, вы захотите использовать  проверенные временем алгоритмы  шифрования, поэтому известия о  таких новых атаках могут обеспокоить", - говорит Пол Кокер (Paul Kocher), президент и главный научный сотрудник расположенной в Сан-Франциско компании Cryptography Research, предоставляющей консультационные услуги. По словам эксперта, банки и другие организации уже затратили миллиарды долларов на переход со стандарта DES (Data Encryption Standard – стандарт шифрования данных), пользовавшегося широкой популярностью до того момента, пока криптографы не обнаружили в нем существенную уязвимость, благодаря которой практические атаки могли привести к успешному взлому.

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

Глава 2. Алгоритм Райндал (Rijndael). Основные особенности шифра Райндал.

2.1 Алгоритм Rijndael. Предварительные математические понятия

Практически все операции Rijndael определяются на уровне байта. Байты можно рассматривать как элементы конечного поля GF (2⁸). Некоторые операции определены в терминах четырехбайтных слов. Введем основные математические понятия, необходимые для обсуждения алгоритма.

Поле GF(2⁸)

Элементы конечного поля могут  быть представлены несколькими различными способами. Для любой степени  простого числа существует единственное конечное поле, поэтому все представления GF (2⁸) являются изоморфными. Несмотря на подобную эквивалентность, представление влияет на сложность реализации. Выберем классическое полиномиальное представление.

Байт b, состоящий из битов b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀, представляется в виде полинома с коэффициентами из {0, 1}:

b₇х⁷ + b₆х⁶ + b₅х⁵ + b₄х⁴ + b₃х³ + b₂х² +

b₁х¹ + b₀

Пример: байт с шестнадцатеричным  значением '57' (двоичное 01010111) соответствует полиному

х⁶ + х⁴ + х² + х + 1

2.2 Сложение

В полиномиальном представлении сумма  двух элементов является полиномом  с коэффициентами, которые равны  сумме по модулю 2 (т.е. 1 + 1 = 0) коэффициентов слагаемых.

Пример: '57' + '83' = 'DA' или в полиномиальной нотации:

(х⁶ + х⁴ + х² + х + 1) + (х⁷ + х + 1) =

х⁷ + х⁶ + х⁴ + х²

В бинарной нотации мы имеем: 01010111 + 10000011 = 11011010. Очевидно, что сложение соответствует простому XOR (обозначается как ) на уровне байта.

Выполнены все необходимые условия  Абелевой группы: операция сложения (каждой паре элементов сопоставляется третий элемент группы, называемый их суммой), ассоциативность, нулевой элемент ('00'), обратный элемент (относительно операции сложения) и коммутативность.

2.3 Умножение

В полиномиальном представлении умножение  в GF (2⁸) соответствует умножению полиномов по модулю неприводимого двоичного полинома степени 8. Полином является неприводимым, если он не имеет делителей, кроме 1 и самого себя. Для Rijndael такой полином называется m(x) и определяется следующим образом: