Шифр Виженера: как он работает

Шифры ·

Почти триста лет этот шифр носил титул le chiffre indéchiffrable — «неразгадываемый». Им пользовались дипломаты, армия Конфедерации в Гражданской войне в США и авторы шифрованных объявлений в викторианских газетах. Разберём, как он устроен, почему оказался таким живучим — и почему носит чужое имя.

Проблема, которую он решал

К XVI веку криптографы уже понимали: любой шифр простой замены обречён. Как бы вы ни перемешивали алфавит, частота букв остаётся прежней. В русском языке «О» встречается примерно в 11 % случаев, и если вы замените её на «Щ», то «Щ» в шифротексте будет встречаться ровно так же часто. Шифр Цезаря ломается ещё проще — у него всего 32 возможных ключа.

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

Кто на самом деле его придумал

Первым идею менять алфавит предложил Леон Баттиста Альберти в 1467 году — он же построил шифровальный диск. Немецкий аббат Иоганн Тритемий в трактате «Polygraphia» описал tabula recta — таблицу, где каждая следующая строка сдвинута на одну позицию. Его схема меняла алфавит строго по порядку, что делало её предсказуемой.

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

Блез де Виженер, французский дипломат, в 1586 году описал в своём «Traicté des chiffres» другую, более сильную схему — автоключ, где после короткого начального ключа продолжением служит сам открытый текст. В XIX веке авторство перепутали, и имя Виженера закрепилось за более простым шифром Беллазо.

Ирония в том, что настоящее изобретение Виженера — автоключ — было заметно стойче того шифра, который носит его имя.

Как это работает

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

Классический пример на английском, с ключом LEMON:

текст: A T T A C K A T D A W N ключ: L E M O N L E M O N L E шифр: L X F O P V E F R N H R

Буква A сдвигается на 11 позиций (буква L — двенадцатая в алфавите, сдвиг считается от нуля) и превращается в L. Следующая T сдвигается на 4 позиции ключевой буквой E и становится X.

Тот же принцип на русском, ключ КЛЮЧ:

текст: П Р И В Е Т М И Р ключ: К Л Ю Ч К Л Ю Ч К шифр: Ъ Ь Ж Щ П Ю К А Ы

Обратите внимание: буква П встречается в тексте дважды, но превращается сначала в Ъ, а потом в К — потому что над ней стоят разные буквы ключа. Именно это и убивает частотный анализ.

Проверьте оба примера — и попробуйте свой текст:

Шифр Виженера онлайн

Математика в одну строку

Формально шифрование описывается сложением по модулю длины алфавита:

E(x) = (x + k) mod N D(y) = (y − k) mod N

где x — номер буквы текста, k — номер буквы ключа, а N — длина алфавита: 33 для русского, 26 для английского.

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

Почему он держался триста лет

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

Шифром пользовались всерьёз. Армия Конфедерации применяла его в Гражданской войне в США, причём с крайне неудачным подбором ключей — федеральные криптоаналитики регулярно читали её депеши. В викторианской Англии шифрованные объявления в газетах — «агонические колонки» — нередко использовали именно Виженера, и разгадывание их было интеллектуальным развлечением.

Ещё в 1917 году журнал Scientific American называл шифр невзламываемым — хотя к тому моменту метод вскрытия был опубликован уже больше полувека.

Как он пал

Первым его сломал Чарльз Бэббидж — тот самый создатель разностной машины — около 1854 года. Результаты он не опубликовал; по одной из версий, работа была засекречена в интересах британской разведки во время Крымской войны.

Поэтому лавры достались прусскому офицеру Фридриху Казиски, который в 1863 году выпустил книгу «Die Geheimschriften und die Dechiffrir-Kunst» с общим методом определения длины ключа. Как именно работает его приём и почему он сводит Виженера к набору простых шифров Цезаря, разобрано отдельно: метод Казиски.

В 1922 году Уильям Фридман предложил индекс совпадений — статистический метод, который определяет длину ключа надёжнее и полностью автоматически.

Родственные шифры

Вокруг основной схемы выросло целое семейство вариантов — все они используют ту же tabula recta, но по-разному выбирают строку.

  • Автоключ Виженера. Настоящее изобретение Блеза де Виженера: после короткого начального ключа продолжением служит сам открытый текст. Периодичность исчезает, и метод Казиски против такой схемы бессилен.
  • Шифр Бофора. Названный в честь адмирала Фрэнсиса Бофора (автора шкалы силы ветра), он вычитает букву текста из буквы ключа, а не складывает их. Приятное свойство: шифрование и расшифровка — одна и та же операция.
  • Шифр Гронсфельда. Упрощение, где ключом служит не слово, а число: каждая цифра задаёт сдвиг. Ключей меньше, стойкость ниже, зато ключ легко запомнить.
  • Шифр Тритемиуса. Предшественник, где сдвиг растёт по фиксированному закону, а не задаётся ключом. Попробовать его можно на странице шифра Тритемиуса.

Принцип Керкгоффса и урок Виженера

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

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

Один частный случай, который остался невзламываемым

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

Логика проста: если ключ случаен, то для перехваченного шифротекста существует ключ, превращающий его в любой осмысленный текст той же длины. «АТАКА» и «ОТБОЙ» одинаково вероятны, и математика не даёт никаких подсказок.

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

Что стоит попробовать дальше

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

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

Частые вопросы

Правда ли, что шифр Виженера придумал Блез де Виженер?

Нет, и это одна из самых устойчивых ошибок в истории криптографии. Систему с повторяющимся ключевым словом описал итальянец Джованни Баттиста Беллазо в 1553 году. Блез де Виженер в 1586 году предложил другую, более стойкую схему с автоключом, где ключ продолжается самим открытым текстом. В XIX веке имена перепутали, и за более простым шифром Беллазо закрепилось имя Виженера.

Почему шифр Виженера называли неразгадываемым?

Потому что он ломает прямой частотный анализ. Одна и та же буква открытого текста шифруется разными символами в зависимости от того, какая буква ключа стоит над ней, поэтому распределение частот в шифротексте выравнивается. Почти три столетия никто не публиковал общего метода вскрытия, и за шифром закрепилось французское прозвище le chiffre indéchiffrable.

Какой длины должен быть ключ?

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

Используется ли шифр Виженера сегодня?

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

Читайте дальше