Стандарт шифрования AES

Стандарт шифрования 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), который был предшественником современного Национального института по стандартам и технологии, объявил конкурс на создание алгоритма, удовлетворяющего требованиям, выдвинутым институтом:

  • применение одного или более открытых алгоритмов шифрования;
  • общедоступность и отсутствие лицензионных отчислений;
  • использование симметричного шифрования;
  • поддержка минимального размера блока в 128 разрядов и размеров ключей в 128, 192 и 256 разрядов;
  • бесплатное распространение по всему миру;
  • приемлемая производительность для различных приложений.

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

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

Читайте: Как заработать на инвестициях в искусственный интеллект? Краудфандинг Daisy от компании EndoTech. Обзор и отзывы о смарт-контракте

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

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

Оцените статью
Добавить комментарий