Шифры Бофора и бегущего ключа

Шифр Бофора — это вариант шифра Виженера, в котором изменена формула шифрования. В шифре Виженера вычисляется C = (P + K) mod 26, а в шифре Бофора — C = (K - P) mod 26.

Это небольшое изменение придаёт шифру Бофора замечательное свойство: он является собственной обратной функцией. Одна и та же операция с одним и тем же ключом выполняет и шифрование, и расшифрование; такое свойство называют взаимностью шифра.

Поскольку в шифре Бофора шифрование и расшифрование являются одной и той же операцией, его называют «самовзаимным» или «инволютивным». Для расшифрования выполняется в точности та же процедура, что и для шифрования.

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

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

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

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

И отправитель, и получатель должны иметь одинаковую копию текста-ключа и договориться о начальной позиции. После этого шифрование выполняется так же, как в шифре Виженера, но с неповторяющимся ключом.

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

Клод Шеннон доказал это: для обеспечения совершенной секретности энтропия ключа должна быть не меньше энтропии сообщения. По-настоящему случайный ключ длиной с сообщение удовлетворяет этому условию.

На практике текст книги не является случайным. Это английская проза со всеми статистическими закономерностями естественного языка. Злоумышленник может перебирать разные книги и начальные позиции, проверяя, похожи ли полученные ключ и открытый текст на естественный язык.

Это свойство «двух текстов», при котором и открытый текст, и ключ должны быть правильным текстом на естественном языке, парадоксальным образом делает шифр с бегущим ключом на практике слабее, чем более короткий, но действительно случайный ключ.

Джован Баттиста Беллазо опубликовал несколько конструкций полиалфавитных шифров в 1550-х годах. Позднее его работу ошибочно приписали Блезу де Виженеру, что привело к исторически неверному названию шифра Виженера.

Шифры Беллазо включали взаимный вариант, предвосхитивший шифр Бофора. Его вклад в полиалфавитную криптографию был значительным, хотя до современных исторических исследований, исправивших эту ошибку, он почти не получал признания.

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

Индекс совпадений (IC) измеряет степень сглаженности распределения частот. Для английского текста IC составляет около 0,065. У идеально случайной подстановки IC равен примерно 0,038. Значения IC полиалфавитных шифров находятся между этими показателями и зависят от длины ключа.

Уильям Фридман разработал статистический тест, позволяющий определить длину ключа полиалфавитного шифра только по шифротексту. Анализируя IC каждой подвыборки символов через каждые n позиций, он мог определить период ключа.

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

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

Появление механических шифров, таких как «Энигма» и SIGABA, а затем и компьютеров коренным образом изменило криптографию. Классические шифры превратились из практических средств защиты в исторические курьёзы и учебные инструменты.

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

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

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

На практике ключи на естественном языке уязвимы для анализа. Тест Фридмана на основе IC и анализ Касиски позволяют определить длину ключа полиалфавитных шифров, сведя их к решаемым простым подстановкам.