Эмуляция аффиных преобразований
Нужна эффективная замена для операций gf2p8affine. Каждый алгоpитм, который мы разрабатываем с использованием инструкций Intel GFNI должен исполняться и на платформе, где эти инструкции не представлены.
По определению любое аффинное преобразование обладает возможносью разлжения на табличные подстановки. Мы планируем эмулировать работу инструкции на платформе с поддержкой векторизации. Для работы с векторами мы можем использовать встроенную псевдо-функцию __builtin_shuffle(). Ранее мы использовали фунуцию affine_byte для расчета результата и подстановки аффинных преобразований от константы. Для данного преобразования необходимо составить две таблицы подстановок: для старших и младших разрядов.
// Аффинные преобразования с использованием таблиц
uint8x16_t gf2p8_affine(uint8x16_t x, const uint64_t M)
{
static const uint8x16_t lut_hi = {
affine(M, 0x00),affine(M, 0x10), ...,affine(M, 0xF0)};
static const uint8x16_t lut_lo = {
affine(M, 0x00),affine(M, 0x01), ...,affine(M, 0x0F)};
return shuffle(lut_hi, x>>4) ^ shuffle(lut_lo, x&0x0F)
}
Циркулянт и Анти-циркулянт
Циркулярная матрица - это матрица, полученная циклическим сдвигом некоторого ассоциированного полинома. Такие матрицы используются при составлении S-Box в качестве обратимого линейного преобразования. Мы говорим про матрицу специальной конструкции, которую можно описать, как произведение в поле GF(2^8) с редуцированием по полиному x8+1. Матрицу преобразования (A) можно определить двумя числами (полиномами), C(x) и D(х):
b(x)= C×a(x) ⊕ D mod (x8+1)
Пока что нам попались две такие циркуляторные (мне не нравится слово "циркулянт") матрицы: от AES S-Box и от SM4 S-Box. Мы можем составить все возможные циркуляторные матрицы и найти обратные к ним.
Матрицу можно составить по сответствующему полиному степени n-1:
С(x)=с0 + с1·x + с2·x2+...+сn-1·xn-1 и константе D(x).
#define m_rotate(M, n) ((M)<<(8*(8-n)) ^ (M)>>(8*(n)))
uint64_t m_circulant(uint8_t C){
return
(C & 0x01 ? E: 0)
^ (C & 0x02 ? m_rotate(E,1): 0)
^ (C & 0x04 ? m_rotate(E,2): 0)
^ (C & 0x08 ? m_rotate(E,3): 0)
^ (C & 0x10 ? m_rotate(E,4): 0)
^ (C & 0x20 ? m_rotate(E,5): 0)
^ (C & 0x40 ? m_rotate(E,6): 0)
^ (C & 0x80 ? m_rotate(E,7): 0);
}
Операцию m_rotate можно выразить через циклические сдвиги единичной матрицы (E).
Сколько всего циркулянтов? как находить анти-циркулянты? Какой период циркуляции? Зачем нужны циркулянты?
-- Всего 128 циркулянтов, включая единичную матрицу E. Все циркулянты имеют порядок вращения Mn=M, как и сам полином Cn mod 0x101 = C, период вращения равнен n=2, 4 или 8. Cn-1=1 -- есть такой признак. Обратной матрицей является полином полученный методом Cr = Cn-2 mod 0x101. Алгоритм нахождения обратного полинома: ищем порядок, находим полином на предыдущем шаге. Из этого описания получаем алгоритм поиска обратного циркулярного преобразования. Вернее, мы находим обратный полином (Cr), такой что
// Алгоритм нахождения обратного циркулянта и порядка повтора
int m_circulant_order(uint8_t C, uint8_t* Cr) {
uint8_t r= C, r_;
int i;
for (i=1; i<8; i++){
r_= r;
r = gf2p8_mul(r,C, 0x101);
if (r==1) {
if(Cr) *Cr = r_;
break;
}
}
return i;
}
// Вывод агоритма подбора циркулянтов (фрагмент) С M Cr M-1 . . . EA=> AE5DBA75EAD5AB57, AE=> EAD5AB57AE5DBA75, order=3 EC=> 6EDCB973E6CD9B37, 3B=> B973E6CD9B376EDC, order=7 EF=> EFDFBF7FFEFDFBF7, EF=> EFDFBF7FFEFDFBF7, order=1 F1=> 1F3E7CF8F1E3C78F, A4=> 4A942952A4499225, order=3 F2=> 9E3D7AF4E9D3A74F, 16=> D0A143860D1A3468, order=7 AES: 1F=> F1E3C78F1F3E7CF8, 4A=> A44992254A942952, order=3 SM4: CB=> A74F9E3D7AF4E9D3, 85=> 43860D1A3468D0A1, order=7