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

Арифметика в поле с конечным числом элементов

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

Существует бесконечно много различных конечных полей. Их число элементов обязательно имеет вид 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), а умножение — И. Поскольку единственный обратимый элемент — 1, деление — это функция тождества .

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

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

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

Примитивные многочлены

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

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

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

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

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

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

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

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

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

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

Умножение

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

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

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

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

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

и

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

   11111101111110 (мод) 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 на каждое число в поле, пока произведение не станет равным 1. Это поиск методом перебора .
• Поскольку ненулевые элементы GF( p ⁿ ) образуют конечную группу относительно умножения, a ^{p n −1} = 1 (при a ≠ 0 ), то обратным элементом для a является a ^{p n −2} .
• Используя расширенный алгоритм Евклида .
• Составим таблицы логарифмирования и возведения в степень для конечного поля, вычтем логарифм из p ⁿ  − 1 и возведем результат в степень.
• Создав модульную мультипликативную обратную таблицу для конечного поля и выполнив поиск.
• Путем сопоставления с составным полем, где инверсия проще, и обратного сопоставления.
• Построив специальное целое число (в случае конечного поля простого порядка) или специальный многочлен (в случае конечного поля не простого порядка) и разделив его на a . ^[6]

Приемы реализации

Генератор таблиц

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

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

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

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

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

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

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

${\displaystyle 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 бит), другое умножение без переноса предварительно вычисленного обратного полинома поля для получения частного = ⌊product / (полином поля)⌋, умножение частного на полином поля, затем xor: результат = product ⊕ ((полином поля) ⌊product / (полином поля)⌋). Последние 3 шага (pclmulqdq, pclmulqdq, xor) используются на этапе сокращения Барретта для быстрого вычисления CRC с использованием инструкции x86 pclmulqdq. ^[7]

Составной показатель степени

Когда k является составным числом , будут существовать изоморфизмы из двоичного поля GF(2 ^k ) в поле расширения одного из его подполей, то есть GF((2 ^m ) ⁿ ), где k = m n . Использование одного из этих изоморфизмов может упростить математические соображения, поскольку степень расширения меньше с компромиссом, что элементы теперь представлены в большем подполе. ^[8] Чтобы уменьшить количество вентилей для аппаратных реализаций, процесс может включать множественное вложение, такое как отображение из GF(2 ⁸ ) в GF(((2 ² ) ² ) ² ). ^[9]

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

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

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

/* Складываем два числа в конечном поле GF(2^8) */ uint8_t gadd ( uint8_t a , uint8_t b ) { return a ^ b ; }        /* Умножить два числа в конечном поле GF(2^8), определенном * модульным полиномиальным отношением x^8 + x^4 + x^3 + x + 1 = 0 * (другой способ — выполнить умножение без переноса с последующим модульным сокращением) */ uint8_t gmul ( uint8_t a , uint8_t b ) { uint8_t p = 0 ; /* аккумулятор для результата умножения */ while ( a != 0 && b != 0 ) { if ( b & 1 ) /* если полином для b имеет постоянный член, добавить соответствующий a к p */ p ^= a ; /* сложение в GF(2^m) является XOR полиномиальных коэффициентов */                           if ( a & 0x80 ) /* GF по модулю: если a имеет ненулевой член x^7, то его необходимо сократить, когда он станет x^8 */ a = ( a << 1 ) ^ 0x11b ; /* вычесть (XOR) примитивный многочлен x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – вы можете изменить его, но он должен быть неприводимым */ else a <<= 1 ; /* эквивалентно a*x */ b >>= 1 ; } return p ; }                     

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

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

Эта программа на языке D умножает числа в конечном поле Rijndael и генерирует изображение PGM :

/** Умножить два числа в конечном поле GF(2^8), определенном полиномом x^8 + x^4 + x^3 + x + 1. */ ubyte gMul ( ubyte a , ubyte b ) pure nothrow { ubyte p = 0 ;            foreach ( неизменяемый счетчик ubyte ; 0 .. 8 ) { p ^= -( b & 1 ) &a a ; автомаска = -(( a >> 7 ) & 1 ); // 0b1_0001_1011 это x^8 + x^4 + x^3 + x + 1. a = cast ( ubyte )(( a << 1 ) ^ ( 0b1_0001_1011 & mask )); b >> = 1 ; }                                     вернуть п ; } 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 ) ; } }                            

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

Смотрите также

• Логарифм Цеха

Ссылки

1. Ханкерсон, Ванстоун и Менезес 2004, стр. 28
2. Корни такого многочлена должны лежать в поле расширения GF( q ), поскольку многочлен неприводим и, следовательно, не имеет корней в GF( q ).
3. Маллен и Панарио 2013, стр. 17
4. Планирование и анализ экспериментов . John Wiley & Sons, Ltd. 8 августа 2005 г. С. 716–720. doi :10.1002/0471709948.app1.
5. Лидл и Нидеррайтер 1983, стр. 553
6. Грошек, О.; Фабшич, Т. (2018), «Вычисление мультипликативных обратных величин в конечных полях с помощью деления в столбик» (PDF) , Журнал электротехники , 69 (5): 400–402, doi : 10.2478/jee-2018-0059 , S2CID  115440420
7. "Быстрое вычисление CRC для универсальных полиномов с использованием инструкции PCLMULQDQ" (PDF) . www.intel.com . 2009 . Получено 2020-08-08 .
8. "Эффективные программные реализации больших конечных полей GF(2n) для приложений безопасного хранения" (PDF) . www.ccs.neu.edu . Получено 2020-08-08 .
9. "bpdegnan/aes". GitHub .

Источники

• Лидл, Рудольф; Нидеррайтер, Харальд (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). «Очень простой метод нахождения минимального многочлена произвольного ненулевого элемента конечного поля». Electronics Letters . 12 (25): 663–664. doi :10.1049/el:19760508.
• da Rocha, VC; Markarian, G. (2006). "Простой метод нахождения следа произвольного элемента конечного поля". Electronics Letters . 42 (7): 423–325. doi :10.1049/el:20060473.
• Тренхолм, Сэм. «Поле Галуа АЭ».
• Планк, Джеймс С. (2007). «Библиотека быстрой арифметики поля Галуа в C/C++».
• Викиверситет: Рид–Соломон для кодеров – Арифметика конечных полей