暗号の歴史とワンタイムパッド ─ 現代暗号の前史

学習目標

本講を終えると、以下を達成できるようになります。

• シーザー暗号とヴィジュネル暗号の仕組みと、それぞれが破られた理由(頻度分析・カシスキー試験)を説明できる
• Enigma が「機械化したヴィジュネル暗号」であった理由と、なぜ Bletchley Park で破られたのかを述べられる
• ワンタイムパッド(OTP) の手順を XOR で正しく書ける
• シャノンの完全秘匿性 の意味(暗号文を見ても平文の確率分布が変わらない)を直観的に説明できる
• OTP が実用にならない3つの理由 ─ 鍵長 = 平文長、真の乱数、鍵の再利用厳禁(two-time pad 攻撃) を述べられる
• DES (1977) と AES (2001) の歴史的位置づけを説明し、なぜ 「完全」 ではなく 「計算量的に十分強い」 暗号が現実解になったのかを理解する

このレッスンの目次

古典暗号 ─ シーザーとヴィジュネル

シーザー暗号 ─ 単純な文字ずらし

各文字をアルファベット上で k 個ずらす だけ。鍵は「ずらす数 k」(0〜25 の 26 通り)。例えば k=3 なら A→D、B→E、…、Z→C。「HELLO」は「KHOOR」になります。

図の見方:平文の各文字を、対応表で3つ後ろの文字に置き換える。復号は同じ k で逆方向にずらす。鍵の総数はわずか 25 通り なので、現代では数秒で全数試行できる。

頻度分析 ─ 単一換字暗号は崩れる

シーザー暗号を一般化して「アルファベットの順序を完全にシャッフル(26! ≈ 4×10^26 通り)」した暗号(単一換字暗号)も、9 世紀のアラビアの学者 アル=キンディー が 頻度分析 で破ってしまいました。英語なら E が圧倒的に多く、続いて T・A・O・I…。暗号文中で最も多い文字は E、次は T、と推測すると鍵が割れる。

ヴィジュネル暗号 ─ 多表式で頻度分析を回避

16 世紀フランスのヴィジュネルが体系化した 多表式暗号。キーワードを平文の長さ分だけ繰り返し、各位置で異なるシーザー暗号を適用します。同じ平文文字でも、位置によって違う暗号文文字になるため、単純な頻度分析が効かなくなります。

図の見方:鍵 KEY (3 文字) を繰り返し、各位置で「平文の文字 + 鍵の文字」分のシフトを行う(A=0, B=1, ...)。同じ平文文字でも位置で結果が変わるため、頻度分析の効きが弱まる。

カシスキー試験 ─ ヴィジュネルも結局破れた

「破れない暗号」と長く信じられたヴィジュネルも、19 世紀に カシスキー試験 と フリードマン解析 によって破られました。鍵長を推定さえできれば、長さ k のヴィジュネルは k 個のシーザー暗号 に分解でき、それぞれを頻度分析で解ける。「鍵が短い・繰り返す・統計的偏りが残る」 限り、暗号は破られる ─ この教訓が、後のワンタイムパッドの設計思想につながります。

機械式暗号 ─ Enigma と第二次世界大戦

Enigma の動き(概念図)

図の見方:キーを打つと電流がプラグボード→3 つのロータ→反射板→ロータ逆順→ランプボードと流れ、対応する暗号文字が点灯する。キーを打つたびにロータが回る ので、同じ文字でも前後で別の文字に変換される ─ 周期が極端に長いヴィジュネル暗号と等価。

なぜ破られたか ─ Bletchley Park の闘い

Enigma は理論上 1.6 × 10^20 通りの鍵設定があり、当時の人間には破れないとされました。しかし英国 Bletchley Park のチーム(アラン・チューリング ほか) は、ドイツ軍の運用上の癖を突いて崩しました。決定打となった要因:

• 定型文(Cribs) ─「Wettervorhersage(天気予報)」「Heil Hitler」など、毎日特定位置に決まった語が出る
• 反射板の性質 ─ 文字 X が文字 X 自身に変換されることは絶対にない(自己回避)。これだけで候補がぐっと減る
• 運用ミス ─ オペレータが推測しやすい初期位置(AAA、自分の名前など)を選ぶ
• Bombe ─ チューリングが設計した電気機械式の総当たり装置。Cribs から矛盾のないロータ設定を高速で絞り込んだ

暗号方式の数学的強度ではなく 運用の隙 を突かれた事例として、現代でも繰り返し参照されます(プロトコルの数学が完璧でも、鍵の使い回し・乱数の偏りで実装が崩れる ─ 後の OTP の壁にも、現代 TLS 攻撃にも共通する教訓)。

つながる知識: Bletchley Park での暗号解読は、現代計算機科学の母胎の一つでもある。チューリングが Bombe の設計過程で具体化した発想は、戦後の汎用計算機・暗号研究に直結した。「暗号 ⇄ 計算量理論」という現在まで続く対の関係は、ここで産まれた。

ワンタイムパッド ─ 絶対に破れない暗号

OTP の動き

図の見方:平文の各ビットと、同じ長さの真の乱数鍵の各ビットを XOR するだけ。XOR は K ⊕ K = 0 という性質があるので、同じ鍵をもう一度 XOR すれば復号できる。アルゴリズム自体は中学生でも実装できるほど単純。

なぜこれが「絶対に破れない」のか ─ 直観

暗号文 11111010 を見たとき、攻撃者にとって平文として可能な値はいくつあるか?2^8 = 256 通り全部。なぜなら、鍵を「平文を任意の値にする鍵」として選べば、どんな平文も同じ暗号文を生成しうるから。例えば:

• 平文が HI(01001000 01001001) なら、鍵 = 10110010 11010101 で暗号文 11111010 10011100 になる
• 平文が NO(01001110 01001111) なら、鍵 = 10110100 11010011 でも暗号文は 11111010 10011100(別の鍵)

つまり攻撃者が 11111010 10011100 という暗号文を手に入れても、平文が HI なのか NO なのか、はたまた OK や BC なのか、区別する手がかりがゼロ。鍵が一様乱数で1度きりなら、暗号文と平文の間には 統計的相関がまったく存在しない。これがシャノンが定式化した 完全秘匿性 です(次節)。

シャノンの完全秘匿性

「平文の分布が変わらない」とは

具体例で考えます。攻撃者は事前知識として「平文は YES か NO のどちらかの返信」と知っているとします。事前確率は Pr(YES)=0.5、Pr(NO)=0.5。

• OTP の場合:暗号文 C を観測しても Pr(P=YES|C) = 0.5、Pr(P=NO|C) = 0.5 のまま。攻撃者の 知識が増えない
• 普通の暗号(AES など)の場合:理論上は鍵を全数試行すれば、ほとんどの鍵候補で平文が「意味のないバイト列」になる。その中で意味のある平文(YES か NO)に復号できる鍵は限定される → 攻撃者の知識は 有限の計算で増えうる(が、計算量が膨大すぎて事実上不可能)

「絶対」 と 「計算量的に十分」 の違い

図の見方:OTP は 情報理論的に絶対安全 ─ どんな計算機でも破れない。AES などは 計算量的に安全 ─ 理論上は鍵を全数試行できるが、現実の時間内には不可能。「絶対」を諦めることで 「短い鍵で長い秘密を守る」 実用性を手に入れた、というのが現代暗号の選択。

考えてみよう: 「短い鍵で長い秘密を守ることは絶対不可能」 とシャノンが証明したのに、なぜ我々は AES-128 で動画ストリーミングを暗号化できるのか?答え:「絶対」 を 「計算量的に絶対不可能」 に置き換えた から。AES-128 を破るには 2^128 通り試す必要があり、地球上の全コンピュータをかき集めても宇宙の年齢のあいだ計算しきれない。「現実的な時間で破れない」 を 「破れない」 と読み替える ─ これが現代暗号の哲学的な妥協点。

OTP が実用化されない3つの壁

壁① 鍵長 = 平文長 ─ 鍵配送が問題を解決しない

1 GB の動画を OTP で暗号化したい?1 GB の真の乱数鍵を、事前に安全な経路で送る必要がある。「データを安全に送りたい」 のに 「同じ量のデータを安全に送る前提が必要」 という 循環 が発生する。鍵を安全に送れる経路があるなら、そもそもその経路で平文を送ればよかった ─ という矛盾。

壁② 真の乱数が必要 ─ 擬似乱数では駄目

OTP の鍵は 真の乱数 でなければなりません。コンピュータが普通に生成する乱数(rand()、メルセンヌ・ツイスタなど)は 擬似乱数 であり、初期値(seed)から 決定的 に生成される ─ つまりパターンがある。これを OTP の鍵にすると「seed = 鍵」になってしまい、結局 seed の長さ(数十〜数百ビット)が真の鍵長になり、長い平文でも seed を当てれば全部解ける。

真の乱数を作るには 物理乱数源(熱雑音・放射線崩壊・量子現象)が必要で、生成速度が遅く、ハードウェアが要る。今の /dev/random も内部にエントロピー源を持っているが、長時間連続では足りない。

壁③ 鍵の再利用は致命的 ─ two-time pad 攻撃

OTP の鍵を 2 度使う と、何が起こるか。同じ鍵 K で2つの平文 P1, P2 を暗号化したとき:

C1 = P1 ⊕ K
C2 = P2 ⊕ K

C1 ⊕ C2 = (P1 ⊕ K) ⊕ (P2 ⊕ K)
        = P1 ⊕ P2 ⊕ (K ⊕ K)
        = P1 ⊕ P2 ⊕ 0
        = P1 ⊕ P2     ← 鍵が消えた!

暗号文同士の XOR が 平文同士の XOR になる。攻撃者は片方の平文の一部(よくある定型文 ─「HTTP/1.1」「Subject:」など)を推測すれば、もう片方の平文の対応位置が剥き出しになる。これが two-time pad 攻撃。VENONA はこれで崩されました。

つながる知識: この two-time pad 攻撃は、OTP に限らず あらゆるストリーム暗号(ChaCha20、AES-CTR、AES-GCM) に共通する弱点です。これらは「鍵 + nonce で擬似ランダムなビット列を生成して XOR」 という OTP の構造を踏襲しており、同じ鍵 + 同じ nonce を 2 度使うと OTP の鍵再利用と同じ事故が起きる。次回(第36回)以降の動作モード(CTR/GCM) で「nonce は絶対再利用してはいけない」という鉄則は、ここに根がある。

DES から AES へ ─ 現代共通鍵暗号の系譜

暗号史タイムライン

図の見方:古典→機械式→OTP(理論的完成)→ シャノンの定式化(1949) を経て、実用的な「短い鍵の暗号」 として DES (1977) と AES (2001) が登場。同じ 1970 年代に 公開鍵暗号(Diffie-Hellman、RSA) も誕生し、暗号は「鍵配送問題」 を解く道具を初めて手にしたが、これは次回・次々回(第37回)のテーマ。

DES (1977) ─ 公的標準としての最初のブロック暗号

米 NIST の前身 NBS が公募し、IBM の Lucifer をベースに採用。56 bit 鍵 / 64 bit ブロック / 16 ラウンド Feistel 構造。当時としては十分な強度だったが、計算機の進歩で 1998 年に EFF DES Cracker(専用ハードウェアで 22 時間で全鍵探索) により破られ、寿命が来た。

過渡期の対応として 3DES(Triple DES)(DES を 3 回かけて実効鍵長を上げる)も使われたが、性能・効率の問題で長期解にはならず、後継の公募が必要になった。

AES (2001) ─ 公開コンペで選ばれた現代標準

NIST は 1997 年に AES の公募を開始。米国外を含む世界中の研究者から 15 候補 が提案され、3 ラウンドの公開選考で 2000 年 10 月に ベルギー製の Rijndael が選定、2001 年に FIPS 197 として標準化。128 bit ブロック / 128・192・256 bit 鍵 / 10〜14 ラウンド SP 構造。Rijndael の設計者ライメンとデーマンは欧州の研究者であり、米政府がスパイ目的で裏口を仕込みやすい IBM 内部の暗号(DES の経緯)に対する反省から、公開・国際化された選考プロセス が重視された。

AES の中身(SubBytes / ShiftRows / MixColumns / AddRoundKey の 4 操作) と動作モード(ECB / CBC / CTR / GCM) は、次回 第36回 共通鍵暗号 で詳しく扱います。本講で見た OTP の3つの壁、特に「鍵再利用は致命的」という教訓が、CTR/GCM の nonce 設計に直接効いてきます。

暗号史を貫く 2 つの教訓

まとめと用語チェック

用語チェック

確認問題