暗号の数学

標数 3 の体

体の表現

標数3の有限体 \(\mathbb{F}_{3^m}\) は，\(F_3[x]\) を各係数が標数3の基礎体 \(\mathbb{F}_3\) から構成される任意の多項式，\(f (x)\) を \(m\) 次の既約多項式として，

\[ \mathbb{F}_{3^m} = F_3[x]/f(x) \]

で表される．

既約多項式は，多くの次数で3項式により表され，計算量の削減の観点から実用上3項式を用いることが多い．3項式を，

\[f(x) = x^m+ax^k+b\qquad (a,b \in(1,2), 0 \lt k \lt m)\]

で表す．

標数3の基礎体 \(\mathbb{F}_3 = \{0, 1, 2\}\) の元 \(a\) は，\(a = (a_h, a_l)\) の2ビットで表すことができる．ここで，\(a_h，a_l\) はそれぞれ2桁の2進数の上位ビットと下位ビットであり，(\(a_h, a_l\)) の取りうる値は，\((0,0)\)，\((0,1)\)，\((1,0)\) のいずれかである．

有限体 \(\mathbb{F}_{3^m}\) の元を \(A(x)\) とするとき，\(A(x)\) の多項式表現は，

\[ A(x) = a_{m-1} \cdot x^{m-1} + a_{m-2} \cdot x^{m-2} + \cdots + a_0 \]

となる．この元の各係数 \(a_i (i = 0, 1, \ldots , m-1)\) は基礎体 \(\mathbb{F}_3\) の元であり，各係数は基礎体のビット表現を用いて，\(a_i = (a_{ih}, a_{il})\) と表すことができる．また，各次数の上位ビットと下位ビットをまとめることにより，次の2つのビット列で表現することができる．

\[ A_h = ( a_{(m-1)h}, a_{(m-2)h}, \ldots a_{0h} ) \] \[ A_l = ( a_{(m-1)l}, a_{(m-2)l}, \ldots a_{0l} ) \]

これを用いると，\(\mathbb{F}_{3^m}\) の元 \(A(x)\) は

\[ A(x) = (A_h, A_l) \]

で表される．

体 \(\mathbb{F}_{3^m}\) 上の演算

体 \(\mathbb{F}_{3^m}\) 上の基本演算を定義する．

加算，減算
有限体 \(\mathbb{F}_{3^m}\) の元 \(A(x)\)，\(B(x)\) の加算結果 \(C(x)\) は，対応する各係数の和より \[ C(x) = (a_{m-1}+b_{m-1})x^{m-1} + (a_{m-2}+b_{m-2})x^{m-2} + \cdots + (a_0+b_0) \] で定義される．

ビット表現を用いた加算，減算の計算アルゴリズムは次のようになる．
加算
入力： \(A(x) = (A_h, A_l), B(x) = (B_h, B_l) \in \mathbb{F}_{3^m}\)
出力： \(C(x) = (C_h, C_l) = A(x) + B(x) \in \mathbb{F}_{3^m} \)
1. \(z = (A_h\ |\ A_l)\ \& \ (B_h\ |\ B_l)\)
2. \(C_l = z \wedge (A_l\ |\ B_l)\)
3. \(C_h = z \wedge (A_h\ |\ B_h\)
ここで，\(|\) は OR，\(\&\) は AND，\(\wedge\) は XOR を表す論理演算である．

減算
標数3の有限体の演算では，\(-B(x) = 2B(x)\) が成立つ．そのため，減算 \(A(x) - B(x)\) は，加算 \(A(x) + 2B(x)\) で置き換えることができる．
ここで，各係数の表現は \(1 = (0, 1)，2 = (1, 0)\) であるため，\(B(x)\) を \(2B(x)\) に変換するには，各係数のビットを反転させれば良い．したがって，減算は加算のアルゴリズムにおいて， \(B_l\) と \(B_h\) を入れ替えれば良い．
入力： \(A(x) = (A_h, A_l), B(x) = (B_h, B_l) \in \mathbb{F}_{3^m}\)
出力： \(C(x) = (C_h, C_l) = A(x) - B(x) \in \mathbb{F}_{3^m} \)
1. \(z = (A_h\ |\ A_l)\ \& \ (B_l\ |\ B_h) \)
2. \(C_l = z \wedge (A_l\ |\ B_h) \)
3. \(C_h = z \wedge (A_h\ |\ B_l) \)
乗算
有限体 \(\mathbb{F}_{3^m}\) における乗算 \(C(x) = A(x)\cdot B(x) \bmod f(x)\) は，多項式乗算と還元の2ステップにより求められる．

多項式乗算
多項式の乗算 \(C(x) = A(x)\cdot B(x)\) は， \[ C(x) = (a_{m-1}b_{m-1})x^{2m-2} + (a_{m-1}b_{m-2}+a_{m-2}b_{m-1})x^{2m-3} + \cdots + a_0b_0 \] である．
入力： \(A(x), B(x) \in \mathbb{F}_{3^m}\)
出力： \(C(x) = A(x)\cdot B(x)\)
1. \(C(x) ← 0 \)
2. For \(i = 0\) to \(m-1\) do
3. 　\(C(x) ← C(x) + A(x) \cdot b_i x_i\)
還元
有限体 \(\mathbb{F}_{3^m}\) における乗算やべき乗算において，多項式の次数が \(m-1\) を超える場合，既約多項式 \(f(x)\) による剰余を求め次数を \(m-1\) 以下にする必要がある．この演算を還元(Reduction)と呼ぶ．
入力：\(C(x) = c_nx^n + \cdots + c_0\ (n \gt m-1), f(x)=x^m+ax^k+b\ (a,b \in(1,2),\ 0 \lt k \lt m)\)
出力：\(C'(x) = C(x) \bmod f(x)\)
1. For \(i = n\) downto \(m\) do
2. 　\(c'_{i-m+k} ← c_{i-m+k} - a c_i\)
3. 　\(c'_{i-m} ← c_{i-m} - b c_i\)
4. 　\(c'_i ← 0\)
5. Return \(C'(x)\)
逆元
逆元は，拡張ユークリッド互助法により求められる．
入力： \(A(x) \in \mathbb{F}_{3^m}, f(x)\)
出力： \(A(x)^{-1} \bmod f(x)\)
1. \(u ← A(x),\ v ← f(x)\)
2. \(g_1 ← 1,\ g_2 ← 0\)
3. While \(\mathrm{deg}(u) \ne 0\) do
4. 　\(j ← \mathrm{deg}(u) - \mathrm{deg}(v)\)
5. 　If \(j \lt 0\) then
6. 　　\(u ← v,\ g_1 ← g_2,\ j ← -j\)
7. 　\(u ← u - (u_{\mathrm{deg}(u)} \cdot v_{\mathrm{deg}(v)})v \cdot x^j\)
8. 　\(g_1 ← g_1 - (u_{\mathrm{deg}(u)}\cdot v_{\mathrm{deg}(v)})g_2 \cdot x^j\)
9. Return \(u_0\cdot g_1\)
ここで，\(\mathrm{deg}(f)\) は多項式 \(f\) の最大次数を求める関数である．
べき乗
入力： \(A(x) \in \mathbb{F}_{3^m},\ d=\sum_{i=0}^{l-1}d_i3^i\)
出力： \(A(x)^d\)
1. If \(l-1 = 0\) then return \(A(x)^{d_0}\)
2. \(B(x) ← A(x)^{d_{i-1}},\ T(x) ← A(x)^2\)
3. For \(i=l-2\) downto \(0\) do
4. 　\(B(x) ← B(x)^3\)
5. 　If \(d_i = 1\) then
6. 　　\(B(x) ← B(x)\cdot A(x)\)
7. 　else if \(d_i = 2\) then
8. 　　\(B(x) ← B(x)\cdot T(x)\)
9. Return \(B(x)\)
3乗算
有限体 \(\mathbb{F}_{3^m}\) の元 \(A(x)\) の3乗算は， \[ A(x)^3 = (a_{m-1}x^{m-1} + \cdots + a_1x + a_0)^3 = a_{m-1}x^{3(m-1)} + \cdots + a_1x^3 + a_0 \] を求め，これを既約多項式 \(f(x)\) で還元することで求められる．
ここで，\(3(m-1)\) 次の多項式は，各係数 \(a_i\) に対する置き換えのみで求められる．
平方根
有限体 \(\mathbb{F}_{3^m}\) 元 \(A(x) (\ne 0)\) に対する平方根は，\(q = 3^m\) とすると \[ \sqrt{A(x)} = A(x)^{\frac{q+1}{4}} \] で求められる．
これは，次のように証明される．
\(A(x) = a,\ \sqrt{A(x)} = b\) とすると， \[ b^2 = (a^{\frac{q+1}{4}})^2 = a^{\frac{q+1}{2}} = a^{\frac{q-1}{2}} a \] となる．ここで，\(a^{q-1}\) は Fermat の小定理より\(1\)であり， \[ b^2 = a^{\frac{q-1}{2}} a = a\] が成立つ．
3乗根
有限体 \(\mathbb{F}_{3^m}\) の元 \(A(x)\) に対する 3乗根は，Fermat の小定理より \[ \sqrt[3]{A(x)} = A(x)^{3^{m-1}} \] で求められる．
この 3乗根の計算には，次のような効率的な方法がある (Barreto)． \[ A(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_{m-1} x^{m-1},\ m = 3u,\ a_m, a_{m+1} = 0 \] とし，上式を次のように変換する． \begin{eqnarray*} 　A(x) &=& \sum_{i=0}^{m-1} a_i x^i \\ &=& \sum_{i=0}^{u} a_{3i} x^{3i} + x \cdot \sum_{i=0}^{u} a_{3i+1}x^{3i} + x^2 \cdot \sum_{i=0}^{u}a_{3i+2}x^{3i} \end{eqnarray*} \[ \sqrt[3]{A(x)} = A(x)^{3^{m-1}} = \sum_{i=0}^{u} a_{3i} x^{i} + x^{1/3} \cdot \sum_{i=0}^{u} a_{3i+1}x^{i} + x^{2/3} \cdot \sum_{i=0}^{u}a_{3i+2}x^{i} \] ここで，\(c_0 = \sum_{i=0}^{u}a_{3i}x^i\)，\(c_1 = \sum_{i=0}^{u}a_{3i+1}x^i\)， \(c_2 = \sum_{i=0}^{u}a_{3i+2}x^i\)とすると， \[ \sqrt[3]{A(x)} = c_0 + c_1 x^{1/3} + c_2 x^{2/3} \] と書くことができる．\(x^{1/3}\)，\(x^{2/3}\)は次数\(m\)により決定されるため，事前計算により求めておくことができる． \(c_0\)，\(c_1\)，\(c_2\)の計算量は無視できるため，3乗根の計算はほぼ乗算2回の計算量になる．

Page Top