初めに
AES本体, AES-GCM, XTS-AESやいくつかの暗号技術で利用される標数2の体の解説や実装方法の紹介をします。今回はまず概念の説明です。
標数2の素体の演算
体というのは通常の数と同じような四則演算ができる集合です。有限個の集合からなる体は有限体といいます。素体とは p を素数としたとき0以上 p-1 以下の整数の集合 𝔽_p=\{0,1,\dots,p-1\} のことです。GF(p) や ℤ_p と書くこともあります（後者は数学で別の意味に使われることが多いので注意）。
𝔽_p の加算、減算、乗算は普通に計算した後 p で割った0以上 p-1 以下の余りを結果とします。割り算（逆数）は乗算と整合性が取れるように定めると有限体となります。
p が256ビット程度の大きな素数のときの話は有限体の実装1（加算）をご覧ください。
標数2の素体というのは p=2 のとき、すなわち0と1しかない体 𝔽_2=\{0,1\} のことです。要素が2個しかないので演算も簡単です。
加算
足し算 x+y の表
x と y がそれぞれ0, 1の2通りなので全部で4パターンです。0+0=0, 0+1=1+0=1, 1+1=2=0（2で割った余りなので）です。
これはビット演算の排他的論理和と同じです。すなわち 𝔽_2 の加算は
typedef bool F2;
F2 add(F2 x, F2 y) { return x ^ y; }
と実装できます。
減算
引き算はどうなるでしょうか。x \in 𝔽_2 に対して x + x = 2x は（x が0であっても1であっても）偶数です。だから2で割った余りは0。
つまり
この両辺から
x を引くと
これは
𝔽_2 の世界でマイナスはプラスと同じということを意味し、引き算は足し算と同じになります。
引き算 x-y の表
だから実装もaddと同じです。
F2 sub(F2 x, F2 y) { return x ^ y; }
乗算
掛け算 xy の表
1×1 = 1以外は全て0になります。これはビット演算の論理積と同じです。こちらは
F2 mul(F2 x, F2 y) { return x & y; }
と実装できます。
除算
0以外の要素 x の逆元（逆数） r は rx \equiv 1 \pmod{p} となる r として定義し、1/x=r と書きます。素体ではどの x (\neq 0) に対しても逆元が存在することが知られています。
除算 x/y は x\times (1/y) として定義します。
𝔽_2 の場合、0以外の要素は1しかなく、1 \times 1=1 なので1の逆元は1です。1/1=1. 除算は0/1=0, 1/1=1.
割り算 x/y の表
y が1のとき x/y=x なので強いて実装すれば
F2 div(F2 x, F2 y)
{
assert(y != 0);
return x;
}
です。
複素数
次に拡大体の話をします。が、𝔽_2 の拡大体の話の前に複素数の話をします。回り道をすっとばして𝔽_2の2次拡大体に飛んでも構いません。
複素数の集合（複素数体）ℂとは実数体ℝに虚数単位 i を追加したものでした。i は2乗して-1になる数です。ℂの要素は実数 a, b を使って z=a+bi と書きました。
複素数
z=a+bi,
w=c+di の加減算は実数同士の加減算です。
z\pm w = (a\pm c) + (b\pm d)i.
乗算は
i を記号として扱って
i^2 が現れたら-1に置き換えます。
zw = (a+bi)(c+di)=(ac+bdi^2)+(ad+bc)i=(ac-bd)+(ad+bc)i.
「虚数単位 i を追加する」という考えを多項式の割り算の余りとして表現する方法を紹介します。𝔽_2 の拡大体はこちらの考えを利用します。
X に関する実数係数多項式の集合を ℝ[X] と書き、それを X^2+1 で割った余り（2次式で割るので余りは1次式）の集合 K を定義します。
K=ℝ[X]/(X^2+1)=\{a+bX|a,b\in ℝ\}.
そうすると
z=a+bX,
w=c+dX \in K について
z\pm w = (a\pm c) + (b\pm d)X.
乗算は
zw = (a+bX)(c+dX)=bdX^2+(ad+bc)X+ac.
ここで
X^2+1 割るために式を変形すると
zw=bd(X^2+1)-bd+(ad+bc)X+ac \equiv (ac-bd)+(ad+bc)X \pmod {X^2+1}.
これは
X \rightarrow i と見なすと虚数単位を導入した場合と同じ関係式です。加減乗算（除算もできる）ができて
K は体となります。
実数体に2次式
X^2+1 を使って作った体なので2次拡大体といいます。複素数体は実数体の2次拡大体なのです。
𝔽_2 の2次拡大体
前述と同様の考えを使って 𝔽_2 を構成します。𝔽_2 係数の多項式全体 𝔽_2[X] を X^2+1 で割った余りを考えたいところですが、残念ながらうまくいきません。
なぜなら X^2+1 は 𝔽_2[X] の中で因数分解できてしまうからです。
※
𝔽_2 の中では2倍したものは0と同じなことに注意。
これは
f=X+1 という0でない要素同士を掛けると0になる（
X^2+1 を
X^2+1 で割った余りは0）ことを意味します。
もし
f の逆元
g が存在して
fg = 1 となったとします。両辺に
f を掛けると
となり
f=0 となって矛盾します。つまり
f の逆元は存在しません。だから
𝔽_2[X]/(X^2+1) は体になりません。
そこで、少しひねって X^2+X+1 で割った余りを考えるとうまくいくことが知られています。X^2+X+1 は 𝔽_2[X] の中で因数分解できないのです。
加減算の定義はそのままです。
𝔽_2[X] の中で X^2+X+1 で割った余りを考えるなら X^2=X+1 が成り立つことに注意すると、乗算は
zw = (a+bX)(c+dX)=bdX^2+(ad+bc)X+ac=bd(X+1)+(ad+bc)X+ac=(ac+bd)+(ad+bd+bc)X.
このようにして作った2次拡大体を 𝔽_{2^2} と書きます。
2^2=4 だから 𝔽_{2^2}=𝔽_4 で4で割った余り \{0,1,2,3\} と思わないでください。前述のように余りの1次式で係数が0か1しか無いので
𝔽_{2^2} = \{0,1,X,1+X\} です。
掛け算 xy の表
|
y＼x
|
0 |
1 |
X |
1+X |
| 0 |
0 |
0 |
0 |
0 |
| 1 |
0 |
1 |
X |
1+X |
| X |
0 |
X |
1+X |
1 |
| 1+X |
0 |
1+X |
1 |
X |
ところでこんな面倒なことをせずに乗算も加減算と同じく要素ごとに掛け算すればいいじゃないかと思われるかもしれません。
(a+bX)(c+dX) := (ac)+bdX.
しかし、これもうまくいかないのです。なぜならともに0でない
0+X と
1+0X をこのルールで掛けると
0+0X=0 となってしまうからです。
先程と同じ理由により、0でないもの同士を掛けて0になったら、逆元が存在しません。
𝔽_2 の8次拡大体と128次拡大体
前節では2次式を使って2次拡大体を作りました。8次の多項式を使うと8次拡大体ができます。
AESなどで使われる拡大体は f(X)=X^8+X^4+X^3+X+1 を使うと決められています。
𝔽_{2^8}=𝔽_2[X]/(X^8+X^4+X^3+X+1).
ディスク暗号化で使われるXTS-AESや認証付き暗号AES-GCMのghashで使われる体は128次拡大体です（暗認本参照）。
こちらは f(X)=X^{128}+X^7+X^2+X+1 という多項式を使います。
𝔽_{2^{128}}=𝔽_2[X]/(X^{128}+X^7+X^2+X+1).
これらはそれぞれ多項式の乗算の後、X^8→X^4+X^3+X+1, X^{128}→X^7+X^2+X+1という置き換えを繰り返すことで余りを計算できます。𝔽_2 と同じく、どの要素も2倍すると0になり、標数2の体と呼ばれます。
まとめ
有限体 𝔽_2 とは0と1だけの集合で、排他的論理和を足し算、論理積を掛け算として定義した体です。
AESなどで使われる 𝔽_{2^8} は 𝔽_2 係数の多項式の集合を、ある8次多項式で割った余りの集合に四則演算を定義したもので8次拡大体と呼ばれます。
8次の代わりに128次の多項式を使うと128次拡大体 𝔽_{2^{128}} ができます。これらの体では2倍すると0、マイナスはプラスと同じになります。
次回は実装の話を紹介します。
Discussion