暗号の数学

計算法 (演算の高速化)

Karatsuba乗算

$2n$ 桁の数 $u$，$v$ の乗算を行うことを考える．$u$，$v$ を基数 $b$ の冪 $x = b^n$ を用いて

\[ u=u_1x+u_0,\quad v=v_1x+v_0 \]

のように上半分と下半分に分ければ，$x$ を基数とした乗算と考えることができる．

このとき単純に $w = u v$ を求めると，

\[ w = u_1v_1x^2+(u_0v_1+u_1v_0)x+u_0v_0 \]

のように $n$ 桁 $\times$ $n$ 桁の乗算が 4回必要である．しかし

\[ u_0v_1+u_1v_0=(u_1+u_0)(v_1+v_0)- (u_1v_1+u_0v_0) \]

または

\[ u_0v_1+u_1v_0=u_1v_1+u_0v_0-(u_1-u_0)(v_1-v_0) \]

という関係を使えば $n$ 桁 $\times$ $n$ 桁の乗算は 3回で済むことが分かる．ここで，さらに $u_1,u_0,v_1,v_0$ の上位の桁を $0$ で埋めて桁数を偶数にするか，あるいは始めから $u$，$v$ の桁数を2の冪にしておけば，3回の乗算に同じアルゴリズムを再帰的に適用することができる．この乗算アルゴリズムを Karatsuba乗算(Karatsuba Multiplication)という．すなわち，$b$ 進法で表現したとき 2桁になる整数同士の乗算は，$b$ 進法で1桁の整数同士の乗算を3回と，それよりもコストの十分に小さい加減算を用いて行うことができる．

$n = 2^k$と仮定したとき，$b$ 進法で $n$ 桁の整数同士の乗算をKaratsuba乗算で行うと，$b$ 進法で1桁の整数同士の乗算が $3^k$ 回必要となる．$k = \log_{2}n$ より，この方法での $b$ 進法で $n$ 桁の整数同士の乗算のコストは，$3^k = 3^{\log_{2}n} = n^{\log_{2}3} \cong n^{1.585}$ 程度で済むことになる．実際には $n$ が $2^k$ で表現できるとは限らないので，$2^k$ で表現できないときは $n^{1.585}$ よりも少し余計にかかる．

多項式の積 (Karatsuba - Offman乗算)

多項式の変数 $x$ の係数を計算するときに，$x^0$ や $x^2$ の係数を再利用することにより，加減算より遅い乗算の回数を削減でき高速化が図れる（$a_i$ や $b_i$ が多項式である場合には効果がある）．

\begin{align} &(a_0 + a_1x)(b_0 + b_1x) = a_0b_0 + (a_0b_1 + a_1b_0)x + a_1b_1x^2\\ &= a_0b_0 + \{(a_0 + a_1)(b_0 + b_1) - a_0b_0 - a_1b_1\}x + a_1b_1x^2 \end{align} \begin{align} &(a_0 + a_1x + a_2x^2)(b_0 + b_1x + b_2x^2)\\ &= a_0b_0 + [\{(a_0 + a_1)(b_0 + b_1) - a_1b_1\} - a_0b_0]x + [(a_0 + a_1 + a_2)(b_0 + b_1 + b_2)\\ &\quad - \{(a_0 + a_1)(b_0 + b_1) - a_1b_1\} - \{(a_1 + a_2)(b_1 + b_2) - a_1b_1\}]x^2\\ &\quad + [\{(a_1 + a_2)(b_1 + b_2) - a_1b_1\} - a_2b_2]x^3 + a_2b_2x^4\\ \end{align}

中国人の剰余定理

定理
$p_1, p_2, \ldots, p_m$ を互いに素な整数とするとき， \begin{align} &x \equiv a_1 \pmod{p_1}\\ &x \equiv a_2 \pmod{p_2}\\ &\cdots\\ &x \equiv a_m \pmod{p_m}\\ \end{align} からなる連立一次合同式は，法 $n＝p_1p_2\ldots p_m$ のもとで次の一意な解をもつ． \[ x = a_1n_1x_1 + a_2n_2x_2+ \cdots + a_mn_mx_m \pmod{n} \] \[ n_ix_i \equiv 1 \pmod{p_i},\quad n_i=n/p_i\]
例
連立一次合同式
\begin{align} x \equiv 1 \pmod{4}\\ x \equiv 3 \pmod{5}\\ x \equiv 2 \pmod{7}\\ \end{align} は，次のように解ける．
\begin{align} &4・5・7 = 35・4 = 28・5 = 20・7 = 140\\ &35・3 \equiv 1 \pmod{4}\\ &28・2 \equiv 1 \pmod{5}\\ &20・6 \equiv 1 \pmod{7}\\ &x = 35・3・1 + 28・2・3 + 20・6・2 = 93 \pmod{140}\\ \end{align}
アルゴリズム
入力：整数 $a_1,a_2,\ldots, a_k\quad p_1,p_2,\ldots, p_k$
出力：解 $x$
1. $M :=p_i,\ b:=a_1$
2. For $i = 2$ to $k$
3. 　$b := \bmod (b + M \mathrm{modinv} (M, p_i)(a_i-b), M p_i)$
4. 　$M := M p_i$
5. Return $b$

剰余演算

べき乗剰余演算
整数 $M$ の法 $N$ におけるべき乗剰余 $R = M^e \bmod N$ を求める．指数 $e$ を 2進表現したときのビット数を $n$ とする．

(1) Binary法(右向き法)
1. $R \leftarrow M$
2. For $i = n - 2$ down to $0$ do
3. 　$R \leftarrow R^2\ \bmod N$
4. 　If $i$-th bit of $e$ is $1$ then
5. 　　$R \leftarrow R・M\ \bmod N$
6. Return $R$
(2) Binary法(左向き法)
1. $R \leftarrow 1$
2. $S \leftarrow M$
3. For $i = 0$ to $n - 1$ do
4. 　 If $i$-th bit of $e$ is $1$ then
5. 　　 $R \leftarrow R\cdot S\ \bmod N$
6. 　 $S \leftarrow S^2\ \bmod N$
7. Return $R$
(3) 中国人の剰余定理の利用

$N$ が合成数の場合，$N$ の因数分解と中国人剰余定理を用いてべき乗剰余演算を高速化できる．

$N=\prod p_i,\ \gcd(p_i, p_j)=1\ (i \ne j)$ と因数分解できた場合， $Y=X^e \bmod\ N$ はすべての $i$ に対して $Y=X^e \bmod\ p_i$ を満たす数である．
$Y$ は，$Y_i=X^e \bmod\ p_i$ を計算すれば中国人剰余定理を用いて，
\[ Y = \sum (N/p_i)d_iY_i\ \bmod\ N \]
で求められる．ここで， $d_i$ は $d_i\cdot N/p_i = 1 \bmod p_i$ を満たす数である．

上記の中国人の剰余定理は，RSA暗号の復号に次のように利用される．

$M = C^d\ \bmod n$　($n = pq:\ p,\ q$ は互いに素な整数)を計算する場合，
\begin{align} &c_1=C\ \bmod p,\quad c_2=C\ \bmod q\\ &d_1=d\ \bmod p-1,\quad d_2=d\ \bmod q-1\\ &m_1= C^d\ \bmod p = c_1^d\ \bmod p = c_1^{d1}\ \bmod p \\ &m_2= C^d\ \bmod q = c_2^d\ \bmod q = c_2^{d2}\ \bmod q \\ \end{align}
より，次の連立方程式を解けばよい．
\[ M \equiv m_1 \pmod{p} \] \[ M \equiv m_2 \pmod{q} \]
各種のべき乗演算
(1) $\underline{Y=X2^k\ \bmod\ N}$
　入力： $X\in Z_N$，$N$ (奇数)，$k \gt 0$
　出力： $X{2^k}\ \bmod\ N$
1. If $k = 0$ then return $X$ else $k = k-1$
2. If $X \leftarrow 2X$
3. If $X \gt N$ then $X \leftarrow X-N$
4. Goto step 1
(2) $\underline{Y=X2^{-k}\ \bmod\ N}$
　入力： $X\in Z_N$，$N$(奇数)，$k \gt 0$
　出力： $X{2^{-k}}\ \bmod\ N$
1. If $k = 0$ then return $X$ else $k \leftarrow k -1 $
2. If $X$ is even then $X \leftarrow X / 2$ else $X \leftarrow (X + N) / 2$
3. Goto step 1
(3) $\underline{Y=X^{-1}\ \bmod 2^k}$
　入力：奇整数 $X$，$0 \lt X \lt 2^k$
　出力： $X^{-1}\ \bmod 2^k$
1. $Y \leftarrow 1$
2. For $i = 2$ to $k$ do
3. 　If $XY \pmod{2^i} \gt 2^{i-1}$ then $Y \leftarrow Y + 2^{i-1}$
4. Return $Y$
(4) $\underline{Z=XY \bmod p^2}$
　入力：整数 $X$，$Y$
　出力： $XY \bmod p^2$
1. $X = a_1 + b_1p$
2. $Y = a_2 + b_2p$
3. $a_1a_2 = a' + b'p$
4. $a'' = a_1b_2 + a_2b_1 + b' \bmod p$
5. $XY \bmod p^2 = (a_1+b_1p)(a_2+b_2p) \bmod p^2$
  $\qquad = a_1a_2 + (a_1b_2 + a_2b_1)p \bmod p^2$
  $\qquad = a' + (a_1b_2 + a_2b_1 + b')p \bmod p^2$
  $\qquad = a' + a''p\quad (\lt p^2)$

逆元

並列逆元
2 つの逆元の計算 $a^{-1}$ と $b^{-1}$ は， \[ a^{-1} = (ab)^{-1}\cdot b \] \[ b^{-1} = (ab)^{-1}\cdot a \] により，１回の逆元と 3回の乗算で行うことができる．
再帰的な繰り返しにより， $t$ 個の逆元は 1回の逆元と $3(t-1)$回の乗算で計算できる．例えば，4個の場合次のようになる． \[ (ab)^{-1} = (ab\cdot cd)^{-1}\cdot cd \] \[ (cd)^{-1} = (ab\cdot cd)^{-1}\cdot ab \]

Montgomery 算法

Montgomery表現
大きな素数 $p$，2進基数 $b$ に対して， \[ R =b^t \gt p \] により，$R$ と $t$ を定義する．このとき， $\mathrm{GF}(p)$ の元 $x$ に対して \[ xR \pmod p \] を $x$ の Montgomery表現という．この表現と通常の表現とは1対1対応である．
Montgomery表現による加法と減法は通常の方法で行われるが，乗法はより効率的に実行できる．そのため，乗算を行う場合に対象とする数を Montgomery表現に変換し，Montgomery空間上で乗算を行い，結果を通常の表現に戻すことにより効率的に乗算を行うことができる．
Montgomery還元
Montgomery表現から通常の表現に戻す演算を Montgomery還元という．Montgomery表現 $y$ の Montgomery還元 $\mathrm{MR}(y)$ は次式で与えられる． \[ \mathrm{MR}(y) = yR^{-1} \pmod p \] Montgomery還元は，以下のアルゴリズムで与えられる．
　入力：整数 $y \lt pR$
　出力： $x = yR^{-1} \pmod{p}$
1. $u \leftarrow -yp^{-1} \pmod{R}$
2. $x \leftarrow (y + up)/R$
3. While $x \ge p$ do $x \leftarrow x - p$
4. Return $x$
上記において，$p^{-1} \pmod{R}$ を事前に計算し保持しておくことで演算を効率化できる．また，$R$ による除算は，$R$ が2進基数のべきであるためシフト演算で計算できる．
なお，$x$ をモンゴメリ表現 $X$ に変換するためには，$R$ を掛けて $p$ による剰余を求めればよいので，あらかじめ $R^2 = R^2 \bmod p$ を用意して $\mathrm{MR}(xR_2)$ を求めればよい．
乗算
- 通常表現
  
  $x, y \in \mathrm{GF}(p)$
  
  $z = xy \pmod{p}$
- Montgomery表現
  
  $X = xR \pmod{p}$
  
  $Y = yR \pmod{p}$
  
  $Z = xyR \pmod{p}$
- Montgomery空間上での乗算
  
  $Z = XYR^{-1} = (xyR^2)R^{-1} = xyR \pmod{p} $
- Montgomery還元
  
  $\mathrm{MR}(Z) = (xyR)R^{-1} = xy \pmod{p} $
逆元
- 通常表現
  
  $x \in \mathrm{GF}(p)$
  
  $z = x^{-1} \pmod{p}$
- Montgomery表現
  
  $X = xR \pmod{p} $
  
  $Z = x^{-1}R \pmod{p} $
- Montgomery空間上での逆元演算
  
  $Z = X^{-1}R^2 = (xR)^{-1}R^2 = x^{-1}R \pmod{p}$
- Montgomery還元
  
  $\mathrm{MR}(Z) = (x^{-1}R)R^{-1} = x^{-1} \pmod{p}$
べき乗
- 通常表現
  
  $x, e \in \mathrm{GF}(p)$
  
  $z = x^e \pmod{p}$
- Montgomery空間上でのべき乗剰余演算 (バイナリ法)
  1. $A \leftarrow R \pmod{p},\quad X \leftarrow xR \pmod{p}$
  2. $i$：number of bit in $e$
  3. $A \leftarrow \mathrm{MR}(AA),\quad i = i - 1$
  4. If $e_i = 1$ then $A = \mathrm{MR}(AX)$.
  5. If $i \ne 0$ then go to step 3.
  6. $z = \mathrm{MR}(A)$

Page Top