Презентация - "Лекция 3. Поля Галуа"

Лекция 3. Поля Галуа. Полиномиальное представление шифра AES

Поля Галуа
Для работы с информацией при кодировании и декодировании данных все арифметические операции выполняются в полях Галуа. Применяется так называемая полиномиальная арифметика или арифметика полей Галуа. Таким образом, результат любой операции также является элементом данного поля. Конкретное поле Галуа состоит из фиксированного диапазона чисел. Характеристикой поля называют некоторое простое число p. Порядок поля, т.е. количество его элементов, является некоторой натуральной степенью характеристики pm, где m∈N. При m=1 поле называется простым. В случаях, когда m>1, для образования поля необходим еще порождающий полином степени m, такое поле называется расширенным. GF(p^m) – обозначение поля Галуа.

Поля Галуа
Задача 1. Представить числа 𝑎 𝑘 в виде полинома над GF( 2 8 ).
Возьмем два числа 𝑎 𝑘 𝑎 1 = 13 16 𝑎 2 = 𝐵𝐹 16
Переведем числа из 16 системы счисления в 2 систему счисления
13 16 = 00010011 2 𝐵𝐹 16 = 10111111 2
Каждый коэффициент 𝑎 𝑘 может быть представлен восьмиразрядным двоичным числом, которому соответствует полином 7-й степени коэффициенты которого (0 или 1) определяется значениями соответствующих битов

Поля Галуа

Поля Галуа

Поля Галуа
В полиномиальном представлении операция умножения представляется в виде умножения полиномов по модулю 𝑚(𝑥) – неприводимого двоичного полинома степени 8. Для алгоритма AES 𝑚 𝑥 = 𝑥 8 + 𝑥 4 + 𝑥 3 +𝑥+1
Задача произвести умножение чисел BF и 13 над полем Галуа.

Поля Галуа
Поскольку старшая степень x превышает 7, добавим к результату полином m(x), домноженный на соответствующую степень x:

Поля Галуа
Сократим кратные слагаемые:

Поля Галуа
Старшая степень x превышает 7 добавим к результату

Поля Галуа
Сократим кратные слагаемые и получим результат

Поля Галуа
Представим полином в двоичном виде

Поля Галуа
Получим BF ∙ 13 = 11011111 = DF