Цифровая подпись ГОСТ -- быстрое редуцирование по модулю простого числа

Настал момент поделиться ноу-хау, как ускорять криптографию ГОСТ. Вернее одна маленькая деталь, но самая важная. Как быстро выполнять редуцирование - модуль простого числа. Как вообще строится цифровая подпись. Есть математика на бублике, в поле целых чисел по модулю простого числа. На этом строится и RSA и ECDSA и ГОСТ. Можно сказать модуль числа - это самая критическая операция - остаток от деления.

Любая операция на бублике: это умножение большого числа (256 или 512 бит) или сложение большого числа сопровождается последующем редуцированием(взятием по модулю).
Простые числа в криптографии часто выбирваются исходя из простоты восприятия человеком и с возможностью оптимизации вычислений, например в ГОСТ представлены простые числа вида P = 2^(n-1)+p0 и P = 2^n - p0 где n=256 или n=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. Операция взятия модуля выполняется всего один раз на множество операций, только при сравнении чисел.

Теперь рассмотрим второй случай, когда простое число представленно суммой P=2^(N-1) + p0, где 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.