暗号の数学
有限体上の演算
- 基礎体乗算
基礎体 \(\mathbb{F}_p\) 上で \(c=a\cdot b\) を求める (\(a, b, c \in \mathbb{F})\)．- 素体 \(\mathbb{F}_p\)
多倍長整数として \(a\cdot b\) を計算し，\(p\) による剰余算を行う． \[c = a\cdot b \bmod p\]
- 素体 \(\mathbb{F}_p\)
- 拡大体乗算
奇素数 \(p\)，\(n \gt 1\) に対する拡大体 \(\mathbb{F}_{p^n}\) の乗算を行う．
拡大体 \(\mathbb{F}_{p^n}\) は，\(F_p[x] / (f(x))\) と同型である． ここで，\(f(x)\) は \(\mathbb{F}_p\) 上の次数 \(n\) の既約多項式である．
有限体の要素の多項式基底表現 \(A(x) \in \mathbb{F}_{p^n}\) は，次の形式をもつ． \[A(x) = a_{n-1}x^{n-1} + \cdots + a_1x + a_0, a_i \in \mathbb{F}_p\] 乗算は 2段階，多項式の乗算と多項式の還元で行われる．
最初に，2つの体要素 \(A(x)\) と \(B(x)\) に関する通常の多項式の乗算を行う． 結果は，次数が \(2n - 2\) の多項式 \(C'(x)\) になる． \[ C'(x) = A(x) \cdot B(x) = c'_{2n-2}x^{2n-2} + \cdots + c'_1x + c'_0, c'_i \in \mathbb{F}_p \] 次に，以下により剰余を計算する． \[ C(x) = C'(x) \bmod f(x), C(x) \in \mathbb{F}_{p^nn} \] この剰余の計算は，\(C'(x)\) における \(n\)次以上の項 (\(2n-2, 2n-3, \cdots , n\) 次の項)を \(f(x)\) で除算して消去する処理である． ここで， \[ T_k(x) = x^k \bmod f(x), (k = n, \ldots 2n-2) \] として，\(T_k(x)\) を事前計算しておけば，\(T_k(x)\) の定数倍と加算により還元が行える． \[ C(x) = c'_{2n-2}T_{2n-2}(x) + \cdots + c'_nT_n(x) + c'_{n-1}x^{n-1} + \cdots + c'_1x + c_0 \] - 乗法逆元
体 \(\mathbb{F}\) 上で \(a\) の乗法逆元 \(c = a^{-1}\) を求める (\(a, c \in \mathbb{F}\))．
拡張ユークリッド互除法
2つの数 \(a\)，\(b\) の最大公約数 \(d\) と \(d = ax + by\) なる \(x\)，\(y\) を同時に求めるアルゴリズムである．
入力: \(a, b \in\mathbb{F}\) (\(a \gt b\)).
出力: \(a\) と \(b\) の最大公約数 \(d\)，\(d = ax + b\) なる \(x\)，\(y\).- If \(b = 0\) then return (|\(a\)|, |\(a\)|/\(a\), \(0\))
- \(x = a; y = b; x_0 = 1; x_1 = 0\)
- While \(y \ne 0\) do
- \(z = x; x = y\)
- \(y = z \bmod y\)
- \(q = \lfloor z / y \rfloor\)
- \(e = x_0; x_0 = x_1\)
- \(x_1 = e - x_1 q\)
- Return (\(x\), \(x_0\), (\(x - a x_0)/b)\)
拡張ユークリッド互除法において，最大公約数 \(d\) が \(1\) のとき，逆元が存在し， \[ 1 = (ax + by)\ \bmod b = ax\ \bmod b \] となり，\(ax = 1 \bmod b\) より \(a\) の法 \(b\) に対する逆元 \(x\) が求められる． \(d \gt 1\) ならば，逆元は存在しない．
ノルム (Norm) 法
\(x\) の逆元は，ノルム \(\mathrm{N}(x)\) を用いて次のように計算できる．
\(x \in \mathbb{F}_{p^n}\)として， \[ z = \sum_{i=0}^{n-1} x^{p^i} = \mathrm{N}(x) \] によりノルム \(z \in \mathbb{F}_p\) を求めることができる．これより， \[ z = x(\prod_{i=1}^{n-1} x^{p^i}) \] であり， \[ y = \prod_{i=1}^{n-1} x^{p^i} \] とおけば，\(y\) は \(x\) の逆元 \(\iota(x)\) となる．すなわち， \[ y\cdot x =z = \mathrm{N}(x) \] である．
上記のノルムを求める計算は，Itoh-Tsujii の方法により計算量の削減が図れる． 例えば，\(n=5\) の場合，以下のようになる． \[ y ← x\cdot x^p \] \[ y ← y\cdot y^{p^2} \] \[ y ← y^p \] \[ z ← x\cdot y \] なお，\(x^p\) の計算には，Frobenius 写像を用いた高速化が図れる． - 平方根
体 \(\mathbb{F}\) 上で \(c^2 = a\) となるような \(c\) を求める (\(a, c \in \mathbb{F}\))．
Tonelli のアルゴリズム
\(x \in \mathbb{F}\) の平方根を求める．
- 体の位数を \(u\) とし，\(u - 1 = 2^s\cdot t\) なる \(s\) と \(t\)（奇数）を求める．
- 非平方数である \(\mathbb{F}\) の元 \(b\) を見つける．
- \(c = b^t\)
- \(x'= x^{-1}\)
- \(r = x^{(t+1)/2}\)
- \(i\) が \(1\) から \(s - 1\) までの間，次を行う．
- \(d = (r^2 \cdot x')^{2^{s-i-1}}\)
- \(d \neq 1\) ならば \(r = r \cdot c\)
- \(c = c^2\)
- \(r\) が負ならば -\(r\) を，そうでなければ \(r\) を出力する．
- 平方数判定
拡大体の元が平方数であるか否かを判定する．- 拡大体 \(\mathbb{F}_{p^n}\)
元 \(x\) が平方数かどうかの判定式は \(x^{(p^n-1)/2} = 1\) である．
指数を \((1+p+p^2+\cdots +p^{n-1})(p-1)/2\) とし，Frobenius写像を用いて \[t=x^{1+p+p^2+\cdots +p^{n-1}}\] を求め，\(t^{(p-1)/2}\) を行う．
(備考) \[ \sum_{i=1}^n x^i = (1 - x^{n+1}) / (1 - x) \] Frobenius 写像
Frobenius 写像 \(\varphi\) は，\(a\) を \(a^p\) に変換する写像である (\(a \in \mathbb{F}_{p^n}\))． \[ \varphi(a) = a^p \] \(x^{ip}\) を \(c_{i,j} \in \mathbb{F}_p\) を用いて \[ x^{ip} = \sum_{j=0}^{n-1} c_{i,j} x^j \qquad (0 \le i \le n-1) \tag{1}\] と書く． ここで， \(c_{0,n-1}=c_{0,n-2}= \cdots = c_{0,1}=0,\ c_{0,0}=1\) である． \[ a^p = a_{n-1}x^{(n-1)p} + \cdots + a_1 x^p + a_0 \tag{2} \] に式(1)を代入すると， \[ a^p = a_{n-1}\left(\sum_{j=0}^{n-1} c_{n-1,j} x^j\right) + \cdots + a_1\left(\sum_{j=0}^{n-1} c_{1,j} x^j\right) + a_0\left(\sum_{j=0}^{n-1} c_{0,j} x^j\right) \tag{3} \] となる．これを \(x^j\) について整理し，既約多項式の剰余の形 \[ a^p = b_{n-1}x^{(n-1)} + \cdots + b_1x + b_0 \tag{4} \] と比較すると \[ \left(\begin{array}{c} b_0 \\ b_1 \\ \cdots \\ b_{n-1} \end{array}\right) = \left(\begin{array}{cccc} c_{0,0} & c_{1,0} & \cdots & c_{n-1,0} \\ c_{0,1} & c_{1,1} & \cdots & c_{n-1,1} \\ \cdots & \cdots & \ddots & \cdots \\ c_{0,n-1} & c_{1,n-1} & \cdots & c_{n-1,n-1} \end{array}\right) \left(\begin{array}{c} a_0 \\ a_1 \\ \cdots \\ a_{n-1} \end{array}\right) \tag{5} \] を得る．
\(c_{i,j}\) は \(a\) に依存しないので，事前計算することができる．
特にOEF (最適拡大体)の場合，既約多項式が \(f(x)=x^n - \omega\) \((n \mid (p-1))\) の形で，式(5) の \(c_{i,j}\) が対角行列となり，次式が得られる． \[ a^p = b_{n-1}x^{(n-1)p} + \cdots + b_1x^p + b_0 \] \[ b_{ip \bmod n} = a_i \omega^{\lfloor ip/n \rfloor} = a_i \omega_i \] ここで，\(p\)，\(n\) および \(\omega\) は元 \(a\) には依存しないため，あらかじめ \(\omega_i = \omega^{\lfloor ip/n \rfloor}\) を計算しておくことができる．
なお，\(\varphi^i(a) = a^{p^i}\) の写像は式(5) の正方行列の \(i\) 乗で求めることができる．
- 拡大体 \(\mathbb{F}_{p^n}\)
- べき乗
有限体 \(\mathbb{F}_{p^n}\) 上でべき乗 \(c = a^e\) を求める (\(a, c \in \mathbb{F}_{p^n}\))．
\(e\) を \(p\) 進数展開し，Frobenius 写像と乗算を行う．
- 初期設定
- \(e \lt 0\) ならば，\(c=(a^{-1})^{(-e)}\)を求める．
- \(e = e \bmod (p^n - 1)\) とする．
- e の p 進展開を求める． \[ e = \sum_{i=0}^{n-1} e_i p^i \]
- \(e_i\) の 2進展開を求める． \[ e_i = \sum_{j=0}^{pLen-1} e_{i,j} 2^j ,\ e_{i,j} \in \{0, 1\} \ (1 \le i \le n-1) \] ここで，\(pLen\) は \(p\) のビット長とする．
- べき乗計算
\[ c = a^e = \prod_{i=0}^{n-1}(a^{p^i})^{e_i} = \prod_{j=0}^{n-1}(a^{d_j})^{2^j},\qquad d_j =
\sum_{i=0}^{n-1} p^i e_{i,j} \]
\(e_{i,j}\) は 0 か 1 であるため，\(d_j\) は \(p^s(1 + p + p^2 + \cdots p^t)\) の形の式のいくつかの和で表すことができる．
\(e\) が与えられた時点で，\(e_{i,j}\) を求め，\(t\) を計算しておく． また， \(a\) が与えられた時点で，\(Table = {a, a^{1+p}, a^{1+p+p^2}, \cdots ,a^{1+p+p^2+\cdots +p^t}}\) を計算しておく．
\(Table\) の値の \(p^s\) 乗と乗算を繰り返し使うことにより \(a^{d_j}\) の計算を高速に行える． また， \(p^s\) 乗の計算は，Frobenius 写像を用いて高速化が図れる．
- 初期設定
／