GF2p8 Аффинные преобразования (ч. 3)

Эмуляция аффиных преобразований

Нужна эффективная замена для операций 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·x²+...+с_n-1·x^n-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. Все циркулянты имеют порядок вращения Mⁿ=M, как и сам полином Cⁿ mod 0x101 = C, период вращения равнен n=2, 4 или 8. C^n-1=1 -- есть такой признак. Обратной матрицей является полином полученный методом Cr = C^n-2 mod 0x101. Алгоритм нахождения обратного полинома: ищем порядок, находим полином на предыдущем шаге. Из этого описания получаем алгоритм поиска обратного циркулярного преобразования. Вернее, мы находим обратный полином (Cr), такой что Cr×C mod 0x101 =1, из которого составляется обратная циркуляторная матрица методом m_circulant(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