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 $ 足夠大。

其他參考文獻: