ワンタイムパッド：一度なら破れず、二度で破れる

メッセージの各バイトをランダムな鍵とXOR演算すれば、暗号文からは何も読み取れません。敵への手がかりは皆無です。しかし同じ鍵を二つの文に使い回すと、鍵は跡形もなく消え去ります。単語をひとつ推測してスライドさせるだけで、重なり合う二つの文が互いを明かし始めます。

計算例 — ワンタイムパッド：一度なら破れず、二度で破れる

文字数	14
この長さで考えられる鍵の総数	5.2 × 10³³
この暗号文が表し得る、同じ長さのメッセージの総数	1.1 × 10²⁰
この暗号文を「retreat at ten」に変換する鍵	11 1e fa a1 83 6d 23 7c 98 ee 06 32 d1 84

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

レッスン

理論 — ワンタイムパッド：一度なら破れず、二度で破れる

ワンタイムパッドは、メッセージの各文字を、その文字のためだけに一度きりランダムに選ばれた鍵文字と組み合わせる暗号です。ここではバイト単位のビットごとの排他的論理和（XOR）を用います。暗号化は C = P ⊕ K であり、復号もまったく同じ演算 P = C ⊕ K で行われます。メッセージと同じ長さの完全な乱数鍵を用いることで、この暗号は完全秘匿性を獲得します。すなわち、暗号文をどれほど観察しても、どのメッセージが送信されたかについての推測は微塵も変わりません。しかし同じ鍵を二つのメッセージに使ってしまうと、鍵は相殺されて C₁ ⊕ C₂ = P₁ ⊕ P₂ となります。ここに推測した単語 w をスライドさせて重ね合わせる手法がクリブ・ドラッギングです。一方のメッセージが実際に w を含んでいる箇所では、w ⊕ C₁ ⊕ C₂ を計算するだけで、もう一方のメッセージの文字がそのまま手に入ります。

各記号の意味

P: メッセージ（1文字につき1バイト）
K: 鍵：メッセージの文字数と同じ長さのランダムなバイト列
C: 暗号文（P ⊕ K）
⊕: 排他的論理和（XOR）：対応する2つのビットが異なる場合に結果が 1 になる演算
w: クリブ：いずれかのメッセージに含まれると推測した単語

前提: メッセージはASCIIバイトとして格納された英小文字とスペースで構成されるものとします。鍵のバイト列は32ビットのシード値から始まる生成器で作られているため、このページで扱える鍵は 2³² ≈ 4.3 × 10⁹ 通りにすぎません。7文字を超えると鍵の数がメッセージの候補数より少なくなってしまうため、シャノンの定義に従えば、本ツールのパッドは厳密には完全秘匿ではありません。本物のパッドには、何人にも再現できない真の乱数バイトが必要です。ある断片が「自然な文字列に見える」とされるのは、全バイトが英字またはスペースであり、かつすべての3連続文字がポーの『黄金虫』（1843年）の前半3分の2に現れる場合です。検証用のペアは同作の後半3分の1から採取しました。mod 26 の文字加算ではなくXORを用いるのは、XORが符号を持たないためです。どちらのメッセージがクリブを含んでいようと、同じ演算で他方の断片が現れます。

すべての鍵を試せば、あらゆるメッセージが現れる 🖖

Attack at dawn のステップを進めて、下から二つの行に注目してください。そこには、まったく同一の暗号文を「retreat at ten」へと変えてしまう鍵が示されています。二つ目の入力欄に、同じ14文字の英字と空白を適当に入力してみても、やはり対応する鍵が現れます。XOR演算は自分自身を打ち消すため、暗号文とメッセージのXORをとれば、それがそのまま鍵になるからです。したがって、仮に敵が 256¹⁴ 通りの鍵をすべて試したとしても、元のメッセージを特定することはできません。得られるのは、その長さで考えられる 27¹⁴ ≈ 1.1 × 10²⁰ 通りの文字列すべてであり、それぞれがただ一つの鍵に対応しています。どの鍵も等確率で選ばれている以上、暗号文を傍受したところで、どの文字列の可能性も傍受前より高まることはありません。シャノンは1949年にこの性質を完全秘匿性と呼び、その代償として、鍵の候補数は少なくともメッセージの候補数と同じだけ必要であると証明しました。繰り返し用いられるヴィジュネル暗号の鍵はずっと小さく、だからこそ頻度分析などの統計的計量によって破られてしまうのです。

推測の前からスペースは透けて見える 🖖

スペースの現れる位置を押してください。鍵は綺麗に相殺されました。C₁ ⊕ C₂ はバイトごとに P₁ ⊕ P₂ そのものであり、鍵の痕跡は微塵も残っていません。ここで青く塗られた 50 バイト中の 19 バイトを見てみましょう。英小文字のバイト値は 0x61 から 0x7a、スペースは 0x20 です。文字とスペースの組み合わせに限って 0x40 のビットが 1 になるため、64 以上の値を持つバイトはすべて、どちらか一方のメッセージだけにスペースがある位置を示しています。単語を一つも推測しないうちから、どちらのメッセージの空白かは分からずとも、単語の区切りが透けて見えているのです。『黄金虫』から抽出した 60 文字のペア 2,000 組で調べると、全体の約 30% の位置でこの特徴が現れます。メレディス・ガードナーが1946年に解読に着手したソ連の暗号通信（アメリカ側の暗号名「ヴェノナ」）は、バイトのXORではなく暗号コードに鍵の数字を加算する仕組みでしたが、一方の暗号文から他方を減算すれば、共有された鍵はまったく同じように消え去ります。鍵の重複は手違いによるものでした。モスクワに迫るドイツ軍の進撃に追われるなか、KGBの暗号帳を印刷していた工房が、およそ 35,000 ページにおよぶ重複した鍵刷りを出荷してしまったのです。

クリブを挟む二つのスペースが鍵を握る 🖖

スペースなしのクリブを押してみてください。位置 26 に「the」を置くと、英字のみで構成された「org」が得られます。その中の3連続文字はすべて基準テキストに実在しますが、実際にはどちらのメッセージにもそこに「the」はありません。前後にスペースを戻して「 the 」にすると、このペアで合格するのは本物の位置だけに絞られます。基準テキストには含まれていない『黄金虫』の後半3分の1から 60 文字のペア 2,000 組を検証したところ、「 the 」は 3,661 箇所でテストを通過し、実際に存在したのは 3,281 箇所と、およそ 10 回中 9 回の精度でした。ところが「the」では 9,615 箇所も通過しながら、的中したのは 4,169 箇所と半分にも達しません。理由は青いバイトにあります。クリブのスペースが英字に化けるのは値が 64 以上のバイトの上だけであり、スペースのまま残るのは 0 の上だけです。それ以外のバイトと重なれば、英字にすらなりません。つまり、クリブの両端のスペースは、いずれかの文に実際に存在する単語の切れ目に命中しなければならず、位置が間違っているのにその二重の偶然が起きることは極めて稀なのです。

全プロセスの詳細解説

パッドを共有する二つのメッセージから5文字を解読する 4 ステップ
同じワンタイムパッドを使って、50 文字のメッセージが二通送信されました。位置 32 から 36 において、C₁ ⊕ C₂ を16進数で表すと 54 06 09 0c 4e です。どちらか一方のメッセージのこの位置に「 the 」（バイト列 20 74 68 65 20）が含まれると推測したとき、もう一方のメッセージの該当する5文字は何になるでしょうか。また、この推測がメッセージ2のものであり、メッセージ2のその位置の暗号文が 9d 8e 23 40 9e であるとすれば、対応する5バイトの鍵はどうなるでしょうか。答えを求めたら「練習問題」を押し、ページ上で次のステップに進んでみてください。

この問題をツールで開く
1. 最初のペアを2進数で書き出してみましょう。0x54 は 01010100、スペースの 0x20 は 00100000 です。XOR演算は2つのビットが異なる桁を 1 にするため、結果は 01110100 となります。これは 16進数で 0x74、すなわち文字 t です。なお、0x54 の 0x40 ビットが 1 であったことから、推測を行う前の段階で、一方のメッセージの位置 32 にスペースが存在することはすでに判明していました。
  
  $0x54 \oplus 0x20 = 01010100 \oplus 00100000 = 01110100 = 0x74 = t$
2. 残りの4文字も同様に計算します。0x06 ⊕ 0x74 = 0x72（r）、0x09 ⊕ 0x68 = 0x61（a）、0x0c ⊕ 0x65 = 0x69（i）、0x4e ⊕ 0x20 = 0x6e（n）。したがって、もう一方のメッセージには「train」が現れます。ここに含まれる3連続文字「tra」「rai」「ain」の3つは、いずれも基準テキストに存在します。
  
  $54 06 09 0c 4e \oplus 20 74 68 65 20 = 74 72 61 69 6e = train$
3. 「 the 」がメッセージ2にあるとすれば、鍵は C₂ ⊕ P₂ で求まります。0x9d ⊕ 0x20 = 0xbd、0x8e ⊕ 0x74 = 0xfa、0x23 ⊕ 0x68 = 0x4b、0x40 ⊕ 0x65 = 0x25、0x9e ⊕ 0x20 = 0xbe です。もしこの推測がメッセージ1に属していたなら、メッセージ2側が「train」となり、鍵バイトは C₁ ⊕「 the 」によって計算されていたはずです。どちらであっても C₁ ⊕ C₂ はまったく同じになるため、計算だけからどちらが正解かを判別することはできません。
  
  $K = C_{2} \oplus P_{2} = 9d 8e 23 40 9e \oplus 20 74 68 65 20 = bd fa 4b 25 be$
4. ツール上では位置 32 のメッセージ2に「 the 」を確定させ、クリブ欄には位置 31 で「 train 」を試しています。これはメッセージ1の「train」が一つの独立した単語であるという推測に基づいています。するとメッセージ2には「y the r」が現れます。これも英字とスペースのみで構成され、含まれる3連文字はすべて基準テキストに見出せるものです。これをメッセージ1に反映させれば、両方の行が7文字まで確定します。
  
  $(C_{1} \oplus C_{2})_{31..37} \oplus 20 74 72 61 69 6e 20 = 59 54 06 09 0c 4e 52 \oplus 20 74 72 61 69 6e 20 = 79 20 74 68 65 20 72$
解答

「train」。推測がメッセージ2のものであれば、鍵のバイト列は bd fa 4b 25 be。C₁ ⊕ C₂ の中には、「 the 」がどちらのメッセージに含まれるかを示す情報は一切ありませんし、今後現れることもありません。二つのメッセージを丸ごと入れ替えても、C₁ ⊕ C₂ はまったく変わらないからです。次の推測によって決まるのは、どの断片が同じメッセージ同士に属しているかという対応関係です。このページで正しく復元できた文字数が表示されるのは、あらかじめ両方のメッセージが与えられているからです。現実の傍受者の手元には二つの行しかなく、それらが意味の通る文章を成すかどうかだけが唯一の手がかりとなります。

$train, K_{32..36} = bd fa 4b 25 be$

学習の道すじ

暗号はいかにして破られるか

参考文献 (2)

The first insight's perfect secrecy and its cost in keys, and the Vigenère link: C. E. Shannon, "Communication Theory of Secrecy Systems," Bell System Technical Journal 28(4), pp. 656–715, October 1949. §10 "Perfect Secrecy", Theorem 6 (pp. 679–682).
The second insight's Venona history: the additive key, the duplicate pages, Gardner's first message: "VENONA: An Overview," Cryptologic Almanac 50th Anniversary Series, Center for Cryptologic History, National Security Agency. DOCID 3575728, approved for release 2009.

42Math チーム · 公表された資料と照合しています。訂正のご指摘を歓迎します。