Взлом шифра Виженера

Общие сведения о шифре Виженера

Шифр Виженера, по сути, был изобретен несколько раз. Впервые данный метод был описан Джованом Баттистой Беллазо в его книге, выпущенной в 1553 году. Тем не менее, в девятнадцатом веке он был назван именем Блеза Виженера, который был французским дипломатом. Метод является простым для понимания и реализации, и его невозможно взломать при помощи простых методик криптографического анализа.

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

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

ATTACKATDAWN

Пользователь, который посылает сообщение, должен записать ключевое слово, например, «LEMON» циклически до тех пор, пока его длина не сравняется с длиной исходного текста:

LEMONLEMONLE

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

1. Исходный текст: ATTACKATDAWN.
2. Используемый ключ: LEMONLEMONLE.
3. Шифрованный текст: LXFOPVEFRNHR.

Расшифровка должна производиться следующим образом:

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

Взлом шифра Виженера

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

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

Тесты Фридмана и Касиски способны оказать помощь в определении длины ключа. В 1863-ем году Фридрих Касиски стал первым, кто сделал публикацию успешного алгоритма атаки на шифр Виженера. Но следует отметить, что Чарльз Беббидж создал данный алгоритм еще в 1854-ом году. В то время когда Беббидж пытался взломать шифр Виженера, Джон Холл Брок Твейтс предложил новый шифр в «Journal of the Society of the Arts». А когда Беббидж доказал, что шифр Твейтса представляет собой только частный случай шифра Виженера, Твейтс предложил ему его взломать. Беббидж сумел расшифровать текст, который оказался поэмой «The Vision of Sin» Альфреда Теннисона, зашифрованной при помощи ключевого слова Emily. Это было имя жены поэта.

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

1. Ключ: ABCDEF AB CDEFA BCD EFABCDEFABCD.
2. Исходный текст: CRYPTO IS SHORT FOR CRYPTOGRAPHY.
3. Зашифрованный текст: CSASXT IT UKSWT GQU GWYQVRKWAQJB.

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

1. Ключ: ABCDAB CD ABCDA BCD ABCDABCDABCD.
2. Исходный текст: CRYPTO IS SHORT FOR CRYPTOGRAPHY.
3. Зашифрованный текст: CSASTP KV SIQUT GQU CSASTPIUAQJB.

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

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

Рисунок 1.

Наблюдения за частотой совпадения показали, что:

Рисунок 2.

где :

• С является размером алфавита,
• N является длинной текста,
• ni является наблюдаемыми частотами повторения символов зашифрованного текста.