暗号の数学
標数 2 の体
標数 2 の体 (Binary Finite Field)
$m$ が正の整数のとき，標数2の体 $\mathrm{GF}(2^m)$ は，各々 $m$ ビットの $2^m$ 個の列から構成される．
例えば，
である．
整数 $m$ は，体の次数と呼ばれる．
$m = 1$ の場合，体 $\mathrm{GF}(2)$ は2を法とした整数の集合 $\{0, 1\}$ である．
- 位数 (Order)
$\mathrm{GF}(2^m)$ の元 $\gamma$ の位数とは，$\gamma^v = 1$ となる最小の正の整数 $v$ である．位数は常に存在し，$2^{m-1}$ を割り切る． $k$ と $l$ が整数で，$\gamma^k = \gamma^l$ となるのは，$k \equiv l\ (\bmod\ v)$ のときのみであり，そのときに限られる． - 生成元 (Generator)
数 $v$ が $2^m - 1$ を割り切るならば，位数 $v$ を持つ $\mathrm{GF}(2^m)$ の元が存在する． 特に，$\mathrm{GF}(2^m)$ において，位数 $2^m - 1$ の元 $\gamma$ が存在し生成元と呼ばれる． $\mathrm{GF}(2^m)$ の全ての元が $\gamma$ のべき乗で表わされるためである． - 指数と離散対数
体 $\mathrm{GF}(2^m)^*$ の元 $g$ が位数 $v$ を持つとき，$\mathrm{GF}(2^m)^*$ の要素 $h$ は $h^v = 1$ のときに限り，ある $l$ に対して $h = g^l$ を満足する． 指数 $l$ は，$h$ の離散対数と呼ばれる． 離散対数は, $v$ を法とした整数である． - 離散対数暗号 (DL-based cryptography)
$\mathrm{GF}(2^m)^*$ の位数が $r$ (素数)の元 $g$ を仮定する．
このとき，鍵ペアを次のように定義する．- 秘密鍵 $s$ を $r$ を法とした整数とする．
- 対応する公開鍵 $w$ を $w = g^s$ で定義される $\mathrm{GF}(2^m)^*$ の元とする．
これが暗号として成立するには，対応する公開鍵から秘密鍵を計算すること(離散対数を求めること)が困難であることが必要である．すなわち，このタイプの公開鍵暗号の安全性は離散対数問題の困難性に依存している．
多項式基底
多項式基底表現
- 多項式基底
多項式基底表現では， $\mathrm{GF}(2^m)$ の各要素は次数が $m$ 以下の異なる多項式を表す． すなわち，ビット列 $(a_{m-1} \ldots a_2 a_1 a_0)$ は，次の多項式を表すものと解釈される． \[ a_{m-1}t^{m-1} + \cdots + a_2t^2 + a_1t + a_0. \] 多項式基底は，次の集合である． \[ B = \{t^{m-1}, \ldots , t^2, t, 1\} .\] ビット列の加算は，多項式の加算に対応する． 乗算は，体多項式と呼ばれる次数 $m$ の既約多項式 $p(t)$ を用いて定義される．すなわち，2つの要素の積は対応する多項式の積を多項式 $p(t)$ で還元したものである．
次数 $m$ の既約多項式 $p(t)$ の各々に対応して $\mathrm{GF}(2^m)$ の多項式基底が存在する． また，すべての次数に対して既約多項式が存在する． - 3項式 (Trinomial)と5項式 (Pentanomial)
多項式 $p(t)$ による還元は，$p(t)$ が少ない項からなる多項式のとき非常に効率的になる．最も少ない項の既約多項式は，3項式 $t^m + t^k + 1$ である．そのため，実用上の利用では，体多項式として3項式(あるいは5項式)を選ぶのが一般的である．
多項式基底の演算
- 3項既約多項式による還元
$\underline{f(x)=x^n+x^t+1,\ 0 \lt t \lt n を法とした還元のアルゴリズム}$
入力： $a(x) = a_{2n-2}x^{2n-2}+a_{2n-3}x^{2n-3}+ \cdots + a_1x + +a_0 \in F_2[x]$
出力： $r(x) \equiv a(x)\ \pmod{f(x)},\ \mathrm{deg}\ r(x) \lt n$- For $i = 2n - 2$ to $n$ by $-1$ do
- $a_{i-n} \leftarrow a_{i-n} + a_i,\ a_{i-n+t} \leftarrow a_{i-n+t} + a_i$.
- Return $r(x) = a_{n-1}x^{n-1} + a_{n-2}x^{n-2} + \cdots + a_1x + a_0$.
- 平方と平方根
多項式基底における平方演算は，$\mathrm{GF}(2^m)$ の要素 $α$ が \[ \alpha = \alpha_{m-1}t^{m-1} + \ldots + a_2t^2 + a_1t + a_0 \] で表されるとき， \[ \alpha^2 = \alpha_{m-1}t^{2m-2} + \ldots + a_2t^4 + a_1t^2 + a_0\ \bmod\ p(t) \] となる．すなわち，平方は元の二進係数すべての間に$0$を挿入することに対応し，計算量は $O(n)$ になる．
また，平方根 $\sqrt{\alpha}$ は，$m-1$ 回平方を行うことにより求められる． - Trace
$\alpha$ が $\mathrm{GF}(2^m)$ の要素ならば，$\alpha$のトレースは \[ \mathrm{Tr}(\alpha) = \alpha + \alpha^2 + \alpha^{2^2} + \ldots + \alpha^{2^{m-1}}. \] で与えられる．
$\mathrm{Tr}(\alpha)$ の値は，$\mathrm{GF}(2^m)$ の半分に対して$0$であり，残りの半分に対して$1$である．
$\underline{\alpha \in \mathrm{GF}(2^m)のトレースを求めるアルゴリズム}$
入力： $\alpha \in \mathrm{GF}(2^m)$
出力： $T = \mathrm{Tr}(\alpha)$- $T \leftarrow \alpha$
- For $i$ from $1$ to $m-1$ do
- $T \leftarrow T^2 + \alpha$
- Return $T$
- Half-Trace
$m$ が奇数ならば，$\alpha \in \mathrm{GF}(2^m)$ の半トレースは， \[ \mathrm{HfTr}(\alpha) = \alpha+ \alpha^{2^2}+ \alpha^{2^4} + \ldots + \alpha^{2^{m-1}} \] で与えられる．
$\underline{\alpha \in \mathrm{GF}(2^m) の半トレースを求めるアルゴリズム}$
入力： $\alpha \in \mathrm{GF}(2^m)$
出力： $H = \mathrm{HfTr}(\alpha)$- $H \leftarrow \alpha$
- For $i$ from $1$ to $(m-1)/2$ do
- $H \leftarrow H^2$
- $H \leftarrow H^2 + \alpha$
- Return $H$
- $\mathrm{GF}(2^m)$ 上の二次方程式の解
$\beta$ が $\mathrm{GF}(2^m)$ の元ならば，式 \[ z^2 + z = \beta \] は $\mathrm{GF}(2^m)$ 上で $2 - 2T$ 個の解を持つ．ここで，$T = \mathrm{Tr}(\beta)$ である． したがって，上式はは 0 または 2 個の解を持つ．$z$ が一つの解ならば，他の解は $z + 1$ である． $\beta = 0$ の場合には，解は$0$と$1$である．
二次方程式の解を求めるアルゴリズムは，$m$ が奇数ならば，$\beta$ の半トレースを計算し $z$ とする． $m$ が偶数の場合は，以下のアルゴリズムとなる．
$\underline{二次方程式の解を求めるアルゴリズム (m: 偶数)}$
入力： 多項式基底表現による有限体 $\mathrm{GF}(2^m)$ とその要素 $\beta \ne 0$
出力： 解が存在するとき，$z^2 + z = \beta$ を満たす要素 $z$- ランダムに $\rho \in \mathrm{GF}(2^m)$ を選ぶ．
- $z \leftarrow $0$,\ w \leftarrow \rho$
- For $i=1$ to $m-1$ do
- $z \leftarrow z^2 + w^2\beta$
- $w \leftarrow w^2 + \rho$
- If $w=0$ then goto step 1
- Return $z$
正規基底
正規基底表現
- 正規基底 (Normal basis)
$\mathrm{GF}(2^m)$ に対する正規基底は，次の形式の集合である． \[ B = \{\theta , \theta^2 , \theta^{2^2}, \cdots, \theta^{2^{m-1}} \} \] ここで，$B$ のどの部分集合もその和が $0$ にはならない（線形代数の言葉で言えば，$B$ の要素は線形独立である）．
すべての正整数 $m$ に対して，$\mathrm{GF}(2^m)$ の正規基底が存在する．
$\mathrm{GF}(2^m)$ の正規基底 $B$ による表現では，ビット列 $(a_0 a_1 a_2 \cdots a_{m-1})$ を以下のように解釈する． \[ a_0\theta + a_1\theta^2 + a_2\theta^{2^2} + \cdots + a_{m-1}\theta^{2^{m-1}} \] 正規基底 $B$ の全ての要素は同じ既約多項式 (Irreducible binary polynomial) $p(t)$ を満足する． この多項式は基底に対する体多項式と呼ばれる． また，既約多項式は，それが正規基底に対する体多項式の場合，正規多項式と呼ばれる． - ガウス正規基底 (Gaussian normal basis)
正規基底表現では，体の要素の2乗の計算は非常に効率的(巡回シフト)に行える．一方，相異なる要素の乗算の計算は一般的に複雑になる． このため，乗算の計算が容易になるようなガウス正規基底と呼ばれる正規基底の特別なクラスを考える．
$\mathrm{GF}(2^m)$ に対するガウス正規基底は，$m$ が 8 で割り切れないとき常に存在する．これらは，最適化正規基底 (ONB; Optimal Normal Basis)と呼ばれる正規基底の中で最も乗算が効率的に行えるクラスを含んでいる．
ガウス正規基底のタイプ ($T$)とは，その基底における乗算の複雑さを表す正の整数である．タイプが小さい程，乗算が効率的に行える． 与えられた $m$ と $T$ に対して標数2の体 $\mathrm{GF}(2^m)$ は，高々1つのタイプ $T$ のガウス正規基底を持つ． タイプ1とタイプ2のガウス正規基底は，すべての正規基底の中で最も効率的な乗算が行えるクラスである．このため，これらは最適化正規基底と呼ばれる． タイプ1ガウス正規基底は，タイプI最適化正規基底と呼ばれ，タイプ2ガウス正規底は，タイプII最適化正規基底と呼ばれる．
有限体 $\mathrm{GF}(2^m)$ でのタイプIのONBが存在する条件は以下の2つである．- $m+1$ が素数である．
- $2$ が $\mathrm{GF}(m+1)$ においての原始根となる．
- $2m+1$ が素数である．
- $2$ が $\mathrm{GF}(2m+1)$ の原始根となるか，または $2m + 1 = 3\ (\bmod 4)$ かつ $2$ が $\mathrm{GF}(2m+1)$ で平方剰余となる．
正規基底の演算
- 平方と平方根
正規基底における平方と平方根は，$\mathrm{GF}(2^m)$ の要素 $\alpha$ が \[ \alpha = (\alpha_0 \alpha_1 \ldots \alpha_{m-1}) \] で表されるとき， \[ \alpha^2 = (\alpha_{m-1} \alpha_0 \alpha_1 \ldots \alpha_{m-2}) \] \[ \sqrt{\alpha} = (\alpha_1 \ldots \alpha_{m-2} \alpha_{m-1} \alpha_0) \] となる． すなわち，平方は係数を右巡回シフトしたものであり，平方根は左巡回シフトしたものである． - Trace
$\alpha$ が $\mathrm{GF}(2^m)$ の要素で $(\alpha_0 \alpha_1 \ldots \alpha_{m-1})$ で表されるならば，$\alpha$ のトレースは \[ \mathrm{Tr}(\alpha) = \alpha_0 \oplus \alpha_1 \oplus \alpha_2 \oplus \ldots \oplus \alpha_{m-1}. \] で与えられる．ここで，$\oplus$ は排他的論理和を表す． - 二次方程式の解
$\underline{二次方程式 (z^2+z=\beta) の解を求めるアルゴリズム}$
入力： 正規基底表現による有限体 $\mathrm{GF}(2^m)$ とその元 $\beta \ne 0$
出力： 解が存在するとき，$z^2+z=\beta$ を満たす元 $z$- Let $(\beta_0 \beta_1\ldots \beta_{m-1})$ be the representation of $\beta$
- $z_0 \leftarrow 0$
- For $i=1$ to $m-1$ do
- $z_i \leftarrow z_{i-1} \oplus \beta_i$
- Return $z \leftarrow (z_0z_1\ldots z_{m-1})$
- 乗算
正規基底のタイプ T に対して，$p = T m + 1$ とする．また，以下の $F(n),\ \Delta F(n)$ を定義する． \[ F(2^i u^j\ \bmod\ p) = i,\ 0 \le i \le m-1,\ 0 \le j \le T\] \[ \Delta F(n) = F(n+1) - F(n)\ \bmod\ m\] ここで，$u$ は，$\bmod p$ での位数 $T$ の整数である． なお，$\Delta F(n)$ は固定であり，基底の選択時に一度計算すればよい．
さらに，正規基底 $\{\beta , \beta^2 , \beta^{2^2}, \cdots, \beta^{2^{m-1}} \}$ に対して，以下を定義する． \[ \delta_j=\beta^{1+2^j},\ j = 1,\cdots,v,\ v = \lceil (m-1)/2 \rceil \] ここで，$h_j\ (1 \le j \le v)$ を正規基底表現 $\delta_j$ における$1$の数とする． また， $w_{j,1},w_{j,2},\cdots,w_{j,h_j}$ を $\delta_j$ における1の位置とする． すなわち， \[ \delta_j = \sum_{k=1}^{h_j} \beta^{2^{w_{j,k}}},\ 1 \le j \le v \] である．ここで，$0 \lt w_{j,1} \lt w_{j,2} \lt \cdots \lt w_{j, h_j} \le m-1$ である．
$\Delta w_{j,k}$ を次のように定義する． \[ \Delta w_{j,k} := w_{j,k} - w_{j, k-1},\ 1 \le j \le v,\ 1 \le k \le h_j,\ w_{j,0}=0 \]
$\underline{w_{j,k}\ h_j を求めるアルゴリズム}$
入力： $F(n)\in [0, m-1]$ for $1 \le n \le p-1$
出力： $w_{j,k},\ h_j$- For $j=1$ to $(m-1)/2$
- $k \leftarrow 1,\ h_j \leftarrow 0$
- For $n=1$ to $p-2$ do
- If $(\Delta F(n) = m - j)$ then
- $w_{j,k} = j - F(n)\ \bmod\ m$
- $k \leftarrow k+1, \ h_j \leftarrow h_j+1$
$\underline{乗算アルゴリズム}$
入力： $A, B \in \mathrm{GF}(2^m),\ \Delta w_{j,k} \in [0, m-1],\ 1 \le j \le v,\ 1 \le k \le h_j, v = (m-1)/2$
出力： $C = AB$- $C \leftarrow A \odot B,\ S_A \leftarrow A,\ S_B \leftarrow B$
- $C \gg 1$
- For $j=1$ to $v$ do
- $S_A \ll 1,\ S_B \ll 1$
- $T_A \leftarrow A \odot S_B,\ T_B \leftarrow B \odot S_A$
- $R \leftarrow T_A + T_B$
- For $k=1$ to $h_j$ do
- $R \gg \Delta w_{j,k}$
- $C \leftarrow C + R$
上記において， $X \odot Y\ (X,Y \in \mathrm{GF}(2^m))$ は，$X$ と $Y$ の係数のビットごとの AND 演算，すなわち，$X \odot Y = (x_0y_0, x_1y_1,\cdots,x_{m-1}y_{m-1})$ を示す． また，$\ll(\gg)$ は左(右)巡回シフトを示す．
／