Научный журнал

Международный журнал прикладных и фундаментальных исследований

ISSN 1996-3955

ИФ РИНЦ = 0,593

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Рахман П.А. 1

---

1 ФГБОУ ВО «Уфимский государственный нефтяной технический университет» Филиал

В рамках данной статьи рассматривается арифметика поля Галуа GF(28) на базе неприводимого многочлена p(x) = x8 + x4 + x3 + x + 1, применяемого в усовершенствованном стандарте шифрования AES. Также рассматривается схема формирования таблиц степеней и логарифмов на базе примитивного элемента α = 3, формулы сложения, умножения и деления, а также инвертирования элементов и возведения в заданную степень. Приводятся примеры выполнения арифметических операций с элементами поля. Также рассматриваются высокопроизводительные схемы прямого умножения и инвертирования элементов.

Статья в формате PDF

1114 KB

поле Галуа

арифметика

эффективные вычисления

стандарт шифрования

1. Neal R.Wagner. The Laws of Cryptography with Java Code. University of Texas San Antonio, 2003.

2. Advanced Encryption Standard. FIPS PUB 197. National Institute of Standards and Technology, U.S. Department of Commerce, 2001.

3. Рахман П.А., Григорьева Т.В. Кодирование информации с применением кодов Рида-Соломона. – Уфа: Изд-во УГНТУ, 2015.

4. Рахман П.А. Алгоритм выбора кратности исправляемых искажений для кодирования информации с применением кодов Рида-Соломона // Международный журнал прикладных и фундаментальных исследований, 2015. – № 10-2. – С. 208–212.

5. Рахман П.А. Рекуррентный алгоритм вычисления формальной производной полинома над полем Галуа и его аппаратная реализация // Международный журнал прикладных и фундаментальных исследований, 2015. – № 12-1. – С. 14–18.

6. Рахман П.А. Рекуррентный алгоритм вычисления усеченной свертки полиномов над полем Галуа и его аппаратная реализация // Международный журнал прикладных и фундаментальных исследований, 2015. – № 12-2. – С. 231–235.

7. Рахман П.А. Арифметика поля Галуа на базе схемы сложения и вычитания логарифмов и ее аппаратная реализация // Международный журнал прикладных и фундаментальных исследований, 2015. – № 12-3. – С. 397–402.

8. Рахман П.А. Арифметика поля Галуа на базе быстрого умножения и инвертирования элементов поля и ее аппаратная реализация // Международный журнал прикладных и фундаментальных исследований, 2015. – № 12-3. – С. 403–408.

В настоящее время информация играет ключевую роль, как в жизни отдельного человека, так и в бизнес-процессах предприятий. Соответственно, защита ее от несанкционированного доступа в системах хранения и каналах передачи данных при помощи технологии шифрования данных является достаточно актуальной задачей [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.

Библиографическая ссылка