megrxu

Residue Number System

Sep 20, 2020  「Cryptography」  

RNS 指 Residue Number System,是一种通用的用来表示数字和快速计算的一种方法。对于大数的模乘,模加等运算,使用 RNS 能够转化为多个较小数字的模乘模加,从而使得原本的运算能够进行并行完成。

RNS 最初设计是用来并行化处理大数的运算。在抵御旁路分析中,常常用掩码技术(Masking)来将运算分解到多路上同时进行计算,使得攻击者无法通过简单功耗分析,探针等常规攻击手段对秘密信息进行窥探。而 RNS 系统似乎也能够一定程度做到类似的事情(但泄露的信息量仍有待研究)。

基本计算过程

转换到 RNS 表示

将一个数字 $X$ 转换到 RNS 表示是较为简单的。首先选取定一组互质的数字作为 RNS 表示的基,之后对 X 按照基中的每个数字取模,得到的一组数字即是 $X$ 在该 RNS 下的表示。

$$ x_i = X \mod m_i $$

RNS 域上的计算

RNS 域上能够进行模乘,模加和模减操作。除法在 RNS 表示下的计算无法使用相同的简单方式,但也有一定的研究。 乘法,加法和减法的实现都是类似的,直接对表示中数字分别进行模 $m_i$ 下的运算即可。

$$ z_i = x_i \odot y_i \mod m_i,~\textrm{where $\odot$ can be } +, -, \times. $$

这主要得益于中国剩余定理

从 RNS 表示中转换出

从 RNS 表示中恢复原来的数字主要有两种思路,一种是通过直接使用中国剩余定理来进行恢复,另一种则使用了混合基数表示的方法,将 RNS 转换到 MRS,再进行计算得到最终的结果。

中国剩余定理(CRT)

\[ \begin{aligned} X = \sum_{i = 1}^k M_{i,1}\xi_i \mod M_1, \\ \xi_i = \left\vert\frac{x_i}{M_{i,1}}\right\vert_{m_i} = x_i \left\vert{M_{i,1}^{-1}}\right\vert \mod m_i, \\ M_{i,1} = \frac{M_1}{m_i}. \end{aligned} \]

然而,由于 $M_i$ 通常较大,$\mod M_i$ 仍然是较难计算的。因此在这种设计中,$\mod M_i$ 一般通过减去多倍的 $M_i$ 来实现。

\[ X = \sum_{i=1}^k M_{i,1}\xi_i \mod M_1 = \sum_{i=1}^k M_{i,1}\xi_i - \alpha M_1, \textrm{with} \alpha < k. \]

有两种方法来计算其中的 $\alpha$.

  1. 由 Shenoy et. Kumaresan 提出的方法引入了一个额外的模数 $m_\text{extra}$, $\alpha$ 的估计值可以通过

\[ \begin{aligned} x_{\text{extra}} &= \left\vert {\sum_{i=1}^k {M_{i,1}} \xi_i - \alpha M_1} \right\vert_{m_\text{extra}} \Leftrightarrow \\ \left\vert {\alpha} \right\vert_{m_{\text{extra}}} &= \left\vert {\left\vert {\sum_{i=1}^{k}M_{i,1}\xi_i - x_{\text{extra}}}\right\vert_{m_\text{extra}}} {\left\vert {M_1^{-1}} \right\vert_{m_\text{extra}}} \right\vert_{m_\text{extra}} \end{aligned} \]

来进行计算。

  1. 由 Kawamura et. al 提出的方法避免了引入额外的模数,而使用了一种不动点逼近的方法。

混合基数表示(MRS)

混合基数表示中,各个权重分别为之前 RNS 基的连乘结果。

$$ X = \sum_{i=1}^{k} t_i \times (\prod_{j=1}^{i-1} m_j) $$

对于 MRS 中的各坐标,计算如下:

\[ \begin{aligned} t_1 &= x_1 \\ t_2 &= \left\vert m_1^{-1} \right\vert_{m_2} \times (x_2 - t_1) \mod m_2 \\ t_3 &= \left\vert (m_1m_2)^{-1} \right\vert_{m_3} \times (x_3 - (t_2m_1 + t_1)) \mod m_3 \\ \vdots \\ t_i &= \left\vert (\prod_{j=1}^{i-1}m_j)^{-1} \right\vert_{m_i} \times (x_i - (\sum_{j=1}^{i-1}(t_j \prod_{l=1}^{j-1}m_l))) \mod m_i \\ \end{aligned} \]

MRS 表示中是精确的,不需要进行其他的分类讨论和近似,因此在我们的最终的实现中,也使用的是转化到 MRS 再进行计算。

RNS 基的选取

由于基需要是互质的整数,有以下几种策略进行选取。

  1. 使用连续的质数
  2. 使用小质数的幂次,结合连续的质数
  3. 仅使用 $2^n$ 或者 $2^n - 1$ (Low-cost Moduli),便于模数运算
  4. 使用 $2^n +1$,$2^n$, $2^n - 1$,便于模数运算

除此之外,为了能够表示所有的可用的坐标,还需要保证 $\prod m_i $ 足够大。

其他参考文献: