Речь идет об оптимизации алгоритма блочного шифра ГОСТ "Кузнечик". Я давно отложил задачу на сладкое, а тут время появилось ее доделать.
В основе шифра Кузнечик лежат две операции. 1) нелинейное биективное преобразование - табличная подстановка. 2) Что-то вполне линейное, в смысле алгебра линейная в конечном поле, на основе арифметики Галуа, с редуцированием по полиному 0x1С3.
Я увидел возможность преобразовать алгоритм, сделать его быстрее.
Итак структура алгоритма такова [ГОСТ 34.12-2015]:
E[K] = X[K10]LSX[K9]... LSX[K2]LSX[K1](a)
Я пропущу описание того, что сделано в первой серии. Я умею выражаться длинными векторами, для этого использую векторные расширения языка Си. Блочный шифр -- это преобразование вектора состоящего из 16 элементов разрядностью 8 бит. Для этого использую описание типа:
Алгоритм защифровывания выглядит так
Шифрование -- это вот такой алгоритм, внутри которого есть функция LS, всего девять циклов по развернутому ключу {K1,K2, ...K10}.
Зашифровывание -- это последовательное применение преобразований:
X[K1], S, L, X[K2], S, L, ... X[K9], S, L, X[K10]
Преобразование X[K](a) = K ⊕ a
Преобразование S -- это таблица подстановок -- "нелинейное биективное преобразование".
Вот добрались до сути. КАК оптимизировать преобразование R16?
Преобразование R выполняется над векторами 16 элементов по 8 бит и содержит 16 циклов.
Кроме всяких пермутаций это преобразование содержит много операций умножения в конечном поле GF(2) с полиномом p(x) = x8 + x7 + x6 + x + 1, или Px = 0x1C3.
Путем долгих мучительных преобразований можно записать, что каждый элемент входного вектора зависит от каждого элемента выходного вектора. Всего 16 наборов констант для каждого элемента. vi = SUM(aj * LMTij) . LMT - это матрица коэффициентов, которую по ходу пришлось пересчитывать и транспонировать, чтобы преобразование стало выглядеть линейно.
На этом этапе я остановился в прошлый раз. Большим достижением казалость то, что алгоритм удалось сделать без ветвления и с ипользованием векторных инструкций. GMULv16 можно заменить на 16 таблиц по 256 значений по 16 байт каждое, 64кБайт. Но это не наш путь.
В цикле можно использовать умножение без переноса, а финальное редуцирование выполнять за пределами цикла.
vi = SUM((aj * LMTij) mod P(x)) = SUM(aj * LMTij) mod P(x)
В результате получаем такой алгоритм:
Может быть есть компромис между размером таблицы и безумным умножением?
Я так понимаю, что большие таблицы медленно обрабатываются, потому что в кеш память не влезают. Если мы делаем алгоритм для контроллера, то таблицы 65кБайт не лезут во флеш память, не лезут в память оперативную, сильно увеличивают объем кода. Обработка таблицы будет идти со скоростью работы памяти, а не со скоростью ядра процессора. Для встроенных приложений нужен компактный код. На нашей целевой архитектуре есть инструкция полиномиального умножения (ARM Cortex-A8+ NEON, ARMv8, Intel Core+AVX), но в контроллерах ARMv7e-m ничего такого нет, вынужденно используем таблицы. Нам понадобятся оба варианта алгоритма. Таблица не лезит в память, поэтому я сделал две таблицы, одна - это таблица умножения на числа 0,1,2,3...15, младшие биты числа. Вторая тоже таблица умножения на числа 0,16,32,64...256, - умножение на старшие биты числа.
В этом варианте умножения используются 32 таблицы по 16 значений по 16 байт, 8кБайт. Надо проверить, какой из двух вариантов быстрее: с подстановкой 8кБайт или с безумным умножением...
Проверил. Сильно зависит от процессора. На 3-м поколении Intel Core-i7 умножение без переносов работает крайне медленно, в пять раз медленнее чем табличный вариант. На 7-м поколении Core-i7 умножение работает в два раза медленнее чем табличный вариант. Разница есть. Табличный вариант позволяет получить скорость зашифровывания около 8 Мбайт/сек. Это все равно медленно.
[11.12.2019] Дальше я исследую возможность переноса алгоритма с умножением полиномов на векторные инструкции ARM NEON. У меня под рукой есть кросс-компилятор GNU ARM Embedded Toolchain, GCC. И есть под рукой плата BeagleBone, на которой могу запустить полученный код. Платформа содержит процессор ARM Cortex-A8 с архитектурой ARMv7-A и поддерживает инструкции NEON.
В системе команд NEON имеется инструкция полиномиального умножения VMULL.P8, которая оперирует с векторами poly8x8_t -- 8 элементов по 8бит. Инструкция производит результат - вектор 128 бит, 8 элементов по 16 бит. Подробнее см. [NEON™ Version: 1.0 Programmer’s Guide] на сайте ARM.
Мой код выглядит так:
Можно ли считать этот результат хорошим. Не знаю. Объективно надо замерить скорость и сравнить результат. Код получился компактный, но не факт что инструкция умножения будет выполняться быстрее, чем обращение к памяти. Делаю 1Миллион циклов зашифровывания и замеряю время -- получаю результат = 2.5 секунды, на платформе beaglebone Texas Instrumens Sitara AM335x. Это получается скорость шифрования 6.4Мбайта/сек. Замеряю результат табличного варианта алгоритма зашифровывания = 4.2 секунды. Мы выиграли время и место. Дальше за счет разворачивания цила удалось повысить скорость зашифровывания при использовании умножения до 7.4Мбайт/сек. Это ХОРОШИЙ результат!
В основе шифра Кузнечик лежат две операции. 1) нелинейное биективное преобразование - табличная подстановка. 2) Что-то вполне линейное, в смысле алгебра линейная в конечном поле, на основе арифметики Галуа, с редуцированием по полиному 0x1С3.
Я увидел возможность преобразовать алгоритм, сделать его быстрее.
Итак структура алгоритма такова [ГОСТ 34.12-2015]:
E[K] = X[K10]LSX[K9]... LSX[K2]LSX[K1](a)
Я пропущу описание того, что сделано в первой серии. Я умею выражаться длинными векторами, для этого использую векторные расширения языка Си. Блочный шифр -- это преобразование вектора состоящего из 16 элементов разрядностью 8 бит. Для этого использую описание типа:
typedef uint8_t uint8x16_t __attribute__((__vector_size__(16)));
Алгоритм защифровывания выглядит так
uint8x16_t kuzn_encrypt(KuznCtx* ctx, const uint8x16_t a)
{
uint8x16_t S = a ^ ctx->K[0];
int i;
for (i=0; i<9; i++){
S = LS(S) ^ ctx->K[i+1];
}
return S;
}
Шифрование -- это вот такой алгоритм, внутри которого есть функция LS, всего девять циклов по развернутому ключу {K1,K2, ...K10}.
Зашифровывание -- это последовательное применение преобразований:
X[K1], S, L, X[K2], S, L, ... X[K9], S, L, X[K10]
Преобразование X[K](a) = K ⊕ a
Преобразование S -- это таблица подстановок -- "нелинейное биективное преобразование".
uint8x16_t LS(uint8x16_t a)
{
int i;
for(i=0; i< 16;i++) a[i] = sbox[a[i]]; // -- подстановка,
uint8x16_t v = R16(a); // -- то самое преобразование L
return v;
}
Вот добрались до сути. КАК оптимизировать преобразование R16?
Преобразование R выполняется над векторами 16 элементов по 8 бит и содержит 16 циклов.
Кроме всяких пермутаций это преобразование содержит много операций умножения в конечном поле GF(2) с полиномом p(x) = x8 + x7 + x6 + x + 1, или Px = 0x1C3.
Путем долгих мучительных преобразований можно записать, что каждый элемент входного вектора зависит от каждого элемента выходного вектора. Всего 16 наборов констант для каждого элемента. vi = SUM(aj * LMTij) . LMT - это матрица коэффициентов, которую по ходу пришлось пересчитывать и транспонировать, чтобы преобразование стало выглядеть линейно.
uint8x16_t GMULv16(uint8x16_t L, uint8x16_t a);
uint8x16_t R16(uint8x16_t a)
{
int i;
uint8x16_t v = {0};
for(i=0; i< 16;i++) {
v ^= GMULv16(LMT[i], a[i]); // -- векторное умножение в поле Px = 0x1C3
}
return v;
}
На этом этапе я остановился в прошлый раз. Большим достижением казалость то, что алгоритм удалось сделать без ветвления и с ипользованием векторных инструкций. GMULv16 можно заменить на 16 таблиц по 256 значений по 16 байт каждое, 64кБайт. Но это не наш путь.
В цикле можно использовать умножение без переноса, а финальное редуцирование выполнять за пределами цикла.
vi = SUM((aj * LMTij) mod P(x)) = SUM(aj * LMTij) mod P(x)
В результате получаем такой алгоритм:
uint8x16_t R16(uint8x16_t a)
{
int i;
uint16x16_t vh = {0};// -- 16 элементов разрядностью 16 бит. 256 бит.
for(i=0; i< 16;i++) {
vh ^= CL_MULv16(LMT[i], a[i]); // -- векторное умножение без переносов
}
uint8x16_t v = RR (vh, Px);// -- финальное редуцирование по полиному P(x),
return v;
}
Может быть есть компромис между размером таблицы и безумным умножением?
Я так понимаю, что большие таблицы медленно обрабатываются, потому что в кеш память не влезают. Если мы делаем алгоритм для контроллера, то таблицы 65кБайт не лезут во флеш память, не лезут в память оперативную, сильно увеличивают объем кода. Обработка таблицы будет идти со скоростью работы памяти, а не со скоростью ядра процессора. Для встроенных приложений нужен компактный код. На нашей целевой архитектуре есть инструкция полиномиального умножения (ARM Cortex-A8+ NEON, ARMv8, Intel Core+AVX), но в контроллерах ARMv7e-m ничего такого нет, вынужденно используем таблицы. Нам понадобятся оба варианта алгоритма. Таблица не лезит в память, поэтому я сделал две таблицы, одна - это таблица умножения на числа 0,1,2,3...15, младшие биты числа. Вторая тоже таблица умножения на числа 0,16,32,64...256, - умножение на старшие биты числа.
uint8x16_t R16(uint8x16_t a)
{
int i;
uint8x16_t v = {0};
uint8x16_t a0 = a & 0xF, a1 = (a >>4) & 0xF;
for(i=0; i< 16;i++) {
v ^= GMULv16_L[i][a0[i]] ^ GMULv16_H[i][a1[i]];
}
return v;
}
В этом варианте умножения используются 32 таблицы по 16 значений по 16 байт, 8кБайт. Надо проверить, какой из двух вариантов быстрее: с подстановкой 8кБайт или с безумным умножением...
Проверил. Сильно зависит от процессора. На 3-м поколении Intel Core-i7 умножение без переносов работает крайне медленно, в пять раз медленнее чем табличный вариант. На 7-м поколении Core-i7 умножение работает в два раза медленнее чем табличный вариант. Разница есть. Табличный вариант позволяет получить скорость зашифровывания около 8 Мбайт/сек. Это все равно медленно.
[11.12.2019] Дальше я исследую возможность переноса алгоритма с умножением полиномов на векторные инструкции ARM NEON. У меня под рукой есть кросс-компилятор GNU ARM Embedded Toolchain, GCC. И есть под рукой плата BeagleBone, на которой могу запустить полученный код. Платформа содержит процессор ARM Cortex-A8 с архитектурой ARMv7-A и поддерживает инструкции NEON.
В системе команд NEON имеется инструкция полиномиального умножения VMULL.P8, которая оперирует с векторами poly8x8_t -- 8 элементов по 8бит. Инструкция производит результат - вектор 128 бит, 8 элементов по 16 бит. Подробнее см. [NEON™ Version: 1.0 Programmer’s Guide] на сайте ARM.
Мой код выглядит так:
#include <arm_neon.h>
uint8x16_t R16(uint8x16_t a)
{
poly16x8_t v0 = {0};
poly16x8_t v1 = {0};
int i;
for(i=0;i<16;i++){
poly8x8_t a8 = vdup_n_u8(sbox[a[i]]);// размножаем значение на все элементы
poly8x16_t p8 = LMT[i];
v0 ^= vmull_p8(a8, vget_low_p8 (p8)); // младшая часть вектора poly8x8
v1 ^= vmull_p8(a8, vget_high_p8(p8));// старшая часть вектора poly8x8
}
/// редуцирование вынесли из цикла
. . .
}
$ arm-eabi-gcc -print-multi-lib
$ arm-eabi-gcc -march=armv7-a+fp -mcpu=cortex-a8 -mfpu=neon-vfpv4 \
-mfloat-abi=hard -O3 -S -o - kuzn.c
vdup.8 d18, r3 -- размножить значение 8x8
vld1.64 {d24-d25}, [r1:64]! -- загрузить LMT 8x8x2
vmull.p8 q13, d18, d24 -- умножить вектора 8x8
vmull.p8 q9, d18, d25 -- умножить вектора 8x8
veor q8, q8, q13 -- исключающее ИЛИ 16x8
veor q11, q11, q9 -- исключающее ИЛИ 16x8
Можно ли считать этот результат хорошим. Не знаю. Объективно надо замерить скорость и сравнить результат. Код получился компактный, но не факт что инструкция умножения будет выполняться быстрее, чем обращение к памяти. Делаю 1Миллион циклов зашифровывания и замеряю время -- получаю результат = 2.5 секунды, на платформе beaglebone Texas Instrumens Sitara AM335x. Это получается скорость шифрования 6.4Мбайта/сек. Замеряю результат табличного варианта алгоритма зашифровывания = 4.2 секунды. Мы выиграли время и место. Дальше за счет разворачивания цила удалось повысить скорость зашифровывания при использовании умножения до 7.4Мбайт/сек. Это ХОРОШИЙ результат!
