Полиалфавитный шифр

Исторические сведения

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

Шифровальная машина Энигма

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

Благодаря работе Ал-Кинди оказалось, что шифры типа «Шифра Цезаря» (то есть моноалфавитные шифры, в которых каждой букве кодируемого текста ставится в соответствие однозначно какая-то шифрованная буква) довольно-таки легко поддаются частотному криптоанализу. Возникла потребность в разработке таких шифров, ручная расшифровка которых может потребовать очень значительных усилий. И на смену моноалфавитным шифрам пришли полиалфавитные шифры. Абу аль-Кинди первым предложил использовать многоалфавитный шифр. В европейских странах это произошло в эпоху Возрождения, когда развитие торговли потребовало надёжные способы защиты информации. Одним из первых предложил полиалфавитный шифр итальянский архитектор Батисте Альберти. Впоследствии данный шифр получил имя дипломата XVI века Блеза де Вижинера. Также вклад в развитие полиалфавитных шифров внёс немецкий аббат XVI века Иоганн Трисемус. Простым, но стойким способом полиалфавитной замены является шифр Плейфера, открытый в начале XIX века Чарльзом Уитстоном. Этот шифр использовался вплоть до I мировой войны. Последним словом в развитии полиалфавитных шифров стали так называемые роторные машины, которые позволяли легко создавать устойчивые к криптоатакам полиалфавитные шифры. Примером такой машины является немецкая машина Enigma, разработанная в 1917 г. Эдвардом Хеберном.

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

Полиалфавитные шифры: суть подхода к шифрованию

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

Суть полиалфавитного шифра заключается в циклическом применении нескольких моноалфавитных шифров к определённому числу букв шифруемого текста. Например, пусть у нас имеется некоторое сообщение x₁ , x₂ , x₃ , ….. x_n , …… x_2n , ….., которое надо зашифровать. При использовании полиалфавитного шифра имеется несколько моноалфавитных шифров (например, n штук). И в нашем случае к первой букве применяется первый моноалфавитный шифр, ко второй букве — второй, к третьей — третий….. к n-ой букве — n-й, а к n+1 опять первый, ну и так далее. Таким образом, получаётся довольно-таки сложная последовательность, которую уже не так просто вскрыть, как один моноалфавитный шифр. Самым важным эффектом, достигаемым при использовании полиалфавитного шифра, является маскировка частот появления тех или иных букв в тексте, на основании которой обычно очень легко вскрываются моноалфавитные шифры.

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

Подробнее см. Шифр Виженера

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

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

Берём первую букву и смотрим, какая буква ключа находится над ней, а затем полученную букву ключа находим в первом столбце квадрата Виженера, а шифруемую букву в первой строке, затем смотрим, какая буква находится на пересечении полученной строки и столбца — она и будет зашифрованной буквой:

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

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

Расшифровывание текста, зашифрованного шифром Виженера, происходит абсолютно аналогично шифрованию.

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

Ещё одним примером полиалфавитного шифра является шифр Гронсфельда. Здесь, в отличие от предыдущего случая, используется числовой ключ, а сама схема очень напоминает шифр Цезаря. Пусть нам надо зашифровать слово EXALTATION. Например, берём в качестве ключа число 31415, затем составляем следующую таблицу:

Получается, что каждой букве соответствует некая цифра, это цифра будет показывать, на сколько позиций будет происходить смещение алфавита для каждой конкретной буквы. Например, покажем, как преобразуется буква E:

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

Взлом полиалфавитных шифров

Проще всего взломать полиалфавитный шифр, зная его период, то есть число используемых моноалфавитных шифров. Тогда, выбрав буквы, соответствующие каждому из моноалфавитных шифров, можно к каждому из них применить так называемый частотный анализ (или какой-нибудь другой метод взлома моноалфавитных шифров), основанный на том, что каждая буква в произвольном тексте появляется с вполне определённой частотой, а значит, посмотрев частоты появления тех или иных букв, можно узнать, как происходит замена. Одним из методов нахождения периода полиалфавитных шифров является метод, предложенный Фредериком Касиски в 1836 году. Он заключается в том, что в зашифрованном тексте находятся одинаковые сегменты длины не меньше, чем три буквы, затем вычисляются расстояния между первыми буквами соседних сегментов. Оказывается, предполагаемый период является кратным наибольшему общему делителю для этих расстояний.

Литература

• А. В. Яковлев, А. А. Безбогов, В. В. Родин, В. Н. Шамкин «Криптографическая защита информации».
• Э. М. Габидулин «Курс лекций по Защите Информации»
• А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черёмушкин «Основы криптографии»

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