Chapter 12
暗号の基礎概念と古典暗号
第 III 部の始まり. 第 II 部では、壊れたデータを直す技術を扱った。ここからは、データを第三者に読まれないようにする暗号を扱う。 使う数学は、有限体、合同算術、多項式とほとんど同じである。違うのは目的で、誤り訂正は「元に戻しやすさ」を、暗号は「鍵を知らない者には戻しにくいこと」を設計する。
この章ではまず、暗号を論じるための言葉を整える。「安全とは何か」「何を秘密にするのか」を曖昧にしたまま進むと、「暗号化したから安全」という誤解に陥る。
この章で使う既出の用語（定義は各リンク先）. \(a \bmod m\)と\(\mathbb{Z}_m\)（01 章 1 節）、\(\gcd\)（01 章 3 節）、逆元と法 26 での 7 の逆元（01 章 5 節）、 XOR \(\oplus\)（04 章 1 節）、二項係数\(\binom{n}{2}\)（06 章 4 節）
1. 用語と枠組み
| 用語 | 記号 | 意味 |
|---|---|---|
| 平文 | \(P\) | 秘密にしたい元のデータ |
| 暗号文 | \(C\) | 暗号化した後のデータ |
| 鍵 | \(K\) | 変換を制御する秘密の値 |
| 暗号化 | \(C = E_K(P)\) | 鍵\(K\)を使って平文を暗号文に変える |
| 復号 | \(P = D_K(C)\) | 鍵\(K\)を使って暗号文を平文に戻す |
ケルクホフスの原理（1883 年）
暗号方式そのものは公開されていてよい。安全性は鍵を秘密にすることだけに頼るべきである。
この原則が正しい理由は 2 つある。
- アルゴリズムはいずれ漏れる（リバースエンジニアリング、内部の人間、論文など）。漏れたときに方式を作り直すのは現実的でないが、鍵なら交換すればよい。
- 公開されて世界中の研究者の攻撃に耐えた方式だけが信頼できる。秘密のままの方式は、まだ誰も本気で攻撃していないだけかもしれない。
仕様を秘密にすることで安全を保とうとする考え方を「隠蔽によるセキュリティ」といい、失敗した例が多い。GSM 携帯電話の通話暗号 A5/1、DVD 映像のスクランブル CSS、交通系 IC カード Mifare Classic の認証暗号 Crypto-1 は、どれも仕様を秘密にしていたが、解析されて破られた。 一方 AES（現在の標準的な共通鍵暗号、2 節と14 章）は仕様が完全に公開され、20 年以上世界中から攻撃を受けても実用的な破り方は見つかっていない。公開されているからこそ信頼できる、というのが現代暗号の立場である。
2. 暗号の分類
共通鍵暗号（対称暗号）
暗号化と復号に同じ鍵を使う。
- 長所: 高速で、実装が軽い。AES は専用命令のある CPU なら 1 秒に数ギガバイトを処理できる。
- 短所: 鍵をどうやって安全に相手に渡すかという鍵配送問題がある。
- 例: AES（14 章）、ChaCha20、DES
\(n\)人が互いに 1 対 1 で通信するには、2 人の組ごとに別の鍵が要るので\(\binom{n}{2} = n(n-1)/2\)個の鍵が必要である。100 人なら 4950 個で、管理しきれなくなる。
公開鍵暗号（非対称暗号）
暗号化と復号に異なる鍵を使う。暗号化に使う公開鍵は誰に知られてもよく、復号に使う秘密鍵は本人だけが持つ。
- 長所: 鍵配送問題を解決できる。デジタル署名（18 章）も作れる。
- 短所: 遅い。AES の数百〜数千倍の時間がかかる。2048 ビットの大きな整数の掛け算を何千回も行う必要があるのに対し、AES は 16 バイトを単純なビット演算の組み合わせで処理するだけだからである。
- 例: RSA（16 章）、楕円曲線暗号（17 章）
\(n\)人なら、各人が公開鍵と秘密鍵の組を 1 つずつ持てばよいので\(n\)組で済む。
ハイブリッド暗号: 実務では両方を組み合わせる。まず公開鍵暗号で共通鍵を安全に共有し（少量のデータなので遅くても問題ない）、実際のデータは共通鍵暗号で高速に暗号化する。 HTTPS で使われる TLS はこの方式で、通信の最初のやり取り（ハンドシェイク）で RSA や楕円曲線を使って共通鍵を共有し、その後の通信は AES などで暗号化する。
3. 攻撃モデル — 「安全」を定義するために
「安全」かどうかは、攻撃者が何を手に入れられると想定するかで変わる。代表的な想定は次の 4 つで、下ほど攻撃者が強い。
| モデル | 攻撃者が手に入れられるもの | 略記（英語名の頭文字） |
|---|---|---|
| 暗号文単独攻撃 | 暗号文だけ | COA (Ciphertext-Only Attack) |
| 既知平文攻撃 | 平文と暗号文の組 | KPA (Known-Plaintext Attack) |
| 選択平文攻撃 | 好きな平文を暗号化させた結果 | CPA (Chosen-Plaintext Attack) |
| 選択暗号文攻撃 | 好きな暗号文を復号させた結果 | CCA (Chosen-Ciphertext Attack) |
現代の暗号方式は、最も強い CCA の攻撃者に対しても安全であることが求められる。そんな強い攻撃者は非現実的に思えるが、実際に起きる。 たとえば、データの長さをそろえるために付ける詰め物（パディング）の形式が正しいかをサーバが復号後に検査し、正しくなければ「復号に失敗しました」というエラーを返すとする。攻撃者は細工した暗号文を大量に送ってエラーの有無を観察するだけで、復号結果を 1 バイトずつ特定できる。これをパディングオラクル攻撃といい、TLS や ASP.NET で実際に悪用された。エラーの有無という小さな情報も、復号をさせる手段になる。
安全性の種類
- 情報理論的安全（無条件安全）: 攻撃者の計算能力が無限でも破れない。暗号化ではワンタイムパッド（5 節）が代表例で、鍵が平文と同じ長さ以上必要になる。
- 計算量的安全: 現実的な計算資源では破れない。実用の暗号はすべてこちらである。
4. 古典暗号とその破り方
以下の古典暗号では、アルファベットを\(\mathrm{A} = 0, \mathrm{B} = 1, \dots, \mathrm{Z} = 25\)の整数とみなし、1 文字ずつ\(\mathbb{Z}_{26}\)（26 で割った余りの世界）で計算する。\(P, C\)は 1 文字に対応する\(0\)〜\(25\)の整数である（5 節では代わりにビット列として扱う）。
シーザー暗号
各文字を\(k\)個ずらす:
攻撃: 鍵\(k\)は\(0\)〜\(25\)の 26 通りで、\(k = 0\)は平文のままなので、実質 25 通りしかない。すべて試す全数探索ですぐに破れる。 上の図のように、暗号文の文字の出現回数を数えると、最も多い文字が E（4 節の頻度分析）のずれた先なので、全数探索すら要らない。
アフィン暗号
と暗号化する。復号には\(a\)の逆元\(a^{-1}\)（\(a a^{-1} \equiv 1 \pmod{26}\)となる数）を使う:
\(a\)の条件: \(a^{-1}\)が存在するのは\(\gcd(a,26)=1\)のときである（01 章 5 節）。\(26 = 2\times13\)なので、\(a\)は 2 でも 13 でも割り切れない\(1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25\)の 12 通りである。 鍵\((a, b)\)は\(12 \times 26 = 312\)通りで、やはり全数探索で破れる。
例: \(a = 7\)、\(b = 3\)とする。01 章 5 節で求めたとおり\(7^{-1} \equiv 15 \pmod{26}\)である。 H（\(P = 7\)）は\(C = 7 \times 7 + 3 = 52 \equiv 0\)で A になる。復号は\(P = 15 \times (0 - 3) = -45 \equiv 7\)（\(-45 + 52 = 7\)）で H に戻る。
\(\gcd(a, 26) = d > 1\)だと復号できない理由: \(P\)と\(P + 26/d\)を暗号化すると、暗号文の差は\(a \cdot 26/d = (a/d) \cdot 26\)である。\(a/d\)は整数なのでこれは 26 の倍数であり、\(\bmod 26\)では同じ暗号文になる。異なる平文が同じ暗号文になるので、暗号文から平文を決められない。 たとえば\(a=2\)なら\(d = 2\)で、\(P=0\)と\(P=13\)がどちらも\(C = b\)になる。逆元が存在することは、暗号が復号できるための必要条件である。
単一換字式暗号
26 文字を任意に並べ替えた対応表を鍵にする。鍵は\(26! \approx 4\times10^{26}\)通りあり、全数探索はできない。
それでも簡単に破れる。単一換字式暗号は同じ文字を必ず同じ文字に置き換えるので、平文で多い文字は暗号文でも多い。これを使うのが頻度分析である。
- 英文で最も多い文字は E（約 12.7%）で、T（約 9.1%）、A（約 8.2%）と続く。
- したがって暗号文で最も多い文字は、E の置き換え先である可能性が高い。
- 2 文字の組（TH, HE, IN）や 3 文字の組（THE, AND）の出現頻度も手がかりになる。
これが古典暗号の根本的な弱点である。平文の統計的な偏りがそのまま暗号文に残るので、鍵の種類がどれだけ多くても破られる。鍵空間の大きさは安全であるための必要条件だが、十分条件ではない。 現代暗号が、平文の 1 ビットの変化を暗号文全体に広げる拡散を重視するのは、この統計的な偏りを消すためである（6 節、14 章）。
ヴィジュネル暗号
鍵を長さ\(L\)の文字列\(K_0 K_1 \cdots K_{L-1}\)とし、\(i\)番目の文字を
と暗号化する。\(L\)種類のシーザー暗号を順番に使い回す方式で、長く「解読不能」と信じられていた。
例: 平文 ATTACK を鍵 KEY（\(K = 10, E = 4, Y = 24\)）で暗号化すると、鍵を KEYKEY と繰り返して
| 平文 | A (0) | T (19) | T (19) | A (0) | C (2) | K (10) |
|---|---|---|---|---|---|---|
| 鍵 | K (10) | E (4) | Y (24) | K (10) | E (4) | Y (24) |
| 暗号文 | K (10) | X (23) | R (43 → 17) | K (10) | G (6) | I (34 → 8) |
となり、KXRKGI になる。同じ T が X と R に、同じ A が K と K に暗号化されていて、1 文字ごとの頻度分析は直接は使えない。
攻撃（カシスキー・テスト、1863 年）:
- 暗号文の中で、繰り返し現れる文字列を探す。
- その出現間隔は、鍵長\(L\)の倍数である可能性が高い。平文に同じ単語（THE など）が 2 回現れ、その距離が\(L\)の倍数なら、2 回とも同じ鍵の文字で暗号化されるので、暗号文にも同じ文字列が現れるからである。
- いくつかの間隔の最大公約数から鍵長\(L\)を推定する（01 章 3 節の\(\gcd\)）。
- 鍵長が分かれば、同じ鍵の文字で暗号化された文字（\(i \bmod L\)が等しい文字）を集めて、それぞれ頻度分析する。
ヴィジュネル暗号は、鍵長さえ分かれば\(L\)個のシーザー暗号に分解でき、それぞれは簡単に破れる。
5. ワンタイムパッド — 完全な暗号
平文と同じ長さのランダムな鍵を用意し、XOR する:
\(C \oplus K = P \oplus K \oplus K = P\)なので、同じ鍵で XOR すれば元に戻る。
情報理論的安全性の証明（シャノン、1949 年）
方針: 暗号文を見た後で、各平文の確率が見る前と変わらないことを示す。変わらなければ、暗号文から平文について何も分からない。
導出: 鍵\(K\)は\(n\)ビットで、\(2^n\)通りの値がどれも同じ確率\(2^{-n}\)で選ばれ（これを一様ランダムという）、平文とは無関係に選ばれるとする。 任意の暗号文\(c\)と任意の平文\(p\)について、\(p \oplus k = c\)となる鍵は\(k = p \oplus c\)の 1 つだけである。
以下、\(\Pr[A \mid B]\)は「\(B\)が起きたと分かっているときに\(A\)が起きる確率」（条件付き確率）を表す。 平文が\(p\)のとき暗号文が\(c\)になるのは、鍵がちょうど\(p \oplus c\)のときなので、\(\Pr[C=c \mid P=p] = 2^{-n}\)である。暗号文が\(c\)になる確率は、平文ごとに場合分けして足し合わせて
となる（平文の確率の合計は 1）。条件付き確率の定義\(\Pr[A \mid B] = \Pr[A \text{ かつ } B]/\Pr[B]\)を 2 通りに使う（ベイズの定理）と
暗号文\(c\)を見た後の平文の確率は、見る前と同じである。攻撃者の平文についての推測は、暗号文を手に入れても何も改善しない ∎
完全に安全なのにほとんど使われない理由
ワンタイムパッドには 3 つの厳しい条件がある。
- 鍵が平文と同じ長さだけ必要: 1 GB のファイルには 1 GB の鍵が要る。それだけの鍵を安全に渡せるなら、平文そのものを渡せばよい。
- 鍵は完全にランダム: 擬似乱数では条件を満たさない。13 章で見るように、規則性があると破られる。
- 鍵を再利用しない: これが最も破られやすい。
同じ鍵を 2 回使うと
となり、鍵が消えて平文どうしの XOR が現れる。自然言語の平文なら、統計的な偏りを使って 2 つを分離できる。 実際、1940 年代のソ連の外交電文では、同じ鍵のページが複数の電文に使い回されていた。米国はこれに気づき、長い年月をかけて一部を解読した（VENONA 計画）。これが冷戦期のスパイ網の発覚につながった。
6. 現代暗号への橋渡し
古典暗号の失敗から、次の設計原則が得られる。
| 教訓 | 現代暗号での対応 |
|---|---|
| 鍵空間は十分大きく | 鍵は 128 ビット以上（\(2^{128}\)通りの全数探索は現実に不可能） |
| 統計的な偏りを残さない | 拡散: 平文の 1 ビットの変化を暗号文全体に広げる |
| 鍵と暗号文の関係を隠す | 混同: 暗号文の各ビットが、鍵の多くのビットに複雑に（足し算や XOR だけでは書けない形で）依存するようにする。そのための部品がS-box（入力のビット列を表で別のビット列に置き換える箱） |
| 鍵を使い回しても安全に | IV / ノンス（メッセージごとに変える、秘密でない値）を鍵と一緒に入力し、同じ鍵でも毎回違う暗号文にする |
| 方式は公開する | 標準化して公開の場で検証する |
「混同と拡散」はシャノンが 1949 年に述べた考え方で、現代のブロック暗号の設計原理になっている。AES の 1 ラウンドは、各バイトを S-box で置き換えるSubBytes（混同）と、バイトを並べ替えて列ごとに混ぜ合わせるShiftRows / MixColumns（拡散）の組み合わせでできている。14 章で詳しく見る。