Chapter 14

ブロック暗号と AES — GF(2^8) が実装に現れる

第 I 部で作った\(\mathrm{GF}(2^8)\)が、ここで暗号の中身そのものになる. 05 章で「1 バイトを 1 個の数として四則演算する世界」を構成した。 AES はその世界の上で、逆元を取り、行列を掛け、多項式を掛ける—— つまり代数の操作をそのまま暗号の攪拌に使っている。
なぜ代数を使うのか。でたらめに混ぜるのではなく、数学的な裏付けのある混ぜ方をすることで、「差分解読法や線形解読法に対して、これだけの強度がある」と証明できるからである。

1. ブロック暗号の枠組み

固定長のブロック（AES は 128 ビット = 16 バイト）単位で暗号化する。

\[ C = E_K(P), \qquad P = D_K(C), \qquad |P| = |C| = 128\ \text{bit} \]

鍵\(K\)を固定すると、\(E_K\)は\(2^{128}\)個の平文から\(2^{128}\)個の暗号文への全単射（置換）である。

設計原理: 混同と拡散（12 章の再掲）

混同 (confusion): 鍵と暗号文の関係を複雑にする → 非線形な変換が必要
拡散 (diffusion): 平文 1 ビットの変化を暗号文全体に波及させる → 線形な混ぜ合わせ

この 2 つを何ラウンドも繰り返すのが現代ブロック暗号の基本構造である。

2 つの主要構造

Feistel 構造（DES など）: ブロックを左右に分け、片方に関数を適用して他方に XOR、左右を入れ替える。

長所: 関数\(F\)が可逆でなくてよい（復号は同じ構造を逆順に回すだけ）

SPN 構造 (Substitution-Permutation Network, AES など): 全体に置換と拡散を交互にかける。

長所: 並列性が高く高速。拡散が速い

2. AES の全体構造

2001 年に NIST が標準化（原案は Rijndael、ベルギーの Daemen と Rijmen による）。

鍵長	ラウンド数
AES-128	10
AES-192	12
AES-256	14

状態 (State)

128 ビットを\(4\times4\)のバイト行列として扱う（列優先で詰める）:

\[ \text{State} = \begin{bmatrix} b_0 & b_4 & b_8 & b_{12}\\ b_1 & b_5 & b_9 & b_{13}\\ b_2 & b_6 & b_{10} & b_{14}\\ b_3 & b_7 & b_{11} & b_{15} \end{bmatrix} \]

各ラウンドの処理

SubBytes — 各バイトを S-box で置換（混同）
ShiftRows — 行ごとに左巡回シフト（拡散）
MixColumns — 各列に行列を掛ける（拡散）
AddRoundKey — ラウンド鍵を XOR（鍵の導入）

（最終ラウンドのみ MixColumns を省略。理由は §7 で述べる。）

3. SubBytes — GF(2^8) の逆元

定義

各バイト\(a\)を次の 2 段階で変換する:

段階 1: \(\mathrm{GF}(2^8)\)（既約多項式\(x^8+x^4+x^3+x+1\) = 0x11B）での乗法逆元を取る:

\[ b = a^{-1} \quad (a \neq 0), \qquad b = 0 \quad (a = 0) \]

（05 章の定理より\(a^{-1} = a^{254}\)。）

段階 2: ビット単位のアフィン変換を施す:

\[ c_i = b_i \oplus b_{(i+4)\bmod 8} \oplus b_{(i+5)\bmod 8} \oplus b_{(i+6)\bmod 8} \oplus b_{(i+7)\bmod 8} \oplus d_i \]

（\(d = \texttt{0x63}\)の第\(i\)ビット。）

なぜ逆元なのか

逆元写像\(a \mapsto a^{-1}\)は、非線形性が理論上ほぼ最良である.
ブロック暗号の 2 大攻撃法に対する耐性が、この写像では数値的に保証されている:
差分解読法への耐性: 差分確率の最大値が\(4/256 = 2^{-6}\)（理論最小に近い）
線形解読法への耐性: 線形バイアスの最大値が\(2^{-3}\)
「なんとなく複雑そうな表」を使うのではなく、代数的に最適な写像を選び、その強度を証明する——ここが AES 設計の思想である。
ではなぜ段階 2 のアフィン変換を足すのか. 逆元写像だけだと\(\mathrm{GF}(2^8)\)上の代数構造が綺麗すぎて、 代数的攻撃（連立方程式として解く攻撃）の足がかりを与えてしまう。また\(0 \mapsto 0\)、\(1\mapsto 1\)という不動点があるのも望ましくない。アフィン変換はこの構造を「濁らせる」ために加えられている。

実装

実際には毎回逆元を計算せず、256 バイトの表を引く（S-box）。例: \(\texttt{0x53} \to \texttt{0xED}\)

（ただしキャッシュタイミング攻撃を避けるため、最近の実装は AES-NI 命令やビットスライスを使い、テーブル参照を避ける傾向にある。）

4. ShiftRows — 列をまたいで混ぜる

第\(i\)行を左に\(i\)バイト巡回シフト:

\[ \begin{bmatrix} b_0 & b_4 & b_8 & b_{12}\\ b_1 & b_5 & b_9 & b_{13}\\ b_2 & b_6 & b_{10} & b_{14}\\ b_3 & b_7 & b_{11} & b_{15} \end{bmatrix} \longrightarrow \begin{bmatrix} b_0 & b_4 & b_8 & b_{12}\\ b_5 & b_9 & b_{13} & b_1\\ b_{10} & b_{14} & b_2 & b_6\\ b_{15} & b_3 & b_7 & b_{11} \end{bmatrix} \]

なぜ必要か. MixColumns は列の中だけを混ぜる。 ShiftRows が無いと、4 つの列が永久に独立したまま混ざらず、 128 ビットではなく 32 ビットの暗号が 4 個並んでいるのと同じになってしまう。 ShiftRows が列をまたいでバイトを動かすことで、次のラウンドの MixColumns が全体を混ぜられる。

5. MixColumns — GF(2^8) 上の行列積

各列（4 バイト）を\(\mathrm{GF}(2^8)\)上のベクトルとみなし、固定行列を掛ける:

\[ \begin{bmatrix}c_0\\c_1\\c_2\\c_3\end{bmatrix} = \begin{bmatrix} \texttt{02} & \texttt{03} & \texttt{01} & \texttt{01}\\ \texttt{01} & \texttt{02} & \texttt{03} & \texttt{01}\\ \texttt{01} & \texttt{01} & \texttt{02} & \texttt{03}\\ \texttt{03} & \texttt{01} & \texttt{01} & \texttt{02} \end{bmatrix} \begin{bmatrix}b_0\\b_1\\b_2\\b_3\end{bmatrix} \]

すべての演算は\(\mathrm{GF}(2^8)\)上——加算は XOR、乗算は 05 章の xtime 法。

計算例

\(c_0 = \texttt{02}\cdot b_0 \oplus \texttt{03}\cdot b_1 \oplus b_2 \oplus b_3\)

\(\texttt{02}\)倍は xtime（左シフト + 必要なら 0x1B を XOR）、 \(\texttt{03}\)倍は\(\texttt{02}\cdot b \oplus b\)。

この行列の設計意図

この行列は MDS 行列である——11 章で出てきた MDS（最大距離分離）と同じ概念。
意味するところは: 入力 4 バイトのうち 1 バイトでも変えれば、出力 4 バイトすべてが変わる。より正確には「入力と出力の変化バイト数の合計が必ず 5 以上」。
この性質のおかげで、AES は 4 ラウンドで完全拡散する（1 バイトの変化が全 16 バイトに波及）。10 ラウンドはその 2 倍以上の余裕を持たせた設計である。
誤り訂正符号の理論（MDS）が、そのまま暗号の拡散設計に使われている—— 第 II 部と第 III 部が同じ数学でつながっている好例である。

6. 鍵スケジュール

128 ビットの鍵から、各ラウンド用の 128 ビット鍵を生成する。

\(W_i\)を 4 バイト（1 語）として、\(W_0..W_3\)が元の鍵。\(i \geq 4\)について:

\[ W_i = \begin{cases} W_{i-4} \oplus \left[\mathrm{SubWord}(\mathrm{RotWord}(W_{i-1})) \oplus \mathrm{Rcon}_{i/4}\right] & (i \equiv 0 \bmod 4)\\ W_{i-4} \oplus W_{i-1} & (\text{otherwise}) \end{cases} \]

RotWord: 4 バイトを 1 バイト左巡回
SubWord: 各バイトに S-box
Rcon: ラウンド定数\((\texttt{02}^{i-1}, 0,0,0)\)——\(\mathrm{GF}(2^8)\)上のべき乗

Rcon がラウンドごとに違う値なのは、対称性を壊すため. もし全ラウンドで同じ処理をすると、スライド攻撃（ラウンドをずらして対応付ける攻撃）が成立してしまう。ラウンド定数はその対称性を意図的に破っている。

7. 復号と、最終ラウンドの謎

復号は各操作の逆を逆順に適用する（InvSubBytes, InvShiftRows, InvMixColumns）。

なぜ最終ラウンドだけ MixColumns が無いのか. これは強度の問題ではなく実装の都合である。 MixColumns を省くと、暗号化と復号の処理構造が対称になり、同じハードウェア/コードを流用しやすくなる。最終ラウンドの MixColumns は、その後に AddRoundKey しか無いため、 攻撃者が自分で逆算できてしまい安全性に寄与しない——だから省いても損失がない。

8. 利用モード — ここを間違えると全部台無し

ブロック暗号は 16 バイトしか暗号化できない。長いデータにはモードが必要。

モード	特徴	評価
ECB	各ブロックを独立に暗号化	使用禁止
CBC	前の暗号文と XOR してから暗号化	パディングオラクルに注意
CTR	カウンタを暗号化して鍵ストリームに	並列可、ストリーム暗号化
GCM	CTR + 認証タグ	推奨（認証付き暗号）

ECB が禁止される理由——「ペンギン画像」の教訓. ECB は同じ平文ブロックが必ず同じ暗号文ブロックになる。つまり平文のパターンがそのまま暗号文に残る。 Linux のマスコット画像を ECB で暗号化すると、色は変わるのにペンギンの形がはっきり見えるという有名な例がある。12 章の「単一換字暗号が統計で破れる」のと全く同じ失敗である。
さらに重要: 暗号化だけでは改ざんを防げない. CTR モードでは、攻撃者が暗号文の 1 ビットを反転させると、復号後の平文の同じビットが反転する。内容は分からなくても狙った場所を書き換えられる。だから現代では認証付き暗号 (AEAD)——AES-GCM や ChaCha20-Poly1305——を使うのが必須である。（09 章で「CRC は改ざん検知に使えない」と述べたのと同じ話。認証には MAC が要る。18 章。）

9. まとめ

要素	数学的正体	役割
SubBytes	\(\mathrm{GF}(2^8)\)の逆元 + アフィン変換	混同（非線形）
ShiftRows	バイトの巡回シフト	拡散（列をまたぐ）
MixColumns	\(\mathrm{GF}(2^8)\)上の MDS 行列積	拡散（列の中）
AddRoundKey	XOR	鍵の導入
鍵スケジュール	S-box + \(\mathrm{GF}(2^8)\)のべき乗	ラウンド鍵生成

AES の安全性は\(\mathrm{GF}(2^8)\)の代数構造に支えられている—— 05 章で作った体が、そのまま世界標準暗号の心臓部になっている。