Шифр Виженера и его эпоха

Триста лет шифр Виженера называли «le chiffre indechiffrable» — нераскрываемый шифр. Он победил частотный анализ Аль-Кинди одной простой идеей.

Идея: много сдвигов сразу

Слабость Цезаря в том, что весь текст сдвигается на одну и ту же величину. Виженер предложил использовать ключевое слово: каждая буква сдвигается на свою величину, заданную буквой ключа.

Ключ KEY означает сдвиги 10, 4, 24 (позиции букв K, E, Y), которые повторяются по кругу вдоль всего текста.

import string
A = string.ascii_uppercase

def vigenere(text, key, decrypt=False):
    out = []
    ki = 0
    for ch in text.upper():
        if ch in A:
            shift = A.index(key[ki % len(key)].upper())
            if decrypt:
                shift = -shift
            idx = (A.index(ch) + shift) % 26
            out.append(A[idx])
            ki += 1
        else:
            out.append(ch)
    return ''.join(out)

msg = "MEET ME AT MIDNIGHT"
enc = vigenere(msg, "LEMON")
dec = vigenere(enc, "LEMON", decrypt=True)
print("Текст:       ", msg)
print("Шифр:        ", enc)
print("Расшифровка: ", dec)

Почему частотный анализ ломается

Одна и та же буква текста превращается в разные символы — в зависимости от позиции в ключе. Буква E может стать то P, то I, то Q. Частоты размазываются, и простой подсчёт символов больше не помогает.

import string
from collections import Counter
A = string.ascii_uppercase

def vigenere(text, key):
    out, ki = [], 0
    for ch in text.upper():
        if ch in A:
            shift = A.index(key[ki % len(key)])
            out.append(A[(A.index(ch) + shift) % 26])
            ki += 1
    return ''.join(out)

plain = "EEEEEEEEEEEEEEEEEEEE"
print("Текст из одних E:", plain)
print("После Виженера:  ", vigenere(plain, "SECRET"))
print()
print("Частоты в шифровке:", dict(Counter(vigenere(plain, "SECRET"))))
print("Одна буква размазалась по нескольким символам!")

Как его всё-таки взломали

В XIX веке Чарльз Бэббидж и Фридрих Касиски нашли слабость: если узнать длину ключа, шифр распадается на несколько обычных шифров Цезаря (каждый со своим сдвигом), а их частотный анализ берёт легко. Длину ключа выдают повторяющиеся куски в шифровке.

Урок: повторяющийся ключ — фундаментальная уязвимость. По-настоящему стойким стал лишь одноразовый блокнот, где ключ такой же длинный, как сообщение, и используется один раз.

Вывод:

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