Шифры перестановок. Шифровка и дешифровка исходного текста методом перестановки (Лабораторная работа № 5)

Лабораторная работа № 5

Шифры перестановок

Цель работы:

Научиться шифровать и дешифровать исходный текст методом перестановки.

Постановка задачи:

Разработать приложение, реализующее один из простейших шифров перестановки.

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

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

Простая перестановка

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

Пример 1

Зашифровать сообщение

MEETING WILL BE ON FRIDAY AT ELEVEN THIRTY

с помощью шифра перестановки с ключом длины 5 вида: 3-1-5-2-4.

Зашифрование

Опуская пробелы между словами, получим текст из 35 букв. Поскольку длина ключа равна 5, нам понадобится таблица из 5 столбцов и 7 строк.

Таблица 1

Итак, выпишем ключ, а под ним нарисуем таблицу для записи текста из 5 столбцов и 7 строк. Впишем сообщение в таблицу построчно, начиная с верхней строки и опуская при этом пробелы между словами (см. таблицу 1). Наконец, выписывая текст из таблицы по столбцам в порядке, заданном ключом, получим шифрованный текст, который запишем в виде серии 5-значных групп:

EGBRA VITIO DENTM NLFYE HILNA LTYEW EITER.

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

Расшифрование

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

Метод дешифрования

Каким бы простым ни был шифр перестановки, может оказаться, что вскрыть его вовсе не так просто. Подсчет частот встречаемости отдельных букв ("монографов") показывает, что они не изменились, но частоты пар букв ("диграфов"), таких как TH, HE и QU, будут отличны от ожидаемой частоты их встречаемости в английском тексте. По этой причине криптоаналитик заподозрит использование шифра перестановки. При попытке дешифрования такой системы его первая задача - определить длину ключа.

Поскольку длина вышеприведенного сообщения составляет 35 букв, получается 7 полных групп по пять букв в каждой. Криптоаналитик не знает, была ли длина исходного сообщения равна 35, или же оно было дополнено буквами-"пустышками" для получения полных пятизначных групп шифрованного текста. Однако в любом из этих случаев это является возможной подсказкой относительно длины ключа. Так как 35=5´7, то стоит проанализировать шифрованный текст в предположении, что длина ключа равна 5 или 7. Криптоаналитик предполагает, что перестановочная таблица имеет "правильную" форму, то есть, что все столбцы имеют одинаковую длину - это может быть и неверно, но начать с этого было бы логично.

Предположим, что ключ действительно имеет длину 5. Тогда две буквы, стоящие рядом в исходном сообщении, в шифрованном тексте будут отстоять друг от друга на 7, 14, 21 или 28 позиций, если только одна из них не находится в конце одной строки, а другая - в начале следующей строки. Поэтому криптоаналитик вписывает шифрованный текст в 5 столбцов по 7 букв. Если записать текст таким образом, велика вероятность того, что буквы, стоящие рядом в открытом тексте, окажутся в одной строке. Записанный таким образом шифрованный текст примет вид, показанный в таблице 2.