Продолжаю тему, понял что некоторые разделы не раскрыты..
Умножение на константу в поле GF(2^8)
Нужен шаблон для матрицы умножения на константу в поле. Причем, умножение на константу реализовать надо в виде матрицы аффинного преобразования, чтобы иметь возможность последовательно накладывать и перемножать матрицы.
Матрица умножения состоит из столбцов, в которых располагаются степени числа 2. При умножении констант, должно быть выполнено редуцирование по образующему полиному.M = [δ·27,δ·26,δ·25,δ·24,δ·23,δ·22,δ·21,δ·20]T
Матрицу нужно транспонировать, если заполнение производится по строкам.
// Алгоритм формирования матрицы умножения на константу в поле GF(2^8)
uint64_t m_mulC(uint8_t c, uint32_t Poly){
uint64_t m = c;
int i;
for (i=1;i<8;i++){
uint8_t v = gf2p8_mul(c, (1<<i), Poly);
m = (m<<8) ^ v;
}
return m_transpose(m);
}
Редуцирование в поле GF(2^8)
Надо уметь выполнять редуцирование в форме аффинных преобразований - в одно действие. Дана старшая часть умножения без переноса, требуется выполнить редуцирование, т.е. перевести разряды в младщую часть. Редуцирование можно выполнить методом умножения на х8 mod Poly. В данном контексте матрица аффинного преобразования получается из выражения m_mulC(Poly & 0xFF, Poly), редуцирование - это матрица умножения в поле на специальную константу.
Таблица матриц редуцирования 0x11B: M=0xB1D3A6FD4B962C58 0x11D: M=0x71E2B51B478E1C38 0x165: M=0xDDBAA952A495F7EE 0x171: M=0x8D1A34685D37E3C6 0x177: M=0x4DD7E3C6C1CFD3A6 0x1C3: M=0x5BEDDAB468D0FBAD 0x1F5: M=0x2346AF5E9F1D1911
Транспонирование матрицы 8х8 бит в поле GF(2^8)
Трюк такой: можно поменять местами матрицу и вектора над которыми матрица работает, результат - можно получить транспонирование матрицы, если на входе диагональная.
// Транспонирование матриц 8x8 бит
__m128i transpose_8x8 (__m128i m){
__m128i E = _mm_set1_epi64x(0x0102040810204080ULL);
return _mm_gf2p8affine_epi64_epi8(E, m, 0);
}
Транспонирование матрицы M = 0x0123456789ABCDEF;
M MT
11101111 =EF 11110000 =F0
11001101 =CD 11001100 =CC
10101011 =AB 10101010 =AA
10001001 =89 00000000 =00
01100111 =67 11110000 =F0
01000101 =45 11001100 =CC
00100011 =23 10101010 =AA
00000001 =01 11111111 =FF
Чтобы убедиться, что это действительно транспонирование, применяем повторно. Повторное транспонирование возвращает матрицу к исходному виду. Транспонирование в таком виде нужно, чтобы динамически составлять матрицы умножения на константу. Ниже привожу функцию динамической генератции матрицы аффинного преобразования, которая выполняет умножение на константу в поле GF(2^8)/0x11B
// Составление Матрицы умножения на константу в поле 0x11B
__m128i m_mulC_11B(uint8_t c) {
__m128i E = _mm_set1_epi64x(0x0102040810204080ULL);
__m128i m = _mm_gf2p8mul_epi8(E, _mm_set1_epi8(c));
return _mm_gf2p8affine_epi64_epi8(E, m, 0);// транспонирование 8x8
}
Матрица редуцирования [1B, 0x11B] A= 0xB1D3A6FD4B962C58 Матрица умножения на [A5, 0x11B] A= 0xABFCF9581A356AD5
