Арифметика конечных полей

В математике , арифметика конечных полей — это арифметика в конечном поле ( поле содержащем конечное число элементов ) в отличие от арифметики в поле с бесконечным числом элементов, например поле рациональных чисел .

Существует бесконечно много различных конечных полей. Их число элементов обязательно имеет вид p ^н где p — простое число , n — целое положительное число , а два конечных поля одинакового размера изоморфны . Простое число p называется характеристикой поля, а целое положительное число n называется размерностью поля над его простым полем .

Конечные поля используются во множестве приложений, в том числе в классической теории кодирования в линейных блочных кодах, таких как коды BCH и коррекция ошибок Рида-Соломона , в алгоритмах криптографии , таких как алгоритм шифрования Rijndael ( AES ), в планировании турниров и в план экспериментов .

Эффективное

Конечное поле с p ^н элементов обозначается GF( p ^н ) и называется также полем Галуа порядка p ^н , в честь основателя теории конечного поля Эвариста Галуа . GF( p ), где p — простое число, представляет собой просто кольцо целых чисел по модулю p . То есть можно выполнять операции (сложение, вычитание, умножение), используя обычную операцию над целыми числами с последующим сокращением по модулю p . Например, в GF(5) 4 + 3 = 7 сокращается до 2 по модулю 5. Деление — это умножение на обратный модуль p , который можно вычислить с помощью расширенного алгоритма Евклида .

Частным случаем является GF(2) , где сложение — это исключающее ИЛИ (XOR), а умножение — AND . Поскольку единственным обратимым элементом является 1, деление является тождественной функцией .

Элементы GF( p ^н ) можно представить в виде полиномов степени строго меньше n над GF( p ). Затем операции выполняются по модулю m(x) , где m(x) — неприводимый многочлен степени n над GF( p ), например, с использованием полиномиального деления в длину . Сложение — это обычное сложение многочленов, но коэффициенты уменьшаются по модулю p . Умножение также является обычным умножением многочленов, но с коэффициентами, умноженными по модулю p , и многочленами, умноженными по модулю многочлена m(x) . Это представление в терминах полиномиальных коэффициентов называется мономиальным базисом (также известным как «полиномиальный базис»).

Существуют и другие представления элементов GF( p ^н ); некоторые из них изоморфны полиномиальному представлению, приведенному выше, а другие выглядят совершенно иначе (например, с использованием матриц). Использование обычного базиса может иметь преимущества в некоторых контекстах.

Когда штрих равен 2, принято выражать элементы GF( p ^н ) в виде двоичных чисел , где коэффициент каждого члена многочлена представлен одним битом в двоичном выражении соответствующего элемента. Фигурные скобки («{» и «}») или подобные разделители обычно добавляются к двоичным числам или их шестнадцатеричным эквивалентам, чтобы указать, что значение дает коэффициенты основы поля, таким образом представляя элемент поля. Например, ниже приведены эквивалентные представления одного и того же значения в конечном поле характеристики 2:

Полиномиальный	х 6 + х 4 + х + 1
Двоичный	{01010011}
Шестнадцатеричный	{53}

Примитивные полиномы

Существует множество неприводимых полиномов (иногда называемых приводящими полиномами ), которые можно использовать для создания конечного поля, но не все они приводят к одному и тому же представлению поля.

Монический имеющий неприводимый полином степени n, коэффициенты из конечного поля GF( q ), где q = p ^т для некоторого простого числа p и натурального числа t называется примитивным многочленом , если все его корни являются примитивными элементами GF( q ^н ). В полиномиальном представлении конечного поля это означает, что x является примитивным элементом. Существует хотя бы один неприводимый многочлен, для которого x является примитивным элементом. Другими словами, для примитивного многочлена степени x порождают каждое ненулевое значение в поле.

В следующих примерах лучше не использовать полиномиальное представление, поскольку значение x меняется между примерами. Монический неприводимый полином x ⁸ + х ⁴ + х ³ + x + 1 над GF(2) не является примитивным. Пусть λ — корень этого многочлена (в полиномиальном представлении это будет x ), то есть λ ⁸ + л ⁴ + л ³ + λ + 1 знак равно 0 . Теперь я ⁵¹ = 1 , поэтому λ не является примитивным элементом GF(2 ⁸ ) и порождает мультипликативную подгруппу порядка 51. Монический неприводимый полином x ⁸ + х ⁴ + х ³ + х ² + 1 над GF(2) является примитивным, и все 8 корней являются генераторами GF(2 ⁸ ) .

Все подружки(2 ⁸ ) имеют всего 128 образующих (см. Число примитивных элементов ), причем для примитивного многочлена 8 из них являются корнями приводящего многочлена. Наличие x в качестве генератора конечного поля полезно для многих вычислительных математических операций.

Сложение и вычитание

Сложение и вычитание выполняются путем сложения или вычитания двух таких полиномов вместе и уменьшения результата по модулю характеристики.

В конечном поле с характеристикой 2 сложение по модулю 2, вычитание по модулю 2 и исключающее ИЛИ идентичны. Таким образом,

Полиномиальный	( х 6 + х 4 + х + 1) + ( х 7 + х 6 + х 3 + х ) = х 7 + х 4 + х 3 + 1
Двоичный	{01010011} + {11001010} = {10011001}
Шестнадцатеричный	{53} + {CA} = {99}

При регулярном сложении многочленов в сумме будет слагаемое 2 x ⁶ . Этот член становится 0 x ⁶ и отбрасывается, когда ответ уменьшается по модулю 2.

Вот таблица с нормальной алгебраической суммой и конечной полевой суммой характеристики 2 нескольких полиномов:

п 1	п 2	п 1 + п 2 под...
		К[ х ]	ГФ(2 н )
х 3 + х + 1	х 3 + х 2	22x 3 + х 2 + х + 1	х 2 + х + 1
х 4 + х 2	х 6 + х 2	х 6 + х 4 + 2x 2	х 6 + х 4
х + 1	х 2 + 1	х 2 + х + 2	х 2 + х
х 3 + х	х 2 + 1	х 3 + х 2 + х + 1	х 3 + х 2 + х + 1
х 2 + х	х 2 + х	22x 2 + 2x	0

В приложениях информатики операции упрощаются для конечных полей характеристики 2, также называемой GF(2 ^н ) Поля Галуа , что делает эти поля особенно популярным выбором для приложений.

Умножение

Умножение в конечном поле — это умножение по модулю приводящего многочлена неприводимого , используемого для определения конечного поля. (То есть, это умножение с последующим делением с использованием уменьшающего полинома в качестве делителя - остаток является произведением.) Символ «•» может использоваться для обозначения умножения в конечном поле.

Конечное поле Рейндала (AES)

Рейндал (стандартизованный как AES) использует конечное поле характеристики 2 с 256 элементами, которое также можно назвать полем Галуа GF(2 ⁸ ). Он использует следующий уменьшающий полином для умножения:

х ⁸ + х ⁴ + х ³ + х + 1.

Например, {53} • {CA} = {01} в поле Рейндала, потому что

	( х 6 + х 4 + х + 1)( х 7 + х 6 + х 3 + х )
=	( х 13 + х 12 + х 9 + х 7 ) + ( х 11 + х 10 + х 7 + х 5 ) + ( х 8 + х 7 + х 4 + х 2 ) + ( х 7 + х 6 + х 3 + х )
=	х 13 + х 12 + х 9 + х 11 + х 10 + х 5 + х 8 + х 4 + х 2 + х 6 + х 3 + х
=	х 13 + х 12 + х 11 + х 10 + х 9 + х 8 + х 6 + х 5 + х 4 + х 3 + х 2 + х

и

	х 13 + х 12 + х 11 + х 10 + х 9 + х 8 + х 6 + х 5 + х 4 + х 3 + х 2 + х мод х 8 + х 4 + х 3 + х 1 + 1
=	(11111101111110 против 100011011)
=	{3F7E мод 11B} = {01}
=	1 (десятичный)

Последнее можно продемонстрировать с помощью деления в столбики (показано с использованием двоичной записи, поскольку оно хорошо подходит для этой задачи. Обратите внимание, что исключающее ИЛИ в примере применяется , а не арифметическое вычитание, которое можно использовать при делении в столбик в начальной школе):

                        
          11111101111110 (mod) 100011011
         ^100011011     
          01110000011110
          ^100011011    
           0110110101110
           ^100011011   
            010101110110
            ^100011011  
             00100011010
              ^100011011  
               000000001

(Элементы {53} и {CA} являются мультипликативными инверсиями друг друга, поскольку их произведение равно 1. )

Умножение в этом конкретном конечном поле можно выполнить и с помощью модифицированной версии « крестьянского алгоритма ». Каждый полином представлен в той же двоичной записи, что и выше. Восьми бит достаточно, поскольку в терминах каждого (приведенного) полинома возможны только степени от 0 до 7.

Этот алгоритм использует три переменные (в смысле компьютерного программирования), каждая из которых содержит восьмибитное представление. a и b инициализируются множимыми; p накапливает произведение и должно быть инициализировано значением 0.

В начале и конце алгоритма, а также в начале и конце каждой итерации этот инвариант верен: a b + p — произведение. Это очевидно верно, когда алгоритм запускается. Когда алгоритм завершится, a или b будут равны нулю, поэтому p будет содержать произведение.

• Запустите следующий цикл восемь раз (по одному на бит). Можно остановиться, когда a или b равно нулю перед итерацией:
  1. самый правый бит b Если установлен , выполняется исключающее ИЛИ произведение p на значение a . Это полиномиальное сложение.
  2. Сдвиньте b на один бит вправо, отбросив самый правый бит и сделав самый левый бит равным нулю. Это делит полином на x , отбрасывая x ⁰ срок.
  3. Следите за тем, ли самый левый бит a установлен в единицу, и вызывайте это значение переносом .
  4. Сместите один бит влево, отбросив самый левый бит и сделав новый самый правый бит нулевым. Это умножает полином на x , но нам все равно нужно учитывать перенос , который представляет собой коэффициент при x. ⁷ .
  5. Если переноса значение числу было равно единице, исключающему или шестнадцатеричному 0x1b (00011011 в двоичном формате). 0x1b соответствует неприводимому многочлену с удаленным старшим членом. Концептуально, старший член неприводимого многочлена и перенос добавляются по модулю 2 к 0.
• у p теперь есть продукт

Этот алгоритм легко обобщается на умножение на другие поля характеристики 2, изменяя длины a , b и p и значение 0x1b соответствующим образом.

Мультипликативное обратное

См. Также: Алгоритм инверсии Ито – Цудзи.

Мультипликативное обратное для элемента a конечного поля можно вычислить несколькими различными способами:

• Умножив a на каждое число в поле, пока произведение не станет единицей. Это грубый поиск .
• Поскольку ненулевые элементы GF( p ^н ) образуют конечную группу относительно умножения, a ^{п н −1} = 1 (для a ≠ 0 ), таким образом, обратным a является a ^{п н −2} .
• Используя расширенный алгоритм Евклида .
• Составляя таблицы логарифма и возведения в степень для конечного поля, вычитая логарифм из p ^н − 1 и возведение результата в степень.
• Создав модульную мультипликативную обратную таблицу для конечного поля и выполнив поиск.
• Путем сопоставления с составным полем , где инверсия проще, и обратного сопоставления.
• Построив специальное целое число (в случае конечного поля простого порядка) или специальный многочлен (в случае конечного поля непростого порядка) и разделив его на .

Хитрости реализации

Таблицы на основе генератора

При разработке алгоритмов вычисления поля Галуа на небольших полях Галуа общий подход к оптимизации производительности состоит в том, чтобы найти генератор g и использовать тождество:

$ab=g^{\log _{g}(ab)}=g^{\log _{g}(a)+\log _{g}(b)}$

реализовать умножение как последовательность поиска в таблице для журнала _g ( a ) и g ^и функции и операцию сложения целых чисел. При этом используется то свойство, что каждое конечное поле содержит генераторы. В примере поля Рейндала полином x + 1 (или {03}) является одним из таких генераторов. Необходимым, но не достаточным условием того, чтобы многочлен был генератором, является его неприводимость .

Реализация должна проверять особый случай, когда a или b равны нулю, поскольку произведение также будет равно нулю.

Эту же стратегию можно использовать для определения мультипликативного обратного тождества:

$a^{-1}=g^{\log _{g}\left(a^{-1}\right)}=g^{-\log _{g}(a)}=g^{|g|-\log _{g}(a)}$

Здесь порядок генератора | g |, — количество ненулевых элементов поля. В случае GF(2 ⁸ ) это 2 ⁸ − 1 = 255 . То есть для примера Рейндала: ( x + 1) ²⁵⁵ = 1 . Таким образом, это можно выполнить с помощью двух справочных таблиц и целочисленного вычитания. Использование этой идеи для возведения в степень также приносит пользу:

$a^{n}=g^{\log _{g}\left(a^{n}\right)}=g^{n\log _{g}(a)}=g^{n\log _{g}(a){\pmod {|g|}}}$

Для этого требуется два поиска в таблице: целочисленное умножение и операция целого числа по модулю. проверку для особого случая a = 0 Снова необходимо выполнить .

Однако в криптографических реализациях с такими реализациями следует быть осторожными, поскольку архитектура кэша многих микропроцессоров приводит к переменному времени доступа к памяти. Это может привести к реализациям, уязвимым для временной атаки .

Умножение без переноса

Для бинарных полей GF(2 ^н ), умножение полей может быть реализовано с использованием умножения без переноса, такого как набор команд CLMUL , который подходит для n ≤ 64. При умножении используется одно умножение без переноса для получения продукта (до 2 n - 1 бит), другое умножение без переноса предварительно вычисленное обратное значение полинома поля, чтобы получить частное = ⌊продукт / (полиномиал поля)⌋, умножение частного на полином поля, а затем xor: результат = продукт ⊕ ((полиномиал поля) ⌊продукт / (поле полином)⌋). Последние 3 шага (pclmulqdq, pclmulqdq, xor) используются на этапе сокращения Барретта для быстрого вычисления CRC с использованием инструкции x86 pclmulqdq.

Составное поле

Когда k — составное число , будут существовать изоморфизмы из двоичного поля GF(2 ^к ) в поле расширения одного из его подполей, т.е. GF((2 ^м ) ^н ) где k знак равно м п . Использование одного из этих изоморфизмов может упростить математические соображения, поскольку степень расширения меньше, но при этом элементы теперь представляются в более крупном подполе. Чтобы уменьшить количество вентилей для аппаратных реализаций, процесс может включать множественное вложение, например отображение из GF(2 ⁸ ) до GF(((2 ² ) ² ) ² ). Существует ограничение реализации: операции в двух представлениях должны быть совместимы, поэтому необходимо явное использование изоморфизма. Точнее, изоморфизм будет обозначаться через map(), это биекция , отображающая элемент из GF(2 ^к ) в GF((2 ^м ) ^н ), удовлетворяющее: map( a + b ) = map( a ) + map( b ) и map( a b ) = map( a ) map( b ) , где операции с левой стороны происходят в GF(2 ^к ) до отображения и операции в правой части происходят в GF((2 ^м ) ^н ) после картирования. Изоморфизм обычно реализуется с помощью матрицы k строк на k бит, используемой для выполнения умножения матрицы на GF(2) элемента GF(2). ^к ) рассматривается как k строка 1-битной матрицы. Определим α как примитивный элемент GF(2 ^к ) и β как примитивный элемент GF((2 ^м ) ^н ). Тогда β ^дж = карта( ​​а ^дж ) и ^дж = карта ⁻¹ ( б ^дж ). Значения α и β определяют матрицу отображения и ее обратную. Поскольку фактическая математика выполняется в GF((2 ^м ) ^н ), приводящий полином для GF((2 ^м ) ^н ) обычно примитивен и β = x в GF((2 ^м ) ^н ). Чтобы удовлетворить ограничению совместимости при сложении и умножении, выполняется поиск для выбора любого примитивного элемента α из GF(2 ^к ), который будет соответствовать ограничению. В случае, когда приводящий полином для GF(2 ^к ) примитивен, возможен альтернативный метод отображения: 1-битные коэффициенты уменьшающего полинома для GF(2 ^к ) интерпретируются как m битовых элементов 0 или 1 из GF(2 ^м ), и будет m примитивных множителей степени n , любой из которых можно использовать как приводящий полином для GF((2 ^м ) ^н ). Отображение составного поля можно обобщить для отображения GF( p ^к ) в составное поле, такое как GF(( p ^м ) ^н ), для любого простого числа p .

Примеры программ

Пример программирования на языке C

Вот некоторый код C , который будет складывать и умножать числа в конечном поле характеристики 2 порядка 2. ⁸ , используемый, например, алгоритмом Рейндала или Рида – Соломона с использованием алгоритма умножения русского крестьянина :

/* Add two numbers in the GF(2^8) finite field */
uint8_t gadd(uint8_t a, uint8_t b) {
	return a ^ b;
}

/* Multiply two numbers in the GF(2^8) finite field defined 
 * by the modulo polynomial relation x^8 + x^4 + x^3 + x + 1 = 0
 * (the other way being to do carryless multiplication followed by a modular reduction)
 */
uint8_t gmul(uint8_t a, uint8_t b) {
	uint8_t p = 0; /* accumulator for the product of the multiplication */
	while (a != 0 && b != 0) {
        if (b & 1) /* if the polynomial for b has a constant term, add the corresponding a to p */
            p ^= a; /* addition in GF(2^m) is an XOR of the polynomial coefficients */

        if (a & 0x80) /* GF modulo: if a has a nonzero term x^7, then must be reduced when it becomes x^8 */
            a = (a << 1) ^ 0x11b; /* subtract (XOR) the primitive polynomial x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – you can change it but it must be irreducible */
        else
            a <<= 1; /* equivalent to a*x */
        b >>= 1;
	}
	return p;
}

В этом примере есть утечки побочного канала кэша, синхронизации и прогнозирования ветвей , и он не подходит для использования в криптографии.

Пример программирования D

Эта программа D умножит числа в конечном поле Рейндала и сгенерирует изображение PGM :

/**
Multiply two numbers in the GF(2^8) finite field defined
by the polynomial x^8 + x^4 + x^3 + x + 1.
*/
ubyte gMul(ubyte a, ubyte b) pure nothrow {
    ubyte p = 0;

    foreach (immutable ubyte counter; 0 .. 8) {
        p ^= -(b & 1) & a;
        auto mask = -((a >> 7) & 1);
        // 0b1_0001_1011 is x^8 + x^4 + x^3 + x + 1.
        a = cast(ubyte)((a << 1) ^ (0b1_0001_1011 & mask));
        b >>= 1;
    }

    return p;
}

void main() {
    import std.stdio, std.conv;
    enum width = ubyte.max + 1, height = width;

    auto f = File("rijndael_finite_field_multiplication.pgm", "wb");
    f.writefln("P5\n%d %d\n255", width, height);
    foreach (immutable y; 0 .. height)
        foreach (immutable x; 0 .. width) {
            immutable char c = gMul(x.to!ubyte, y.to!ubyte);
            f.write(c);
        }
}

В этом примере не используются какие-либо ветки или поиск по таблицам, чтобы избежать побочных каналов, и поэтому он подходит для использования в криптографии.

См. также

• логарифм Зеха

Источники

• Лидл, Рудольф; Нидеррайтер, Харальд (1983), Конечные поля , Аддисон-Уэсли, ISBN  0-201-13519-1 (переиздан в 1984 году издательством Cambridge University Press ISBN   0-521-30240-4 ).
• Маллен, Гэри Л.; Панарио, Дэниел (2013), Справочник по конечным полям , CRC Press, ISBN  978-1-4398-7378-6
• Хэнкерсон, Даррел; Ванстон, Скотт; Менезес, Альфред (2004), Руководство по криптографии эллиптических кривых , Springer, ISBN  978-0-387-21846-5

Внешние ссылки

• Гордон, Г. (1976). «Очень простой метод найти минимальный полином произвольного ненулевого элемента конечного поля». Электронные письма . 12 (25): 663–664. дои : 10.1049/эл:19760508 .
• да Роша, ВК; Маркарян, Г. (2006). «Простой метод найти след произвольного элемента конечного поля». Электронные письма . 42 (7): 423–325. дои : 10.1049/эл:20060473 .
• Тренхолм, Сэм. «Поле Галуа А.Э.» .
• Планк, Джеймс С. (2007). «Библиотека быстрой арифметики полей Галуа на C/C++» .
• Викиверситет: Рид – Соломон для программистов – арифметика конечных полей