Аль-Кинди и частотный анализ

В IX веке арабский учёный Аль-Кинди придумал метод, который на тысячу лет вперёд сломал все простые шифры подстановки. Это был первый научный взлом в истории.

Проблема простой подстановки

Шифр Цезаря слаб из-за малого числа ключей. А что, если перемешать алфавит произвольно? Тогда каждой букве соответствует случайная другая буква, и вариантов становится астрономически много — больше 400 септиллионов. Перебрать невозможно. Кажется, что такой шифр непробиваем.

Но Аль-Кинди заметил кое-что важное.

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

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

Посчитаем частоты в зашифрованном тексте:

from collections import Counter

cipher = "WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ " * 4
letters = [c for c in cipher if c.isalpha()]
freq = Counter(letters)

print("Буква : сколько раз")
for ch, n in freq.most_common(8):
    print(f"  {ch}   :  {n}")

top = freq.most_common(1)[0][0]
print()
print("Самая частая буква в шифровке:", top)
print("Скорее всего это зашифрованная E")

Как это ломает шифр

Криптоаналитик строит таблицу частот, сопоставляет самые частые символы шифровки с самыми частыми буквами языка и постепенно угадывает соответствия. Дальше помогают короткие слова и повторяющиеся сочетания.

from collections import Counter

# Типичный порядок частот букв в английском
ENGLISH = "ETAOINSHRDLCUMWFGYPBVKJXQZ"

cipher = "P===Z ZXLMP MXLMP".replace("=", "")
freq = Counter(c for c in cipher if c.isalpha())
ordered = [c for c, _ in freq.most_common()]

guess = {}
for enc_ch, eng_ch in zip(ordered, ENGLISH):
    guess[enc_ch] = eng_ch

print("Предполагаемое соответствие (по частоте):")
for k, v in guess.items():
    print(f"  шифр {k} -> возможно {v}")

Почему это важно

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

Вывод:

Аль-Кинди (IX век) изобрёл частотный анализ: считаем, как часто встречаются символы шифровки, и сопоставляем с частотами букв языка. Так ломается любая простая подстановка, даже с триллионами ключей.