単換字暗号：文字を数えて26!通りの鍵を破る

シャーロック・ホームズの物語の一節を、未知の鍵で暗号化しました。シーザー暗号なら、25通りの鍵を一つずつ試しながらカイ二乗値の棒グラフを眺めてみてください。一般的な換字暗号なら、最もよく出る暗号文字を英語の最頻出文字と結びつけ、現れる単語を読み解きながら辻褄を合わせていきます。

計算例 — 単換字暗号：文字を数えて26!通りの鍵を破る

鍵の総数	25
文の文字数	120
解析による推定値（最小のχ²）	23.3
次点（2番目に小さい値）	445.8
正しい鍵か	正解
120文字の無作為な文章20,000編における正解率	100.0%

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

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

レッスン

理論 — 単換字暗号：文字を数えて26!通りの鍵を破る

単換字暗号は、鍵に従って平文の各文字を別の文字へと毎回同じ規則で置き換える暗号です。アルファベット26文字の並べ替えであるため、鍵の総数は 26! ≈ 4.03 × 10²⁶ 通りに及びます。その特殊な形がシーザー暗号で、すべての文字を一律に同じ文字数だけずらします。選べる鍵は25通りしか残りません。これらに対して、暗号文に現れる文字の出現頻度を普通の文章における文字の出現頻度と比較して鍵を突き止める手法を、頻度分析と呼びます。

各記号の意味

χ²: カイ二乗値：アルファベット26文字にわたる (O − E)² / E の総和。この値が小さいほど、復号文の文字出現回数が自然な英語に近いことを意味します
O: 評価対象の復号文において、ある文字が実際に現れた回数（観測度数）
E: 同じ長さの文章において、『踊る人形』の文字比率から期待される出現回数（期待度数）

前提: 暗号化されるのはアルファベット26文字のみです。空白や句読点はそのまま残るため、各単語の文字数がそのまま露呈します（踊る人形の暗号でも旗によって単語の区切りが示されていました）。ここでいう「英語の基準」には、あるホームズ作品の全39,859文字における出現回数を用いています。教材で使われる暗号文は別の作品から切り出されているため、基準となる文章自身と照合されてしまうことはありません。試行実験では、疑似乱数生成器を用いて『美しき自転車乗り』から無作為に文章と鍵を抽出しているため、何度試しても常に同じ検証結果が再現されます。

25通りの鍵を試すのは一瞬ですが、どれが正解かを見極めるには30文字ほど要ります 🖖

シーザー暗号の鍵は25通りしかありません。手作業でもすべて試せる数です。骨が折れるのは、復号された文のうちどれが英語として自然かを判断する作業でしょう。この画面ではその役目をピアソンのカイ二乗値に委ねています。同じ長さの文章で『踊る人形』から予測される文字数と、復号文の文字数とのずれを、文字ごとに足し合わせた統計量です。別のホームズ作品から抽出した20,000箇所の無作為な文章で試すと、最小スコアが正しい鍵を指す確率は、12文字で85.0%、31文字では99.1%に達します。失敗例を見るにはシーザー暗号（11文字）を押してみてください。真の鍵を差し置いてずらし量7が最小スコアとなり、dan reoep swoという文字列を返します。生身の読者なら一目で退ける並びでも、統計量にはそれを見抜く術がありません。

文字を数えて特定できるのはe、あとは微々たる手がかり 🖖

600文字の文章なら、出現頻度の順に対応づけるだけで、400回の無作為な試行のうち96.5%でeを正しい位置に当てられます。しかし、それに続く文字は頻度が接近しすぎていて、短い文章では順位が狂ってしまいます。『踊る人形』を見ても、a、o、i、n、h、sの比率はすべて6.3%から8.0%の間に密集しており、わずかな偶然で順位が簡単に入れ替わってしまうのです。全文字を頻度順で機械的に対応づけた場合、正解できるのは出現する23.5文字中、平均してわずか6.3文字。文全体の三分の一にすぎません。同じ物語のなかで人形の暗号に挑んだホームズも、まさにそう語っています。「Eに続く英語の文字の順位は決して明瞭ではない。印刷物全体の平均で見られる優位性も、短い一文のなかでは容易に逆転しうる」。彼は暗号文がもっと届くのを待ち、浮かび上がる単語を読んだのです。

短編小説を丸ごと一編暗号化しても、なお五つの文字を見誤る 🖖

暗号文を長くすれば出現回数は安定します。しかしそれは、いま読んでいる文章固有の頻度に落ち着くだけの話です。同じ作家の作品であっても、二つの物語の文字頻度が完全に一致することはありません。換字暗号（短編まるごと一編）を押してみてください。『美しき自転車乗り』全32,725文字の頻度を『踊る人形』と比較すると、21文字は正しい位置に収まるものの、h、i、n、f、yの五つの文字を間違え、正解率は文全体の76.1%にとどまります。『美しき自転車乗り』ではh（6.69%）がi（6.67%）やn（6.34%）をわずかに上回っていますが、『踊る人形』ではiとnがhより上位に位置しています。ちなみにホームズ自身は頻度順をT、A、O、I、N、S、H、R、D、Lだと述べていますが、その台詞が書かれた物語の中ですら、実際の頻度はSよりHの方が高いのです。

全プロセスの詳細解説

計算が終わり、読解が始まるとき 4 ステップ
換字暗号（600文字）を押してください。毎秒10億通りの鍵を試すコンピュータが、すべての鍵を総当たりで試すにはどれほどの時間がかかるでしょうか？そのうえで暗号文を解読してみましょう。出現頻度を数えることで何が分かり、頻出する単語からは何が読み取れるでしょうか？

この問題をツールで開く
1. 鍵の総数は 26! = 403,291,461,126,605,635,584,000,000 通りあり、およそ 4.03 × 10²⁶ 通りです。毎秒 10⁹ 通りを試しても 4.03 × 10¹⁷ 秒かかります。1年は 3.16 × 10⁷ 秒ですから、1.28 × 10¹⁰ 年、すなわち128億年（12.8×10⁹年）の歳月を要する計算になります。
  
  $26! = 403291461126605635584000000 \approx 4.03 \times 1 0^{26}, \frac{4.03 \times 1 0 ^{26}}{1 0 ^{9} \times 3.16 \times 1 0 ^{7}} = 1.28 \times 1 0^{10} years$
2. 暗号文で最も多く現れる文字はIで、600文字中80文字、割合にして13.3%を占めます。『踊る人形』におけるeの出現率は12.44%ですから、Iはeだと判断できます。しかし、それに続く三文字のO、N、Xはそれぞれ49回、47回、45回と僅差で、確信を持って順位をつけることは不可能です。機械的に頻度順で対応づけるとt、a、oが割り当てられますが、三文字とも不正解です。結果一覧の表がその代償を物語っています。順位だけで対応づけても、正解できるのは23文字中わずか3文字、文全体の14.2%にすぎません。
  
  $\frac{80}{600} = 13.3% \approx 12.44% : I \to e, 49, 47, 45 for O, N, X$
3. そこで単語に着目します。三文字の単語OBJとXDIがそれぞれ5回ずつ現れており、XDIの末尾のIはeでした。ここからtheが連想されるため、Xはt、Dはhと推測できます。そうするとOBJはandである可能性が最も高くなり、Oはa、Bはn、Jはdと決まります。最も頻出する二文字の単語PK（8回）にはofが当てはまり、5回出現するXPはtoと読めるため、先ほどの推測とも見事に一致します。
  
  $XDI \to t h e, OBJ \to an d, PK \to o f, XP \to t o$
4. この八つの文字をマスに入力してみてください。e、t、h、a、n、d、o、fの文字だけで、600文字中321文字、全体の53.5%が埋まり、冒頭の一行はf·o· the ·ea·· 1894 to 1901と読めるようになります。文字の出現回数から引き出せる情報はここまでです。年号の前にあるf·o·は十中八九fromですから、新たにrとmが手に入ります。ここから先は、純粋に文章を読み解く時間です。
  
  $\frac{321}{600} = 53.5% of the message from 8 letters$
解答

すべての鍵を総当たりするには128億年（12.8×10⁹年）かかります。文字を数えることで定まるのはeの1文字だけですが、頻出する三つの単語からさらに7文字が判明し、この8文字だけで文全体の53.5%が解読できます。

$1.28 \times 1 0^{10} years; 8 letters \to 53.5%$

学習の道すじ

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

参考文献 (1)

Both passages the page counts, and Holmes's words quoted in the second and third insights: Arthur Conan Doyle, "The Adventure of the Dancing Men" and "The Adventure of the Solitary Cyclist," in The Return of Sherlock Holmes. Project Gutenberg eBook #108.

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