Настал момент поделиться ноу-хау, как ускорять криптографию ГОСТ. Вернее одна маленькая деталь, но самая важная. Как быстро выполнять редуцирование - модуль простого числа. Как вообще строится цифровая подпись. Есть математика на бублике, в поле целых чисел по модулю простого числа. На этом строится и RSA и ECDSA и ГОСТ. Можно сказать модуль числа - это самая критическая операция - остаток от деления.
Любая операция на бублике: это умножение большого числа (256 или 512 бит) или сложение большого числа сопровождается последующем редуцированием(взятием по модулю).
Простые числа в криптографии часто выбирваются исходя из простоты восприятия человеком и с возможностью оптимизации вычислений, например в ГОСТ представлены простые числа вида
Все операции в поле выполняются по модулю. Например, умножение по модулю - это умножение и модуль числа.
// Умножение с редуцированием по модулю простого числа.
void bn_mulm(bn* r, bn* a, bn* b)
{
int cy = bn_mul(r, a, b);
bn_mod(r, cy, Prime);
}
Вычисление модуля можно выполнять оптом, т.е. сначала выполнить все операции умножения и сложения, а потом выпонить редуцирование результата по модулю. Но это может быть накладно с точки зрения числа операций умножения и сложения. Т.е. если на входе число 512 бит, то умножение таких чисел даст 1024 бита. И последующие операции нужно будет выполнять с разрядностью 1024 бита. По этой причине все алгоритмы стрим по принципу: умножение - редуцирование. Редуцирование надо выполнять после каждого умножения больших чисел.
Переходим к сути. Давайте будем выполнять упрощенную операцию редуцирования, которая возвращает результат умножения обратно в 512 бит. При этом результат редуцирования может быть незавершенной операцией взятия модуля просто числа.
Что в таком случае редуцирование?
Представим результат операции - как перенос (сx- число, которое вылезло за пределы 512 бит) и число X, которое осталось в пределах 512 бит {cx, x}. При этом число x имеет разрядность 512 бита, а перенос - 32 или 64 бита, зависит от архитектуры процессора, ориентируемся на 64 бита.
Наша задача сводится к тому, чтобы вычесть из числа {cx,x} простое число несколько раз, чтобы перенос стал нулевым. При этом остаток помещается в 512 бит, но может требовать дальнейших операций по редуцированию. Нам важно только одно - результат редуцирования помещается в заданные 512 бит. Операцию можно выполнить в два этапа.
Алгоритм 1. Быстрое редуцирование в поле P = 2^N - p0
1. {cy,x} : = {cx, x} - (2^512-p0)*cx;
В результате cy может быть равен нулю или единице.
2. if cy>0 then {cy,x} : = {cy, x} - P;
Чтобы это работало на P надо наложить некоторые ограничения p0 < 2^(n-m), где m - разрядность переноса.
Алгоритм можно упростить:
Алгоритм 1.1. Быстрое редуцирование P = 2^N - p0
1. {cy,x} : = x + p0*cx;
2. if cy>0 then x : = x + p0;
Быстрое редуцирование не является взятием по модулю. Редуцирование возвращает число в заданную разрядность 2^n. Операция взятия модуля выполняется всего один раз на множество операций, только при сравнении чисел.
Теперь рассмотрим второй случай, когда простое число представленно суммой
, где N -- разрядность поля, 256 или 512.
Алгоритм 2. Быстрое редуцирование P = 2^(N-1) + p0
1. {cy,x} : = {cx, x} - 2*(2^511+p0)*cx = x - 2*p0;
В результате cy может быть равен нулю или (-1).
2. if cy<0 then {cy,x} : = {cy, x} + P;
При значении cy == (-1) x находится в интервале [-2*p0; -1], в старшем бите единица (1).
Полагаю равносильно заменить P на втором шаге на 2P. Cуть операции редуцирования не меняется.
Алгоритм 2.1. Быстрое редуцирование P = 2^(N-1) + p0
1. {cy,x} : = {cx, x} - 2*(2^511+p0)*cx = x - 2*p0*cx;
В результате cy может быть равен нулю или (-1).
2. if cy<0 then {cy,x} : = {cy, x} + 2*P = x + 2*p0;
Отдельно рассматриваем редуцирование при сложении и вычитании
Алгоритм 3. Сложение с редуцированием
1. {cy, x} := a+b
В результате cy принимает значения 0 или 1.
2. if (cy>0) {cy,x} := {cy,x} - (2^N - p0) = x + p0
Может понадобится третий шаг, очень мало вероятно:
3. if (cy>0) {cy,x} := {cy,x} - (2^N - p0) = x + p0
Для примера рассмотрим операцию вычисления умножения двух больших чисел разрядностью N. Зачем? Просто так, добавить больше нечего.
// Алгоритм 4. Умножение с накоплением (со сложением)
uint64_t bn_mla_512(uint64_t* r, uint64_t *a, uint64_t d)
{
unsigned __int128 ac = 0;
int i;
for (i=0;i<8; i++) {
ac += (unsigned __int128)d*a[i] + (unsigned __int128)r[i];
r[i] = (uint64_t)ac;
ac = ac>>64;
}
return (uint64_t)ac;
}
Операция "Умножение с накоплением" используется в реализации Алгоритма 1.1, быстрого редуцирования.
// Алгоритм 5. Умножение с вычитанием
int64_t bn_mls_512(uint64_t* r, uint64_t *a, uint64_t d)
{
__int128 ac = 0;
int i;
for (i=0; i<8; i++) {
ac += (unsigned __int128)r[i] - (unsigned __int128)a[i]*d;
r[i] = (uint64_t)ac;
ac = ac>>64;
}
return (int64_t)ac;
}
Операция "Умножение с вычитанием" используется в реализации Алгоритма 2.1, быстрого редуцирования.
Эффективность описания операции (Alg.5) сомнительна, в рабочем проекте я использую ассемблер. Данное описание мне понадобилось для отладки под GCC 10 на платформе Intel x86_64.