Онлайн
Alvaros
.
- Регистрация
- 14.05.16
- Сообщения
- 21.452
- Реакции
- 101
- Репутация
- 204
Эта публикация вызвана необходимостью дать возможность обучаемым изучать и моделировать процессы шифрования/расшифрования и дешифрования последнего стандарта США. Ознакомление с имеющимися публикациями в сети не соответствуют программе обучения в силу их поверхностного подхода, неполноты изложения, и отсутствия должной строгости. Например, нигде не встречается выбор и задание примитивного элемента, формирующего поле, без чего работу и подготовку специалиста, особенно криптоаналитические явления и процессы, организовать и моделировать невозможно. В этой работе используется описание, несколько отличное от оригинала AES, представленного FIPS PUB 197. Здесь описывается шифр AES, с использованием матриц над GF(2[SUP]8[/SUP]), но примечания работы сохраняются, т. е. шифр реализуется над конечным расширенным полем GF (2[SUP]8[/SUP]). На русском языке достаточно полная и доступная версия шифра изложена Зензиным О.С. и Ивановым М.А.
МАТЕМАТИЧЕСКИЕ ОСНОВЫ СТАНДАРТА ШИФРОВАНИЯ AES США
AES – блочный шифр с длиной блоков равной 128 битам, и шифр поддерживает ключи длиной
Шифр AES преобразует исходное состояние блока, обозначаемое символом S (State) и принадлежащее множеству матриц {M4(GF(2[SUP]8[/SUP]))} (то есть S є{M4(GF (2[SUP]8[/SUP]))} – матрица 4 × 4 байта, с ее элементами (коэффициентами) в GF (2[SUP]8[/SUP])), к другому шифрованному состоянию в {M4 (GF (2[SUP]8[/SUP]))}.
Пример 1. Блок данных длиной в 128 = 4·32, 4 слова по 32 разряда представляется квадратной таблицей байтов из 4-х строк и 4-х столбцов. Каждая строка содержит байты из 4-х разных 32 разрядных слов, а столбец – байты одного и того же 32-разрядного слова. Весь квадрат образован 4×4 = 16 байтами, которые могут обрабатываться как самостоятельные единицы.
Именно такой подход к представлению данных определяет и обеспечивает байт-ориентированную структуру шифра и обработку данных. Ключ шифра K расширяется в
Представление данных, выбранное для элементов поля GF(2[SUP]8[/SUP])
В шифре AES используется байтовая структура данных. Представление, выбранное в [1] из векторного пространства GF(2[SUP]8[/SUP]), соответствующего полю GF(2[SUP]8[/SUP])[X]/< φ(x) >, где φ(x) – неприводимый многочлен,
. Для удобства и лучшего понимания изучаемого материала, а для уяснения деталей выполнения вычислений с карандашом в руках ниже приводятся многочисленные числовые примеры и следующая таблица 1.
Таблица 1. Соответствие десятичных, шестнадцатеричных, двоичных чисел и многочленов
В работе используются четыре представления для обозначения каждого элемента расширенного поля в GF(2[SUP]8[/SUP]), которые являются эквивалентными одно другому.
Представление данных, используемых в шифре AES
Выберем десятичное целое число, эквивалент которого будем представлять
различными формами в других системах счисления:
1. 212[SUB]10[/SUB], десятичным видом – числом в 10-ой системе счисления.
2. {11010100}b, представление элементов сообщения двоичным вектором – элементом векторного пространства GF(2[SUP]8[/SUP]) двоичных векторов,
3.
4. {D4}[SUB]16[/SUB], – шестнадцатеричное представление – числом в 16-системе счисления,
⊕ – операция поразрядного суммирования векторов из GF(2[SUP]8[/SUP]) по mod2 (без переноса 1 в старший разряд).
⊗ – операция умножения элементов (векторов, многочленов, чисел) из поля GF(2[SUP]8[/SUP])
Алгоритм стандарта AES и шифра RIGNDAEL оперирует с байтами информации, которые отождествляются с элементами конечного поля Галуа GF(2[SUP]8[/SUP]). Степень расширения простого поля GF(2) равна 8. Все элементы расширенного поля при представлении их многочленами имеют показатель степень не более семи (≤ 7).
Достигается такое положение приведением всех результатов действий с элементами поля по модулю неприводимого многочлена степени 8, который является формирующим многочленом для этого поля. Кроме неприводимого многочлена для построения поля необходимо задавать примитивный элемент.
В рассматриваемом алгоритме примитивный элемент задан (его порядок должен быть равен порядку мультипликативной группы поля), а многочлен фиксирован и имеет вид φ(x). Не располагая этими характеристикам, работать со стандартом не получится
или 1{1b} в 16-ричной форме.
Шестнадцатеричная запись неприводимого многочлена 1{1b} использует 9 разрядов и многочлен φ(x) не принадлежит полю GF(2[SUP]8[/SUP]).
Таблица П1 представления элементов поля GF(2[SUP]8[/SUP]) (в конце текста в Приложении).
В таблице П1 размещены все элементы поля в порядке возрастания показателя степени примитивного элемента (α = 00000011[SUB]2[/SUB] = 3[SUB]10[/SUB]), мультипликативный порядок которого равен 255.
Рассмотрим примеры выполнения арифметических операций над элементами поля при различных представлениях этих элементов. Любой байт исходного текста (элемент поля) формально можно представить строкой символов
Пример 2. Элемент расширенного поля GF(2[SUP]8[/SUP]) задан в виде двоичного вектора:
Описание многочленом этого элемента имеет вид:
Если доопределить значения ai двоичными значениями, i = 0(1)7, например, так
так как
Шестнадцатеричное представление этого элемента α[SUB]16[/SUB] = {с1}={11000001}, а десятичное
α[SUB]10[/SUB] =
При выбранном примитивном элементе поля степенное представление
α[SUB]i[/SUB] ={с1}= α[SUP]178[/SUP].
Входим в таблицу П1 элементов поля GF(2[SUP]8[/SUP]) со значением α[SUP]178[/SUP] и в соответствующих столбцах для этой строки находим описанные представления, а также другие характеристики этого элемента поля. Для понимания возможных преобразований с элементами поля рассмотрим операции с его элементами в деталях.
Суммирование элементов поля GF(2[SUP]8[/SUP])
Сложение в рассматриваемом поле представляет операцию поразрядного суммирования значений разрядов слагаемых без переноса единицы в старший разряд. Это операция исключающего ИЛИ (EXOR – EXLUSIV OR) часто обозначается просто XOR. В модулярной арифметике такое сложение называется суммированием по модулю два (mod2).
Пример 3. Выберем в качестве операндов многочлены
Двоичное представление суммы многочленов по модулю два имеет вид
[A(x)⊕B(x)]mod2 = {11000001}⊕ {00001101} = {11001100};
16-ричное представление {c1}⊕{0D}={cc}sub>16=α[SUP]55[/SUP];
степенное представление α[SUP]178[/SUP] + α[SUP]238[/SUP] = α[SUP]55[/SUP]· {α[SUP]123[/SUP] + α[SUP]183[/SUP]} = α[SUP]55[/SUP]· 1 = α[SUP]55[/SUP].
Представление многочленами
Заметим, что при сложении операндов степень многочлена результата не
увеличивается, и необходимость приведения его по модулю неприводимого многочлена поля φ(x) не возникает. Коэффициенты результата приводятся по модулю два, т. е. все четные коэффициенты обращаются в нуль.
В полях характеристики 2 действия сложения и вычитания операндов равнозначны. Для каждого элемента поля в аддитивной группе обратным к нему (противоположным) является он сам. Так, для элемента (а) противоположным является (-а), так как а + (-а) = 0. Нулевой элемент (единица аддитивной группы поля, нейтральный элемент) в шестнадцатеричном виде – это {00}[SUB]16[/SUB].
Умножение элементов поля GF(2[SUP]8[/SUP])
Операция обычного умножения операндов (в отличие от модулярного ⊗) обозначается точкой между операндами, или знак умножения вообще опускается, когда не возникает опасности разночтения. Операнды в двоичном представлении умножаются по обычным правилам «столбиком». Будем перемножать те же, что и ранее операнды.
Пример 4. Умножение операндов в двоичном представлении
А(х)· В(х) = {c1}·{0d}
Остаток от деления получает вид двоичного, многочленного и 16-ричного представлений (как элемент поля)
R(x) = 01011 1010[SUB]2[/SUB] =
Степенное представление здесь не приводим, но по таблице П1 его можно найти.
Остаток от деления на неприводимый многочлен φ(x) в его двоичном представлении результата умножения операндов принимаем в качестве произведения операндов как элементов поля GF(2[SUP]8[/SUP]).
Выполним умножение операндов в представлении многочленами.
Пример 5. Умножение операндов элементов поля в многочленном представлении
А(х) ⊗ В(х) = {c1}⊗{0d}
A(x) ⊗ B(x) =
=(x[SUP]10[/SUP]+
=(x[SUP]10[/SUP]+
Здесь символ (moddφ (x),2) обозначает приведение по двойному модулю: многочлен по модулю φ(x), а его коэффициенты по модулю два, т.е. четные коэффициенты обнуляются. Получившаяся степень (deg(A(x)⊗ B(x)) =10) результата произведения выводит (этот многочлен — результат) за пределы поля. Чтобы результат принадлежал полю, его приводят (редуцируют, делят) по модулю неприводимого многочлена. Выполним такое деление обычным способом (уголком)
Пример 6. Необходимость деления многочленов возникает при
их умножении А(х)⊗В(х)/ φ(x).(Операции деления в поле нет, когда надо что-то поделить, это что-то умножают на обратный элемент делителя в поле)
– остаток отделения на φ(x) принадлежит полю GF(2[SUP]8[/SUP]), и его принимаем в качестве окончательного результата
Иначе умножение A(x)⊗B(x) представимо как
где R(x) остаток и degR(x)< deg φ(x).
Степенное представление для получения произведения элементов поля самое удобное.
A(x)· B(x) = α[SUP]178[/SUP]· α[SUP]238[/SUP] = α[SUP](178+238)[/SUP] = α[SUP]416[/SUP] = α[SUP]161[/SUP]α[SUP]255[/SUP] =α[SUP]161[/SUP] = {ba}[SUB]16[/SUB].
Для любого ненулевого элемента β поля справедливо β·1 =β. Мультипликативной единицей в GF(2[SUP]8[/SUP]) является элемент {01}[SUB]16[/SUB] =α[SUP]255[/SUP].
Все вычисленные произведения для различных представлений операндов эквивалентны (преобразуются в один элемент поля со значением {ba}[SUB]16[/SUB]).
Наряду с обычным (классическим) рассмотрением операции умножения элементов в двоичном поле существует более удобная схема. Именно такая схема и реализована в стандарте AES.
Рассмотрим сущность этого способа умножения
Пример 7. Другой способ умножения в конечном поле. Пусть задан произвольный многочлен седьмой степени
и значения его коэффициентов
Умножим его на
С этой целью определяют значение
В этом случае при записи A(x) в сдвиговом регистре умножению на x полинома A(x), т.е.
В алгоритме стандарта шифрования введена операция (функция) xtime( ), которая по существу и выполняет умножение полинома на х, так как это описано ранее. Многократное применение xtime обеспечивает умножение на x[SUP]8[/SUP]. Далее вычисляя сумму различных степеней, можно получить результат умножения произвольных элементов поля GF(2[SUP]8[/SUP]).
Пример 8. Перемножим многочлены A(x) = {c1}[SUB]16[/SUB] и B(x) = {11}[SUB]16[/SUB], используя их 16-ичные представления и представляя суммой {11} ={10⊕01}.
{c1}⊗{11}={11000001}⊗{00010001}={c1}⊗{10⊕01}={a4}⊕{c1}=01100101 ={65}[SUB]16[/SUB].
Детализируем все действия. Элемент х в поле GF(2[SUP]8[/SUP]) имеет представление
x = {02}[SUB]16[/SUB]=(00000010)[SUB]2[/SUB].
{c1}⊗{11}={c1}⊗{10}⊕{c1}⊗{01}= α[SUP]178[/SUP]· α[SUP]100[/SUP]⊕α[SUP]178[/SUP]· α[SUP]0[/SUP]={a4}⊕{c1}, так как α[SUP]178[/SUP]· α[SUP]100[/SUP]=α[SUP](178+100-255)[/SUP]=α[SUP]23[/SUP]={a4}
Тогда умножение на него приводит просто к сдвигу первого операнда на 1 разряд влево.
{c1}⊗ {02} = xtime{c1} = 11000001⊗ 00000010= 110000010 — 9-ти разрядное двоичное число. Этот результат выходит за пределы нашего поля. Его возвращают вычитанием неприводимого многочлена поля φ(х), преобразуя в элемент поля. Итоговый результат 10011001 = {99}
{c1}⊗ {04} = xtime(99) = 10011001⊗ 00000010 =100110010 — 9-ти разрядное двоичное число. Этот результат выходит за пределы нашего поля. Его возвращают вычитанием неприводимого многочлена поля φ(х), преобразуя в элемент поля. Итоговый результат 00101001 = {29}
Очередной шаг процедуры
{c1}⊗ {08} = xtime(29) = 00101001⊗ 00000010 = 0101 0010 = {52}.
Здесь результат не суммируем с φ(x), так как коэффициент
И еще один шаг
{c1}⊗ {10} = xtime(52) = 01010010⊗00000010 = 10100100 = {a4}[SUB]16[/SUB].
Здесь также не суммируем с φ(x), так как коэффициент
Таким образом, найдено значение первого слагаемого в сумме для исходного
выражения, где второе слагаемое равно {c1}[SUB]16[/SUB].
Теперь находим окончательно
{c1}⊗ {11} = {c1}⊗ {10}⊕ {c1}⊗ {01} = {a4} ⊕ {c1} =10100100⊕ 11000001 = {65} или
проверка обычным умножением (степенное представление)
A(x)∙ B(x) = {c1}∙{11} = α[SUP]178[/SUP]∙α[SUP]4[/SUP] = α[SUP]182[/SUP]
(по таблицам находим в строке для α1[SUP]182[/SUP]) α[SUP]182[/SUP] соответствует {65}[SUB]16[/SUB].
Еще большего эффекта при производстве вычислений можно достигнуть, если укрупнить элементы, с которыми выполняются манипуляции. Так в криптоалгоритме RIJNDAEL используются 32-разрядные (4-х-байтовые) слова. Составляющие байт разряды не анализируются по отдельности. Такой подход позволяет 4-байтовому слову в соответствие поставить многочлен А(х) степени не более трех, и коэффициенты которого лежат в поле GF(2[SUP]8[/SUP]).
Операция умножения таких слов
где
В качестве такого многочлена выбран многочлен
Последнее свойство оказывается очень полезным при вычислениях.
Для рассматриваемых многочленов операция сложения выполняется аналогично (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$.
Коэффициенты
Окончательно результатом D(x) умножения ⊗ двух многочленов по модулю
$inline$D(x) = A(x)⊗B(x) = d_3x^3 ⊕ d_2x^2 ⊕ d_1x ⊕ d_0$inline$, где
или более кратко в векторно – матричной записи,
выполним умножение В(х) на х по
реализуется циклический сдвиг байтов.
Приложение
Таблица П1 — расширенного поля, неприводимый многочлен φ(х)=Р (х), примитивный элемент α=3[SUB]16[/SUB]
