Взлом частотным анализом

Главное оружие против классических шифров — статистика. Буквы в языке встречаются неравномерно, и это всё выдаёт.

Это учебная классика: частотный анализ показывает, ПОЧЕМУ простые шифры небезопасны. Мы ломаем собственный шифр, а не чужие системы.

Идея частотного анализа

В любом естественном языке буквы встречаются с разной частотой. В английском чаще всего идут E, T, A, O. В русском — О, Е, А, И. Шифр подстановки не меняет частоты — он только переименовывает буквы. Значит, самая частая буква шифр-текста, скорее всего, соответствует самой частой букве языка.

Считаем частоты

В Python модуль collections даёт удобный Counter. Посчитаем частоты букв в зашифрованном тексте:

from collections import Counter

cipher = "WKLV LV D VLPSOH PHVVDJH HQFUBSWHG ZLWK FDHVDU"
letters = [c for c in cipher if c.isalpha()]
freq = Counter(letters)

for letter, count in freq.most_common(5):
    print(letter, count)

Вывод:

H 5
L 4
V 4
W 3
D 3

Чаще всего встречается H. В английском чаще всего E. Сделаем предположение: H в шифре — это E в оригинале. Это даёт сдвиг 3 (от E до H ровно три буквы). Проверим гипотезу.

Проверяем гипотезу автоматически

Раз мы подозреваем шифр Цезаря, найдём сдвиг автоматически: предположим, что самая частая буква шифр-текста — это E, и вычислим ключ.

import string
from collections import Counter
alphabet = string.ascii_uppercase

cipher = "WKLV LV D VLPSOH PHVVDJH HQFUBSWHG ZLWK FDHVDU"

def decrypt(text, key):
    return "".join(
        alphabet[(alphabet.index(c) - key) % 26] if c in alphabet else c
        for c in text
    )

most_common = Counter(c for c in cipher if c.isalpha()).most_common(1)[0][0]
guessed_key = (alphabet.index(most_common) - alphabet.index("E")) % 26
print("Предполагаемый ключ:", guessed_key)
print("Расшифровка:", decrypt(cipher, guessed_key))

Вывод:

Предполагаемый ключ: 3
Расшифровка: THIS IS A SIMPLE MESSAGE ENCRYPTED WITH CAESAR

Сработало! Мы взломали шифр, не зная ключа заранее — просто посчитали буквы. Для шифра подстановки приём чуть сложнее (нужно подбирать соответствие для каждой буквы), но принцип тот же.

Главный вывод урока

Частотный анализ — причина, по которой все классические шифры считаются небезопасными. Чем длиннее перехваченный текст, тем точнее статистика и тем легче взлом. Современные шифры специально устроены так, чтобы шифр-текст выглядел абсолютно случайным и никакая статистика буквы не выдавала.

Историческая справка

Частотный анализ описал арабский учёный аль-Кинди ещё в IX веке. Так что приёму, который мы только что запустили на Python, больше тысячи лет.