頻度分析 (暗号)

頻度分析とは

暗号解読の手法の一つである頻度分析（Frequency analysis）は、暗号文中に現れる文字や特定の文字列がどれくらいの頻度で出現するかを統計的に分析し、これを手掛かりとして平文を解読する技術です。これは、平文で使用される言語が持つ統計的な特徴（特定の文字や単語の出現頻度の偏りなど）を前提とし、暗号文だけを用いて解読を試みるため、「暗号文単独攻撃」と呼ばれる分類に含まれます。

原理と対象

この手法が特に有効なのは、古典暗号の中でも「換字式暗号」と呼ばれる形式、特に「単一換字式暗号」に対してです。単一換字式暗号では、平文の各文字が常に同じ特定の別の文字、数字、あるいは記号に変換されるため、平文における文字の出現頻度と暗号文における文字の出現頻度がほぼ一対一で対応します。

自然言語においては、特定の文字（例えば英語の'e'や日本語の「い」）の出現頻度には顕著な偏りがあり、この偏りは文章の内容によらず比較的安定しています。したがって、暗号文の文字出現頻度を数え上げ、既知の言語における文字出現頻度と比較することで、暗号文中の文字がどの平文の文字に対応しているかを推定し、解読を進めることが可能となります。

頻度分析を通じて平文の言語を推定することもできます。さらに、特定の組織や個人の文書に現れる特有の頻度の偏りを利用して分析精度を高める場合もあります。

暗号文が文字だけでなく数字や記号で構成されている場合でも、それが平文の文字と対応していれば、例えば2桁の数字が1文字に対応するポリュビオスの暗号表のように、対応関係を推定した上で同様の頻度分析を適用することが可能です。

適用方法

頻度分析において手掛かりとなるのは、単に一文字ずつの出現頻度だけではありません。例えば英語の場合、単文字頻度では'e', 't', 'a', 'o', 'i', 'n'などが高い順で現れる傾向にありますが、これだけでなく、二文字の並び（連接文字、ダイグラム）では'th', 'he', 'in'などが、三文字の並び（トライグラム）では'the', 'and', 'ing'などが高い頻度で出現します。また、特定の文字の後に続く文字に強い偏りが見られる「連接特徴」（例：英語で'q'の後はほぼ必ず'u'）も有力な情報となります。単語の区切りが判明している場合は、単語自体の出現頻度も利用できます。

出現頻度だけでなく、同じ文字や文字列が暗号文中のどの位置に、どれだけの間隔で現れるかといった「反復特徴」も重要な手掛かりとなります。

ただし、実際の文章における文字出現頻度にはばらつきがあり、特に短い暗号文では統計的な誤差が大きくなる可能性があります。また、意図的に特定の文字の使用を避ける（例：特定の文字を使わない小説）など、作為的に頻度を操作された暗号文には単純な頻度分析は通用しにくい場合があります。

頻度分析を用いた解読作業は、統計データに基づいて文字の対応関係を仮説立て、それを文章に適用して矛盾がないか検証し、必要に応じて仮説を修正するという試行錯誤を繰り返します。高い頻度で現れる文字だけでなく、非常に低い頻度で現れる文字も対応関係を推測する手助けとなります。文法的な構造や文脈を考慮することも、適切な文字を絞り込む上で重要です。この解読には、単調な頻度集計作業をこなす根気と、クロスワードパズルのような論理的推論と試行錯誤のセンスが求められます。第二次世界大戦中には、イギリスやアメリカが新聞のクロスワードパズルで暗号解読官を募集したという逸話も残っています。頻度集計作業は、第二次世界大戦期にIBMの機械によって自動化が始まりました。フィクションの世界では、エドガー・アラン・ポーの「黄金虫」やアーサー・コナン・ドイルの「踊る人形」といった作品で、この頻度分析が謎解きの重要な要素として描かれています。

歴史的背景

頻度分析の歴史は古く、その存在が確認できる最も古い記録は9世紀に遡ります。アラビアの博学者アル＝キンディーが著した暗号解読に関する手記に、この分析手法についての記述が見られます。これは、暗号解読法そのものに関する最古の記録でもあります。

15世紀頃、ルネサンス期を迎えたヨーロッパにもこの解読法は伝播しました。当時のヨーロッパでは、シフト暗号をさらに複雑にした鍵付き換字などが用いられていましたが、頻度分析は換字表の複雑さに関わらず解読を可能にし、これらの工夫を無効にしてしまいました。16世紀には、多くの外交暗号文が他国によって頻度分析を駆使して解読されていたと言われています。

単一換字暗号が頻度分析に対して脆弱であることが明らかになると、その対策として新たな換字式暗号が考案されました。同音換字は、平文の特定の文字（頻度が高いもの）に複数の暗号文文字を割り当て、無作為に選択することで頻度の偏りを抑える手法で、1401年には既にその使用記録があります。多表式換字（ヴィジュネル暗号など）は、複数の換字表を鍵に従って切り替えて使用する方式で、平文の同じ文字でも変換結果が異なるため、暗号文の頻度が攪拌されます。綴字換字（プレイフェア暗号など）は、複数の平文文字（例えば2文字単位のダイグラム）をまとめて別の複数の暗号文文字に対応させる手法で、単文字頻度分析を撹乱する効果があります。

これらの新しい換字式暗号、特に多表式換字は、手作業での処理が複雑だったため当初は普及が遅れましたが、18世紀には採用が広まり、ヴィジュネル暗号は19世紀半ばまで解読不能と信じられていた時期もありました。

多表式換字への対抗策と限界

しかし、頻度分析の技術も改良され、単一文字だけでなく複数文字の出現頻度や、特定のパターン（例：反復する文字列）の出現間隔に着目する手法が登場しました。多表式換字の解読に大きな進歩をもたらしたのが、19世紀の「カシスキーテスト」と20世紀初頭の「一致反復率」です。カシスキーテストは、暗号文中に同じ文字列が複数回出現する場合、その出現間隔が鍵の周期の倍数である可能性が高いことを利用し、鍵の長さを特定する手法です。一致反復率は、暗号文から無作為に選んだ二つの文字が一致する確率を計算することで、統計的に鍵周期の長さを推定する手法です。

これらの改良された頻度分析手法に対しても十分な安全性を確保できる換字式暗号が登場したのは、20世紀初頭に開発されたローター式暗号機のような機械式暗号によってです。例えばエニグマ暗号機は、ローターの組み合わせにより極めて長い鍵周期を実現し、単純な頻度分析を困難にしました。しかし、これらの機械式暗号も、その設計上の特徴や暗号文の統計的性質をさらに高度に分析する手法によって最終的には解読されました。

現代の暗号技術は、頻度分析を含む「暗号文単独攻撃」はもちろん、より厳しい「既知平文攻撃」や「選択暗号文攻撃」に対しても安全であることを目標に設計されています。これにより、平文の言語的な特徴を手掛かりとする古典的な頻度分析は、現代の暗号システムに対しては有効な解読手段とはなっていません。

その他の応用

なお、頻度分析の考え方は暗号解読に限らず、未解読の古代文字の分析や、テキストデータの統計的分析など、様々な分野で応用されています。

もう一度検索