GF2p8 Аффинные преобразования в Композитные поля GF((2^4)^2)

Расширение и сужение поля

Идея в том, чтобы вместо операции над 8-и битными значениям использовать операции с 4-х битными значениями. Как осуществить переход?

В теории полей Галуа есть понятие расширение поля. Расширением GF(2^4) образованного полиномом q(x) до GF(2^8) c образующим полиномом p(z) является полином второго порядка GF((2^4)^2) s(y), но действующий с 4х битными коэффициентами. Запишем так:
s(y) = y²+t·y+n. – полином расширения поля, второго порядка,
где t – “trap” n – “norm” коэффициенты 4 бит. Коэффициенты хотелось бы выбрать таким образом, чтобы один из них (t) обратился в единицу.

Необходимо описать, как выглядят операции в поле: умножение и инверсия. Все числа в надстройке поля представляются парами: старшая и младшая часть:
a = a₁·y+a₀
y - символизирует сдвиг на 4 разряда.

Умножение в композитном поле выглядит следующим образом:
(a₁·y+a₀)(b₁·y+b₀) = (a₁·b₁)·y² + (a₀·b₁+b₀·a₁)·y + a₀·b₀

Используя редуцирование по полиному y2+t·y+n =0, получаем:
(a₁·y+a₀)(b₁·y+b₀) = (a₀·b₁ + b₀·a₁ + a₁·b₁·t)·y + (a₀·b₀ + a₁·b₁·n) = r₁·y + r₀
Результат представлен в виде пары чисел разрядностью 4 бита.

Таким образом, можно выразить умножение, через умножение нижнем поле GF(2^4):
r₁ = (a₀·b₁ + b₀·a₁ + a₁·b₁·t) mod q(x)
r₀ = (a₀·b₀ + a₁·b₁·n) mod q(x)

Также можем выразить операцию инверсии, через инверсию в нижнем поле:
(a₁·y + a₀)^-1 = (d·a₁)·y + d·(a₁·t + a₀),
где d = (a₁²·n + a₁·a₀·t + a₀²)^-1 –- инверсия в поле GF(2^4).
r₁ = (d·a₁) mod q(x)
r₀ = d·(a₁·t + a₀) mod q(x)

Можно проверить справедливость формулы инверсии с использованием операции умножения.

Надо определить коэффициенты {t, n}, выбрать полином в поле GF(2^4).
Всего существует 4 значения n удовлетворяющих требованию t=1 и три нередуцируемх полинома четвертой степени. Для каждого набора параметров можно составить 8 матриц трансформации.

Нередуцируемые полиномы 4-ого порядка:
13: q(x) =x4+x+1
19: q(x) =x4+x3+1
1F: q(x) =x4+x3+x2+x+1

Вариант расчета: t=1, n=1100 – используется в литературе, применительно к полям GF(2^8)/0x11B (AES) и в сочетании с полиномом GF(2^4)/0x13.

Нас интересует составление матриц изоморфного преобразования между полем GF(2^8) и композитным полем GF((2^4)^2)

Для реализации нам понадобятся следующие алгоритмы:
1. умножение и инверсия в поле расширения;
2. умножение и инверсия в поле основания GF(2^4);
3. выбор генератора поля в композитном поле GF((2^4)^2);
4. составление и проверка матрицы трансформации между полем GF(2^8) и композитным полем GF((2^4)^2).

Операции в поле GF(2^4) можно реализовать методом табличной подстановки. Ниже привожу таблицы инверсии и редуцирования. Кроме того, можно реализовать таблицу квадратов и таблицу умножения на константу. Любую функцию одного переменного мы можем записать LUT таблицей (LookUp Table), четыре входа. При описаний логики для FPGA, четырех-битные LUT – оптимальный случай, поскольку, логика на четыре входа и таблица на четыре входа умещается в один логический элемент. При разработке алгоритмов с использованием векторных инструкций выигрыш в том, что вся таблица помещается в вектор 16 байт и для подстановки можно использовать функцию SHUFFLE.

Таблицы инверсии для полиномов 4-ого порядка:
13: 0,1,9,E,D,B,7,6,F,2,C,5,A,4,3,8
19: 0,1,C,8,6,F,4,E,3,D,B,A,2,9,7,5
1F: 0,1,F,A,8,6,5,9,4,7,3,E,D,C,B,2
Таблицы редуцирования старшей части полиномиального умножения:
13: 0,3,6,5,C,F,A,9,B,8,D,E,7,4,1,2
19: 0,9,B,2,F,6,4,D,7,E,C,5,8,1,3,A
1f: 0,F,1,E,2,D,3,C,4,B,5,A,6,9,7,8

Выбор генератора композитного поля можно совместить с генерацией таблицы инверсии, как было показано ранее. В данном случае нам нужно установить соответствие между (a) примитивным элементом поля GF(2^8) и (b) примитивным элементом поля GF((2^4)^2).

Алгоритм подбора генератора поля GF((2^4)^2):
1. Выбираем следующий примитивный элемент (b) поля GF((2^4)^2).
2. Составляем каким-то чудом матрицу прямого и обратного преобразования.
3. Выполняем проверку: произведение прямой и обратной матрицы дает единичную. 
Проверяем действительно ли полученное преобразование – изоморфизм. 
Если условие не выполняется, выбираем следующий примитивный элемент (b),
возвращаемся к шагу 1.

Свойства изоморфизма
    map(a×b) = map(a)×map(b)
    map(a⊕b) = map(a)⊕map(b)

Проверить можно гомоморфизм групповой по отношению к операциям сложения и умножения, для i,j принадлежащих множеству [0..2^k-1] должно выполняться:
a^t = aⁱ+a^j => b^t = bⁱ+b^j
a^i+j = aⁱ·a^j => b^i+j = bⁱ·b^j

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

Multiplicative Inverse GF((2^4)^2) 0x13, N=1100
 00 01 09 0E 0D 0B 07 06 0F 02 0C 05 0A 04 03 08
 AA A0 C7 CB 52 57 4F 4B FE F1 3E 3D 82 8A 2D 2F
 55 E9 50 E7 6A 8F 6C 87 B1 45 BA 41 2E 1E 2C 1F
 66 FA F5 60 96 48 4C 9F 5E D8 D5 5B 3F 1B 1A 3C
 BB 2B 7D C9 B0 29 7A C5 35 97 4E 17 36 9E 4A 16
 22 E6 14 56 E8 20 53 15 A9 75 D4 3B 72 A3 38 D9
 33 F4 E5 B7 EB BC 30 FB D3 9C 24 8E 26 86 DE 95
 99 B4 5C A2 A8 59 BF 90 D1 EF 46 C4 C8 42 E1 DC
 CC DA 1C 8B AF 9A 6D 27 C0 D7 1D 83 A5 93 6B 25
 77 BE A4 8D DF 6F 34 49 B5 70 85 AE 69 D2 4D 37
 11 AB 73 5D 92 8C B3 F2 74 58 10 A1 B8 FD 9B 84
 44 28 F3 A6 71 98 E4 63 AC FC 2A 40 65 EA 91 76
 88 D6 E2 F8 7B 47 CA 12 7C 43 C6 13 80 DB EC F7
 EE 78 9D 68 5A 3A C1 89 39 5F 81 CD 7F E0 6E 94
 DD 7E C2 F9 B6 62 51 23 54 21 BD 64 CE F6 D0 79
 FF 19 A7 B2 61 32 ED CF C3 E3 31 67 B9 AD 18 F0

Алгоритм (2) поиска матрицы прямого и обратного преобразования привожу ниже. Идея сводится к тому, чтобы из степеней генератора поля (a) составить диагональную матрицу и применив те же степени к генератору поля (b) сформировать по столбцам матрицу изоморфного преобразования. Для составления обратной матрицы поля меняются местами.

/* Алгоритм составления матрицы изоморфного преобразования
    a - примитивный элемент поля А
    P1 - образующий полином поля A
    b - примитивный элемент поля B 
    P2 - образующий полином поля B
 */
uint64_t map_ab(uint8_t a, uint32_t P1, uint8_t b, uint32_t P2)
{
	uint64_t m=0;
	int i;
	for(i=0;i<8;i++){
		int k=1;
		uint8_t v=1, r=1;
		while (v != (1<<(i))) {
			v = gf2p8_mul(v, a, P1);
			r = gf2p8_mul(r, b, P2);
		}
		m |= (uint64_t)r<<(8*(7-i));
	}
	return m_transpose(m);
}

В представленном алгоритме при выполнении операции умножения для композитного поля применяется арифметика композитного поля GF((2^4)^2), для поля AES арифметика поля GF(2^8), функции gf2p8_mul для композитного поля и для GF(2^8) по сути будут разные.

Матрицы изоморфного преобразования 11B => 13, N=1100
11B=>13 03 20 M =03A85C6870D2ACA0 M-1 =B1B042829AD45E54
11B=>13 03 22 M =737AF0C870D2ACA0 M-1 =A1B062A23A94BE14
11B=>13 03 35 M =91BC4AC4AE720CA0 M-1 =5FD0BAFAC21C2E9C
11B=>13 03 36 M =3FCE4664AE720CA0 M-1 =AFD01A5AE2DCCE5C
11B=>13 03 41 M =5DFC1C18DCAC72A0 M-1 =83700CACA4128692
11B=>13 03 45 M =81506EB8DCAC72A0 M-1 =B370CC6CE432E6B2
11B=>13 03 5B M =05E608CAA20CD2A0 M-1 =259024044C2A36AA
11B=>13 03 5E M =A7EADA6AA20CD2A0 M-1 =759064448C8A560A

Полученный результат позволяет выполнять операции композитного поля на инструкциях GFNI при изоморфном преобразовании из композитного поля в поле AES. И наоборот, позволяет перейти от операций в поле GF(2^8) к операциям меньшей разрядности GF(2^4). Такая техника может давать прирост производительности при реализации алгоритмов шифрования аппаратно и в микроконтроллерах.

В качестве тестового примера для проверки работоспособности методики выполняем генерацию S-Box AES в композитном поле с использованием изоморфного преобразования. При этом операция инверсии выполняется в арфиметике композитного поля.

S(x) = (A·M-1)·(M·x)-1 ⊕ C
A =F1E3C78F1F3E7CF816 - матрица аффинных преобразовний AES. 
C =6316
M =A7EADA6AA20CD2A016, -- матрица изоморфного преобразования
M-1 =759064448C8A560A16, -- обратное изоморфное преобразование
(A·M-1) =2F33DDCF49B6701E16

sbox[x] = affine(m_mul(A, M_), composite_inverse(affine(M, x)))^0x63;

Результат совпадает!

Расчет S-Box CLEFIA в композитных полях

Ранее мы рассматривали пример расчета нелинейного преобразования блочного шифра CLEFIA в изоморфных полях GF(2^8). Хотим закрепить навык выполнения расчетов в композитных полях и использовать технику преобразования в композитное поле, с расчетом инверсии на полиноме GF(2^4)/0x13.

Расчет нелинейного преобразования (биекции) дается следующим выражением:

S(x) = A2·(A1·x ⊕ C1)-1 ⊕ C2
A2,A1 - матрицы аффинных преобразовний.
инверсия считается в поле GF(2^8)/0x11D.
A1 =0x81605C6503015118 C1=0x1E
A2 =0x449002302058410A C2=0x69

Перейдем к расчетам в композитном поле:

S(x) = (A2·M-1)·((M·A1)·x ⊕ (M·C1))-1 ⊕ C2
инверсия считается в композитном поле GF((2^4)^2)/0x13.
M =B9C292428A441A2016
M-1 =9F547C4E5A805C0A16
(M·A1)  =FE297B311D0D060116,  (M·C1) =0x6A
(A2·M-1) =205054DA8048C31A16

// Расчет SBox - фрагмент кода
sbox[x] = affine(m_mul(A2,M_), composite_inverse(affine(m_mul(M,A1), x) 
                                               ^ affine(M,C1))) ^ C2;

Результат совпадает!

[1] D. Canright. A Very Compact S-box for AES
[2] A. Rudra et al. Efficient Rijndael Encryption Implementation with Composite Field Arithmetic