Шифр Rijndael. Математические основы работы.

AdvancedEncryptionStandard (AES), также известный как Rijndael — симметричный алгоритм блочного шифрования, принятый в качестве стандарта шифрования правительством США по результатам конкурса AES: RIJNDAEL имеет наилучшее сочетание стойкости, производительности, эффективности реализации и гибкости. Его низкие требования к объему памяти делают его идеально подходящим для встроенных систем. Авторами шифра являются ЙонДэмен и Винсент Рюмен, начальные буквы фамилий которых и образуют название алгоритма. Этот алгоритм хорошо проанализирован и сейчас широко используется.

В стандарте AES алгоритм оперирует байтами, которые рассматриваются как элементы конечного поля GF(2⁸). Элементами поля GF(2⁸) являются многочлены степени не более семи, которые могут быть заданы строкой своих коэффициентов. Если байт представить в виде: {α₇, α₆, α₅, α₄, α₃, α₂, α₁, α₀}, α_i∈{0,1}, 0<=i<=7, то элемент поля описывается многочленом α₇x⁷+ α₆x⁶+ α₅x⁵+ α₄x⁴+ α₃x³+ α₂x²+ α₁x+ α₀

Для перевода двоичного представления байта в шестнадцатеричное можно воспользоваться следующими таблицами:

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

Раундовые преобразования в AES оперируют 32-разрядными словами. Четырехбайтовому слову может быть поставлен в соответствие многочлен α(х) с коэффициентами из GF(2⁸) степени не более трех: α(х)= α₃x³+ α₂x²+ α₁x+ α₀, где α_i∈GF(2⁸), 0<=i<=3.

Для элементов конечного поля определены аддитивные и мультипликативные операции.

Сложение суть операция поразрядного XOR, обозначается как . Пример выполнения операции сложения в виде многочленов: (х⁶ +х⁴ +х² +х +1) (х⁷ + х +1)= х⁷ +х⁶ +х⁴ +х². В конечном поле для любого ненулевого элемента α существует обратный элемент –α, при этом α+(-α)=0, где нулевой элемент это {00}. В GF(2⁸) справедливо α+α=0, т.е. каждый ненулевой элемент является своей собственной аддитивной инверсией. Сложение двух многочленов с коэффициентами из GF(2⁸) суть операции сложения многочленов с приведением подобных членов в поле GF(2⁸). Таким образом, сложение двух 4-байтовых слов суть операция поразрядного XOR.

Умножение, обозначаемое далее как •, более сложная операция. Умножение в GF(2⁸) – это операция умножения многочленов со взятием результата по модулю неприводимого многочлена φ(х) восьмой степени и с использованием операции XOR при приведении подобных членов. В AES выбран φ(х)= х⁸ +х⁴ +х³ +х +1. Для того чтобы результат умножения мог быть представлен 4-байтовым словом, необходимо взять результат по модулю многочлена степени не более 4. Авторы шифра выбрали многочлен х⁴+1, для которого справедливо xⁱmod(х⁴+1)=x^{imod 4}. Для любого ненулевого элемента α справедливо α•1=α. Мультипликативной единицей в GF(2⁸) является элемент {01}.

Дата добавления: 2015-12-01