Наша задача реализация методов модульной арифметики для ZKP и PQC-пост-квантовой криптографии. Методов оказалось много. Раньше я ссылался на учебник [GECC] (сокр. Guide to Elliptic Curve Criptography), где разобраны разнообразные алгоритмы для криптографии, включая модульную арифметику и арифметику Галуа. В настоящее время появился ряд методов, к ним относятся, оптимизированные методы умножения Шоупа (Shoup) и Плантарда(Plantard, Thomas), а также новая тенденция в использовании модульной арифметики со знаком.
PQC - пост квантовая криптография основана на использование модульной арифметики в кольце полиномов с добавлением квантового шума Ring-LWE. Коэффициенты полиномов считаются в форме векторов длиной 256 элементов и выше.
ZKP - Zero-Knowledge Proof - концепция построения доказательства с нулевым разглашением, применяется например, для доказательства использования сложной функции без раскрытия информации о самой функции; для доказательства использования приватных данных без раскрытия данных. Применяется в распределенных вычислительных системах MPC - Multi-Party Computation.
Какой метод модульной арифметики может быть наиболее эффективным?
При выборе метода мы ориентируемся на систему команд целевой платформы: векторные инструкции CPU или GPU. И в настоящее время это должны быть 16/32/64 битные числа и вектора. Алгоритмы должны выражаться в векторных инструкциях сохраняющих разрядность элементов, таких как `mul_hi` - high product и `mul_lo` - low product, а также операции типа dot product с отложенным редуцированием по модулю могут дать прирост производительности. Операции могут быть с расширением знака или без знака. Заметим, что знаковая и беззнаковая операции умноженения идентичны signed low product и в целевой системе команд одна из операций может быть не представлена и выполняться через приведение типа. В системе команд могут быть представлены операции типа `madd` - умножения с накоплением и `msub` - умножение с вычитанием, в двух вариантах - старшая и младшая часть. Отдельно хочется упомянуть инструкции со странной разрядностью 52, которая рождается на месте мантиссы от double, в системе команд Intel AVX-IFMA.
Векторные инструкции не используют признаки переполнения и переноса разряда - это сильно осложняет реализацию методов для работы с большими числами произвольной разрядности. В этих случаях можно прибегнуть к непозиционной системе исчисления, основанной на CRT-китайской теореме об остатках, см. RNS-Residue Number System.
Оптимизированные алгоритмы опираются на сдвиг 16-, 32-, 52- или 64 бит и отложенное редуцирование Баррета при сложении и вычитании в ядре, при использовании модульных операций в цикле.
Algorithm 1.1. Signed Barrett modular reduction
*Require*: $0\lt q\lt\beta/2$, $-\beta q\leqslant z = z_1 \beta + z_0 \lt 2^{31}q$, где $-2^{31} \leqslant z_0 \lt 2^{31}$
*Require*: precomputed $u = \lfloor (2^{\lfloor \log(q)\rfloor -1} \beta)/q \rceil$
*Ensure*: Returns $r \equiv a \bmod^{\pm} q$ ; $-q\lt r \leqslant q$
- $t ← \lfloor au/\beta \rfloor \gg 2^{\lfloor \log(q)\rfloor -1}$ -- signed low product and arithmetic shift
- $t ← t \cdot q \bmod^{\pm} \beta$ -- signed low product
- $r ← z - t$ -- signed remainder
Algorithm 2. Montgomery's modular multiplication
*Require*: $b,w \in [0,p)$; $p\lt\beta/2$
*Require*: precomputed $J = p^{-1} \mod \beta$, $w' = \beta w \mod p$
*Ensure*: Returns $r = b\cdot w \mod p$
- $U = u_1\beta + u_0 ← bw'$ -- (wide product)
- $q ← u_0J \mod \beta$ -- (low product)
- $h ← \lfloor qp/\beta\rfloor$ -- (high product)
- $r ← u_1 - h$
- $r ← r + p$ if $r \lt 0$
последнюю строчку можно исключить, если принять $r \in (-p, p)$. Две последовательные операции _low product_ в строчке (1) и (2) можно объединить.
Algorithm 2.1. Signed Montgomery's modular multiplication
*Require*: $b,w \in [0,p)$; $p\lt\beta/2$
*Require*: precompute $J = p^{-1} \bmod^{\pm} \beta~$; $w' = w\beta \bmod p~$;
*Require*: precompute $\tilde{w} = w'\cdot J \bmod^{\pm} \beta$ -- (signed low product)
*Ensure*: Returns $r = b\cdot w \bmod^{\pm} p$
- $u_1 ← \lfloor bw'/\beta \rfloor$ -- (signed high product)
- $q ← b\tilde{w} \bmod^{\pm} \beta$ -- (signed low product)
- $t ← \lfloor qp/\beta\rfloor$ -- (signed high product)
- $r ← u_1 - t$
Для алгоритма важен метод вычисления обратного значения $p^{-1}$. Мы его вычисляем в 32 битных числах, потом приводим к знаковому типу $p^{-1} \bmod^{\pm} \beta$.
*Listing* Функция для вычисления $q^{-1} \bmod 2^{s}$, для $s\lt 32$:
uint32_t mod_inverse(uint32_t q, int s) {
uint32_t q_inv = 1;
for (int i = 1; i < s; i++) {
if (((q * q_inv) & ((~0uL)>>(31-i))) != 1) {
q_inv += (1u<<i);
}
}
return q_inv;
}
Алгоритм -авторский, так и родился в виде программы. Базовая идея - инверсия по модулю должна давать единицу для любых s. Аналогичный метод может быть использован для нахождения константы при замене деления. Подобный метод возникал в конечных полях Галуа и все они, вероятно, могут быть выражены через расширенный алгоритм Евклида.
