Преобразования в композитных полях
Базовая идея состоит в том, чтобы выполнять вычисления в простых, самых простых полях GF(2^2), а для перехода к большей разрядности использовать расширение поля.
Аффинные преобразования позволяют параллельно расчитывать множество матриц меньшей размерности, матрицы можно масштабировать 8x8 => 4x4 => 2x2, если научиться раскладывать операции в поле GF(2^8) на две операции в поле GF(2^4) и дальше на четыре операции GF(2^2).
Существует всего один нередуцируемый полином поля GF(2^2) 2 степени .
0x07 p(x) =x2+x+1
И три нередуцируемых полинома 4 степени.
0x13 p(x) = x4+x+1 0x19 p(x) = x4+x3+1 0x1F p(x) = x4+x3+x2+x+1
Почему так хочется снизить степень полинома. Поля GF(2^4) привлекательны тем, что любая унарная операция может быть представлена таблично и подставляться с использованием векторных иструкций Intel PSHUFB, или аналогичных. Размер таблиц 16 байт. Вся таблица помещается в векторный регистр. Использование векторных инструкций для табличной подстановки создает возможность выполнять алгоритм с фиксированными задержками.
Для реализации в аппаратуре представляет интерес дальнейшее снижение размерности, потому что операции в поле GF(2^2) выглядят очень просто.
Инверсия в поле GF(2^2) представлена матрицей 2x2, эта же матрица отвечает за возведение в квадрат, поскольку x-1 = xp-2=x2.
1 0 =2 1 1 =3
умножение на 1:
1 0 =2 0 1 =1
умножение на 2, сдвиг-редуцирование по полиному 0x7, XTime(a):
1 1 =3 1 0 =2
умножение на 3:
0 1 =1 1 1 =3
Утверждаем, что инверсию (gf2p2_inv) можно выполнить в одну инструкцию с использованием аффинных преобразований, а умножение (gf2p2_mul) в поле GF(2^2) можно выполнить в две-три инструкции gf2p8affine.
Для иллюстрации аппаратной реализации функций инверсии и умножения в поле GF(2^2) привожу логические функции соответствующие операциям. Функция довольно простая, выражена в базисе логических функций: Исключающее ИЛИ, И, 1. Любую логику можно выразить в этом базисе. Этот базис соответствует операции gf2p8affine. Таким образом, функцию аффинного преобразования можно использовать и для параллельного вычисления каскада подобных операций. Преобразование произвольных логических фукнций из базиса {И,ИЛИ,НЕ} к базису: {Исключающее ИЛИ, И, 1} -- достойно отдельной статьи. В литературе показано, что применение композитного поля для расчетов позволяет существенно снизить число логических элементов для реализации операций в поле и S-Box, в частности. Надо научиться представлять логическую функцию заданную таблично в виде разложения в каскад операций аффинного преобразования.
Операция инверсии в нижнем поле GF(2^2)/q(x)=x2+x+1 запишется следующим образом.
r0 = x0 ⊕ x1 r1 = x1
Можем выразить операцию инверсии в композитном поле через инверсию в нижнем поле:
d = (a12·n + a1·a0·t + a02)-1 -- инверсия в поле GF(2^2). r1 = d·a1 mod q(x) r0 = d·(a1·t + a0) mod q(x) Результат операции: r = r1·y + r0
При этом разложении все операции (умножение, сложение и инверсия) выполняются в поле GF(2^2)
Можно выразить умножение в композитном поле GF((2^2)^2)/s(y)=y2+y+10 через умножение в нижнем поле GF(2^2):
a = a1·y + a0, b = b1·y + b0 r1 = (a0·b1 + a1·(b0 + b1·t)) mod q(x) r0 = (a0·b0 + a1·b1·n) mod q(x) Результат операции: r = r1·y + r0
Значения параметров поля: t=1, n=2.
Ниже привожу реализацию функций умножени и инверсии в композитном поле GF((2^2)^2).
/*! Инверсия в композитном поле GF((2^2)^2) */
uint8_t gf2p4_composite_inverse(uint8_t x, uint32_t Poly) {
const uint8_t N = 0x2, P2 = 0x7;
uint8_t a1 = x>>2 & 0x3;
uint8_t a0 = x&0x3;
uint8_t D = gf2p2_mul(a0,a0^a1, P2)
^ gf2p2_mul(gf2p2_mul(a1, a1, P2), N, P2);
uint8_t d = gf2p2_inv(D, P2);
uint8_t b0 = gf2p2_mul(a0^a1, d, P2);
uint8_t b1 = gf2p2_mul(a1, d, P2);
return b1<<2 | b0;
}
/*! Умножение в композитном поле GF((2^2)^2) */
uint8_t gf2p4_composite_mul(uint8_t a, uint8_t b, uint32_t Poly) {
const uint8_t N=0x2, P2 = 0x7;
uint8_t a1 = (a>>2) & 0x3, a0 = a & 0x3;
uint8_t b1 = (b>>2) & 0x3, b0 = b & 0x3;
uint8_t d = gf2p2_mul( b0,a0, P2);
uint8_t r1 = gf2p2_mul((a0^a1), (b0^b1), P2) ^ d;
uint8_t r0 = gf2p2_mul(gf2p2_mul(b1,a1, P2),N,P2) ^ d;
return (r1<<2) | r0;
}
Таблица инверсии в поле GF(2^4)/p(x)=x4+x+1 0 1 9 E D B 7 6 F 2 C 5 A 4 3 8 Таблица инверсии в композитном поле GF((2^2)^2) 0 1 3 2 F C 9 B A 6 8 7 5 E D 4
Таблицы инверсии нужны для проверки реализации и поиска генератора поля (почему то генератор поля мы проверяем по таблице инверсии). Для перехода от вычислений в поле GF(2^4) в композитное поле и обратно GF((2^2)^2) используем матрицы изоморфного преобразования. Алгоритм расчета матриц изоморфного преобразования 4x4 такой же как и для расчета в композитных полях GF(2^8)=>GF((2^4)^2), был представлен в предыдущей части. Матрицы 4x4 мы упаковываем в формат 8x8, это позволяет использовать те же функции работы с матрицами аффинных преобразований, тот же инструментарий. Замечу, что два независимых преобразования 4x4 можно выполнить на одной операции аффинного преобразования 8x8.
изоморфное преобразование GF(2^4)/0x13 => GF((2^2)^2) 13=>07 02 04 M =010C0E0800000000 M-1 =01060A0800000000 13=>07 02 05 M =0F040E0800000000 M-1 =050E020800000000 13=>07 02 06 M =0502060800000000 M-1 =0702060800000000 13=>07 02 07 M =030A060800000000 M-1 =0B0A0E0800000000
Матрицы изоморфного преобразования M =01060A080000000016 1000 =0x8 1110 =0xE 1100 =0xC 0001 =0x1 M-1 =01060A080000000016 1000 =0x8 1010 =0xA 0110 =0x6 0001 =0x1
Для отладки функций использовал данные и результаты расчета матриц преобразования из статьи[1]. Следующий шаг -- научиться считать еще более сложные композитные поля, в частности GF(((2^2)^2)^2) -- поле "Тауэр"/"Матрешка", используется в криптографии Rainbow. Причем есть две цели: преобразовать поле Тауэр к полю GF((2^4)^2) для использования 4-х битных таблиц и инструкций PSHUFB; или преобразовать Тауэр к полю GF(2^8)/0x11B для использования инструкций GFNI.
