Блочный шифр "Кузнечик". Умножение в изоморфном представлении поля GF(2^8)
Весь цикл сообщений посвященный аффинным преобразованиям мы затеяли ради того чтобы представить этот и подобные ему алгоритмы. Ниже мы рассматриваем преобразование алгоритма шифрования ГОСТ Р 34.12-2015 Кузнечик к изоморфному представлению поля. Целью преобразования является ускорение работы за счет использования инструкций Intel GFNI.
Алгоритм зашифровывания выглядит, как последовательное примение частей преобразования: наложение ключа, биективное нелинейное преобразование S-Box, Линейные преобразования. Линейные преобразования можно свести к умножению в поле GF(2^8)/0x1C3. Можно записать линейные преобразование, как умножение вектора состояния (uint8x16_t, 16 байт) на матрицу коэффициентов (16х16 элементов). Алгоритм линейных преобразований (L) выглядит, как умножение матрицы на вектор:
// Линейное преобразование ГОСТ "Кузнечик"
uint8x16_t LMT[16];
// пересчет матрицы линейного преобразования
for(i=0; i<16; i++)
LMT_iso[i] = _mm_gf2p8affine_epi64_epi8(LMT[i], M, 0);
// пересчет коэффициентов S-Box
for(i=0; i<256; i++)
sbox_iso[i]= affine_byte(M, sbox[affine_byte(Mr, i)]);
/*! Линейное преобразование
В цикле выполняется умножение с редуцированием по полиному 0x11B */
uint8x16_t LS(uint8x16_t s) {
uint8x16_t r = {0};
int i;
for(i=0; i<16; i++) {
uint8_t v = sbox_iso[s[i]];
r ^= _mm_gf2p8mul_epi8(_mm_set1_epi8(v), LMT_iso[i]);
}
return r;
}
/*! Зашифровывание */
uint8x16_t kuzn_encrypt(uint8x16_t* K, const uint8x16_t a)
{
int i;
a = _mm_gf2p8affine_epi64_epi8(a, M, 0);
uint8x16_t s = a ^ K[0];
for (i=0; i<9; i++)
s = LS(s) ^ K[i+1];
return _mm_gf2p8affine_epi64_epi8(s, Mr, 0);
}
Получается простое описание. Преобразование констант из матрицы коэффициентов LMT, как и аффинные преобразования S-Box, можно выполнить статически. Попробую алгоритм выразить формулой. Я убежден, что для программистов проще читать код, чем разбираться в формулах. Я применяю формулы там, где запись дает понимание. В формуле видны все места, куда надо вставить прямое и обратное преобразование. В частности, надо выполнить аффинные преобразования ключа K из представления поля 0x1C3 в 0x11B. Если дана функция двух переменных, то следует выполнить преобразования обеих переменных. Для разработчиков важно уяснить, что прямую и обратную матрицу добавляют в формулу в сочетании M-1·M·А, а потом, используя линейные преобразования, "вдвигают" матрицу внутрь формулы: M-1·А·M. Или же применяют к уравнению (слева) одно и тоже линейное преобразование: к левой и правой частям. В аналитических выкладках, надо четко понимать, какая операция в каком представлении поля и на каком полиноме выполняется.
gfmul[0x1C3](K, x) = M-1gfmul[0x11B](M·K, M·x); sbox[0x1C3](x) = M-1sbox[0x11B](M·x); sbox[0x11B](x) = M·sbox[0x1C3](M-1x);
Ключи (K) пересчитываются в представление поля 0x11B на этапе развертывания ключа. После подстановки формулы sbox[0x1C3] в качестве аргумента gfmul[0x1C3], произведение матриц
gfmul[0x1C3](K, x) = M-1gfmul[0x11B](M·K, (M· M-1)sbox[0x11B](M·a));
Благодаря тому, что gfmul[0x1C3] выполняется в цикле, умножение вектора состояния на обратную и прямую матрицу можно вынести из цикла. В итоге в цикле аффинные преобразования не используются, матрицы изоморфного преобразования применяются только ко входным и выходным данным алгоритма зашифровывания, в то время как умножение производится на полиноме 0x11B.
В таблице представлены матрицы изоморфного аффинного преобразования из представления поля GF(2^8) 0x1C3 в 0x11B и обратно. В расчете можно использовать любую пару.
Таблица преобразований из представления поля 0x1C3 в 0x11B M =0x5D0CE430CEE6BCD0 M-1 =0xC9248C8EB6BE7C4A M =0x61D8CC543E9296A4 M-1 =0x359C60B0663A0EDA M =0x2FA2EA44FA5AD66C M-1 =0x6332D8D6145ED06E M =0x59A208A62EC29AF4 M-1 =0x61EC0A04B4F2D01C M =0xED406082D258646E M-1 =0x89F844381A0602F0 M =0x5BD81880DC3CDA0A M-1 =0x494212C2C6360E08 M =0x0340F81A7C8C1EBA M-1 =0x87864834BAD4025C M =0xC90C4A9E5604C632 M-1 =0x195A202216CC7C46
Идеальный S-Box
Глядя на алгоритм Кузнечик, видно его несовершенство.. Совершенный алгоритм -- тот, который сохраняя высокую степень нелинейности S-Box дает высокую производительность и высокую степень параллельности кода. Для этого нелинейное преобразование S-Box должно выражаться математическими операциями. В статьях предлагают S-Box полученные с использованием операции инверсии (возведения в степень) и аффинных преобразований, (англ. APA -- affine-power-affine).
s(x) = A2·Inv(A1·a(x)⊕C1) ⊕C2
В итоге формула "совершенного алгоритма" для следующего поколения ГОСТ выражается следующим циклом. При этом стандартизировать алгоритм можно с использованием любого из 30 нередуцируемых полиномов поля GF(2^8) и любых немыслимых аффинных преобразований, прежде всего в качестве основы для проектирования S-Box выбираются циркулянты - матрицы построенные на вращении полинома, которые дают обратимые преобразования. Возможно существует декомпозиция, которая представляет S-Box Кузнечик в совершенном виде.
// Предлагаемый алгоритм с использованием APA S-Box и матричного умножения.
uint8x16_t LS(uint8x16_t s) {
s = _mm_gf2p8affine_epi64_epi8(s, A1, C1);
s = _mm_gf2p8affineinv_epi64_epi8(s, A2, C2);
uint8x16_t r = {0};
for(i=0; i<N; i++) {
s = _mm_alignr_epi8(s,s,1);
r^= _mm_gf2p8mul_epi8(s, LMR[i]);
}
return r;
}
Такая структура алгоритма позволяет получить производительность 1 такт на цикл алгоритма.
