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

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

Пример 4.1

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

MEETING WILL BE ON FRIDAY AT ELEVEN THIRTY

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

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

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

Таблица 4.1

Итак, выпишем ключ, а под ним нарисуем таблицу для записи текста из 5 столбцов и 7 строк. Впишем сообщение в таблицу построчно, начиная с верхней строки и опуская при этом пробелы между словами (см. таблицу 4.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 букв. Если записать текст таким образом, велика вероятность того, что буквы, стоящие рядом в открытом тексте, окажутся в одной строке. Записанный таким образом шифрованный текст примет вид, показанный в таблице 4.2.

Таблица 4.2

Следующий шаг - проанализировать различные пары букв в каждой строке, чтобы определить среди них наиболее вероятные диграфы. В этом деле серьезным подспорьем оказывается наличие таблицы частот встречаемости диграфов английского языка. Такие таблицы можно найти в своде, опубликованном Университетом имени Брауна (см. [2.2]), и в различных книгах по криптографии. Например, мы находим, что в первой строке вышеприведенной таблицы 4.2 пары ME, TI и ET более употребительны, чем другие. Такой анализ нужно провести по каждой строке и отметить связанные между собой факты. Так, если в первой строке буква T на самом деле стоит перед буквой I, то столбец 2 должен стоять слева от столбца 4. Выполняя это упражнение для каждой строки, криптоаналитик надеется найти подтверждение своим предположениям и, таким образом, восстановить перестановочную таблицу и получить исходный текст. Не каждая связь будет правильной, некоторые будут противоречить друг другу; но есть надежда, что будет найдено достаточное число истинных связей, чтобы отсеять ложные. Доказательством тому является таблица 4.3.

Таблица 4.3

Хотя в таблице есть некоторые противоречия, некоторые связи между столбцами возникают достаточно часто, чтобы заслужить дальнейшего рассмотрения. К таким относятся пары столбцов:

1-5, 2-4, 3-1 и 5-2.

Если теперь мы упорядочим столбцы шифрованного текста, как подсказывают эти пары, начиная с третьего столбца (нам придется опробовать и другие столбцы в качестве начального), мы увидим, что шифрованный текст следует перегруппировать так, что столбцы шифрованного текста

3-1-5-2-4

станут столбцами

1-2-3-4-5

открытого текста, а первая строка шифрованного текста

E T M I E

становится строкой открытого текста

M E E T I.

Аналогично, вторая строка шифрованного текста

G I N L W

превращается в

N G W I L,

и получение оставшейся части сообщения подтверждает правильность дешифрования.

Мы привели очень простой пример: ключ был короткий, его длина была очевидна и найдена с первой попытки. Однако это хорошая иллюстрация метода вскрытия. Этим примером мы также показали, что наличие таблицы частот диграфов, хотя и не является непременным условием, но способно значительно облегчить решение задачи. Если бы длина шифрованного текста не была кратна 5, то для длины ключа возможное равенство 5 (или 7, как в данном случае) не так бросалось бы в глаза, и пришлось бы перебирать и другие значения длины ключа. Для ключей, имеющих длину не больше 5, возможно даже применение метода "грубой силы", так как число возможных перестановок столбцов весьма невелико (всего 120 для длины ключа 5). Если длина ключа превышает число 5, то использование метода полного перебора становится весьма трудоемким, и вручную практически невыполнимо, тогда как описанный выше "метод диграфов" можно реализовать для любой длины ключа, которая может встретиться на практике. Зная все это, криптограф попытается как можно тщательнее замаскировать длину ключа. Он может также прибегнуть и к другим мерам, таким как