Шифр виженера как расшифровать

Шифр Виженера

Шифр Виженера (фр.  Chiffre de Vigenère ) — метод полиалфавитного шифрования буквенного текста с использованием ключевого слова.

Этот метод является простой формой многоалфавитной замены. Шифр Виженера изобретался многократно. Впервые этот метод описал Джован Баттиста Беллазо (итал.  Giovan Battista Bellaso ) в книге La cifra del. Sig. Giovan Battista Bellasо в 1553 году, однако в XIX веке получил имя Блеза Виженера, французского дипломата. Метод прост для понимания и реализации, он является недоступным для простых методов криптоанализа.

Содержание

История

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

То, что сейчас известно под шифром Виженера, впервые описал Джованни Батиста Беллазо в своей книге La cifra del. Sig. Giovan Battista Bellasо. Он использовал идею tabula recta Трисемуса, но добавил ключ для переключения алфавитов шифра через каждую букву.

Блез Виженер представил своё описание простого, но стойкого шифра перед комиссией Генриха III во Франции в 1586 году, и позднее изобретение шифра было присвоено именно ему. Давид Кан в своей книге «Взломщики кодов» отозвался об этом осуждающе, написав, что история «проигнорировала важный факт и назвала шифр именем Виженера, несмотря на то, что он ничего не сделал для его создания».

Шифр Виженера имел репутацию исключительно стойкого к «ручному» взлому. Известный писатель и математик Чарльз Лютвидж Доджсон (Льюис Кэрролл) назвал шифр Виженера невзламываемым в своей статье «Алфавитный шифр» англ.  The Alphabet Cipher , опубликованной в детском журнале в 1868 году. В 1917 году Scientific American также отозвался о шифре Виженера, как о неподдающемся взлому. Это представление было опровергнуто после того, как Касиски полностью взломал шифр в XIX веке, хотя известны случаи взлома этого шифра некоторыми опытными криптоаналитиками ещё в XVI веке.

Шифр Виженера достаточно прост для использования в полевых условиях, особенно если применяются шифровальные диски. Например, «конфедераты» использовали медный шифровальный диск для шифра Виженера в ходе Гражданской войны. Послания Конфедерации были далеки от секретных, и их противники регулярно взламывали сообщения. Во время войны командование Конфедерации полагалось на три ключевых словосочетания: «Manchester Bluff», «Complete Victory» и — так как война подходила к концу — «Come Retribution».

Гилберт Вернам попытался улучшить взломанный шифр (он получил название шифр Вернама-Виженера в 1918 году), но, несмотря на его усовершенствования, шифр так и остался уязвимым к криптоанализу. Однако работа Вернама в конечном итоге всё же привела к получению шифра, который действительно невозможно взломать.

Описание

В шифре Цезаря каждая буква алфавита сдвигается на несколько строк; например в шифре Цезаря при сдвиге +3, A стало бы D, B стало бы E и так далее. Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Для зашифровывания может использоваться таблица алфавитов, называемая tabula recta или квадрат (таблица) Виженера. Применительно к латинскому алфавиту таблица Виженера составляется из строк по 26 символов, причём каждая следующая строка сдвигается на несколько позиций. Таким образом, в таблице получается 26 различных шифров Цезаря. На разных этапах кодировки шифр Виженера использует различные алфавиты из этой таблицы. На каждом этапе шифрования используются различные алфавиты, выбираемые в зависимости от символа ключевого слова. Например, предположим, что исходный текст имеет вид:

Человек, посылающий сообщение, записывает ключевое слово («LEMON») циклически до тех пор, пока его длина не будет соответствовать длине исходного текста:

Первый символ исходного текста A зашифрован последовательностью L, которая является первым символом ключа. Первый символ L шифрованного текста находится на пересечении строки L и столбца A в таблице Виженера. Точно так же для второго символа исходного текста используется второй символ ключа; то есть второй символ шифрованного текста X получается на пересечении строки E и столбца T. Остальная часть исходного текста шифруется подобным способом.

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

Если буквы A-Z соответствуют числам 0-25, то шифрование Виженера можно записать в виде формулы:

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

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

1. Поиск длины ключа. Можно анализировать распределение частот в зашифрованном тексте с различным прореживанием. То есть брать текст, включающий каждую 2-ю букву зашифрованного текста, потом каждую 3-ю и т. д. Как только распределение частот букв будет сильно отличаться от равномерного (например, по энтропии), то можно говорить о найденной длине ключа.
2. Криптоанализ. Совокупность l шифров Цезаря (где l — найденная длина ключа), которые по отдельности легко взламываются.

Тесты Фридмана и Касиски могут помочь определить длину ключа.

Метод Касиски

В 1863 году Фридрих Касиски был первым, кто опубликовал успешный алгоритм атаки на шифр Виженера, хотя Чарльз Беббидж разработал этот алгоритм уже в 1854 году. В то время когда Беббидж занимался взломом шифра Виженера, John Hall Brock Thwaites представил новый шифр в «Journal of the Society of the Arts»; когда Беббидж показал, что шифр Thwaites’а является лишь частным случаем шифра Виженера, Thwaites предложил ему его взломать. Беббидж расшифровал текст, который оказался поэмой «The Vision of Sin» Альфреда Теннисона, зашифрованной ключевым словом Emily — именем жены поэта.

Тест Касиски опирается на то, что некоторые слова, такие как «the» могут быть зашифрованы одинаковыми символами, что приводит к повторению групп символов в зашифрованном тексте. Например: сообщение, зашифрованное ключом ABCDEF , не всегда одинаково зашифрует слово «crypto»:

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

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

Расстояние между повторяющимися DYDUXRMH равно 18, это позволяет сделать вывод, что длина ключа равна одному из значений: 18,9,6,3 или 2. Расстояние между повторяющимися NQD равно 20. Из этого следует, что длина ключа равна 20 или 10, или 5, или 4 или 2. Сравнивая возможные длины ключей, можно сделать вывод, что длина ключа (почти наверняка) равна 2.

Тест Фридмана

Тест Фридмана (иногда называемый каппа-тест) был изобретен Вильямом Фридманом в 1920 году. Фридман использовал индекс совпадения, который измеряет частоты повторения символов, чтобы взломать шифр. Зная вероятность того, что два случайно выбранных символа текста совпадают (примерно 0,067 для англ. языка) и вероятность совпадения двух случайно выбранных символов алфавита (примерно 1 / 26 = 0,0385 для англ. языка), можно оценить длину ключа как:

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

Частотный анализ

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

Варианты

Вариант running key (бегущий ключ) шифра Виженера когда-то был невзламываемым. Эта версия использует в качестве ключа блок текста, равный по длине исходному тексту. Так как ключ равен по длине сообщению, то методы предложенные Фридманом и Касиски не работают (так как ключ не повторяется). В 1920 году Фридман первым обнаружил недостатки этого варианта. Проблема с running key шифра Виженера состоит в том, что криптоаналитик имеет статистическую информацию о ключе (учитывая, что блок текста написан на известном языке) и эта информация будет отражаться в шифрованном тексте. Если ключ действительно случайный, его длина равна длине сообщения и он использовался единожды, то шифр Виженера теоретически будет невзламываемым.

Виженер фактически изобрёл более стойкий шифр — шифр с автоключом. Несмотря на это, «шифр Виженера» ассоциируется с более простым многоалфавитным шифром. Фактически эти два шифра часто путали, называя их le chiffre indechiffrable. Беббидж фактически взломал более стойкий шифр с автоключом, в то время когда Касиски издал первое решение взлома многоалфавитного шифра с фиксированным ключом. Метод Виженера зашифровки и расшифровки сообщений иногда относится к «варианту Битфорда». Его отличие от шифра Битфорда, изобретенного сэром Френсисом Битфордом, который, тем не менее, подобен шифру Виженера, заключается в использовании немного измененного механизма шифрования и таблиц.

Несмотря на очевидную стойкость шифра Виженера, он широко не использовался в Европе. Большее распространение получил шифр Гронсфилда, созданный графом Гронсфилдом, идентичный шифру Виженера, за исключением того, что он использовал только 10 различных алфавитов (соответствующих цифрам от 0 до 9). Преимущество шифра Гронсфилда состоит в том, что в качестве ключа используется не слово, а недостаток — в небольшом количестве алфавитов. Шифр Гронсфилда широко использовался по всей Германии и Европе, несмотря на его недостатки.

Шифр виженера как расшифровать

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

В шифре Цезаря каждая буква алфавита сдвигается на несколько позиций; например в шифре Цезаря при сдвиге +3, A стало бы D, B стало бы E и так далее.
Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Для зашифровывания может использоваться таблица алфавитов, называемая tabula recta или квадрат (таблица) Виженера. Применительно к латинскому алфавиту таблица Виженера составляется из строк по 26 символов, причём каждая следующая строка сдвигается на несколько позиций. Таким образом, в таблице получается 26 различных шифров Цезаря. На каждом этапе шифрования используются различные алфавиты, выбираемые в зависимости от символа ключевого слова. Например, предположим, что исходный текст имеет такой вид:

Человек, посылающий сообщение, записывает ключевое слово («LEMON») циклически до тех пор, пока его длина не будет соответствовать длине исходного текста:

Квадрат Виженера, или таблица Виженера, может быть использована для шифрования и расшифровывания

Первый символ исходного текста («A») зашифрован последовательностью L, которая является первым символом ключа. Первый символ зашифрованного текста («L») находится на пересечении строки L и столбца A в таблице Виженера. Точно так же для второго символа исходного текста используется второй символ ключа; то есть второй символ зашифрованного текста («X») получается на пересечении строки E и столбца T. Остальная часть исходного текста шифруется подобным способом.

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

Шифр Виженера

Калькулятор шифрует входной текст на русском языке шифром Виженера. Неалфавитные символы (пробелы, знаки препинания, цифры) — не преобразуются.

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

Суть алгоритма шифрования проста. Шифр Виженера — это последовательность шифров Цезаря с различными значениями сдвига (ROTX — см. Шифр Цезаря). То есть к первой букве текста применяется преобразование, например, ROT5, ко второй, например, ROT17, и так далее. Последовательность применяемых преобразований определяется ключевой фразой, в которой каждая буква слова обозначает требуемый сдвиг, например, фраза ГДЕ ОН задает такую последовательность шифров Цезаря: ROT3-ROT4-ROT5-ROT15-ROT14, которая повторяется, пока не будет зашифрован весь текст сообщения.

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

Еще там можно прочитать про вариант шифра с бегущим ключом (running key), который был когда-то был невзламываемым. Этот вариант заключается в использовании в качестве ключа блока текста, равного по длине исходному тексту. Впрочем, и этот вариант, как оказалось, успешно поддается взлому. Проблема с бегущим ключом шифра Виженера состоит в том, что криптоаналитик имеет статистическую информацию о ключе (учитывая, что блок текста написан на известном языке) и эта информация будет отражаться в шифрованном тексте. Если ключ действительно случайный, его длина равна длине сообщения и он использовался единожды, то шифр Виженера теоретически будет невзламываемым, но такие системы уже относятся к классу систем одноразового кода, или одноразового шифр-блокнота (one-time pad). Они действительно не поддаются взлому, однако их практическое применение довольно затруднительно.

Взлом шифра Виженера с помощью частотного криптоанализа

«Представьте себе такую ситуацию… Как-то раз, уходя со службы около часу ночи (руководитель должен подавать хороший пример), вы замечаете торчащий в дверях измятый клочок бумаги… Бумага отменная, слегка пахнет мускусом; почерк явно женский и веет от него этаким французским шармом. Теперь, по здравом размышлении, новая сотрудница мисс Хари начинает казаться вам, пожалуй, немножко слишком экзотичной. Ее французский акцент, неизменное черное платье для коктейля, нитка черного жемчуга, подчеркивающая декольте, и этот будоражащий запах мускуса, наполняющий комнату, когда она входит… Она говорит, что работала раньше в региональном вычислительном центре Мак-Дональда в Киокаке. Что-то тут не так. Подождите… Неужели мисс Хари шпионит в пользу знаменитой французской фирмы И Бей Эм? А эта записка — шифровка, в которой все секреты вашего новейшего чудо-компилятора? Чтобы уличить мисс Хари, записку нужно расшифровать. Но как?»

На Хабре уже пару раз мелькали статьи о книге Чарльза Уэзерелла «Этюды для программистов». Перед вами фрагмент одного из самых интересных, на мой взгляд, этюдов — «Секреты фирмы», основной задачей в котором является взлом шифра Виженера. Не так давно я реализовал этот этюд, и в моей статье я расскажу о том, как я это сделал и что в итоге получилось.

Задача

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

Затем выбирается ключевое слово и многократно записывается под исходным текстом. Наконец, каждая пара (символ исходного текста; символ ключевого слова под ним) шифруется с помощью таблицы соответствующим этой паре символом. Например, фраза «звезда забега» будет зашифрована с помощью ключа «багаж» и приведенной выше таблицы так:

Идея решения

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

Договоримся называть дистанцией между двумя символами разность их позиций в алфавите: например, дистанция между ‘а’ и ‘в’ — это 2. Тогда можно заметить, что если дистанция между i-м и j-м символами ключевого слова равна d, то дистанция между соответствующими символами исходного текста составляет -d. Следовательно, если нам удастся найти ключевое слово, то мы сможем свести шифр Виженера к шифру простой замены: каждая буква исходного текста будет заменена на другую, при этом соответствие букв будет взаимно-однозначным. Взломать такой шифр не составит труда.

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

Таким образом, программа будет состоять из трех частей:
1) Определение длины ключевого слова
2) Поиск ключевого слова
3) Поиск перестановки алфавита и расшифровка текста

Длина ключевого слова

Длину ключевого слова проще всего найти, используя метод индекса совпадений. Этот метод был предложен Уильямом Фридманом в 1922 году для взлома оригинального шифра Виженера, но он сработает и в нашем случае. Метод основан на том факте, что вероятность совпадения двух случайных букв в некотором достаточно длинном тексте (индекс совпадений) — это постоянная величина. Таким образом, если разбить текст на L групп символов, каждая из которых зашифрована шифром простой замены (напомню, это и означает, что L — длина ключевого слова), то индексы совпадений для каждой из групп будут довольно близки к теоретическому значению этой величины; для всех других разбиений индексы совпадений будут гораздо ниже. Индекс совпадений можно посчитать по формуле

(fi — количество i-х букв алфавита в тексте, а n — его длина)

Ниже, например, приведены индексы совпадений для текста, зашифрованного с помощью ключа «проект» (6 символов).

Таким образом, для определения длины ключевого слова нужно посчитать индексы совпадений для разбиения текста на L = 1, 2,… групп, а затем выбрать из полученных величин первую, значительно превосходящую большинство остальных. Но… тут есть небольшая хитрость. Что если текст зашифрован с использованием ключа, который можно разделить на несколько похожих частей? Снизу приведена таблица индексов совпадений для того же текста, что и в первом примере, но зашифрованного с помощью ключа «космос» (те же 6 символов). Как же определить длину ключа в таком случае?

Я поиграл с различными способами и выяснил, что проще всего выбрать необходимый индекс так: нужно взять первый индекс, для которого справедливо: 1.06*ИС > ИСi, i = 1, 2,… Умножения на 1.06 в большинстве случаев хватает, чтобы настоящий ИС стал превосходить «кратные» ИС (в нашем примере это индексы при L = 12 и 18), но недостаточно для того, чтобы ложные индексы (при L = 3, 9 и 15) превзошли настоящие.

Конечно, мой способ не дает 100% результат. Более того, если текст зашифрован с помощью слова, состоящего из одинаковых частей (например, «тартар»), то длина ключевого слова в любом случае будет определена неверно (если, конечно, мы хотим найти осмысленное ключевое слово): нет никакой разницы между шифрованием ключом «тартар» и «тар». Поэтому важно дать пользователю возможность изменять длину ключа в ходе работы программы: к примеру, не подошла 6, значит, стоит попробовать 3 или 12.
К счастью, для зашифрованной записки из книги все определяется довольно просто. Взглянув на таблицу индексов совпадений, можно с уверенностью сказать, что длина ключевого слова — 7 символов.

Ключевое слово

Теперь, когда длина ключа найдена, можно приступить к поиску самого ключевого слова. Сперва нужно определить вероятности различных сдвигов между группами, на которые мы разбили шифр (напомню, что каждая группа зашифрована с помощью некоторой перестановки алфавита, при этом перестановки отличаются лишь сдвигом каждой буквы на несколько позиций в алфавите). Для нахождения вероятностей сдвигов я воспользовался идеей, предложенной переводчиками «Этюдов». Если опустить все математические выкладки, она заключается в следующем. Для каждой группы мы считаем количество символов x (x = ‘а’, ‘б’, . ‘я’) в ней и на основании информации о частоте букв в русском языке оцениваем вероятность того, что символу x шифра соответствует символ y (y = ‘а’, ‘б’, . ‘я’) исходного текста. Сопоставляя полученные таблицы вероятностей для различных групп, мы можем вычислить вероятности сдвигов r (r = 1, 2, . 32) между этими группами. В результате мы получаем таблицу, показывающую, какова вероятность сдвига r между группами i и j для любых двух групп и любого сдвига.

Найти само ключевое слово можно двумя способами. Первый способ — это найти наилучшую конфигурацию сдвигов, используя (только) полученную таблицу. Полный перебор занял бы очень много времени, поэтому я пошел другим путем. Я искал ключ следующим образом. Возьмем любое слово подходящей длины и вычислим его характеристику — сумму вероятностей сдвигов между каждыми двумя символами в нем (сдвиги между символами ключевого слова и между буквами перестановок в различных группах шифра совпадают с точностью до знака). Теперь внесем небольшое изменение в исследуемое слово. Если после изменения характеристика слова стала лучше, то мы запоминаем новое слово, в противном же случае забываем новое слово и возвращаемся к старому. Внося таким образом случайные изменения, мы довольно быстро найдем лучшее слово.

Проблема заключается лишь в том, что наилучшее слово далеко не всегда является ключевым. Тесты показали, что уже для текстов из 1024 символов ключ и лучшее слово зачастую различаются на один символ. Например, лучшее слово для записки из книги — «федиска». Не знаю я такого слова! Для более коротких текстов ключ определяется совершенно неверно. Поэтому от поиска ключа на основании только таблицы пришлось отказаться.

Второй способ поиска ключа простой и неинтересный, зато эффективный. Мы берем словарь и вычисляем характеристику каждого подходящего слова (для повышения скорости работы программы я разделил слова по их длинам). Лучшее слово мы берем в качестве ключевого. Такой метод работает корректно даже для коротких (400-500 символов) текстов, но у него есть очевидный недостаток: если ключевого слова нет в словаре, то программа ни при каких условиях не сработает верно.

Впрочем, если ключ в словаре есть, второй метод гораздо эффективнее первого. Поэтому в своей программе я использовал его. Этот метод сразу же дал правильное (как выяснилось позднее) ключевое слово — «редиска».

Перестановка алфавита

Имея ключевое слово, мы можем модифицировать текст так, что он окажется зашифрован шифром простой замены. Для этого необходимо циклически сдвинуть символы L-ой группы (L = 2, 3, . длина ключа) на дистанцию между первой и L-ой буквами ключевого слова влево по алфавиту. После внесения этих изменений нам остается найти, какие буквы исходного текста соответствуют символам шифротекста.
Попробуем сделать это тем же способом, каким мы искали ключевое слово без словаря. Возьмем любую таблицу соответствий между символами исходного и зашифрованного текстов (например, предположим, что букве ‘а’ соответствует буква ‘а’, букве ‘б’ — ‘б’, и т. д.) и расшифруем текст с её помощью. Посчитаем количество всевозможных биграмм (сочетаний по 2 буквы) в полученном тексте. Сравнив результат с эталонной таблицей, вычислим характеристику полученного текста (я вычислял характеристику так:

(b_ij — количество биграмм в «расшифрованном» тексте, а p_ij — вероятность встречи определенной биграммы в русском языке)

Затем будем вносить случайные изменения в таблицу соответствий и на каждом шаге вычислять новую характеристику. Если новая характеристика оказывается лучше (больше) старой, запоминаем изменения, иначе откатываем их. В результате у нас получается правильная таблица соответствий букв, и мы можем восстановить исходный текст!

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

Также интересно взглянуть на графики зависимости номера итерации от номера успешного изменения таблицы перестановок (слева) и характеристики текста от номера изменения таблицы (справа).

Мы видим, что характеристика текста изменяется с каждым изменением таблицы перестановок более-менее линейно, а число попыток, необходимых для нахождения нового успешного изменения таблицы растет довольно быстро. Зависимость характеристики текста от числа итераций похожа на логарифмическую. Действительно, по нижним графикам видно, что если x — число итераций, y — характеристика и t — номер успешного изменения таблицы, то x∼e^t, y∼t, следовательно, y∼ln(x). Логарифм растет довольно медленно, но его рост не ограничен асимптотами, поэтому на нахождение правильной таблицы соответствий уходит довольно большое, но не бесконечное количество работы. Впрочем, тесты показывают, что 10 — 12 тысяч итераций всегда достаточно.

Заключение

После реализации описанных алгоритмов и добавления графического интерфейса получилась вот такая программа:

Программа успешно расшифровывает тексты длиной 400-500 символов и больше, время работы не превышает 10 секунд. Я думаю, это неплохой результат.

UPD Вот ссылка на мою программу. Я делал её в Visual Studio 2012 и использовал Windows Forms, так что перед запуском убедитесь, что у вас установлен соответствующий распространяемый пакет и .net Framework 4. В программе можно зашифровать текст (для этого введите текст в верхнюю часть формы и ключевое слово; если ключевое слово не будет введено, оно будет выбрано случайным образом) или взломать шифр (для этого введите шифротекст и нажмите «Взлом!»; если при этом будут указаны длина ключевого слова или само ключевое слово, эти данные будут использованы для расшифровки, в противном случае программа подберет их сама).