暗号の数学
奇標数の拡大体
有限体(ガロア体)は,通常の代数演算(加算,減算,乗算,非0要素による除算)が成立ち,かつ代数法則(結合則,分配則)が成立つ有限個の要素からなる集合である.
有限体の次数は,体に含まれる要素の数である. 有限体は,素数 $p$ と正整数 $m$ に対して,$\mathbb{F}_{p^m}$ (または $\mathrm{GF}(p^m)$ で表される.
$m \gt 1$ のとき,有限体の要素は $\mathbb{F}_p$ 上の係数を持つ多項式として表される.
拡大体の演算
- 奇標数の拡大体に関する基本演算
奇素数 $p$,$m \gt 1$ に対する拡大体 $\mathbb{F}_{p^m}$ の演算を考える. これには,特別な場合として最適拡大体 (OEF; Optimal Extension Field)
が含まれる.
拡大体 $\mathbb{F}_{p^m}$ は,$F_p[t] / (f(t))$ と同型である. ここで,
$f(t)$ は $\mathbb{F}_p$ 上の次数 $m$ のモニック既約多項式である.
有限体の要素の多項式基底表現 $A(t) \in \mathbb{F}_{p^m}$ は,次の形式をもつ.
\[ A(t) = a_{m-1}t^{m-1} + \cdots+ a_1 t + a0,\quad a_i \in \mathbb{F}_p \]
算術演算は,体多項式を法として実行される.体多項式の選択は,剰余還元の複雑さを決定する.
- 加算と減算
体の要素に対する加算と減算は,対応する多項式表現の係数をそれぞれ加算または減算し,必要に応じて(係数が $p$ より大きいかまたは負の場合)法 $p$ による還元 ($p$ を引くかまたは加える)を行う.
- 乗算
乗算は2段階,多項式の乗算と多項式の還元で行われる. 最初に,2つの体要素 $A(t)$ と $B(t)$ に関する通常の多項式の乗算を行う.結果は,次数が $2m-2$ 以下の次の多項式 $C'(t)$
になる.
\[ C'(t) = A(t) \times B(t) = c_{2m-2}'t^{2m-2} + \cdots + c_1't + c_0',\quad c_i'\in \mathbb{F}_p \]
係数 $c_i', i = 0, 1, \cdots, 2m-2$ を計算する筆算による方法では,部分体 $\mathbb{F}_p$ における $m^2$ 回の乗算と $(m-1)^2$ 回の加算を必要とする. 次に,
$C(t) = C'(t) \bmod f(t),\ C(t) \in \mathbb{F}_{p^m}$ による剰余を計算する. 二乗は乗算の特別な場合と考えられる.この場合は,筆算における係数の乗算の回数が
$m(m+1)/2$
に減少する.
$p$ の値を選択することにより,部分体での乗算のコストを減少させることができる.
- 平方根
有限体 $\mathbb{F}_{p^m}$ の要素が平方数か否かをテストするアルゴリズム
入力: 有限体 $\mathbb{F}_{p^m}$ とその要素 $g$.
出力: メッセージ "square" または "not a square".
- $b := g^{(p^m - 1)/2}$.
- If $b$ is $0$ or $1$ return "square" ; else return "not a square".
(NOTE. $b$ should be $0$ only if $a$ is $0$, and should otherwise be $+1$ or $-1$.)
有限体 $\mathbb{F}_{p^m}$ における平方根を求めるアルゴリズム
入力: 有限体 $\mathbb{F}_{p^m}$ とその要素 $g$.
出力: $z^2 = g$ となる要素 $z$, あるいは平方根が存在しない場合は“no square roots exist”を出力.
- If $g = 0$ then return $0$
- $k := (p^m + 1) / 4$
- If $k$ is not an integer, then go to step 6
- $z := g^k$
- If $z^2 = g$ then return $z$. Otherwise return “no square roots exist”
- ランダムに $y \in \mathbb{F}_{p^m}$ を選ぶ.
- If $y$ is a square, then go to step 6
- Write $p^m-1 = k\ 2^e$ with $k$ odd, and $y := y^k$
- $A := g^k,\ z := g^{(k+1)/2}$
- If $A^{2^{e-1}} \ne 1$, then return “no square roots exist”
- If $A = 1$, then go to step 14
- $A^{2^i} = 1$ となる最小の整数を $i$ とする.
- $A := A y^{2^{e-i}},\ z := z y^{2^{e-i-1}}$. Go to step 11
- Return $z$
最適拡大体 (Optimal Extension Field)
- 最適拡大体とは
最適拡大体 (Optimal Extension Field : OEF)は,次の条件を満たす有限体$\mathbb{F}_{p^m}$ である.
- $p$ は,$2^n\pm c,\ \log_2 c \le \lfloor n/2 \rfloor$ なる擬似メルセンヌ素数である.
- $\mathbb{F}_p$ 上の既約多項式 $f(t) = t^m - \omega$ が存在する.
標数 $p$ は,実装するプラットフォームに適した値に選ぶことにより高速化が図れる.例えば,32ビット演算マシンでは,$p$ は $2^{32}$ よりわずかに小さい値に選ばれる.
最適拡大体には,演算を効率化できるタイプIとタイプIIの2つの特別なケースがある.
- タイプI最適拡大体 (タイプI OEF)
タイプI OEFは,$p = 2^n \pm 1$ の最適拡大体である.
タイプI OEFでは,基礎体 $\mathbb{F}_p$ の剰余還元の演算が効率的に行える.
- タイプII最適拡大体 (タイプII OEF)
タイプII OEFは,既約多項式 $f(t) = t^m - 2$ を持つ最適拡大体である.
タイプII OEFでは,拡大体 $\mathbb{F}_{p^m}$ での剰余還元の演算が効率的に行える.
最適拡大体は,タイプIとタイプIIを同時に満たすことができる.
- 部分体の乗算
OEFにおける部分体 $\mathbb{F}_p$ の乗算のアルゴリズム
入力: 素数 $p = 2^n\pm c,\ \log_2 c \le \lfloor n/2 \rfloor$,
$0 \le a, b \lt p$.
出力: 整数 $r \equiv ab \pmod{p}$.
- $x \leftarrow ab$
- $q_0 \leftarrow x \gg n$
- $r_0 \leftarrow x - (q_0 \ll n)$
- $r \leftarrow r_0$
- $i \leftarrow 0$
- While $q_i \gt 0$
- $q_{i+1} \leftarrow q_ic \gg n$
- $r_{i+1} \leftarrow q_ic - (q_{i+1} \ll n)$
- $i \leftarrow i + 1$
- $r \leftarrow r + r_i$
- While $(r \ge p)$
- $r \leftarrow r - p$
このアルゴリズムでは,最初の while ループを最大2回繰り返すため,高々2回の $c$ による乗算が行われる.
- 拡大体の剰余還元
既約多項式を法とする体 $\mathbb{F}_{p^m}$ における拡大体の剰余還元を計算するアルゴリズム.
入力: 次数が $2m-2$ 以下の多項式 $C'(t)$,$f(t) = t^m - \omega$ が $\mathbb{F}_p$ 上の既約多項式となる整数 $\omega$.
出力: 次数が $m$ 未満の多項式 $C(t) \equiv C'(t) \pmod{f(t)}$.
- Let $C(t) = c_{m-1}t^{m-1} + \cdots + c_0$ and $C'(t) =
c_{2m-2}'t^{2m-2} + \cdots + c_0'$
- $c_{m-1} \leftarrow c_{m-1}'$
- For $i$ from $m-2$ downto $0$, $j$ from $2m-2$ downto $m$
- $c_i \leftarrow \omega c_j' + c_i'$
このアルゴリズムは,$\omega$ による最大 ($m-1$) 回の部分体の乗算が必要である. タイプII OEFのように $\omega = 2^i$ であれば,この乗算はビットシフトで行うことができる.
- 拡大体の逆元
体の要素 $β$ の $ββ^{-1} = 1 \in \mathbb{F}_{p^m}$ なる乗法に関する逆元 $β^{-1}$ を計算するアルゴリズム.
入力; 有限体 $\mathbb{F}_{p^m}$ と非 $0$ の体要素 $β$
出力: 逆元 $β^{-1}$
- $r \leftarrow (p^m - 1) / (p - 1)$
- $b \leftarrow β^{r-1}$
- $c \leftarrow bβ$
- $χ \leftarrow c^{-1}$
- $β^{-1} \leftarrow bχ$