Шифры перестановки. Шифрующие таблицы

При шифровании перестановкой символы шифруемого текста пере­ставляются по определенному правилу в пределах блока этого текста. Шифры перестановки являются самыми про­стыми и, вероятно, самыми древними шифрами.

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

С начала эпохи Возрождения (конец XIV столетия) начала возрож­даться и криптография. В разработанных шифрах перестановки того времени применяются шифрующие таблицы, которые, в сущности, задают правила перестановки букв в сообщении. В качестве ключа в шифрующих таблицах используются:

• размер таблицы;

• слово или фраза, задающие перестановку;

• особенности структуры таблицы.

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

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

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

Пример. Зашифруем сообщение:

ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ

с помощью таблицы 5х7 и ключевого слова «ПЕЛИКАН»:

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

ГНВЕП ЛТООА ДРНЕВ ТЕЬИО РПОТМ БЧМОР СОЫЬИ

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

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

Пример. Ниже приведен один из вариантов магического квадрата размером 4х4. Зашифруем с его помощью сообщение:

ПРИЛЕТАЮ ВОСЬМОГО

Шифртекст, получаемый при считывании содержим правой таблицы по строкам, имеет вполне загадочный вид:   

ОИРМ ЕОСЮ ВТАЬ ЛГОП.

Число магических квадратовбыстро возрастает с увеличением раз­ме­ра квадрата. Существует только один магический квадрат размером 3х3 (ес­ли не учитывать его повороты). Количество магических квадратов 4х4 состав­ляет уже 880, а количество магических квадратов 5х5 – около 250000. Магические квадраты средних и больших размеров могли слу­жить хорошей базой для обеспечения нужд шифрования того времени, поскольку практически нереально выполнить вручную пepe6op всех вариантов для такого шифра.

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

Число вариантов двойной перестановки быстро возрастает при увеличении размера таблицы. Однако и двойная перестановка не отличается высокой стойкостью и сравнительно просто "взламывается" при любом размере таблицы шифрования.

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

К шифрам перестановки относится и шифр Кардано. В середине ХVI века итальянским математиком Кардано была выдвинута идея исполь­зова­ния части самого передаваемого открытого текста в качестве ключа и новый способ шифрования, получивший название «решетка Кардано». Для ее изготовления берется квадратный кусок картона, в котором по специ­а­ль­ным правилам прорезаются «окна». При шифровании решетка накла­ды­ва­лась на лист бумаги, и открытый текст вписывался в окна. Затем ре­шетка поворачивалась на 90 градусов, и вновь вписывался текст, всего 4 раза.

Главное требование к «решетке Кардано» – при всех поворотах окна не должны попадать на одно и то же место бумаги. Пустые места заполнялись произвольными буквами, затем шифрограмма выписывалась построчно. Решетка Кардано позволяет осуществлять перестановку букв достаточно быстро.

Как математик, Кардано сумел вычислить количество квадратов-решеток (ключей) заданного размера N x N. Если N – четное число, то это количество равно . При N =10 оно имеет порядок десять в пятнадцатой степени.