В настоящее время информация играет ключевую роль, как в жизни отдельного человека, так и в бизнес-процессах предприятий. Соответственно, защита ее от несанкционированного доступа в системах хранения и каналах передачи данных при помощи технологии шифрования данных является достаточно актуальной задачей [1]. Однако, современные стандарты шифрования данных [2] базируются на специализированных разделах математики, в частности, арифметике поля Галуа GF(28), и для разработки программных или аппаратных реализаций, требуются дополнительные исследования [3-8] и выведение достаточно простых для понимания, и в то же время, высокопроизводительных вычислительных схем для конкретных стандартов шифрования информации.
Арифметика поля Галуа GF(28) с применением логарифмов в стандарте шифрования данных AES. Поле Галуа GF(28) является частным случаем расширенных конечных полей GF(2m) характеристики 2 и имеет широкое применение не только в помехоустойчивом кодировании информации, но и криптографии для защиты информации.
В частности, широко распространенное поле Галуа GF(28) используется в стандарте AES – Advanced Encryption Standard (усовершенствованный стандарт шифрования).
Поле Галуа GF(28) по определению содержит 256 элементов:
Поле Галуа GF(28), по определению являющееся полем многочленов вида 
, образуется на базе простого поля Галуа GF(2) и неприводимого многочлена 8-й степени. В стандарте шифрования AES используется неприводимый многочлен следующего вида:
(1)
В двоичном представлении неприводимый многочлен выглядит как 
, а в десятичном представлении: 
.
Наименьшим примитивным элементом поля GF(28) является элемент 
, и при помощи него можно получить все ненулевые элементы поля, и он применяется в стандарте шифрования AES. В двоичном представлении примитивный элемент поля выглядит как (α)2 = 11, а в десятичном представлении, соответственно, как (α)10 = 3.
Для формирования таблицы степеней примитивного элемента 
используется представленная ниже рекуррентная схема для случая поля Галуа GF(28) с неприводимым многочленом p(x) = x8 + x4 + x3 + x + 1.
Что касается таблицы логарифмов, то ее можно формировать параллельно с формированием таблицы степеней, используя десятичное представление степеней примитивного элемента в качестве индексов таблицы логарифмов.
В двоичном представлении элементов поля операцию умножения на (α)2 = 11 в поле Галуа GF(28) можно свести к операции сдвига влево на один разряд и операции сложения («побитового» XOR), причем в случае если старший бит «предыдущей» степени был ненулевым, то еще выполняется «побитовый» XOR с двоичным эквивалентом (р)2 = 100011011 неприводимого многочлена.
(2)
Под выражением 
понимается сдвиг двоичного числа влево на один разряд с последующей операцией «побитового» XOR результата сдвига с самим числом. Под выражением 
понимается сдвиг двоичного числа влево на один разряд с последующей операцией «побитового» XOR результата сдвига с самим числом, с последующей операцией «побитового» XOR результата с двоичным эквивалентом неприводимого многочлена.
Примечание. Поскольку в десятичном виде примитивный элемент поля GF(28) выглядит как (α)10 = 3, то будем также обозначать k-ую степень примитивного элемента как 3k, а логарифм от элемента a по основанию примитивного элемента как log3a.
Ниже на рис. 1 (в виде матрицы 16 x 16) приведены степени примитивного элемента (α)10 = 3 поля Галуа GF(28), образованного при помощи неприводимого многочлена p(x) = x8 + x4 + x3 + x + 1. Степени примитивного элемента для компактности приведены в десятичном представлении, и расположены построчно (по 16 в строке), начиная с 0-й степени, и заканчивая 255-й.
Рис. 1. Таблица степеней 3k для поля Галуа GF(28) для AES
Примечание 1. Для того, чтобы выбрать в таблице требуемую степень 3k, необходимо выбрать строку и столбец таким образом, чтобы сумма индексов строки и столбца (индексы строк приведены в левом заголовочном столбце серого цвета, индексы столбцов – в верхней заголовочной строке серого цвета) была равна показателю степени k.
Также ниже на рис. 2 (в виде матрицы 16 x 16) приведены логарифмы по основанию примитивного элемента (α)10 = 3 поля GF(28). Логарифмы расположены построчно (по 16 в строке) для всех элементов поля, начиная с (a)10 = 0, заканчивая (a)10 = 255. Заметим, что логарифм от 0 не существует (соответствующая ячейка «N/A»).
Рис. 2. Таблица логарифмов log3a для поля Галуа GF(28)для AES
Примечание 2. Для того, чтобы выбрать в таблице логарифм log3a заданного элемента a поля GF(28), необходимо выбрать строку и столбец таким образом, чтобы сумма индексов строки и столбца (индексы строк приведены в левом заголовочном столбце серого цвета, индексы столбцов – в верхней заголовочной строке серого цвета) была равна десятичному представлению (эквиваленту) элемента a.
Тогда с учетом всего вышесказанного имеем арифметику поля Галуа GF(28), образованного с помощью неприводимого многочлена p(x) = x8 + x4 + x3 + x + 1 и на базе применения логарифмов по основанию примитивного элемента поля (α)10 = 3:
- 
- 
(3)
- 
Кроме того, если необходимо найти обратный элемент по умножению, то можно воспользоваться упрощенным вариантом формулы деления элементов:
- 
. (4)
Наконец, для возведения в степень v заданного элемента a поля GF(28) можно использовать формулу, применив операцию модулярного умножения логарифмов:
- 
(5)
Пример 1. Найдем сумму элементов расширенного поля GF(28), представленных в виде соответствующих чисел «87» и «131» в десятичной системе счисления. Имеем,
.
Таким образом, 
.
Пример 2. Найдем произведение элементов поля GF(28), представленных в виде соответствующих чисел «87» и «131» в десятичной системе счисления. По таблице логарифмов для поля GF(28) имеем логарифмы элементов: 
и 
. Тогда получаем:
.
По таблице степеней для поля GF(28) имеем 3178 = (193)10. Таким образом:
.
Пример 3. Найдем отношение элементов поля GF(28), представленных в виде соответствующих чисел «131» и «193» в десятичной системе счисления. По таблице логарифмов для поля GF(28) имеем логарифмы элементов: 
и 
. Тогда получаем:
.
По таблице степеней имеем 3157 = (191)10. Таким образом:
.
Пример 4. Найдем обратный элемент по умножению для элемента «191», представленного в десятичном виде. По таблице логарифмов имеем логарифм элемента: 
. Тогда обратный элемент:
.
По таблице степеней имеем 398 = (87)10. Таким образом:
.
Пример 5. Возведем элемент «13», представленный в десятичном виде, в заданную степень v = 17. По таблице логарифмов для поля GF(28) имеем логарифм элемента: 
. Тогда по формуле получаем:
.
По таблице степеней имеем 3221 = (81)10. Таким образом,
.
Схемы прямого умножение и инвертирование элементов поля Галуа GF(28) в криптографическом стандарте AES. В случае необходимости высокопроизводительного прямого умножения элементов a и b поля Галуа GF(28), можно использовать заранее подготовленную свертку многочленов a(x) и b(x) по модулю p(x) = x8 + x4 + x3 + x + 1:
Рис. 3. Таблица обратных элементов по умножению для поля Галуа GF(28) для AES
Аппаратную реализацию схемы умножения мы не будем приводить в силу ее громоздкости. Отметим лишь, что ее несложно построить при помощи 64 двухвходовых логических элементов «И» и 8 многовходовых сумматоров по модулю 2.
Также в случае необходимости применения высокопроизводительного вычислителя обратного элемента по умножению (для ускорения операции деления), можно использовать заранее вычисленную таблицу обратных элементов по умножению.
Ниже на рис. 3 (в виде матрицы 16 x 16) приведены обратные элементы по умножению для элементов поля Галуа GF(28), представленные в десятичном виде. Обратные элементы по умножению расположены построчно (по 16 в строке) для всех элементов поля, начиная с (a)10 = 0, заканчивая (a)10 = 255. Заметим, что обратного элемента по умножению для нуля не существует (соответствующая ячейка «N/A»).
Для аппаратной реализации таблицы можно использовать ПЗУ емкостью 256 x 8 бит.
Заключение
Таким образом, в рамках данной статьи рассмотрено поле Галуа GF(28) на базе неприводимого многочлена p(x) = x8 + x4 + x3 + x + 1, которое применяется в криптографическом стандарте AES (усовершенствованный стандарт шифрования). Также рассмотрены схема формирования таблиц степеней и логарифмов на базе примитивного элемента (α)10 = 3, формулы сложения, умножения и деления, а также инвертирования элементов и возведения в заданную степень. Приведены примеры выполнения арифметических операций с элементами поля. Также рассмотрены высокопроизводительные схемы прямого умножения и инвертирования элементов поля.
Полученные результаты могут быть использованы при разработке эффективных программных и аппаратных реализаций вычислительных блоков в рамках шифрования и дешифрования информации по криптографическому стандарту AES.