GF(2**m) のベクトル表現

久しぶりに Rijndael 暗号で Galois 体 GF(256) をいじったら、 原始多項式の根である原始元と、 既約多項式 (因数分解できない多項式) の根によるベクトル表現がごっちゃになってしまい、 記憶が薄れていたのを実感しました。 用語と意味を簡単に復習します。

Galois 体は有限体です。 体というからには、加算と乗算の 2 種の演算が定義でき、 それぞれに単位元・逆元が存在し、 結合・分配法則がなりたつ演算と集合の組になっています。 有限体なので交換法則もなりたちます。 集合の元の個数が有限の体を Galois 体と呼びます。 集合の元の個数 q を、 Galois 体の位数と呼びます。 位数 q の Galois 体を GF(q) と表記します。 素数 q を位数に選び、ゼロから q - 1 までの q 個の整数の元αとβに対して、 加算 + を (α+β) mod q、 乗算 * に (αβ) mod q とすると GF(q) になります。

2 は素数なので、 GF(2) が存在します。 元は 0 と 1 です。 加算は排他的論理和、 乗算は論理積です。

     + | 0 1     * | 0 1
    --------    --------
     0 | 0 1     0 | 0 0
     1 | 1 0     1 | 0 1

いろいろと証明を飛ばして、 GF(q) が存在するなら、 GF(q**m) も存在します。 後者を前者の拡大体と呼びます。 つまり、 GF(2) が存在するのだから、 GF(4)、 GF(8)、 GF(16) といった Galois 体が存在します。 さらにすっ飛ばして、 GF(2) から GF(4) を求めるには GF(2) で因数分解できない多項式 (既約多項式) を使います。

ここで、 既約多項式を考えます。

x**2 + x + 1

1 以外のこの多項式の根の一つを α としましょう。

α**2 + α + 1 == 0 より

α**0 == 1
α**1 == α
α**2 == α + 1
α**3 == α**2 + α == 1

すると、 α**3 が 1 に戻ります。 この性質があるため、 ゼロ、1、α、α**2 の 4 つの元をもつ位数 4 の体 GF(4) ができます。

        + |     0     1    α α**2           * | 0     1    α α**2
    ------|------------------------       ------|--------------------
        0 |     0     1    α α**2           0 | 0     0     0     0
        1 |     1     0 α**2    α           1 | 0     1    α α**2
       α |    α α**2     0     1          α | 0    α α**2     1
    α**2 | α**2    α     1     0       α**2 | 0 α**2     1    α

この例のように、 ある多項式 F があり、 F == 0 の根 α が、 GF(q) のゼロでない元 α、α**2、α**3、…、α**(q-2) になっており、 さらに α**(q-1) == 1 になるとき、多項式 F を GF(q) の原始多項式と呼びます。 この根 α を GF(q) の原始元と呼びます。 ところで、 既約多項式 F は一つとは限りません。 なので F == 0 の根 v が常に原始元αになるとは限りません。

さて、 GF(2) の GF(2**m) の元は原始元αに対して、ゼロ、1、α、α**2、…、α**(2**m - 2) です。 元を α**i と記す方法を「べき表現」と呼びます。 これまた途中をすっ飛ばすと、 元 α**i を、 F(v) == 0 であることを利用して、 GF(2) の元であるゼロと 1 を係数 a[j] とする v の m - 1 次多項式で表すことができます。 これをビット・ベクトルにしたものを「ベクトル表現」と呼びます。

α**i == a[m-1] * v**(m-1) +…+ a[1] * v + a[0]

GF(4) すなわち GF(2**2) では F(v) == v**2 + v + 1 == 0 かつ α == v

    0 == 0 * α + 0
α**0 == 0 * α + 1
α**1 == 1 * α + 0
α**2 == 1 * α + 1

GF(8) すなわち GF(2**3) では F(v) == v**3 + v + 1 == 0 かつ α == v

    0 == 0 * α**2 + 0 * α + 0
α**0 == 0 * α**2 + 0 * α + 1
α**1 == 0 * α**2 + 1 * α + 0
α**2 == 1 * α**2 + 0 * α + 0
α**3 == 0 * α**2 + 1 * α + 1
α**4 == 1 * α**2 + 1 * α + 0
α**5 == 1 * α**2 + 1 * α + 1
α**6 == 1 * α**2 + 0 * α + 1

ベクトル表現は加算向けで、 GF(2) の和を係数ごとに求めて計算をおこないます。 GF(2) の和はビット演算では排他的論理和なので計算は容易です。

べき表現は乗算向けで、 指数の整数和を求めて 2**m - 1 で割った余りを指数に選ぶと積が求まります。

一方、 ベクトル表現同士の乗算を整数乗算のアナロジーでおこなうことも可能です。 足し算は排他的論理和でおこないます。 そしてビットシフトするのですが、 ここで、 原始多項式にしたがって桁あふれしている分を足すと α をかけた元になります。 GF(8) の場合に確かめてみます。

α**0 * α == 0 * α**2 + 1 * α + 0 == α**1
α**1 * α == 1 * α**2 + 0 * α + 0 == α**2
α**2 * α == 1 * α**3 + 0 * α**2 + 0 * α + 0
           == (1 * α + 1) + 0 * α**2 + 0 * α + 0
           == 0 * α**2 + 1 * α + 1 == α**3
α**3 * α == 1 * α**2 + 1 * α + 0 == α**4
α**4 * α == 1 * α**3 + 1 * α**2 + 0 * α + 0
           == (1 * α + 1) + 1 * α**2 + 0 * α + 0
           == 1 * α**2 + 1 * α + 1 == α**5
α**5 * α == 1 * α**3 + 1 * α**2 + 1 * α + 0
           == (1 * α + 1) + 1 * α**2 + 1 * α + 0
           == 1 * α**2 + 0 * α + 1 == α**6
α**6 * α == 1 * α**3 + 0 * α**2 + 1 * α + 0
           == (1 * α + 1) + 0 * α**2 + 1 * α + 0
           == 0 * α**2 + 0 * α + 1 == α**0

試しに GF(8) の α**3 * α**5 == α**1 をベクトル表現のビットシフトで計算する手順は次のようになります。

w0 = 1 * α**2 + 1 * α + 1 = α**5
z0 = 0 * α**2 + 0 * α + 0
v0 = 0 * α**2 + 1 * α + 1 = α**3

w0[0] == 1
z1 = 0 * α**2 + 1 * α + 1 = z0 + v0
v1 = 1 * α**2 + 1 * α + 0 = v0 * α

w0[1] == 1
z2 = 1 * α**2 + 0 * α + 1 = z1 + v1
v2 = (1 * α + 1) + 1 * α**2 + 0 * α + 0 = v1 * α
   == 1 * α**2 + 1 * α + 1

w0[2] == 1
z3 = 0 * α**2 + 1 * α + 0 = z2 + v2
   => α**1

ところで、 上のわかりやすい例のように、 いつも既約多項式 F が原始多項式であるとは限りません。 言い換えると、 F(v) = 0 の v が原始元になるとは限りません。 そうなるかどうかは、 多項式の選び方に依存します。 例えば、 AES が使っている GF(2**8) の既約多項式 F = x**8 + x**4 + x**3 + x + 1 では、 v ではなく v + 1 が原始元です。 v の多項式を使って原始元をベクトル表示すると 0x03 です。 そのため、 _rijndael.c の乗算で使っている、 べき表示の指数部からベクトル表示を求める exptbl で、 exptbl[1] の値は 0x03 になっています。