Криптографическая система защиты информации на
Основе стандарта AES (Rijndael)
В криптографии используются симметричные и асимметричные системы (алгоритмы) шифрования. Среди симметричных алгоритмов шифрования особое место занимает алгоритм DES, который на протяжении трех десятилетий был по сути международным стандартом симметричного шифрования. Столько высокую популярность этому алгоритму обеспечила его стойкость — за 25 лет интенсивного криптоанализа не было найдено методов вскрытия этого шифра, существенно отличающихся по эффективности от полного перебора по ключевому пространству. Однако сегодня DES считается устаревшим по многим другим важным параметрам: длине ключа, удобству реализации, на современных процессорах, быстродействию и др.
Учитывая это, в 1997 г. Национальный институт стандартов и технологий США (NIST) объявил о начале конкурса по принятию нового стандарта криптографической защиты для закрытия важной информации правительственного уровня на замену существующему с 1974 г. алгоритму DES.
В настоящей работе рассматривается шифрование по алгоритму AES (Advanced Encryption Standard), который в октябре 2000 г. был признан победителем конкурса, проводимого NIST, как имеющий наилучшее сочетание стойкости, производительности, эффективности реализации и гибкости.
Алгоритм AES (вначале он имел наименование Rijndae по начальным буквам бельгийских разработчиков Райменом (Rijmen) и Даменом (Daemen) является блочным шифром. Алгоритм представляет каждый блок кодируемых данных в виде двумерного массива байт размером 4×4, 4×6 или 4×8 в зависимости от установленной длины блока. Далее на соответствующих этапах преобразования производятся либо над независимыми столбцами, либо над независимыми строками, либо вообще над отдельными байтами в таблице.
Все преобразования в шифре имеют строгое математическое обоснование. Сама структура и последовательность операций позволяют выполнять данный алгоритм эффективно как на 8-битных так и на 32-битных процессорах.
Шифрование
Rijndael представляет собой итеративный блочный шифр, имеющий переменную длину блоков и различные длины ключей. Длина ключа и длина блока могут быть независимо друг от друга 128, 192 или 256 бит. Промежуточные результаты преобразований называются состояниями.
Блоки данных состояния можно представить в виде прямоугольного массива байтов. Этот массив имеет 4 строки, а число столбцов обозначено как Nb и равно длине блока, деленной на 32. Ключ шифрования также представлен в виде прямоугольного массива с четырьмя строками, число столбцов в котором обозначено как Nk и равно длине ключа, деленной на 32.
Система шифрования по стандарту AES с алгоритмом работы представлена в приложении 3 для случая, когда длина блока открытого текста Nb = 6 словам (слово равно 32 битам, а длина ключа Nk =4 словам). Тогда таблицы массива байт открытого текста и массива ключей будут выглядеть следующим образом:
Таблица 1
| a00 | a01 | a02 | a03 | a04 | a05 | k00 | k01 | k02 | k03 | ||||
| a10 | a11 | a12 | a13 | a14 | a15 | k10 | k11 | k12 | k13 | ||||
| a20 | a21 | a22 | a23 | a24 | a25 | k20 | k21 | k22 | k23 | ||||
| a30 | a31 | a32 | a33 | a34 | a35 | k30 | k31 | k32 | k33 |
Условные обозначения на схемах математических функций приведены в приложении 4.
Процесс шифрования состоит из следующих этапов:
· начальное добавление раундового ключа (начальное забеливание),
· раундовое преобразование в течение (r – 1) раундов,
· заключительный раунд.
Раундовый ключ получается из ключа шифрования с помощью специального алгоритма генерации ключей, который описан ниже.
Число раундов обозначено как r и зависит от значений Nb и Nk. Оно приведено в таблице 2.
Таблица 2
| r | Nb = 4 | Nb = 6 | Nb = 8 |
| Nk = 4 | |||
| Nk = 6 | |||
| Nk = 8 |
Начальное добавление раундового ключа. В преобразовании добавление раундового ключа (начальное забеливание) цикловой ключ добавляется к состоянию посредством сложения по модулю 2. Длина раундового Nk ключа равна длине блока Nb.
| a00 | a01 | a02 | a03 | a04 | a05 | k00 | k01 | k02 | k03 | k04 | k05 | = | b00 | b01 | b02 | b03 | b04 | b05 | ||
| a10 | a11 | a12 | a13 | a14 | a15 | Å | k10 | k11 | k12 | k13 | k14 | k15 | b10 | b11 | b12 | b13 | b14 | b15 | ||
| b20 | b21 | b22 | b23 | b24 | b25 | |||||||||||||||
| a20 | a21 | a22 | a23 | a24 | a25 | k20 | k21 | k22 | k23 | k24 | k25 | |||||||||
| b30 | b31 | b32 | b33 | b34 | b35 | |||||||||||||||
| a30 | a31 | a32 | a33 | a34 | a35 | k30 | k31 | k32 | k33 | k34 | k35 |
Сложение и вывод результатов осуществляется в следующей последовательности: a00Å k00= b00, a10Å k10= b10,…, a35Å k35= b35.
Раундовое преобразование. Это преобразование включает в себя нелинейное преобразование матрицы данных и добавление раундового ключа. Нелинейное преобразование матрицы состоит из трех шагов: замены байтов матрицы на новые значения (S- box - преобразования), циклического сдвига строк матрицы влево, перемешивания столбцов матрицы (умножения матрицы данных слева на постоянную матрицу-циркулянт M.
| М = | ||||
Преобразование замена байтпредставляет собой нелинейную замену байт, выполняемую независимо с каждым байтом состояния. Таблицы замены (или S-box) являются инвертируемыми и построены из композиции двух преобразований: а) получение обратного элемента, б) применение аффинного преобразования (над GF(2)). Эти преобразования определены как:
| b0 | = | * | a0 | Å | |||||||||
| b1 | a1 | ||||||||||||
| b2 | a2 | ||||||||||||
| b3 | a3 | ||||||||||||
| b4 | a4 | ||||||||||||
| b5 | a5 | ||||||||||||
| b6 | a6 | ||||||||||||
| b7 | a7 |
Применение описанного S-box ко всем байтам состояния можно проиллюстрировать как:
 |
Рис.3.3. Преобразование замены байтов
Преобразование S- box в виде таблицы приведено в приложении 5, табл. 1.
Преобразование сдвига строк подразумевает, что последние 3 строки состояния циклически сдвигаются на различное число байт. Строка 1 сдвигается на С1 байт, строка 2 - на С2 байт и строка 3 - на С3 байт. Значения сдвигов С1, С2 и С3 зависят от длины блока Nb. Их величины приведены в таблице 2.
Таблица 2. - Величина сдвига для разной длины блоков.
| Nb | C1 | C2 | C3 |
В преобразовании перемешивания столбцов столбцы состояния рассматриваются как многочлены над полем GF(28) и умножаются по модулю x4+1 на многочлен c(x), выглядящий следующим образом:
c(x)='03' x3 + '01' x2 + '01' x + '02'.
Это может быть представлено в виде матричного умножения. Пусть b(x)=c(x)*a(x),
| b0 | = | * | a0 | ||||
| b1 | a1 | ||||||
| b2 | a2 | ||||||
| b3 | a3 |
Конечное поле GF(28) порождается неприводимым полиномом g(x) = x8+x4+x3+x2+1. Операция сложения в этом поле является ни чем иным, как побитовым суммированием по модулю 2, умножение выполняется как обычное умножение полиномов над GF(2) по модулю полинома g(x).
В графическом виде преобразование перемешивание столбцов выглядит так.
 |
Рис.3.4. Преобразование перемешивания столбцов.
Добавление раундового ключа. В конце каждого раунда с полученным в результате всех преобразований блоком складывается посредством поразрядного сложения по модулю 2 раундовый ключ. Это осуществляется аналогично начальному добавлению раундового ключа.
Заключительный раундотличается от остальных только тем, что в нём исключается преобразование перемешивания столбцов.