ブロック暗号の内部構造（SPN と Feistel）と AES のラウンド関数

ブロック暗号とは何を解く道具か

ブロック暗号は、固定長のビット列（ブロック）を鍵で別の同じ長さのビット列へ写す全単射の置換です。AES のブロック長は 128 ビット固定。鍵 K を一つ決めると、2^128 通りの平文ブロックを 2^128 通りの暗号文ブロックへ一対一で対応づける巨大な置換表が決まる、と考えると本質に近い。

理想は「鍵ごとにランダムな置換表が選ばれる」状態ですが、2^128 要素の表を本当に持つことは不可能です。そこで実際の設計は、単純な変換を何度も重ねて、ランダムな置換と区別がつかない写像を作ります。この「単純な変換」と「重ね方」を規定するのが、本記事で扱うラウンド関数と**全体構造（SPN / Feistel）**です。

設計の二原理：混乱と拡散（Shannon）

安全なブロック暗号の設計指針は、Claude Shannon が1949年に定式化した2つの性質に集約されます。

• 混乱（confusion）：暗号文と鍵の関係を、できるだけ複雑で非線形にする。鍵の1ビットが暗号文に与える影響が、単純な式で書けないようにする。主に**非線形な置換（S-box）**が担う。
• 拡散（diffusion）：平文1ビットの情報を、暗号文の多数のビットへばらまく。平文を1ビット変えたら、暗号文の約半分のビットが反転する（雪崩効果）状態を目指す。主にビット位置の入れ替えと線形混合が担う。

混乱だけでは、局所的な置換に統計的偏りが残れば全体に伝播しません。拡散だけでは線形なので、線形代数で鍵を解かれます。両者を交互に十分回数重ねることで初めて、平文・鍵のあらゆるビットが暗号文全体に複雑に絡む状態に到達します。これがラウンドを反復する根本理由です。

SPN と Feistel：全体構造の二系統

ラウンド関数を組み上げる骨格には、歴史的に二系統あります。

SPN（Substitution-Permutation Network） は、各ラウンドで「鍵加算 → 全ブロックへの置換（Substitution）→ 全ブロックの並べ替え・混合（Permutation）」を施します。ブロック全体を毎ラウンド変換するため拡散が速く、各バイトの処理が独立で並列化・高速化に向く。AES がこの系統です。難点は、置換が全単射（可逆）でなければ復号できず、復号回路は各変換の逆を別途用意する必要がある点です。

Feistel 構造 は、ブロックを左右 L,R の2半分に割り、L' = R、R' = L XOR F(R, K) と更新します。鍵依存の関数 F が可逆である必要がないのが最大の特長で、F を自由に非線形設計できます。さらに暗号化と復号がラウンド鍵の順序を逆にするだけで同一回路になります。DES や Blowfish がこの系統。難点は1ラウンドで半分しか変換されないため、同等の拡散により多くのラウンドを要することです。

GF(2^8)：AES の演算が住む世界

AES のバイト演算は、整数の足し算・掛け算ではなく**有限体 GF(2^8)（ガロア体、2の8乗個の元を持つ体）**の上で定義されます。なぜ「体」かというと、加減乗除がすべて閉じて成立する構造でなければ、S-box の逆元計算や MixColumns の可逆性が保証できないからです。

GF(2^8) の1元は1バイト（8ビット）を、係数が0か1の7次多項式とみなしたものです。

• 加算：対応する係数同士の排他的論理和（XOR）。繰り上がりが無いので a + b は単なる a XOR b。減算も同じ（自分自身が逆元）。
• 乗算：多項式として掛け合わせた後、既約多項式 x^8 + x^4 + x^3 + x + 1（16進で 0x11B）で割った剰余を取る。8ビットに収まるよう「畳み込む」操作です。

GF(2^8) の加算は XOR：
  0x57 + 0x83 = 0x57 XOR 0x83 = 0xD4

GF(2^8) の乗算（×2、xtime）の擬似コード：
  function xtime(b):        # b に多項式 x を掛ける ＝ 1ビット左シフト
    shifted = b << 1
    if (b & 0x80) != 0:     # 最上位ビットが立っていたら8ビットを超える
      shifted = shifted XOR 0x11B   # 既約多項式で畳み込む（剰余を取る）
    return shifted & 0xFF

この体構造のおかげで、各バイトに0以外なら必ず乗法逆元が存在します。S-box の非線形性は、この「逆元を取る」操作を土台にしています。ハッシュや暗号で出てくる有限体の前提知識は 暗号の基礎 と地続きです。

AES の4変換：1ラウンドの中身

AES は 128 ビットを 4x4 バイトの状態（State）として扱います。列優先で並べた16バイトに、毎ラウンド次の4変換を施します。

SubBytes（混乱を担う）

各バイトを S-box で別バイトに置換する、唯一の非線形変換です。S-box は2段で構成されます。(1) そのバイトの GF(2^8) における乗法逆元を取る（0は0のまま）。(2) その結果に GF(2) 上のアフィン変換（固定の線形写像＋定数 0x63 の XOR）を施す。逆元計算が強い非線形性を、アフィン変換が固定点や代数的単純さの排除を担います。実装上は事前計算した256要素の置換表を引くだけです。

SubBytes（バイトごとに独立に適用）:
  for each byte s in State:
    s = AffineTransform( Inverse_GF256(s) )   # 逆元 → アフィン変換
  # 実装は s = SBOX[s] と1回の表引きで済む

ShiftRows（拡散・行方向）

状態の各行を左に巡回シフトします。第0行は0バイト、第1行は1バイト、第2行は2バイト、第3行は3バイト。これにより同じ列に固まっていたバイトが別々の列へ散らばり、次の MixColumns で列をまたいだ拡散が効くようになります。単独では弱いが、MixColumns との組で「行と列の両方向」に情報を広げる役割です。

MixColumns（拡散・列方向）

状態の各列（4バイト）を GF(2^8) 上の固定行列で掛け、1列内の4バイトを相互に混ぜます。乗じる定数は 02 03 01 01 の巡回で、{02},{03} の乗算は前述の xtime で実装できます。1バイトの変化が同じ列の4バイト全体に波及するため、ShiftRows と合わせて「数ラウンドで全128ビットへ完全拡散」を達成する主役です。最終ラウンドだけは MixColumns を省く（復号の対称性を整えるためで、安全性は損なわれません）。

AddRoundKey（鍵の注入）

状態とラウンド鍵（128ビット）を単純に XOR します。GF(2^8) の加算そのものです。これが鍵を暗号文に絡める唯一の箇所で、各ラウンドで異なるラウンド鍵を鍵スケジュールから導いて使います。S-box や MixColumns は鍵に依存しない固定変換なので、鍵の秘密はすべてこの XOR を通じて入ります。

ラウンド全体の流れ

初回に鍵を一度入れてから、ラウンドを反復します。最終ラウンドだけ MixColumns が無いことに注意してください。

AES-128 暗号化（10ラウンド）の骨格:
  AddRoundKey(State, K0)              # 初期ホワイトニング
  for r = 1 .. 9:                    # 通常ラウンド
    SubBytes(State)
    ShiftRows(State)
    MixColumns(State)
    AddRoundKey(State, Kr)
  # 最終ラウンド（MixColumns なし）
  SubBytes(State)
  ShiftRows(State)
  AddRoundKey(State, K10)

最初の AddRoundKey（ホワイトニング）が無いと、初段の SubBytes は鍵に無関係な固定写像になり、攻撃者に既知の入口を与えてしまいます。鍵を「最初・各ラウンド末・最後」に挟むことで、入口も出口も鍵で覆う設計です。

なぜ 10 / 12 / 14 ラウンドなのか

AES のラウンド数は鍵長で決まり、AES-128 は10、AES-192 は12、AES-256 は14です。この数の根拠は2段階で理解できます。

第一に、完全拡散に必要な最小ラウンド数。 ShiftRows と MixColumns の組により、わずか2ラウンドで128ビット全体が相互に依存します（任意の入力1バイトが2ラウンド後には全16バイトへ影響する）。つまり拡散の観点だけなら数ラウンドで足ります。

第二に、安全余裕（セキュリティマージン）の上乗せ。 規定ラウンド数は、完全拡散に必要な数より大幅に多く取られています。設計当時に知られていた差分解読・線形解読は、AES-128 に対しておよそ6〜7ラウンドあれば理論上破れないことが示せました。実際の10ラウンドは、その約1.5〜2倍を確保し、将来発見される攻撃や近似的な解読法に対する余裕を持たせた値です。

鍵長が長いほどラウンドを増やすのは、鍵が長い＝攻撃者が探索すべき空間が広い分、暗号にも相応の「攪拌の深さ」を持たせて鍵スケジュール経由の関連鍵攻撃などへの耐性を揃えるためです。鍵長と安全性の対応そのものは鍵長が長いほど総当たりに強い、という前提と地続きで、公開鍵基盤（PKI）と証明書 で扱う鍵管理の文脈にもつながります。

まとめ：4変換と2構造で一望する

ブロック暗号は、単純な変換を反復してランダムな置換を近似する装置です。その反復の骨格が SPN（全体を毎回変換・並列向き） と Feistel（半分ずつ・暗復号が対称） の二系統で、AES は前者。1ラウンドは SubBytes（混乱）・ShiftRows・MixColumns（拡散）・AddRoundKey（鍵注入） から成り、すべての演算は GF(2^8) という有限体の上で閉じています。混乱と拡散を十分回数重ねる必要があるからこそ、完全拡散に要する数より多い 10/12/14 ラウンドを取り、安全余裕を確保しています。

暗号の全体像は 暗号の基礎、可逆性の観点での対比は ハッシュ化と暗号化の違い、暗号化通信での実運用は TLS / SSL で深掘りできます。