頻度分析（Frequency Analysis）

シーザー暗号のような単純な暗号は総当たり攻撃で破れるが、鍵空間が26! \approx 4 \times 10^{26}にもなる単一換字式暗号ではそうはいかない。しかし、この膨大な鍵空間を持つ暗号にも致命的な弱点がある。それが頻度分析（Frequency Analysis）である。

頻度分析とは、暗号文中の文字の出現頻度を調べ、言語に固有の文字頻度パターンと比較することで、暗号文と平文の対応関係を推定する手法である。同じ平文の文字が常に同じ暗号文の文字に変換される単一換字式暗号に対して有効であり、古典暗号の解読における最も強力な武器とされる。

原理

どの自然言語でも、文字の出現頻度には偏りがある。英語では「E」が最も頻出し、全体の約12.7%を占める。一方、「Z」はわずか0.07%程度しか現れない。単一換字式暗号では平文の各文字が常に同じ暗号文字に変換されるため、この頻度の偏りが暗号文にもそのまま引き継がれる。

英語の文字頻度表

以下は英語における各アルファベットの標準的な出現頻度（%）である。この数値は大量の英語テキストの統計から得られたものであり、サンプルが十分に長ければほぼ一致する。

上位12文字を覚えやすい順に並べた「ETAOIN SHRDLU」は、暗号解読者の間で広く知られたフレーズである。

バイグラム・トライグラム

1文字の頻度だけでなく、連続する2文字（バイグラム）や3文字（トライグラム）の頻度も解読の強力な手がかりとなる。

特に「THE」は英語で圧倒的に多いトライグラムであり、暗号文中で3文字の同じ組み合わせが頻出すれば、それが「THE」に対応する可能性が高い。これだけで3文字分の対応が一度に判明する。

解読の手順

頻度分析による単一換字式暗号の解読は、以下の手順で進める。

ステップ1：暗号文の文字頻度を数える。暗号文中の各文字の出現回数を集計し、頻度順に並べる。

ステップ2：最頻文字を仮定する。暗号文で最も多い文字を、英語で最も多い「E」に対応させる。次に多い文字は「T」や「A」の候補とする。

ステップ3：バイグラム・トライグラムを活用する。暗号文中の頻出する文字組み合わせを探し、「THE」「AND」「ING」などとの対応を推測する。

ステップ4：単語パターンを推測する。1文字の単語は「a」か「I」しかない。2文字の頻出語は「of」「to」「in」「is」など。部分的に判明した文字から単語を推測して対応を埋める。

ステップ5：確認と修正。仮定した対応で暗号文を置換し、意味の通る文になるか確認する。矛盾があれば仮定を修正して繰り返す。

まとめ

頻度分析の登場により、単一換字式暗号は鍵空間がどれほど大きくても安全ではないことが明らかになった。この脅威に対抗するために、文字ごとに異なる換字表を使うヴィジュネル暗号（多表式暗号）が開発された。

実践

下のウィジェットにテキストを入力すると、各文字の出現頻度を分析できる。暗号文を入力して頻度分布を確認してみよう。

Python実装

Pythonによる頻度分析の実装を示す。暗号文の各文字の出現頻度を集計し、英語の標準頻度と比較する。

from collections import Counter

def frequency_analysis(text):
    clean = ''.join(c.upper() for c in text if c.isalpha())
    counts = Counter(clean)
    total = len(clean)
    print(f"文字数: {total}\n")
    for ch, cnt in counts.most_common():
        bar = '█' * int(cnt / total * 100)
        print(f"  {ch}: {cnt:3d} ({cnt/total*100:5.2f}%) {bar}")

# 英語の標準頻度（参考値）
ENGLISH_FREQ = {
    'E':12.70,'T':9.06,'A':8.17,'O':7.51,
    'I':6.97,'N':6.75,'S':6.33,'H':6.09,
    'R':5.99,'D':4.25,'L':4.03,'C':2.78
}

# シーザー暗号の自動解読（chi-squared法）
def crack_caesar(ciphertext):
    clean = ''.join(c.upper() for c in ciphertext if c.isalpha())
    best_shift, best_score = 0, float('inf')
    for shift in range(26):
        decrypted = ''.join(
            chr((ord(c) - 65 - shift) % 26 + 65) for c in clean
        )
        freq = Counter(decrypted)
        total = len(decrypted)
        score = sum(
            (freq.get(ch, 0)/total*100 - ef)**2 / ef
            for ch, ef in ENGLISH_FREQ.items()
        )
        if score < best_score:
            best_shift, best_score = shift, score
    return best_shift

ct = "KHOOR ZRUOG"
shift = crack_caesar(ct)
print(f"推定シフト量: {shift}")
plain = ''.join(
    chr((ord(c)-65-shift)%26+65) if c.isalpha() else c
    for c in ct
)
print(f"復号結果: {plain}")