ギャロワ体（Galois Field）と AES：数学的構造の解説

有限体の基本概念

• 256 要素の普遍性
  • すべての有限体が同サイズであれば互いに同値であるため、要素数が 256 の体（GF(2^8)） は常に普遍的な性質を共有します。
  • この領域は、20 歳で亡くなったエvariste ガロワによって数学的に開拓されました。
• GF(2^8) の定義
  • 「要素数が $2^8$ 個を持つガロア体」と呼ばれます。
  • 多項式の次数が $n$ 以下で、係数を $p$ を法とした整数から選択したものが対応します（特性 $p$ を持つ体）。
• 数値と多項式への対応
  • 数字は単なる多項式として表されます（例：$0 \to 0, 1 \to 1$）。
  • 係数は $p$ を法とするため、$2 = 1 \times x + 0 = x$ とみなします。
  • これにより、数字の 2 進法表現とガロア体の多項式表現に単純な対応関係が生まれます。

数値との対応表（簡略化後）

数値	2 進表記	GF(2^8) 多項式表現	簡略化後
0	0	0	0
1	1	1	1
2	10	$1x + 0$	x
3	11	$1x + 1$	x + 1
4	100	$1x^2$	x²
5	101	$x^2 + 1$	x² + 1
8	1000	$x^3$	x³
16	10000	$x^4$	x⁴
21	10101	$x^4 + x^2 + 1$	x⁴ + x² + 1

• 実用上の扱い: 実行時に多項式に変換する必要はなく、実際に $x$ を評価する必要もありません。置換テーブルの計算やシフト・XOR 演算で十分機能します。

---

有限体の加算

有限体における加算は、基礎となる多項式の加算によって決定されますが、係数は単一ビット（0 または 1）のみ許されるため、独特な性質を持ちます。

加算の具体例

• 通常の加算: $1 + 2 = 1 + (x) = x + 1 \to$ 2 進法

  11

  $\to$ 3
• 同項数の足し合わせ: $2 + 2 = x + x = 2x \equiv 0x \to$ 0
  • $2x = 0x$ は、係数が単一ビットの性質による「巻き戻し（wraparound）」現象です。

重要な結論：加算と XOR の同一性

• GF(2^8) においては、加算、減算、XOR がすべて同じ演算になります。
  • $a + b = a \oplus b$
• これは単一ビットごとの加算で進位ビットを捨てること（半加算）に相当し、回路設計上決して奇妙な挙動ではありません。

GF(2^4) における加算表の例

以下の表は、4 ビット（16 進数に対応）の有限体での加算を示しています（同値であり XOR 表でもあります）。

	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
0	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
1	1	0	3	2	5	4	7	6	9	8	b	a	d	c	f	e
2	2	3	0	1	6	7	4	5	a	b	8	9	e	f	c	d
3	3	2	1	0	7	6	5	4	b	a	9	8	f	e	d	c
4	4	5	6	7	0	1	2	3	c	d	e	f	8	9	a	b
5	5	4	7	6	1	0	3	2	d	c	f	e	9	8	b	a
6	6	7	4	5	2	3	0	1	e	f	c	d	a	b	8	9
7	7	6	5	4	3	2	1	0	f	e	d	c	b	a	9	8
8	8	9	a	b	c	d	e	f	0	1	2	3	4	5	6	7
9	9	8	b	a	d	c	f	e	1	0	3	2	5	4	7	6
a	a	b	8	9	e	f	c	d	2	3	0	1	6	7	4	5
b	b	a	9	8	f	e	d	c	3	2	1	0	7	6	5	4
c	c	d	e	f	8	9	a	b	4	5	6	7	0	1	2	3
d	d	c	f	e	9	8	b	a	5	4	7	6	1	0	3	2
e	e	f	c	d	a	b	8	9	6	7	4	5	2	3	0	1
f	f	e	d	c	b	a	9	8	7	6	5	4	3	2	1	0

注: スードク（数独）に似ていますが、逆元が存在するためには、各出力が各行および各列にちょうど一回ずつ現れる必要があります。

---

有限体の乗算

有限体における乗算は多項式の乗算と同じ原理ですが、次数 $n$ よりも高い多項式が生じないよう**削減（reduction）**する必要があります。

乗算の具体例と還元プロセス

• 基本的な乗算: $2 \times 2 = x \times x = x^2 \to$ 2 進法

  100

  $\to$ 4
• 次数超過の問題: $16 \times 16 = x^4 \times x^4 = x^8$ は GF(2^8) を超えてしまいます。
• 削減多項式（Reducing Polynomial）の導入:
  • AES では、高次項を削減するために以下の多項式が用いられます： $$x^8 + x^4 + x^3 + x + 1 \quad (\text{16 進数表記：} \mathbf{0x11b})$$
  • 削減には、この多項式の倍数を引き去る（XOR する）操作を行います。

還元計算の例

元の多項式を減算（加算と同じ XOR）することで高次項を消去します：

x^8 - (x^8 + x^4 + x^3 + x + 1) = -(x^4 + x^3 + x + 1)

• 各要素は加法逆元（自身）と等しいため、符号変化は無視されます。
• 最終結果: $x^4 + x^3 + x + 1 \to$ 2 進法

  11011

  $\to$ 10 進数 27

注目すべき点: この還元処理により、偶数同士の積が奇数になることがあります。

削減演算による特性

• 削減多項式の倍数を引き去るだけであり、数学構造そのものを変化させることはありません。
• GF(2^8) を掛けた場合の 256 項ある乗算表（AES スタンダード）は、低位ビットで値が跳ね回る複雑なパターンを示します。

GF(2^4) の乗算表と削減多項式

GF(16) の例では、削減多項式 0x13 ($x^4 + x + 1$) が用いられます。

	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
2	0	2	4	6	8	a	c	e	3	1	7	5	b	9	f	d
3	0	3	6	5	c	f	a	9	b	8	d	e	7	4	1	2
4	0	4	8	c	3	7	b	f	6	2	e	a	5	1	d	9
5	0	5	a	f	7	2	d	8	e	b	4	1	9	c	3	6
6	0	6	c	a	b	d	7	1	5	3	9	f	e	8	2	4
7	0	7	e	9	f	8	1	6	d	a	3	4	2	5	c	b
8	0	8	3	b	6	e	5	d	c	4	f	7	a	2	9	1
9	0	9	1	8	2	b	3	a	4	d	5	c	6	f	7	e
a	0	a	7	d	e	4	9	3	f	5	8	2	1	b	6	c
b	0	b	5	e	a	1	f	4	7	c	2	9	d	6	8	3
c	0	c	b	7	5	9	e	2	a	6	1	d	f	3	4	8
d	0	d	9	4	1	c	8	5	2	f	b	6	3	e	a	7
e	0	e	f	1	d	3	2	c	9	7	6	8	4	a	b	5
f	0	f	d	2	9	6	4	b	1	e	c	3	8	7	5	a

実装例（C++）

以下のコードは、「農夫」的なビットごとの乗算とガロア加算を組み合わせ、最後に削減多項式による還元を行います。

// ビットごとの（「農夫」的）乗算、ガロア加算を使用
for (int bit = 3; bit >= 0; bit--) {
    if (b & (1 << bit))
        c = c ^ (a << bit);
}

// ガロア体へ還元（削減多項式の引き算）
// irr: 削減多項式 (例：0x13)
// high: 高ビットマスク (例：0x10)
int irr = 0x13; 
int high = 0x10; 

for (int bit = 3; bit >= 0; bit--) {
    if (c & (high << bit)) { // もし高次のビットが立っていれば
        c = c ^ (irr << bit); // ガロア「減算」で引き去る
    }
}

補足: GF(2^8) の乗算表は省略しますが、順方向の乗算は短いアルゴリズムで実行できます。しかし、非線形性が高いため除算は困難です。一般には逆元のテーブルを事前に作成して利用します。対数・逆対数の表も有効な手法です。

---

AES の演算

AES は、バイトからなる $4 \times 4$ のグリッドに対して以下の 4 つの演算を適用します。

1. S ボックス（置換ボックス）
   • グリッド内の各バイトに対し、乗法逆元の計算とアフィン変換を行うことで置換します。
   • アフィン変換は、0/1 を掛ける加算と乗算の組み合わせです。
   • 「0 の問題」（慣例として $1/0 = 0$ と定義）を修正し、乗法逆元の連鎖を数学的に不可能にするように設計されています。
2. ShiftRows（行シフト）
   • グリッド内の各バイトを水平方向にシフトします。
   • 第 $i$ 行は $i$ バイト分円形にシフトされます。
3. MixColumns（列混合）
   • 各列に対して有限体における乗算と加算の行列演算を行います。
   • 用いられる行列は非特異であり、逆演算が存在します。
   • 「入力バイトが一つだけ変化すれば出力も必ず変化する」ように設計されており、拡散性を高めます。
4. AddRoundKey（ラウンド鍵の加算）
   • 最後に、各バイトにラウンド鍵を加算します（GF(2^8) ではこれは XOR と同じ演算です）。

---

なぜ手間をかけるのか？（有限体の利点）

有限体上で作業することには、以下の大きな利点があります。

• 数字は小さく保たれる
  • GF(2^8) 内の要素は常に 1 バイト です。乗算や除算を行ってもサイズが増えません。
• 各演算に対して逆元が存在する
  • 復号化が可能になります。通常の $2^n$ を法とする単純な mod 演算（掛けると高次ビットが失われる）よりも優れています。
• 数学的理論が確立されている
  • 歴史は 1830 年代まで遡ります。優れた混合関数を選出しやすく、新しい解析技法に対するリスクを低減できます。
• 十分な演算があり、豊かに組み合わせられる
  • AES は「除算」「転置」「行列演算」などの多様な非可換・非線形な操作を組み合わせることで強固さを得ています。
  • 加算のみではシフト暗号、乗算のみでは線形暗号にしかなりませんが、有限体による多様な演算はこれを防ぎます。

参考資料: FIPS 197（AES 標準仕様）や Rijndael（AES）の原論文には、これらの設計意図に関する詳細な説明と例が含まれています。