Шифр Виженера: История и принцип работы

Введение

Простой тип полиалфавитной системы шифрования

Шифр Вигенера (viʒnɛːʁ) — это метод шифрования алфавитного текста, при котором каждая буква открытого текста кодируется с помощью различного шифра Цезаря, чей сдвиг определяется соответствующей буквой другого текста – ключа. Например, если открытый текст – "attacking tonight", а ключ – "OCULORHINOLARINGOLOGY", то:
первая буква "a" открытого текста сдвигается на 14 позиций в алфавите (потому что первая буква "O" ключа – 14-я буква алфавита, если считать с 0), в результате получается "o";
вторая буква "t" сдвигается на 2 (потому что вторая буква "C" ключа означает 2), в результате получается "v";
третья буква "t" сдвигается на 20 ("U"), в результате получается "n", с переходом на начало алфавита;
и так далее, в результате получается сообщение "ovnlqbpvt hznzouz". Если получатель сообщения знает ключ, он может восстановить открытый текст, обратив этот процесс. Таким образом, шифр Вигенера является частным случаем полиалфавитной подстановки. Впервые описанный Джован Баттиста Белласо в 1553 году, шифр легко понять и реализовать, но он сопротивлялся всем попыткам взломать его до 1863 года, спустя три столетия. Это принесло ему название *le chiffrage indéchiffrable* (французский: «неразшифруемый шифр»). Многие пытались реализовать схемы шифрования, которые по сути являются шифрами Вигенера. В 1863 году Фридрих Касиски первым опубликовал общий метод дешифровки шифров Вигенера. В XIX веке схема была ошибочно приписана Блезу де Вигенеру (1523–1596) и получила свое нынешнее название.

История

Первое хорошо задокументированное описание полиалфавитного шифра было сделано Леоном Баттистой Альберти около 1467 года и использовало металлический шифровальный диск для переключения между шифрующими алфавитами. Система Альберти переключала алфавиты только после нескольких слов, а переключения обозначались записью буквы соответствующего алфавита в шифротексте. Позже Иоганн Тритемий в своей работе Polygraphiae (завершённой в рукописном виде в 1508 году, но впервые опубликованной в 1518 году) изобрел tabula recta – важнейший компонент шифра Виженера. Однако шифр Тритемия предоставлял прогрессивную, но довольно жёсткую и предсказуемую систему переключения между шифрующими алфавитами. В 1586 году Блез де Вигенер опубликовал тип полиалфавитного шифра, называемый шифром автоключа, поскольку его ключ основан на исходном открытом тексте, при дворе Генриха III Франции. Однако шифр, известный сегодня как шифр Виженера, основан на том, что первоначально описал Джован Баттиста Белласо в своей книге 1553 года La cifra del Sig. Джован Баттиста Белласо. Он опирался на tabula recta Тритемия, но добавил повторяющийся "контрсигнал" (ключ) для переключения шифрующих алфавитов для каждой буквы. В то время как Альберти и Тритемий использовали фиксированный шаблон подстановок, схема Белласо означала, что шаблон подстановок можно было легко изменить, просто выбрав новый ключ. Ключи обычно представляли собой отдельные слова или короткие фразы, заранее известные обеим сторонам, или передавались "по отдельному каналу" вместе с сообщением, таким образом, метод Белласо требовал надёжной защиты только ключа. Поскольку относительно легко обеспечить безопасность короткой ключевой фразы, например, в ходе предыдущей частной беседы, система Белласо была значительно более безопасной. Однако, в отличие от современного шифра Виженера, шифр Белласо не имел 26 различных "сдвигов" (различных шифров Цезаря) для каждой буквы, а вместо этого имел 13 сдвигов для пар букв. В XIX веке изобретение этого шифра, по сути разработанного Белласо, было ошибочно приписано Вигенеру. Дэвид Кан в своей книге «Разрушители кодов» сожалеет об этом неверном приписывании, говоря, что история «проигнорировала этот важный вклад и вместо этого назвала регрессивный и элементарный шифр в его честь, хотя он не имел к нему никакого отношения». Шифр Виженера получил репутацию исключительно надёжного. Известный писатель и математик Чарльз Латвидж Доджсон (Льюис Кэрролл) назвал шифр Виженера невзламываемым в своей статье «Алфавитный шифр» в детском журнале в 1868 году. В 1917 году журнал Scientific American описал шифр Виженера как «невозможно поддающийся расшифровке». Эта репутация была незаслуженной. Известно, что Чарльз Бэббидж взломал вариант шифра ещё в 1854 году, но не опубликовал свою работу. Касиски полностью взломал шифр и опубликовал технику в XIX веке, но даже в XVI веке некоторые опытные криптоаналитики могли время от времени взламывать шифр. Например, Конфедеративные Штаты Америки использовали латунный шифровальный диск для реализации шифра Виженера во время Гражданской войны в США. Сообщения Конфедерации были далеки от секретности, и Союз регулярно расшифровывал их. На протяжении всей войны руководство Конфедерации в основном полагалось на три ключевые фразы: «Манчестерский блеф», «Полная победа» и, к концу войны, «Да придет возмездие». Шифр Виженера с полностью случайным (и не используемым повторно) ключом, длина которого равна длине сообщения, становится одноразовым шифром – теоретически невзламываемым шифром. Гилберт Вернам попытался улучшить сломанный шифр (создав шифр Вернама-Виженера в 1918 году), но технология, которую он использовал, была настолько громоздкой, что оказалась непрактичной.

The very first well documented description of a polyalphabetic cipher was by Leon Battista Alberti around 1467 and used a metal cipher disk to switch between cipher alphabets. Alberti's system only switched alphabets after several words, and switches were indicated by writing the letter of the corresponding alphabet in the ciphertext. Later, Johannes Trithemius, in his work Polygraphiae (which was completed in manuscript form in 1508 but first published in 1518), invented the tabula recta, a critical component of the Vigenère cipher. The Trithemius cipher, however, provided a progressive, rather rigid and predictable system for switching between cipher alphabets. In 1586 Blaise de Vigenère published a type of polyalphabetic cipher called an autokey cipher – because its key is based on the original plaintext – before the court of Henry III of France. The cipher now known as the Vigenère cipher, however, is based on that originally described by Giovan Battista Bellaso in his 1553 book La cifra del Sig. Giovan Battista Bellaso. He built upon the tabula recta of Trithemius but added a repeating "countersign" (a key) to switch cipher alphabets every letter. Whereas Alberti and Trithemius used a fixed pattern of substitutions, Bellaso's scheme meant the pattern of substitutions could be easily changed, simply by selecting a new key. Keys were typically single words or short phrases, known to both parties in advance, or transmitted "out of band" along with the message, Bellaso's method thus required strong security for only the key. As it is relatively easy to secure a short key phrase, such as by a previous private conversation, Bellaso's system was considerably more secure. Note, however, as opposed to the modern Vigenère cipher, Bellaso's cipher didn't have 26 different "shifts" (different Caesar's ciphers) for every letter, instead having 13 shifts for pairs of letters. In the 19th century, the invention of this cipher, essentially designed by Bellaso, was misattributed to Vigenère. David Kahn, in his book, The Codebreakers lamented this misattribution, saying that history had "ignored this important contribution and instead named a regressive and elementary cipher for him [Vigenère] though he had nothing to do with it". The Vigenère cipher gained a reputation for being exceptionally strong. Noted author and mathematician Charles Lutwidge Dodgson (Lewis Carroll) called the Vigenère cipher unbreakable in his 1868 piece "The Alphabet Cipher" in a children's magazine. In 1917, Scientific American described the Vigenère cipher as "impossible of translation". That reputation was not deserved. Charles Babbage is known to have broken a variant of the cipher as early as 1854 but did not publish his work. Kasiski entirely broke the cipher and published the technique in the 19th century, but even in the 16th century, some skilled cryptanalysts could occasionally break the cipher. The Confederate States of America, for example, used a brass cipher disk to implement the Vigenère cipher during the American Civil War. The Confederacy's messages were far from secret, and the Union regularly cracked its messages. Throughout the war, the Confederate leadership primarily relied upon three key phrases: "Manchester Bluff", "Complete Victory" and, as the war came to a close, "Come Retribution". A Vigenère cipher with a completely random (and non reusable) key which is as long as the message becomes a one time pad, a theoretically unbreakable cipher. Gilbert Vernam tried to repair the broken cipher (creating the Vernam–Vigenère cipher in 1918), but the technology he used was so cumbersome as to be impracticable.

Криптоанализ

Идея шифра Вигенера, как и всех других полиалфавитных шифров, заключается в маскировке частоты встречаемости букв в открытом тексте, чтобы затруднить прямое применение частотного анализа. Например, если P – наиболее часто встречающаяся буква в зашифрованном тексте, написанном на английском языке, можно предположить, что P соответствует букве e, поскольку e – наиболее часто используемая буква в английском языке. Однако, при использовании шифра Вигенера, буква e может быть зашифрована разными буквами шифротекста в разных частях сообщения, что делает невозможным простой частотный анализ. Основная слабость шифра Вигенера – повторяемость его ключа. Если криптоаналитику удается правильно определить длину ключа n, шифротекст можно рассматривать как n взаимопереплетенных шифров Цезаря, каждый из которых можно легко взломать по отдельности. Длину ключа можно определить методом перебора всех возможных значений n, либо исследование Касиски и тест Фридмана могут помочь в определении длины ключа (см. ниже: и ).

Анализ частоты

Когда длина ключа известна, шифротекст можно переписать в столько же столбцов, при этом каждый столбец соответствует одной букве ключа. Каждый столбец состоит из открытого текста, зашифрованного отдельным шифром Цезаря. Ключ Цезаря (сдвиг) – это буква ключа Виженера, использованная для данного столбца. Используя методы, аналогичные тем, что применяются для взлома шифра Цезаря, можно определить буквы в шифротексте. Усовершенствование анализа Касиски, известное как метод Керкхоффса, сопоставляет частоты букв в каждом столбце с частотами букв открытого текста, сдвинутыми на определенное значение, чтобы определить ключевую букву (сдвиг Цезаря) для этого столбца. Как только каждая буква ключа известна, криптоаналитику остается лишь расшифровать шифротекст и получить открытый текст. Метод Керкхоффса неприменим, если таблица Виженера была переставлена, а не использовались обычные алфавитные последовательности, однако анализ Касиски и тесты на совпадения все еще могут быть использованы для определения длины ключа.

Вариант Бофорта

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

Шифр Гронсфельда

Несмотря на кажущуюся надёжность шифра Виженера, он так и не получил широкого распространения в Европе. Шифр Гронсфельда — вариант, который Гаспар Шотт приписал графу Гронсфельду (Josse Maximilaan van Gronsveld, урождённый van Bronckhorst), однако на самом деле он использовался значительно раньше послом герцога Мантуи в 1560-х и 1570-х годах. Он идентичен шифру Виженера, за исключением того, что использует всего 10 различных шифровальных алфавитов, соответствующих цифрам от 0 до 9: ключ Гронсфельда 0123 эквивалентен ключу Виженера ABCD. Шифр Гронсфельда более устойчив, поскольку его ключ не является словом, но менее устойчив из-за использования всего 10 шифровальных алфавитов. Именно шифр Гронсфельда получил широкое распространение в Германии и Европе, несмотря на свои недостатки.

Шифр автоключа Вигенера

Вигенер на самом деле изобрел более надежный шифр – шифр автоключа. Однако название "шифр Вигенера" закрепилось за более простым полиалфавитным шифром. Фактически, эти два шифра часто принимали друг за друга, и оба иногда называли "неразгаданным шифром". Бэббидж фактически взломал гораздо более надежный шифр автоключа, но Касиски обычно признается автором первого опубликованного решения для полиалфавитных шифров с фиксированным ключом.