Во-первых, никто не понимает, как пользоваться инструкциями GF-NI - нечеловеческая математика. Расширение состоит из трех инструкций, которые расчитывают матричные операции над полиномами: M*x+C, M*x-1+C и полиномиальное умножение с редуцированием A⊙B mod 0x11B. В систему команд введены инструкции для работы всего с одним полиномом (0x11B), в то время как этот полином используется мало в каких алгоритмах.
Первая операция M*x+C (аффинные преобразования gf2p8affine) не привязана никак к полиному(0x11B), можно сказать про полином вида x8+1, по которому выполняется редуцирование.
Операцию циклического сдвига A<<<n можно представить, как умножение и редуцирование по полиному x8+1. Запишется так: A×2n mod 0x101. Боже, откуда такое чувство, что меня никто не понимает?! Полиномиальное представление двоичных чисел - это просто термин такой, буквой x обозначается сдвиг на разряд. Вот что, например, написано про полиномиальное умножение в стандарте AES.. Rijndael S-box можно представить, как аффинное преобразование от обратного числа и записать в виде набора цикличекских сдвигов.s = b ⊕ (b<<<1) ⊕ (b<<<2) ⊕ (b<<<3) ⊕ (b<<<4) ⊕ 6316Это же утверждение записать через операцию полиномиального умножения (умнжения без переносов) и операцию редуцирования по полиному.
S = A×3110 mod 24710.Это чтобы всех запутать сделано: числа даны в десятичном виде, операции в поле - умножение полиномиальное и редцирование по полиному x8+1.
Первое, что нашлось по теме использования инструкции - много циклических сдвигов можно представить, как аффинное преобразование [0x80.pl].
Из всего это следует, что подстановку AES S-box можно выполнить единственной инструкией gf2p8affineinv: S = A*inv(x)+C. Надо понять, как записать и протестировать эту возможность. Матрица преобразования записана в стандарте AES.
// Матрица аффинного преобразования, сдвиги: 0,1,2,3,4
|11111000|
|01111100|
|00111110|
|00011111|
|10001111|
|11000111|
|11100011|
|11110001|
// Матрица Обратного аффинного преобразования, сдвиги: 1,3,6
|01010010|
|00101001|
|10010100|
|01001010|
|00100101|
|10010010|
|01001001|
|10100100|
Сдвиги в прямой матрице можно представить полиномом 7й степени (x7+x3+x2+x+1)=0xF1 сдвиги в обратной (x7+x5+x2)=0xA4. Для расчета обратного преобразования предлагается использовать утверждение (x7+x3+x2+x+1)^3 mod (x8+1)==(x7+x5+x2). Методом уножения на себя два раза из полинома 7й степени можно получить обратный ему полином.
Таким образом, утверждается, что имея полином A 7й степени, можно получить обратный ему полином B 7й степени, для которых выполняется условие A×B mod (x8+1) = 1. Не уверен, что это правило работает, но оставил.
// Нахождение обратного полинома 7й степени.
void inverse_af2(uint32_t poly)
{
uint32_t mask = 0xFF;
uint32_t p = poly & mask;
uint32_t r;
r = pmul(p, p);// умножение полиномиальное
r = (r ^ (r>>8))& mask;// редуцирование
r = pmul(r, p);// умножение полиномиальное
r = (r ^ (r>>8))& mask;// редуцирование
return r;
}
Навык поиска обратного значения нам понадобился, чтобы составлять прямые и обратные матрицы аффинных преобразований.
Обратный полином можно найти и методом подбора, перебрать все элементы поля, пока не найдется удовлетворяющий условию -- произведение на обратный элемент дает единицу.
// Операция умножения в поле GF(2^8) с полиномом Poly
uint32_t gf2p8_mul(uint32_t p, uint32_t i, uint32_t Poly){
uint32_t r=0;
while (i) {
if (i&1)r^=p;
if (p&0x80){
p=(p<<1) ^ Poly;
} else
p=(p<<1);
i>>=1;
}
return r;
}
Следующий инструмент разработки - составление таблиц преобразования, прямых и обратных. Тут надо вспомнить некоторое свойство. После g^(p-1) = g. Число g - генератор поля выбирается таким образом чтобы его степени проходили по всем элеементам - это, например, число 3. Методом уножения числа на 3 можно перебрать все элементы поля.
// Инициализация таблицы инверсии inv(x) == x-1
static void initialize_inv(uint8_t inv[256])
{
uint8_t p = 1, q = 1;
do {
p = gf2p8_mul(p, 0x03, Poly);// умножить p на 3
q = gf2p8_mul(q, 0xF6, Poly);// делить q на 3
inv[p] = q;
} while p != 1);
inv[0] = 0;
}
В цикле используется умножение на обратное число (0xF6), вместо деления на 3. Произведение чисел p и q единица, одно для другого на каждом цикле остается обратным числом. За счет выбора генератора, перебираются все числа, кроме нуля. В результате получаем таблицу обратных чисел.
Таблица обратных чисел для Poly=11B
00 01 8D F6 CB 52 7B D1 E8 4F 29 C0 B0 E1 E5 C7
74 B4 AA 4B 99 2B 60 5F 58 3F FD CC FF 40 EE B2
3A 6E 5A F1 55 4D A8 C9 C1 0A 98 15 30 44 A2 C2
2C 45 92 6C F3 39 66 42 F2 35 20 6F 77 BB 59 19
1D FE 37 67 2D 31 F5 69 A7 64 AB 13 54 25 E9 09
ED 5C 05 CA 4C 24 87 BF 18 3E 22 F0 51 EC 61 17
16 5E AF D3 49 A6 36 43 F4 47 91 DF 33 93 21 3B
79 B7 97 85 10 B5 BA 3C B6 70 D0 06 A1 FA 81 82
83 7E 7F 80 96 73 BE 56 9B 9E 95 D9 F7 02 B9 A4
DE 6A 32 6D D8 8A 84 72 2A 14 9F 88 F9 DC 89 9A
FB 7C 2E C3 8F B8 65 48 26 C8 12 4A CE E7 D2 62
0C E0 1F EF 11 75 78 71 A5 8E 76 3D BD BC 86 57
0B 28 2F A3 DA D4 E4 0F A9 27 53 04 1B FC AC E6
7A 07 AE 63 C5 DB E2 EA 94 8B C4 D5 9D F8 90 6B
B1 0D D6 EB C6 0E CF AD 08 4E D7 E3 5D 50 1E B3
5B 23 38 34 68 46 03 8C DD 9C 7D A0 CD 1A 41 1C
Заметим, что аналогичным образом можно составить таблицу экспоненты и логарифма числа, в качестве генератора используется число 2. Т.е. табличное представление умножения и инверсии через экспонирование и логарифирование чисел, с отображением на конечное поле 255 с обычной модульной арифметикой -- это нас не пугает, потому что традиционно используется в расчетах кодов Рида-Соломона. Интересно, можно ли аффинными преобразованиями получить экспоненту или логарифм числа, чтобы заменить таблицы на аффинные преобразования?
Вернемся к генерации таблиц.
S = A×inv(x)⊕C = AF(inv[x])⊕ 6316Всего существует 30шт нередуцируемых полиномов восьмого порядка, которые можно использовать для построения полей GF(2^8). Утверждается, что все поля образованные нередуцируемыми полиномами 8-ого порядка изоморфны, т.е. имеют однозначное отображение одного множества чисел на другое множество. Это можно не доказывать, и так очевидное утверждение.
Другое утверждение -- представления полей GF(2^8) с разными полиномами можно отображать используя аффинные преобразования с матрицей 8x8 бит. Вот только как эти матрицы получать? Погуглить в интернете?! Нашел работы 2019-2021 года по разработке новых алгоритмов для пост-квантовой криптографии, нашел оптимизации таблиц подстановок типа S-box на основе таких преобразований. От Intel традиционно, внедрение новых инструкций Intel для криптографии продвигает Shay Gueron и группа товарищей, по его работам, патентам с его участием и статьям можно проследить развитие направления.
[US9800406] US Патент описывет преобразование представления GF(2^8) для вычисления S-Box китайского национального алгоритма блочного шифра SM4. Образующий поле AES полином x8 + x4 + x3 + x + 1=0x11B, в SM4 используется образующий полином x8 + x7 + x6 + x5 + x4 + x2 + 1=0x1F5. Преобразования Sbox записывается следующим образом.
SBoxSM4(x) = A2*inv(A1*x⊕C1)⊕C2
SBoxAES(x) = A*inv(x) + 6316
Матрицы SM4
|1 0 1 0 0 1 1 1| |1 1 0 0 1 0 1 1|
|0 1 0 0 1 1 1 1| |1 0 0 1 0 1 1 1|
A1=|1 0 0 1 1 1 1 0| A2=|0 0 1 0 1 1 1 1|
|0 0 1 1 1 1 0 1| |0 1 0 1 1 1 1 0|
|0 1 1 1 1 0 1 0| |1 0 1 1 1 1 0 0|
|1 1 1 1 0 1 0 0| |0 1 1 1 1 0 0 1|
|1 1 1 0 1 0 0 1| |1 1 1 1 0 0 1 0|
|1 1 0 1 0 0 1 1| |1 1 1 0 0 1 0 1|
C1=(1 1 0 0 1 0 1 1)TC2=(1 1 0 1 0 0 1 1)T
Матрица AES [NIST FIPS 197]
|1 0 0 0 1 1 1 1|
|1 1 0 0 0 1 1 1|
|1 1 1 0 0 0 1 1|
A =|1 1 1 1 0 0 0 1|
|1 1 1 1 1 0 0 0|
|0 1 1 1 1 1 0 0|
|0 0 1 1 1 1 1 0|
|0 0 0 1 1 1 1 1|
C =(1 1 0 0 0 1 1 0)T
Патент представил матрицу преобразования элементов из поля SM4(0x1F5) в поле AES(0x11B)
Матрица отображения
|0 1 1 0 0 0 1 0|
|1 1 1 0 1 0 1 0|
|0 0 1 1 1 1 0 0|
M=|1 0 0 0 0 1 1 0|
|0 0 0 0 0 1 0 0|
|0 0 1 0 0 1 1 0|
|1 1 0 1 1 1 1 0|
|0 1 0 1 0 0 0 1|
Отображение из SM4 в AES можно описать выражением
y = M*(A1*x⊕C1)Обратное отображение из AES в SM4
s = A2*(M-1*A-1*u)⊕C2
Матрицы 8x8 можно перемножать между собой и сокращать выражения.
Матрицы отображения
|01010010| |11001011|
|10111100| |10011010|
|00101101| |00001010|
M*A1=|00000010|, A2*M-1*A-1=|10110100|
|10011110| |11000111|
|00100101| |10101100|
|10101100| |10000111|
|00110100| |01001110|
M*C1=0x65 C2 =0xD3
Такие же преобразования можно совершать в любом поле. Всего насчитывается 30 нередуцируемых полиномов пригодных для подобных преобразований.
Для разработки необходимы методы: 1) Поиск матриц M для перехода между представлениями, 2) Декомпозиция S-Box 3) перемножение матриц, поиск обратных матриц, произведение матрицы на вектор - линейная алгебра. Из своего образования вспоминаю LU-разложение матриц, и свойства линейности матриц, которое позволяет представлять аффинные преобразования в виде перестановок, т.е снизить разрядность операции. Надо вспоминать линейную алгебру! Довольно много разных алгоритмов используют различные полиномы. Эти инструкции позволяют существенно ускуорить их работу, но пока нет опыта использования и надо затратить усилия на освоение математики и разработку алгоритмов синтеза таблиц.
Ниже привожу таблицу нередуцируемых полиномов..
Таблица нередуцируемых полиномов (30 шт):
x^8 + x^7 + x^5 + x^4 + 1
x^8 + x^6 + x^5 + x^4 + 1
x^8 + x^7 + x^5 + x^3 + 1
x^8 + x^6 + x^5 + x^3 + 1
x^8 + x^5 + x^4 + x^3 + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1
x^8 + x^6 + x^5 + x^2 + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x^2 + 1
x^8 + x^7 + x^3 + x^2 + 1
x^8 + x^6 + x^3 + x^2 + 1
x^8 + x^5 + x^3 + x^2 + 1
x^8 + x^4 + x^3 + x^2 + 1
x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + 1
x^8 + x^7 + x^5 + x^4 + x^3 + x^2 + 1
x^8 + x^7 + x^6 + x + 1
x^8 + x^7 + x^5 + x + 1
x^8 + x^6 + x^5 + x + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x + 1
x^8 + x^7 + x^3 + x + 1
x^8 + x^5 + x^3 + x + 1
x^8 + x^4 + x^3 + x + 1 - AES
x^8 + x^6 + x^5 + x^4 + x^3 + x + 1
x^8 + x^7 + x^2 + x + 1
x^8 + x^7 + x^6 + x^5 + x^2 + x + 1
x^8 + x^7 + x^6 + x^4 + x^2 + x + 1
x^8 + x^6 + x^5 + x^4 + x^2 + x + 1
x^8 + x^7 + x^6 + x^3 + x^2 + x + 1
x^8 + x^7 + x^4 + x^3 + x^2 + x + 1
x^8 + x^6 + x^4 + x^3 + x^2 + x + 1
x^8 + x^5 + x^4 + x^3 + x^2 + x + 1
Следующая статья по теме - закрепление. Материала много для одного сообщения, но надо дополнить.
[S.Gueron et al. Speed up over the Rainbow] "All the representations of GF(2^8) are isomorphic. Therefore, it is possible to pass from one representation to another by means of multiplying by an 8 ×8-bit matrix"
