AES — американский стандарт шифрования, часть I

    image

    Эта публикация вызвана необходимостью дать возможность обучаемым изучать и моделировать процессы шифрования/расшифрования и дешифрования последнего стандарта США. Ознакомление с имеющимися публикациями в сети не соответствуют программе обучения в силу их поверхностного подхода, неполноты изложения, и отсутствия должной строгости. Например, нигде не встречается выбор и задание примитивного элемента, формирующего поле, без чего работу и подготовку специалиста, особенно криптоаналитические явления и процессы, организовать и моделировать невозможно. В этой работе используется описание, несколько отличное от оригинала AES, представленного FIPS PUB 197. Здесь описывается шифр AES, с использованием матриц над GF(28), но примечания работы сохраняются, т. е. шифр реализуется над конечным расширенным полем GF (28). На русском языке достаточно полная и доступная версия шифра изложена Зензиным О.С. и Ивановым М.А.

    Математические основы стандарта шифрования AES США


    AES – блочный шифр с длиной блоков равной 128 битам, и шифр поддерживает ключи длиной $N_к$, равной 128, 192 или 256 бит. AES – это шифр с итерационным ключом: состоит из повторного применения раундового преобразования состояния блока State шифруемого текста. Число раундов шифра обозначается $N_r$ зависит от длины ключа ($N_r = 10$ для ключа 128 битов, $N_r= 12$ для ключа 192 бита и $N_r = 14$ для ключа 256 бит).

    Шифр AES преобразует исходное состояние блока, обозначаемое символом S (State) и принадлежащее множеству матриц {M4(GF(28))} (то есть S є{M4(GF (28))} – матрица 4 × 4 байта, с ее элементами (коэффициентами) в GF (28)), к другому шифрованному состоянию в {M4 (GF (28))}.

    Пример 1. Блок данных длиной в 128 = 4·32, 4 слова по 32 разряда представляется квадратной таблицей байтов из 4-х строк и 4-х столбцов. Каждая строка содержит байты из 4-х разных 32 разрядных слов, а столбец – байты одного и того же 32-разрядного слова. Весь квадрат образован 4×4 = 16 байтами, которые могут обрабатываться как самостоятельные единицы.

    Именно такой подход к представлению данных определяет и обеспечивает байт-ориентированную структуру шифра и обработку данных. Ключ шифра K расширяется в $N_r+1$ подключей, обозначаемых матрицей Ki ={M4(GF(28))}, принадлежащей множеству {M4 (GF(28))}, (i = 0, 1, ..., Nr). Перестановка элементов в матрице S, возникающая при операции сдвига строк обозначена символом р(х).

    Представление данных, выбранное для элементов поля GF(28)


    В шифре AES используется байтовая структура данных. Представление, выбранное в [1] из векторного пространства GF(28), соответствующего полю GF(28)[X]/< φ(x) >, где φ(x) – неприводимый многочлен,

    $φ(x) = x^8 + x^4 + x^3 + x + 1$

    . Для удобства и лучшего понимания изучаемого материала, а для уяснения деталей выполнения вычислений с карандашом в руках ниже приводятся многочисленные числовые примеры и следующая таблица 1.

    Таблица 1. Соответствие десятичных, шестнадцатеричных, двоичных чисел и многочленов

    В работе используются четыре представления для обозначения каждого элемента расширенного поля в GF(28), которые являются эквивалентными одно другому.

    Представление данных, используемых в шифре AES


    Выберем десятичное целое число, эквивалент которого будем представлять
    различными формами в других системах счисления:

    1. 21210, десятичным видом – числом в 10-ой системе счисления.

    2. {11010100}b, представление элементов сообщения двоичным вектором – элементом векторного пространства GF(28) двоичных векторов,

    3. $x^7+ x^6 + x^4 + x^2$, многочленное представление – элементом поля Галуа GF [28], соответствующим двоичному вектору,

    4. {D4}16, – шестнадцатеричное представление – числом в 16-системе счисления,

    ⊕ – операция поразрядного суммирования векторов из GF(28) по mod2 (без переноса 1 в старший разряд).
    ⊗ – операция умножения элементов (векторов, многочленов, чисел) из поля GF(28)

    Алгоритм стандарта AES и шифра RIJNDAEL оперирует с байтами информации, которые отождествляются с элементами конечного поля Галуа GF(28). Степень расширения простого поля GF(2) равна 8. Все элементы расширенного поля при представлении их многочленами имеют показатель степень не более семи (≤ 7).

    Достигается такое положение приведением всех результатов действий с элементами поля по модулю неприводимого многочлена степени 8, который является формирующим многочленом для этого поля. Кроме неприводимого многочлена для построения поля необходимо задавать примитивный элемент.

    В рассматриваемом алгоритме примитивный элемент задан (его порядок должен быть равен порядку мультипликативной группы поля), а многочлен фиксирован и имеет вид φ(x). Не располагая этими характеристикам, работать со стандартом не получится

    $φ(x) = x^8 + x^4 + x^3 + x + 1$

    или 1{1b} в 16-ричной форме.
    Шестнадцатеричная запись неприводимого многочлена 1{1b} использует 9 разрядов и многочлен φ(x) не принадлежит полю GF(28).
    Таблица П1 представления элементов поля GF(28) (в конце текста в Приложении).
    В таблице П1 размещены все элементы поля в порядке возрастания показателя степени примитивного элемента (α = 000000112 = 310), мультипликативный порядок которого равен 255.

    Рассмотрим примеры выполнения арифметических операций над элементами поля при различных представлениях этих элементов. Любой байт исходного текста (элемент поля) формально можно представить строкой символов $a_i, i = 0(1)7$, коэффициентов двоичного вектора в виде:

    ${a_7, a_6, a_5, a_4, a_3, a_2, a_1, a_0}, a_i∊GF(2), i = 0(1)7.$


    Пример 2. Элемент расширенного поля GF(28) задан в виде двоичного вектора:

    ${a_7, a_6, a_5, a_4, a_3, a_2, a_1, a_0}, a_i∊GF(2), i = 0(1)7$


    Описание многочленом этого элемента имеет вид:

    $(x) = a_7 x^7 + a_6 x^6 + a_5 x^5 + a_4x^4 + a_3 x^3 + a_2 x^2 + a_1 x^1 + a_0 x^0$


    Если доопределить значения ai двоичными значениями, i = 0(1)7, например, так ${a_7, a_6, a_5, a_4, a_3, a_2, a_1, a_0}$ = {11000001}2, то получим многочлен

    $α(x) = x^7 + x^6 +1,$

    так как $ a_5 = a_4 =a_3 =a_2 =a_1 = 0.$

    Шестнадцатеричное представление этого элемента α16 = {с1}={11000001}, а десятичное

    α10 = $2^7 + 2^6 + 2^0$ = 128 + 64 + 1 = 19310.

    При выбранном примитивном элементе поля степенное представление
    αi ={с1}= α178.
    Входим в таблицу П1 элементов поля GF(28) со значением α178 и в соответствующих столбцах для этой строки находим описанные представления, а также другие характеристики этого элемента поля. Для понимания возможных преобразований с элементами поля рассмотрим операции с его элементами в деталях.

    Суммирование элементов поля GF(28)


    Сложение в рассматриваемом поле представляет операцию поразрядного суммирования значений разрядов слагаемых без переноса единицы в старший разряд. Это операция исключающего ИЛИ (EXOR – EXLUSIV OR) часто обозначается просто XOR. В модулярной арифметике такое сложение называется суммированием по модулю два (mod2).

    Пример 3. Выберем в качестве операндов многочлены
    $A(x) = x^7+ x^6 + 1;$
    $B(x) = x^3 + x^2 + x^0.$
    Двоичное представление суммы многочленов по модулю два имеет вид
    [A(x)⊕B(x)]mod2 = {11000001}⊕ {00001101} = {11001100};

    16-ричное представление {c1}⊕{0D}={cc}sub>16=α55;
    степенное представление α178 + α238 = α55· {α123 + α183} = α55· 1 = α55.

    Представление многочленами
    $(x^7+x^6+1)⊕ (x^3+x^2+1)(mod2)= (x^7+x^6+x^3+x^2+2)(mod2)=x^7+x^6+x^3+x^2.$
    Заметим, что при сложении операндов степень многочлена результата не
    увеличивается, и необходимость приведения его по модулю неприводимого многочлена поля φ(x) не возникает. Коэффициенты результата приводятся по модулю два, т. е. все четные коэффициенты обращаются в нуль.

    В полях характеристики 2 действия сложения и вычитания операндов равнозначны. Для каждого элемента поля в аддитивной группе обратным к нему (противоположным) является он сам. Так, для элемента (а) противоположным является (-а), так как а + (-а) = 0. Нулевой элемент (единица аддитивной группы поля, нейтральный элемент) в шестнадцатеричном виде – это {00}16.

    Умножение элементов поля GF(28)


    Операция обычного умножения операндов (в отличие от модулярного ⊗) обозначается точкой между операндами, или знак умножения вообще опускается, когда не возникает опасности разночтения. Операнды в двоичном представлении умножаются по обычным правилам «столбиком». Будем перемножать те же, что и ранее операнды.

    Пример 4. Умножение операндов в двоичном представлении
    А(х)· В(х) = {c1}·{0d}

    Остаток от деления получает вид двоичного, многочленного и 16-ричного представлений (как элемент поля)
    R(x) = 01011 10102 = $x^7+ x^5+ x^4+ x^3+ x $= {ba}16. Старший разряд остатка равен нулю и не учитывается.
    Степенное представление здесь не приводим, но по таблице П1 его можно найти.

    Остаток от деления на неприводимый многочлен φ(x) в его двоичном представлении результата умножения операндов принимаем в качестве произведения операндов как элементов поля GF(28).

    Выполним умножение операндов в представлении многочленами.

    Пример 5. Умножение операндов элементов поля в многочленном представлении
    А(х) ⊗ В(х) = {c1}⊗{0d}
    A(x) ⊗ B(x) = $(x^7+ x^6+ 1)⊗(x^3+ x^2+1) $(moddφ(x),2) =
    =(x10+$ x^9+ x^9+ x^8+ x^7+ x^6+ x^3+ x^2+1)$(moddφ(x),2) =
    =(x10+$ x^8+ x^7+ x^6+ x^3+ x^2+1)$(moddφ(x),2).

    Здесь символ (moddφ (x),2) обозначает приведение по двойному модулю: многочлен по модулю φ(x), а его коэффициенты по модулю два, т.е. четные коэффициенты обнуляются. Получившаяся степень (deg(A(x)⊗ B(x)) =10) результата произведения выводит (этот многочлен — результат) за пределы поля. Чтобы результат принадлежал полю, его приводят (редуцируют, делят) по модулю неприводимого многочлена. Выполним такое деление обычным способом (уголком)

    Пример 6. Необходимость деления многочленов возникает при
    их умножении А(х)⊗В(х)/ φ(x).(Операции деления в поле нет, когда надо что-то поделить, это что-то умножают на обратный элемент делителя в поле)

    – остаток отделения на φ(x) принадлежит полю GF(28), и его принимаем в качестве окончательного результата $R(x) = x^7+x^5+x^4+x^3+x$ модулярного умножения.

    Иначе умножение A(x)⊗B(x) представимо как
    $(x^2 + 1)(x^8 + x^4+ x^3+ x +1)⊕ (x^7+ x^5+ x^4+ x^3+ x) = = (x^2+1)·φ(x)⊕R(x)$ = {ba}16161,
    где R(x) остаток и degR(x)< deg φ(x).
    Степенное представление для получения произведения элементов поля самое удобное.
    A(x)· B(x) = α178· α238 = α(178+238) = α416 = α161α255161 = {ba}16.

    Для любого ненулевого элемента β поля справедливо β·1 =β. Мультипликативной единицей в GF(28) является элемент {01}16255.
    Все вычисленные произведения для различных представлений операндов эквивалентны (преобразуются в один элемент поля со значением {ba}16).

    Наряду с обычным (классическим) рассмотрением операции умножения элементов в двоичном поле существует более удобная схема. Именно такая схема и реализована в стандарте AES.

    Рассмотрим сущность этого способа умножения


    Пример 7. Другой способ умножения в конечном поле. Пусть задан произвольный многочлен седьмой степени
    $A(x) = a_7x^7+ a_6x^6+ a_5x^5+ a_4x^4+ a_3x^3+ a_2x^2+ a_1x+ a_0$
    и значения его коэффициентов $(a_7 a_6 a_5 a_4 a_3 a_2 a_1 a_0) = (10000011)_2$.

    Умножим его на $x$ и получим $a_7x^8+ a_1x^2+ a_0x$. Этот результат не принадлежит полю GF(28) степень его многочлена больше 7 и его необходимо привести по модулю φ(x) = 1{1b}, после чего такое произведение станет элементом поля GF(28).

    С этой целью определяют значение $ a_7 $, если $а_7 = 0$ то результат уже принадлежит полю, если же $ a_7 = 1$, то достаточно вместо деления выполнить лишь вычитание A(x)x – φ(x) или операцию XOR для произведения A(x)x с φ(x).

    В этом случае при записи A(x) в сдвиговом регистре умножению на x полинома A(x), т.е. $A(x)⊗{00000010} = A(x)⊗{02}$ соответствует сдвиг полинома A(x) на один разряд в сторону старших разрядов (влево, т.е. увеличение вдвое) и, если требуется, применяется операция XOR с неприводимым многочленом поля 1{1b}16 =φ(x).

    В алгоритме стандарта шифрования введена операция (функция) xtime( ), которая по существу и выполняет умножение полинома на х, так как это описано ранее. Многократное применение xtime обеспечивает умножение на x8. Далее вычисляя сумму различных степеней, можно получить результат умножения произвольных элементов поля GF(28).

    Пример 8. Перемножим многочлены A(x) = {c1}16 и B(x) = {11}16, используя их 16-ичные представления и представляя суммой {11} ={10⊕01}.
    {c1}⊗{11}={11000001}⊗{00010001}={c1}⊗{10⊕01}={a4}⊕{c1}=01100101 ={65}16.

    Детализируем все действия. Элемент х в поле GF(28) имеет представление
    x = {02}16=(00000010)2.
    {c1}⊗{11}={c1}⊗{10}⊕{c1}⊗{01}= α178· α100⊕α178· α0={a4}⊕{c1}, так как α178· α100(178+100-255)23={a4}

    Тогда умножение на него приводит просто к сдвигу первого операнда на 1 разряд влево.
    {c1}⊗ {02} = xtime{c1} = 11000001⊗ 00000010= 110000010 — 9-ти разрядное двоичное число. Этот результат выходит за пределы нашего поля. Его возвращают вычитанием неприводимого многочлена поля φ(х), преобразуя в элемент поля. Итоговый результат 10011001 = {99}

    $\begin{array}{r} - \begin{array}{r} 110000010\\ 100011011\\ \end{array} \\ \hline \begin{array}{r} 10011001 \end{array} \end{array}$


    {c1}⊗ {04} = xtime(99) = 10011001⊗ 00000010 =100110010 — 9-ти разрядное двоичное число. Этот результат выходит за пределы нашего поля. Его возвращают вычитанием неприводимого многочлена поля φ(х), преобразуя в элемент поля. Итоговый результат 00101001 = {29}

    $\begin{array}{r} - \begin{array}{r} 100110010\\ 100011011\\ \end{array} \\ \hline \begin{array}{r} 00101001 \end{array} \end{array}$


    Очередной шаг процедуры
    {c1}⊗ {08} = xtime(29) = 00101001⊗ 00000010 = 0101 0010 = {52}.
    Здесь результат не суммируем с φ(x), так как коэффициент $a_7 = 0$.

    И еще один шаг
    {c1}⊗ {10} = xtime(52) = 01010010⊗00000010 = 10100100 = {a4}16.
    Здесь также не суммируем с φ(x), так как коэффициент $a_7 = 0$.
    Таким образом, найдено значение первого слагаемого в сумме для исходного
    выражения, где второе слагаемое равно {c1}16.
    Теперь находим окончательно
    {c1}⊗ {11} = {c1}⊗ {10}⊕ {c1}⊗ {01} = {a4} ⊕ {c1} =10100100⊕ 11000001 = {65} или

    $\begin{array}{r} - \begin{array}{r} 10100100\\ 11000001\\ \end{array} \\ \hline \begin{array}{r} 01100101 \end{array} \end{array}$



    проверка обычным умножением (степенное представление)
    A(x)∙ B(x) = {c1}∙{11} = α178∙α4 = α182
    (по таблицам находим в строке для α1182) α182 соответствует {65}16.

    Еще большего эффекта при производстве вычислений можно достигнуть, если укрупнить элементы, с которыми выполняются манипуляции. Так в криптоалгоритме RIJNDAEL используются 32-разрядные (4-х-байтовые) слова. Составляющие байт разряды не анализируются по отдельности. Такой подход позволяет 4-байтовому слову в соответствие поставить многочлен А(х) степени не более трех, и коэффициенты которого лежат в поле GF(28).

    Операция умножения таких слов
    $A(x) = a_3x^3 + a_2x^2 + a_1x + a_0$ и
    $B(x) = b_3x^3 + b_2x^2 + b_1x+b_0$,
    где $a_i, b_i$єGF(28), i = 0(1)3, выполняется по модулю многочлена степени не более четырех. Взятие результата произведения по модулю неприводимого многочлена степени 4 обеспечивает всегда получение результата произведения, как элемента поля.

    В качестве такого многочлена выбран многочлен $ψ(x) = x^4 + 1$. Он имеет наиболее простую запись, и для него справедливо
    $x_i (mod(x^4+1)) = x_i (mod4)$.
    Последнее свойство оказывается очень полезным при вычислениях.
    Для рассматриваемых многочленов операция сложения выполняется аналогично (XOR поразрядное по mod2)
    $inline$A(x)⊕ B(x) = (a_3⊕ b_3) x^3 ⊕ (a_2⊕ b_2) x^2 ⊕ (a_1⊕ b_1)x ⊕ (a_0⊕ b_0)$inline$.

    Умножение многочленов.
    $inline$A(x)⊗ B(x) = C(x) = (c_6x^6 ⊕ c_5x^5 ⊕ c_4x^4⊕ c_3x^3 ⊕ c_2x^2 ⊕ c_1x^1 ⊕ c_0) mod(x^4+1)$inline$.
    Коэффициенты $c_j, j = 0(1)6$ определяются из соотношений
    $C_0 = a_0⊕b_0$,
    $C_1 = a_1b_0⊕ a_0b_1$,
    $C_2 = a_2b_0 ⊕ a_1b_1⊕a_0b_2$,
    $C_3 = a_3b_0⊕ a_2b_1⊕ a_1b_2⊕a_0b_3$,
    $C_4 = a_3b_1⊕ a_2b_2⊕ a_1b_3$,
    $C_5 = a_3b_2⊕ a_2b_3$,
    $C_6 = a_3b_3$.

    Окончательно результатом D(x) умножения ⊗ двух многочленов по модулю $x^4+1$ будет
    $inline$D(x) = A(x)⊗B(x) = d_3x^3 ⊕ d_2x^2 ⊕ d_1x ⊕ d_0$inline$, где
    $d_0 = a_0b_0⊕ a_3b_1⊕ a_2b_2⊕ a_1b_3$,
    $d_1 = a_1b_0⊕ a_0b_1⊕ a_3b_2⊕ a_2b_3$,
    $d_2 = a_2b_0⊕ a_1b_1⊕ a_0b_2⊕ a_3b_3$,
    $d_3 = a_3b_0⊕ a_2b_1⊕ a_1b_2⊕ a_0b_3$,
    или более кратко в векторно – матричной записи,

    выполним умножение В(х) на х по $mod(х^4+1)$, учитывая свойства многочлена. Такому умножению, как и ранее, соответствует циклический сдвиг байтов в пределах слова в направлении старшего байта. Так как
    $x^4mod(x^4 + 1) = x_i mod4 = x^0 = 1$, то
    $x∙ B(x) = b_2x^3+ b_1x^2+ b_0x+ b_3 => x∙(b_3 b_2 b_1 b_0)$
    реализуется циклический сдвиг байтов.

    Приложение


    Таблица П1 — расширенного поля, неприводимый многочлен φ(х)=Р (х), примитивный элемент α=316



    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 7

      +1
      Алгоритм стандарта AES и шифра RIGNDAEL

      Он Rijndael, а не RIGNDAEL
      Непонятна цель это статьи на Хабре.
      Шифр Rijndael очень хорошо описан и известен.
      Зачем это жевать в 100500-й раз?
        0
        Опечатку поправил. Спасибо.
        Вы попробуйте на основе описания без наличия поля Дешифровать
          0
          Этот шифр настолько хорошо известен, что существуют готовые имплементации шифрования на различных языках программирования. Есть готовые библиотеки, есть имплементации в железе, есть описание алгоритма на основе матричных перестановок.
          В принципе даже можно дешифровать используя только бумагу и ручку, непонятно только зачем. Скорость такого дешифрования будет очень низкая. Полезность минимальная или вообще отсутствует?

          Какое практическое применение этой статьи? Я честно не понимаю.
            0
            А Вы понимаете, что готовые имплементации делались вручную их авторами. Вам не приходилось обучать других, отсюда непонимание подобных публикаций.
            В тех что упомянули 100500 Вам все понятно, и что Вы хотели бы понять.
            Мне лично понятно, что ни одна из 100500 публикаций не может быть использована ни для обучения, ни для практического применения, и я указал почему. А Вы разницы не улавливаете и Ваша оценка ничем не подкреплена, кроме 100500. Мне думается, что это несерьезно, даже возражать не хочется. Но Вы единственный, кто откликнулся. Спасибо.
              0
              А Вы понимаете, что готовые имплементации делались вручную их авторами.

              разумеется
              но для имплементирования шифра на языке программирования мне(или кому бы то ни было) не нужно изучать поля Галуа, чтобы понять как получается S-матрица, достаточно иметь таблицу готовых значений. Так как полином все время один и тот же, то и таблица все время одна и таже. Практический смысл объяснения полей Галуа в данном случае сводится к нулю. Если бы вы описывали коды коррекции, тогда возможно объяснение полиномов и имело бы какой-то смысл.
              Вам не приходилось обучать других, отсюда непонимание подобных публикаций.

              ваши допущения указывают на ваше высокомерие. Намеки же на недостаточность знаний/опыта, при незнании собеседника обычно означают отсутствие аргументов.
              Мне лично понятно, что ни одна из 100500 публикаций не может быть использована ни для обучения, ни для практического применения, и я указал почему.

              наверное вы невнимательно читали, что я вам написал. Хабр это не военный институт (извините, но стиль вашего описания намекают на вашу принадлежность к военным институтам). Материал, который вы публикуете несет нулевой практический смысл, он мог бы иметь теоретический смысл, если бы вы преподавали здесь основы криптографии, да и то сомнительно.

              Если вам очень хочется описать AES, то вы могли рассказать скажем про эволюцию практических имплементаций: ECB, CBC, CTR, XTS и т.д.
              А еще интереснее наверное бы было описание не американских, а российских шифров, их достоинства и недостатки по отношение к AES.
              Меньше полей Галуа и больше интересных фактов :)
              Успехов.
                0
                >Практический смысл объяснения полей Галуа в данном случае сводится к нулю.
                >Материал, который вы публикуете несет нулевой практический смысл.
                Помните у А. С. Пушкина: «Мы почитаем всех нулями, а единицами себя»
                Если Вы знакомы с высшей алгеброй, то должны знать, что таблицы поля меняются и от других параметров, не единым неприводимым многочленом задается поле.
                И не надо за меня решать, что и как мне делать, я вполне самостоятелен.
                Лучше разбирайтесь с комментариями к своей публикации
                Непонимание часто имеет причиной недостаток образования. Выпячивать это не рекомендуется. Еще раз Спасибо.
        0
        >разумеется
        но для имплементирования шифра на языке программирования мне(или кому бы то ни было) не нужно изучать поля Галуа, чтобы понять как получается S-матрица, достаточно иметь таблицу готовых значений. Так как полином все время один и тот же, то и таблица все время одна и таже. Практический смысл объяснения полей Галуа в данном случае сводится к нулю. Если бы вы описывали коды коррекции, тогда возможно объяснение полиномов и имело бы какой-то смысл.

        Возможно потому, что Вам (или кому бы то ни было) всегда чего-то достаточно, в России не созданы ни операционные системы, ни СУБД, ни телефоны, ни электроника, ни микроскопы электронные… Говорить от имени ВСЕХ (без должных полномочий) — это как раз и есть высокомерие.
        Не надо только мне писать о том, что в России создано. Я даже знаю кем создано и где и вообще в курсе.

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое