Генерация ключей для шифрования на основе

Конечных полей

Введение

Один из методов генерации ключей основан на теории конечных полей. Средства генерации конечных полей за цикл длиной qⁿ вырабатывают qⁿ-1 различных последовательностей (элементов) без их повторения, где q – характеристика поля (основание системы счисления), n - степень расширения поля [3,7]. Последовательности, вырабатываемые согласно теории конечных полей, являются псевдослучайными (они не вырабатывают нулевой элемент), также при генерации ключей для шифрования случайный их характер является одним из основных требований, обеспечивающим необходимую стойкость шифра. Стойкость криптографической системы увеличивается с увеличением длины последовательности и степени их случайности. Рассмотрим методику генерации псевдослучайных элементов конечных полей.

Конечные поля на основе колец многочленов

Конечные поля можно построить из колец многочленов так же, как строятся поля из кольца целых чисел. Пусть имеется кольцо многочленов GF(q)[ x ] над полем q. Выбирая из GF(q)[ x ] произвольный многочлен p (x), можно построить кольцо отношений, используя p (x) в качестве модуля для заданной арифметики этого кольца. Для произвольного приведенного p (x) над полем q кольцом многочленов по модулю p (x) называется множество всех многочленов GF(q)[ x ], степень которых не превосходит степени p (x), с операциями сложения и умножения по модулю p (x). Это кольцо принято обозначать GF(q)[ x ]/ p (x). Произвольный многочлен r (x) кольца GF(q)[ x ] можно отобразить в многочлен кольца GF(q)[ x ]/ p (x) с помощью соответствия r (x) ® R_p(x) GF(q)[ x ] - остаток от деления GF(q)[ x ]/ p (x). Два многочлена a (x) и r (x) из GF(q)[ x ], отображаемые в один и тот же многочлен из GF(q)[ x ]/ p (x), называются сравнимыми:

r (x) = a (x)[mod p (x)]. (2.1)

Тогда a (x) = p (x) × S (x) + r (x) для некоторого многочлена S (x).

Пример: в кольце многочленов над GF(2) выберем p (x) = x ³ + 1. Тогда кольцо многочленов по модулю p (x) GF(2)[ x ] / (x ³ + 1). Оно состоит из элементов {0, 1, x, x+ 1, x ², x ² + 1, x ² +x, x ² +x+ 1}. В этом кольце умножение выполняется так:

(x ² + 1)×(x ²) = R [(x ²+1) × (x ²)] = R [ x (x ³+1) + x ² + x ] = x ² + x.

Здесь использована редукция x ⁴ = x (x³+ 1) + x.

Кольцо многочленов по модулю приведенного многочлена является полем тогда и только тогда, когда p (x) прост. Если над полем GF(q) найден простой многочлен p (x), то можно построить поле GF(qⁿ),содержащее qⁿ элементов, где q – характеристика поля, n – степень pасширения поля. В этом построении элементы представляются многочленами над GF(q) степени n – 1. Всего существует qⁿ таких многочленов и, следовательно, столько же элементов поля.

Например, поле GF(2²) можно построить по полю GF(2), используя примитивный полином p (x) = x ² + x+ 1. Перебирая все возможные разложения, легко проверить непроводимость этого многочлена. Элементы поля задаются многочленами (0, 1, x, x+ 1).

В таблице 2.1 показаны способы представления элементов поля GF(4), а таблицы сложения и умножения их (таблицы 2.2 и 2.3) даны ниже.

Таблица 2.1

Многочленные обозначения	Двоичные обозначения	Целочисленные Обозначения	Степенные обозначения
			х 0
х			х 1
х +1			х 2

Таблица 2.2

+			х	х +1
x x +1	x x +1	x +1 x	х x +1	х +1 х

Таблица 2.3

*			х	х +1
х х +1		х х +1	х х +1	х +1 х

Примитивные элементы

Примитивным элементом поля GF(q) называется такой элемент a, что все элементы поля, за исключением 0, могут быть представлены в виде степени элемента a. Например, в поле GF(5) = 2, 2¹=2, 2²=4, 2³=3, 2⁴=1, так что 2 является примитивным элементом поля GF(5). Примитивные элементы полезны при построении полей, если один из них найден, то, перемножая степени этого примитивного элемента, можно составить таблицу умножения в поле. Каждое поле содержит примитивный элемент.

Пусть b ₁, b ₂,…, b_{q- 1} ненулевые элементы поля GF(q), тогда

х^{q- 1}-1 = (x - b ₁)×(x - b ₂)…(x - b_{q- 1}),

и пусть b - какой-либо ненулевой элемент из GF(q), тогда

b^{q- 1} = (b - b ₁)×(b - b ₂)…(b - b_{q- 1}) = 1

Тогда b является корнем многочлена x^{q- 1}-1.

Группа ненулевых элементов поля GF(q) по умножению является циклической. Для простого q- 1 это тривиально, так как порядок всех элементов, за исключением 0 и 1 равен q- 1, так что каждый элемент примитивен. В каждом поле Галуа имеется примитивный элемент [7].

Структура конечного поля

С помощью примитивного элемента можно построить поле Галуа. Например, в поле GF(8) порядок каждого ненулевого элемента равен 7 или делит на 7, так как 7 – простое число. Поэтому каждый ненулевой элемент является примитивным. Поле GF(8) можно построить с помощью многочлена
p (x) = x ³ +x ² + 1. Другие неприводимые многочлены приведены в таблице приложения 2. Основываясь на примитивном элементе a, который является корнем p (x)получим:

a = x ¹ = 010,

a ² = x ² = 100,

a ³ = x ² + 1 = 101,

a ⁴ = x ² + x+ 1 = 111,

a ⁵ = x+ 1 = 011,

a ⁶ = x ² + x = 110,

a ⁷ = a ⁰= x ⁰ = 001.

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

a ⁵ × a ⁶ = a ⁴, a ⁵ + a ⁶ = a ³.

При построении расширения поля в виде множества многочленов удоб-но, чтобы примитивному многочлену соответствовал примитивный элемент поля. Тогда построение поля можно осуществлять с помощью простых многочленов, называемых примитивными. Примитивным многочлен p (x)над полем GF(q) называется простой многочлен над GF(q), такой, что в расширении поля, построенным по модулю p (x),соответствующему многочлену, элемент поля является примитивным. Для каждого поля существуют примитивные многочлены всех степеней [7].

Число элементов наименьшего подполя поля GF(q) называется характеристикой поля GF(q). Каждое поле Галуа содержит единственное наименьшее подполе, число элементов которого равно простому числу. Следовательно, характеристика каждого поля Галуа является простым числом. Например, для GF(32) наименьшее подполье GF(2) содержит два элемента.

В поле Галуа GF(q) можно построить подполе GF(p), где p – простое число. В частности, если q является простым числом, то поле GF(q) можно интерпретировать как поле чисел по модулю q. Следовательно, для заданного простого числа существует только одно поле с заданным числом элементов, хотя оно может быть представлено разными способами. Два поля, отличающиеся только представлениями, называются изоморфными.

Пусть GF(q) – некоторое поле, пусть GF(Q) – расширение поля GF(q) и пусть b - элемент GF(Q). Простой многочлен f (x) наименьшей степени над GF(q), для которого f (b) = 0, называется минимальным многочленом элемента b над GF(q). Каждый элемент b из GF(Q) имеет единственный минимальный многочлен над GF(q). Если минимальный элемент многочлена f (x) равен b и b является корнем многочлена g (x), то f (x) делит g (x).

Элемент b является всегда корнем многочлена x^Q - x, который разлагается на простые многочлены над полем GF(q):

х^Q – x = f ₁(x) × f ₂(x) …f_k (x).

Если Q = q^m, то каждый делитель многочлена x - x, неприводимый над полем GF(q), имеет степень равную m или меньшую.

При Q = q разложение сводится к равенству:

х^q - x = x× (x - b ₁)×(x - b ₂)…(x - b_{q- 1}).

Следовательно, минимальный многочлен над полем GF(q) элемента b, принадлежащего GF(q), является многочленом первой степени f (x) = x - b.

Пусть a - примитивный элемент поля Галуа GF(Q), являющегося расширением поля GF(q), и пусть m – степень минимального многочлена f (x) элемента a над GF(q). Тогда число элементов в поле равно Q = q^m и каждый элемент может быть представлен в виде:

b = a_{m- 1} a^{m- 1} + a_{m- 2} a^{m- 2} +…+a ₁ a+a ₀,

где a_{m- 1}, a_{m- 2}, …, a ₀ – элементы поля GF(q).

В данном случае порядок элемента b (или цикл повторения) равен делителю числа q^m- 1. Например, все ненулевые элементы поля GF(64) могут быть представлены как степени примитивного элемента a. Этими элементами являются 0, 1, a, a ², …, a ⁶², и

х ⁶³- x = x× (x - 1)×(x - a)×(x - a ²)…(x - a ⁶²).

Так как (a ²¹)³ = a ⁶³ = 1, то порядок элемента a ²¹ равен 3. Тот же порядок имеет элемент a ⁴².

Каждое поле Галуа содержит p^m элементов, где p – некоторое простое число, а m – положительное целое число.

В поле GF(q) = GF(p^m) характеристики p для любых элементов a, b и любого положительного целого m справедливо

Здесь a ± b и a × b также корни многочлена x - x и множество корней замкнуто относительно операции сложения.

Для каждого целого положительного m над каждым конечным полем GF(q) существует хотя бы один простой многочлен степени m.

Двойственный многочлен f ^*(x) для f (x) определяется как

x^m × f ,

где m – степень f (x).