GF2p8 Кодирование Рида-Соломона в изоморфном представлении поля

Коды Рида-Соломона считаются через экспоненты и логарифмы по таблице. А у нас с внедренеием инструкций Intel GFNI появилось две другие возможности: использовать инструкцию умножения и аффинные преобразования.

Для примера я взял коды РС из проекта библиотеки генеации QR-кодов. Там используется полином поля G(2^8) P = 0x11D. Кодирование производится в цикле. При переходе к операциям умножения в поле 0x11D, цикл кодрования выглядит так.

	for(i = 0; i < data_length; i++) {
		uint8_t fb =  data[i] ^ Z[0];
		for(j = 0; j < ecc_length-1; j++) {
			Z[j] = Z[j+1] ^ gf2p8_mul(fb, g[j], 0x11D);
		}
		Z[j] = gf2p8_mul(fb, g[j], 0x11D);
	}
	for(i = 0; i < ecc_length; i++) {
		ecc[i] = Z[i];
	}

Преобразование алгоритма для расчета в изоморфном представлении поля с образующим полиномом 0x11B:

	const uint64_t M = 0xFFAACC88F0A0C080;
	const uint64_t Mr= 0xFFAACC88F0A0C080;

	for(i = 0; i < data_length; i++) {
		uint8_t fb =  affine(M,data[i]) ^ Z[0];
		for(j = 0; j < ecc_length-1; j++) {
			Z[j] = Z[j+1] ^ gf2p8_mul(fb, g[j], 0x11B);
		}
		Z[j] = gf2p8_mul(fb, g[j], 0x11B);
	}
	for(i = 0; i < ecc_length; i++) {
		ecc[i] = affine(Mr, Z[i]);
	}

Данное преобразование предполагает так же изоморфные преобразования компонент вектора генератора кодов (g). Векторизация алгоритма может быть выполнена по вложенному циклу.

[1]The comeback of Reed Solomon codes N.Drucker, Sh.Gueron, V.Krasnov

Приложение

Довеском идет код для расчета остатка от деления на 255. Когда в контроллере нет полиномиального умножения, приходится использовать способ расчета умножения и инверсии с использованием таблиц логарифмов и экспонент.

// Multiplication in Galua Fields
int gf_mul(int x, int y) {
    if (x == 0 || y == 0) return 0;
    return exp_[(log_[x] + log_[y])%255];
}
// Inversion in Galua Fields
int gf_inv(int x) {
    return exp_[255 - log_[x]];
}
// Division in Galua Fields
int gf_div(int x, int y) {
    if (x == 0) return 0;
    return exp_[(log_[x] + 255 - log_[y]) % 255];
}

Самая неудобная операция в этом случае - вычисление остатка от деления на 255. Избавился от деления.

// Остаток от деления на 255
uint8_t mod255(unsigned v) {
	uint32_t q = (v*0x1010102UL)>>(24);
	return q;
}

// Остаток от деления на 255
uint8_t mod255(unsigned v) {
	return v + (v>>8);
}

А этот вариант самый простой, применим для сложения логарифмов.

Такая вот оптимизация.

[2] Исходники на Github

Крипто-Рубль. Изоморфные преобразования при вычислении Хеш функции Stribog

Для расчета хеш функции ГОСТ Р 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