GF2p8 Аффинные преобразования (ч. 5): блочный шифр ГОСТ "Кузнечик"

Блочный шифр "Кузнечик". Умножение в изоморфном представлении поля 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], произведение матриц M· M^-1 = E дает единицу, сокращается:

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 такт на цикл алгоритма.