暗号と符号 12 · 暗号の基礎概念と古典暗号

Chapter 12

暗号の基礎概念と古典暗号

第 III 部の始まり. 第 II 部では「壊れても直す」技術を扱った。ここからは「読まれないようにする」技術に移る。

面白いことに、使う数学はほとんど同じである。有限体、合同算術、多項式—— 違うのは目的だけ。誤り訂正は「復元しやすさ」を設計し、暗号は「復元しにくさ」を設計する。

この章ではまず、暗号を語るための共通言語を整える。 「安全とは何か」「何を秘密にするのか」——ここを曖昧にしたまま先に進むと、 「暗号化したから安全」という危険な誤解に陥る。

1. 用語と枠組み

用語意味
平文 (plaintext) \(P\)秘密にしたい元のデータ
暗号文 (ciphertext) \(C\)変換後のデータ
鍵 (key) \(K\)変換を制御する秘密の値
暗号化\(C = E_K(P)\)
復号\(P = D_K(C)\)

ケルクホフスの原理（1883）

暗号方式そのものは公開されていてよい。安全性は鍵の秘密性だけに依存すべきである。

なぜこの原則が正しいのか:

「隠蔽によるセキュリティ (security through obscurity)」は失敗する. 実例は枚挙にいとまがない——携帯電話の A5/1、DVD の CSS、Mifare Classic の Crypto-1。 どれも「仕様を秘密にする」ことに頼っていたが、解析されて一斉に破られた。

逆に AES は仕様が完全公開され、20 年以上の全世界からの攻撃に耐えている。 公開されているからこそ信頼できる、というのが現代暗号の立場である。

2. 暗号の分類

共通鍵暗号（対称暗号）

暗号化と復号に同じ鍵を使う。

\(n\)人が互いに通信するには\(\binom{n}{2} = n(n-1)/2\)個の鍵が必要。 100 人なら 4950 個——管理が破綻する。

公開鍵暗号（非対称暗号）

暗号化と復号に異なる鍵を使う。公開鍵は誰でも入手可、秘密鍵は本人だけ。

\(n\)人でも鍵ペアは\(n\)個で済む。

実務では両方を組み合わせる（ハイブリッド暗号）.

  1. 公開鍵暗号で「共通鍵」を安全に渡す（少量のデータなので遅くても問題ない）
  2. 実際のデータは共通鍵暗号で高速に暗号化

HTTPS（TLS）はまさにこれをやっている。 ハンドシェイクで RSA や楕円曲線を使って鍵を共有し、その後の通信は AES で流す。

3. 攻撃モデル — 「安全」を定義するために

攻撃者が何を持っているかで、要求される強度が変わる。

モデル攻撃者が持てるもの略記
暗号文単独攻撃暗号文のみCOA
既知平文攻撃平文と暗号文のペアKPA
選択平文攻撃好きな平文を暗号化させられるCPA
選択暗号文攻撃好きな暗号文を復号させられるCCA

現代暗号は最も厳しい CCA モデルで安全であることを要求する. 「そんな強い攻撃者は非現実的では?」と思うかもしれないが、実際には起こる。 たとえばサーバが「復号に失敗しました」というエラーを返すだけで、 攻撃者はそれを手がかりに復号オラクルとして使える （パディングオラクル攻撃——実際に TLS や ASP.NET で悪用された）。

「まさかそんな攻撃はされない」という仮定は、必ず裏切られるというのが暗号の教訓である。

安全性の種類

4. 古典暗号とその破り方

シーザー暗号

各文字を\(k\)個ずらす。\(\mathbb{Z}_{26}\)上で:

\[ C = P + k \bmod 26, \qquad P = C - k \bmod 26 \]

攻撃: 鍵は 25 通りしかない。全数探索で即座に破れる（総当たり数秒）。

アフィン暗号

\[ C = aP + b \bmod 26 \]

復号には\(a\)の逆元が必要:

\[ P = a^{-1}(C - b) \bmod 26 \]

\(a\)の条件: 01 章の定理より\(\gcd(a,26)=1\)。 \(26 = 2\times13\)なので、\(a\)は 2 でも 13 でも割れない数——\(\varphi(26)=12\)通り。 鍵空間は\(12 \times 26 = 312\)通り。やはり全数探索で破れる。

01 章で学んだ逆元が、さっそく実用的な意味を持った. \(\gcd(a,26)\neq1\)の\(a\)を選ぶと、異なる平文が同じ暗号文になってしまい復号不能になる。 たとえば\(a=2\)なら\(P=0\)と\(P=13\)がどちらも同じ暗号文になる。 「逆元が存在する」ことは、暗号が復号可能であるための必須条件である。

単一換字式暗号

26 文字を任意に並べ替える。鍵空間は\(26! \approx 4\times10^{26}\)——全数探索は不可能。

しかし簡単に破れる。頻度分析を使う:

ここに古典暗号の根本的な弱点がある. 単一換字は「1 文字を 1 文字に置き換える」だけなので、 平文の統計的な偏りがそのまま暗号文に残る。 鍵空間がどれだけ大きくても、統計が漏れていれば意味がない。

教訓: 鍵空間の大きさは安全性の必要条件であって、十分条件ではない。 現代暗号が「拡散 (diffusion)」——平文 1 ビットの変化を暗号文全体に散らす——を 重視するのは、この統計的漏洩を消すためである（14 章）。

ヴィジュネル暗号

複数のシーザー暗号を鍵の長さで循環させる。長らく「解読不能」と信じられた。

攻撃（カシスキー・テスト、1863）:

  1. 暗号文中に繰り返し現れる文字列を探す
  2. その出現間隔は、鍵長の倍数である可能性が高い
  3. 間隔の GCD から鍵長を推定（01 章の GCD がここで使われる）
  4. 鍵長が分かれば、同じ鍵文字で暗号化された文字を集めてそれぞれ頻度分析

つまり「複数のシーザー暗号」に分解してしまえば、各々は簡単に破れる。

5. ワンタイムパッド — 唯一の完全な暗号

平文と同じ長さのランダムな鍵を用意し、XOR する:

\[ C = P \oplus K, \qquad P = C \oplus K \]

情報理論的安全性の証明（シャノン、1949）

任意の暗号文\(c\)と任意の平文\(p\)について、\(k = p \oplus c\)という鍵が必ず 1 つ存在し、 鍵は一様ランダムなのでその確率は\(2^{-n}\)。したがって

\[ \Pr[P = p \mid C = c] = \frac{\Pr[C=c\mid P=p]\Pr[P=p]}{\Pr[C=c]} = \frac{2^{-n}\Pr[P=p]}{2^{-n}} = \Pr[P=p] \]

暗号文を見ても、平文の確率分布が一切変化しない = 情報が全く漏れていない ∎

完全に安全なのに、ほとんど使われない理由. 3 つの厳しい条件があるため:

  1. 鍵が平文と同じ長さ必要 → 1 GB のファイルには 1 GB の鍵。それを安全に渡せるなら平文を渡せばよい
  2. 鍵は完全にランダム → 擬似乱数では駄目（13 章で見るように、規則性があれば破られる）
  3. 鍵の再利用は絶対禁止 ← これが最も破られやすい

同じ鍵を 2 回使うと即座に破綻する:

$$C_1 \oplus C_2 = (P_1\oplus K)\oplus(P_2\oplus K) = P_1 \oplus P_2$$ 鍵が消えて平文どうしの XOR が現れる。あとは自然言語の統計で分離できる。

実際、ソ連の暗号 VENONA は鍵パッドを再利用したために米国に解読された。 冷戦期のスパイ網が暴かれたのは、この 1 点のミスが原因である。

6. 現代暗号への橋渡し

古典暗号の失敗から得られた設計原則:

教訓現代暗号での対応
鍵空間は十分大きく128 ビット以上（\(2^{128}\)は総当たり不可能）
統計的偏りを残すな拡散 (diffusion): 1 ビットの変化を全体に波及
鍵と平文の関係を隠せ混同 (confusion): 非線形変換（S-box）
鍵を再利用するなIV / ノンスの導入
方式は公開せよ標準化と公開検証

シャノンが 1949 年に定式化した「混同と拡散」が、現代ブロック暗号の設計原理そのものである. AES の 1 ラウンドは、まさに

の組み合わせでできている。14 章で詳しく見る。