Для расчета хеш функции ГОСТ Р 34.11-2012 "Stribog" выполняется табличная подстановка в цикле - это общепринятая практика.
Если вернуться к определению алгоритма, его описывают последовательностью матричных операций S, P, L, X:
S - подстановка Sbox для каждого элемента 8x8 байт.
P - транспонирование матрицы 8х8 байт
L - линейное преобразование.
X - исключающее ИЛИ.
Линейное преобразование может быть представлено операцией умножения матрицы коэффициентов 8x8 на матрицу состояния 8x8 в поле GF(2^8) с полиномом 0x171.
LM = {
0x71, 0x05, 0x09, 0xB9, 0x61, 0xA2, 0x27, 0x0E,
0x04, 0x88, 0x5B, 0xB2, 0xE4, 0x36, 0x5F, 0x65,
0x5F, 0xCB, 0xAD, 0x0F, 0xBA, 0x2C, 0x04, 0xA5,
0xE5, 0x01, 0x54, 0xBA, 0x0F, 0x11, 0x2A, 0x76,
0xD4, 0x81, 0x1C, 0xFA, 0x39, 0x5E, 0x15, 0x24,
0x05, 0x71, 0x5E, 0x66, 0x17, 0x1C, 0xD0, 0x02,
0x2D, 0xF1, 0xE7, 0x28, 0x55, 0xA0, 0x4C, 0x9A,
0x0E, 0x02, 0xF6, 0x8A, 0x15, 0x9D, 0x39, 0x71,
Пояснение, как оно соотносится с с матрицей A.
Колонка 1 матрицы M - это элемент A[0] = 0x8e20faa72ba0b470,
для которого выполнен разворот порядка следования бит.
8E=>71 20=>04 FA=>5F
Колонка 2 матрицы M - это элемент A[8],
. . .
Колонка 8 матрицы M - это элемент A[56],
Я независимо вывел эту таблицу, из представленнй таблицы подстановки. О возможности подобного представления читал в статье автора [1].
Продемонструю, как выполнить декомпозицию таблиц. Берем два числа: первоя строка, вторая и третья колонка:
A[1] = 0x47107ddd9b505a38
A[2] = 0xad08b0e0c3282d1c
Выделяем по маске 7 бит в каждом байте
(A[1] & ~0x0101010101010101) >> 1)^A[2] видим числа 0x8E008E8E8E000000. В каждом байте стоит полином, по которуму производится редуцирование 0x171, с отраженным порядком бит будет 0x8E. Перед нами просто таблица умножения в поле GF(2^8)/[0x171] с отраженным порядком следования бит в байте.
Линейное преобразование может быть представлено таблично.
Cвойство L(a+b) = L(a) + L(b), как и свойство L(a*b) = L(a)*L(b) - действует и для таблицы.
Мы рассматриваем возможность реализации без таблицы, с использованием афинных преобазований и операци умножения в поле GF(2^8). Операция умножения может быть выполнена с использованием векторных инструкций умножения без переносов (Intel), полиномиального умножения (Arm Neon). Афинные преобразования могут выполняться с использованием векторных инструкций без обращения к таблицам.
Оптимизация под векторные инсрукции Arm Neon. 16 байт составляют вектор, используя вектора можно в два действия эмулировать работу операции умножения на константу. Для эмуляции используется свойство линейности преобразования.
Оптимизация под GF-NI:
Парадокс в том, что отечественные алгоритмы Stribog и Kuznyechik можно считать с использованием американской криптографии. Американская криптография использует умножение в поле GF(2^8) по полиному 0x11B. Отечетсвенная криптография использует умножение с редуцированием по полиному 0x171 в алгоритме Stribog, 0x1C3 в алгоритме Kuznyechik. Можно использовать афинные изоморфные преобразования, чтобы отобразить все матрицы и коэффициенты для использования умножения в поле 0x11b.
Матрицы изоморфного преобразования мы научились находить[2]. Для преобразования 0x171=> 0x11B можно использовать
матрицы
матрицы изоморфного преобразования 171 => 11B "Stribog"
171=>11B 02 0E M =49A24EE22C984CF0 M-1 =FB44BAF0CC5A0A1C
171=>11B 02 17 M =C30E560C5240D828 M-1 =6D0A141C3A9C2046
171=>11B 02 52 M =B1A27CD0765CD234 M-1 =F5481A5CBE24D86E
171=>11B 02 54 M =29903A0892D47ABC M-1 =E5126608F2EC44F0
171=>11B 02 A0 M =C154448014AEDCC6 M-1 =1B8C164A06F81208
171=>11B 02 B4 M =1590FECC3E8E8CE6 M-1 =9960C6DA5E32485C
171=>11B 02 F6 M =090EFAA096722E1A M-1 =6FD8B46E36428C4A
171=>11B 02 FD M =A7541EDA2602426A M-1 =CB20B646D48660DA
Изоморфное представление матрицы LM в поле 0x11B:
unsigned char LM_11b = {
0xF6,0x55,0x74,0xE4,0x56,0x3E,0xC1,0x2F,
0x54,0xDF,0x17,0x9E,0xA9,0x60,0x43,0x02,
0x43,0x1D,0x10,0x2E,0xEB,0xBB,0x54,0x65,
0xA8,0x01,0x39,0xEB,0x2E,0xA1,0xE1,0xAD,
0x93,0xAB,0x81,0x26,0x4E,0x42,0xF5,0xCE,
0x55,0xF6,0x42,0x0D,0xFB,0x81,0xC7,0x0E,
0xBA,0x5C,0xA6,0xEF,0x38,0x30,0xEC,0x71,
0x2F,0x0E,0x07,0xD1,0xF5,0x2A,0x4E,0xF6,
Необходимо таже преобразовать таблицу Sbox в изоморфное представление
Sbox_iso = MR·S·RM-1, где MR и RM-1 - матрицы прямого и обратного изоморфного преобразования из поля образованного полиномом 0x171 в поле 0x11b. R - отражение порядка следования бит.
void SPLX_11b(const uint8_t* s, uint8_t* r)
{
int i,j,k;
for (i=0; i<8; i++)
for (j=0; j<8; j++) {
uint8_t v= 0;
for (k=0; k<8; k++)
v ^= gf2p8_mul(LM_11b[j*8+k], Sbox_iso[s[k*8+i]]);
r[i*8+j] ^= v;
}
}
Полученный алгоритм выполняет операции S,P,L,X. В цике выполняется операция умножения в поле GF(2^8)/0x11B. Оптимизация под ARM Neon может использовать полиномиальное умножение с последующим редуцированием.
Я озаглавил сообщение "Крипто-рубль..". Все алгоритмы добычи крипто-валют основаны на вычислении хеш-функций, этот алгоритм удалось выполнить исключительно в 8-битных числах. Это открывает возможность векторизовать алгоритм для параллельного вычисления до 64 хешей. Другая оптимизация - изоморфное преобразование в композитное поле позволяет получить эффективную реализацию алгоритма аппаратно в ASIC или на FPGA.
[1]
Algebraic Aspects of the Russian Hash Standard GOST R 34.11-2012, O. Kazymyrov, V. Kazymyrova
