頻度分析の解説

何世紀もの間、メッセージを隠す最良の方法は、アルファベットの各文字を別の文字に置き換えることでした。可能な鍵の数は天文学的なので、この暗号は破られないように見えました。ところが9世紀のバグダードの学者が、すでにその弱点を見抜いていました。言語にはほかよりはるかによく使われる文字があり、どれだけ置き換えてもそれは隠せないのです。頻度分析は暗号解読を当て推量から方法論へと変え、今でも新しい暗号に対して誰もが最初に試す手段です。

暗号文字を多い順に並べ、英語の頻度と対応させた棒グラフ。その下には、最初のいくつかの文字が解けた暗号文
暗号文字を多い順に並べ、英語の頻度と対応させた棒グラフ。その下には、最初のいくつかの文字が解けた暗号文

換字式暗号

単一換字式暗号は、決まった表に従ってアルファベットの各文字を別の文字に置き換えます。たとえば A は Q に、B は W に、という具合で、どの文字も1回ずつ使われます。この表が鍵です。アルファベットをずらすだけで鍵が25個しかないシーザー暗号と違い、換字式暗号では文字をどんな順序にも並べられます。鍵は 26! 通り、約 4 × 10²⁶ 個です。1秒に10億個の鍵を試すコンピューターでも、すべてを試すには100億年以上かかります。

アル=キンディーの発見

850年ごろ、アラブの哲学者アブー・ユースフ・アル=キンディーは秘密のメッセージの解読に関する論考を著しました。これが頻度分析について知られている最古の記述です。彼の助言はこうです。同じ言語の長い文章を用意して各文字の出現回数を数え、次に秘密のメッセージの文字を数えて対応させる。最も多いものを最も多いものに、2番目を2番目に。クルアーンを研究する学者たちは何世代にもわたって文字や単語を数えており、それがこの発想の源になったのかもしれません。

文字、ペア、単語

英語では文字の約12.7%が E、9%が T、8%が A で、Z は1000文字以上に1回しか現れません。1文字ごとの出現数は、特に短いテキストでは大まかな方向を示すだけなので、暗号解読者は見つけられるあらゆるパターンを利用します。英語では、1文字の単語は A か I です。最も多いペアは TH、HE、IN、ER で、最も多い二重文字は LL、EE、SS、OO です。Q のあとにはほぼ必ず U が続きます。よく現れる3文字の単語はおそらく THE で、T、H、E がわかれば THAT や THERE といった単語も次々に判明します。どの言語にも独自の指紋があります。ドイツ語やオランダ語では E がさらに優勢で、ポルトガル語では A が首位です。

女王の命取りとなった暗号

1586年、イングランドに幽閉されていたスコットランド女王メアリーは、アンソニー・バビントンと暗号の手紙をやり取りしていました。バビントンは彼女を救い出し、女王エリザベス1世を暗殺しようと企てていたのです。手紙はビール樽に隠して運び出されましたが、エリザベスの諜報長官フランシス・ウォルシンガムの手を経ており、その配下の暗号解読者トマス・フェリペスが頻度分析で暗号を破りました。それは、よく使う単語のための記号をいくつか加えた換字式暗号でした。解読された手紙は陰謀へのメアリーの関与を証明し、彼女は1587年2月に処刑されました。

頻度を隠す

暗号の作り手も反撃しました。同音字暗号はよく使われる文字にそれぞれ複数の記号を割り当て、どの記号もほぼ同じ頻度で現れるようにしました。意味のない記号であるヌルを文中にばらまき、出現数を混乱させることもありました。本当の答えは、16世紀のヴィジュネル暗号のような多表式暗号とともに現れました。暗号化の途中で複数のアルファベットを切り替えるため、1つの平文の文字がさまざまな暗号文字になります。この暗号は、19世紀にチャールズ・バベッジとフリードリヒ・カシスキーが鍵の長さを突き止め、各アルファベットに別々に頻度分析を適用する方法を示すまで持ちこたえました。

コンピューターが暗号パズルを解く方法

プログラムもすべての鍵を試すことはできませんが、登ることはできます。推測から出発し、結果がどれだけその言語らしいかを、通常は2~4文字の組がどれだけありふれているかで採点し、鍵の中の文字のペアを入れ替えて、スコアが上がる入れ替えを残していきます。どの入れ替えも役に立たなくなったら鍵を揺さぶって再び登り始め、最良の結果を残します。山登り法と呼ばれるこの方法は、数百文字の換字式暗号を1秒もかからずに解き、その変種は何世紀も人々を寄せつけなかった歴史的な暗号も解読してきました。

現代の頻度分析

AES のような現代の暗号は、暗号文が完全にランダムに見えるように設計されています。どのバイト値も同じ頻度で現れ、同じメッセージでも暗号化するたびに結果が変わります。頻度分析は手も足も出ません。それでも、その考え方は生き続けています。言語の統計は、復号が正しいかどうかを見分けたり、パズルや脱出ゲームの暗号を解いたり、古文書館で見つかった古い暗号の手紙を読んだりするのに役立ちます。2023年には、何世紀も失われていたスコットランド女王メアリーの手紙が、コンピューターの助けを借りて解読されました。

試してみよう

頻度分析ツールを開くと、英語、ドイツ語、フランス語、スペイン語、イタリア語、ポルトガル語、オランダ語のいずれかで書かれた暗号文が表示されます。グラフで文字の出現数をその言語と比べ、文字のペア、二重文字、短い単語といった手がかりを使って、鍵を1文字ずつ埋めていきましょう。行き詰まったら「ヒント」と「答え合わせ」が助けになり、ソルバーは山登り法がどのように解読を仕上げるかを見せてくれます。

よくある質問

英語で E が最も多い文字なのはなぜですか?

THE、BE、HE、WE、ARE など、英語で最もよく使われる単語の多くに含まれ、-ED や -ES といったよくある語尾にも現れるからです。ほとんどのヨーロッパの言語も同じで、フランス語、ドイツ語、オランダ語、スペイン語でも E が首位です。

頻度分析はどんな暗号でも破れますか?

いいえ。破れるのは、平文の各文字が常に同じ記号に置き換えられる暗号です。暗号化の途中で置き換え方を変える暗号や、文字ではなくビットを扱う現代の暗号には別の方法が必要で、まったく破れないものもあります。

暗号パズル(クリプトグラム)とは何ですか?

格言や文を単一換字式で暗号化し、読者が手で解けるように印刷したものです。暗号パズルは19世紀から新聞に掲載されてきており、このツールが示すのとまったく同じ方法で解きます。短い単語と最も多い文字から始めるのです。

スコットランド女王メアリーの失われた手紙はどのように解読されたのですか?

2023年、ジョージ・ラスリー、ノルベルト・ビーアマン、Satoshi Tomokiyoの3人は、フランスの図書館にある57通の暗号の手紙がメアリーのものであることを突き止めました。その暗号は200近い記号を使っていたため、彼らはコンピューターによる山登り法で多くの記号のおおよその意味を推定し、残りを丹念な手作業で解き明かしました。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

頻度分析ツールを開く