5.3. Методы перестановки

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

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

Шифрование по методу двойной транспозиции включает следующие шаги.

1 шаг. Определение длины блока и, соответственно длин ключей шифрования. При определении длины блока следует учитывать, что последний блок текста, как правило, содержит символов меньше, чем все другие блоки и в соответствии с методом недостающие позиции заполняются каким-либо одним произвольным символом, что увеличивает возможность раскрытия кода. Следовательно, целесообразно длину блока определять таким образом, чтобы в последнем блоке как можно меньше недоставало символов. Так, например, если длина текста 2342 символа, а длина ключей не должна быть меньше 8 и больше 11, то целесообразно выбрать ключи, длина каждого из которых равна 9. При этом в последнем блоке будет недоставать всего 7 символов. Если же длина текста 7564 символов, то при таких же ограничениях на длину ключей, оптимальный вариант, когда длина одного ключа будет равна 8, а длина другого – 11. При этом в последнем блоке будет недоставать всего 4 символа.

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

Пусть Т₀ – исходный текст. Получим Т_i такие, что , где k – количество блоков.

3 шаг. Определение значений ключей. Каждый ключ, длиною k содержит в произвольном порядке неповторяющиеся числа от 1 до k. Например, ключ длиною 8 символов может быть следующим:

3

7

5

1

8

4

2

6

Очевидно, что для матрицы размерностью m´n количество всевозможных пар ключей будет составлять m!n! (следует напомнить, что количество перестановок определяется по формуле: P_n=n!). Таким образом, например, для ключей, длина каждого из которых – 8 (длина блока 64 символа) возможно 8!8!=40320  40320=1625702400 пар ключей. В такой ситуации, когда криптоанализ сводится к поиску значений ключей, даже при использовании современных ЭВМ определение ключей шифрования путем перебора представляет некоторую сложность: требует значительного времени. Расшифровка кода становиться еще более сложной, если длины ключей неизвестны. Для матрицы размерностью 16´16 (длина блока 256 символов) поиск ключей методом перебор даже с помощью современных средств весьма затруднителен.

4 шаг. Предварительно заметим, что данный шаг будет повторяться столько раз, сколько получилось блоков. С каждым блоком текста необходимо выполнить следующие действия. Сначала текст записывается построчно в матрицу в соответствии со значением первого ключа. Первые n символов блока записываются в строку, с номером соответствующим числу, которое стоит на первом месте в первом ключе. Вторые n символов блока записываются в строку, с номером, соответствующим числу, которое стоит на втором месте в первом ключе. Аналогичным образом необходимо поступить со всеми последующими группами символов данного блока. Затем необходимо склеить строку (по m символов), считывая символы из таблицы по столбцам в соответствии со вторым ключом. Первыми будут m символов, которые стоят в столбце с номером, соответствующим числу, находящимся на первом месте во втором ключе. К ним следует приклеить m символов из столбца, номер которого соответствует числу, находящимся на втором месте во втором ключе. Аналогичным образом считываются и приклеиваются к строке все остальные символы.

При выполнении описанных операций с каждым блоком каждый раз получаем , такое, что + + …+ = , где и есть закодированный текст.

Продемонстрируем применение этого метода на конкретном примере. Пусть имеется следующий текст.

Т₀ = ИЗВЕСТНА ОДНА ЗАМЕЧАТЕЛЬНАЯ ОСОБЕННОСТЬ ПОВЕДЕНИЯ ГОЛУБЕЙ – ВЕЛИКОЛЕПНАЯ ОРИЕНТАЦИЯ И УМЕНИЕ ВЕРНУТЬСЯ ИЗ ЛЮБОГО МЕСТА КОРМЕЖКИ ИЛИ ВОДОПОЯ. ЭТА ОСОБЕННОСТЬ И ПОСЛУЖИЛА ПРИЧИНОЙ ОДОМАШНИВАНИЯ ГОЛУБЯ.

1 шаг. В этом тексте 199 символов. Если мы ограничим выбор ключей их длиной (например, от 4 до 7), но оптимальными для данного текста будут ключи с длинами – либо 4 и 5, либо 5 и 5. В этих случаях в последнем блоке будет недоставать всего одного символов. Очевидно, что из представленных пар целесообразно выбрать последнюю. Таким образом, длина блока будет равна 25.

2 шаг. Теперь разобьем текст на блоки, а для удобства заменим пробелы подчеркиванием.

Т₁ = ИЗВЕСТНА_ОДНА_ЗАМЕЧАТЕЛЬН

Т₂ = АЯ_ОСОБЕННОСТЬ_ПОВЕДЕНИЯ_

Т₃ = ГОЛУБЕЙ_–_ВЕЛИКОЛЕПНАЯ_ОР

Т₄ = ИЕНТАЦИЯ_И_УМЕНИЕ_ВЕРНУТЬ

Т₅ = СЯ_ИЗ_ЛЮБОГО_МЕСТА_КОРМЕЖ

Т₆ = КИ_ИЛИ_ВОДОПОЯ._ЭТА_ОСОБЕ

Т₇ = ННОСТЬ_И_ПОСЛУЖИЛА_ПРИЧИН

Т₈ = ОЙ_ОДОМАШНИВАНИЯ_ГОЛУБЯ.Р

3 шаг. Выберем ключи.

k1 =

3

5

1

4

2

k2 =

2

4

3

5

1

4 шаг. Зашифруем с помощью ключей и матрицы первый блок ткста. Заметим, что первые 5 символов первого блока необходимо записать в матрицу в третью строку (первое число первого ключа равно 3). Вторые 5 символов первого блока необходимо записать в матрицу в пятую строку. Матрица будет заполнена так, как показано на рисунке (рис_).

3		Д	Н	А	_	З
5		Т	Е	Л	Ь	Н
1		И	З	В	Е	С
4		А	М	Е	Ч	А
2		Т	Н	А	_	О
		2	4	3	5	1

Теперь в соответствии с ключом k₂ получим закодированный текст первого блока, выписывая текст из матрицы по столбцам (сначала из второго столбца, затем из четвертого и т.д.)

= НЕЗМН_ЬЕЧ_АЛВЕАЗНСАОДТИАТ

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

= НЕЗМН ЬЕЧ АЛВЕАЗНСАОДТИАТСОЯНБЬЕОЯНТВ ИЕ ДС НОПАЕОЕЯОЛЙИОУП-Л ЛЕ КРБН ВАГОЕУНЕЕИЕТТВ МУН ЯНЬАЕИОРЯТЛМЕИ Б М АЮЕЖЗКОГОСС ПСИ ЯБИТООО ЭВ ЕЛАДЩЩК.ИСИНЛ УИС ЛЧОАИЖНТППОРНИЬВБЙ МН.ООШАЯ ГА ИРДЛНИУОЯО

Безусловно, найти какие-либо закономерности в данном коде достаточно сложно. Криптоанализ сводится к определению метода шифрования и подбору ключа. Существует немало методов достаточно похожих на метод двойной транспозиции. К ним относится следующий метод шифрования данных.

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

Метод во многом напоминает предыдущий: сначала необходимо разбить текст на блоки, длина которых равна n*n, где n – длина стороны квадрата (измеряемая в клетках), затем по определенному правилу занести символы блока в квадрат, а затем построчно считать и склеить в строку. Так поступить с каждым блоком текста.

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

Очевидно, что криптоанализ сводится к поиску магического квадрата. Здесь следует помнить, что число магических квадратов быстро возрастает с увеличением размера квадрата. Существует только один магический квадрат размером 3´3 (если не учитывать его повороты). Количество магических квадратов 4´4 составляет уже 880, а количество магических квадратов 5´5, как отмечают многие специалисты, – около 250000 [31, 42].

Для методов перестановки характерны простота алгоритма, возможность программной реализации и низкий уровень криптостойкости, так как при большой длине исходного текста в шифрованном тексте проявляются статистические закономерности ключа, что и позволяет его быстро раскрыть. Другой недостаток этих методов – легкое раскрытие, если удается направить в систему для шифрования несколько специально подобранных сообщений. Так, если длина блока в исходном тексте равна k символам, то для раскрытия ключа достаточно пропустить через систему шифрования k-1 блоков исходного текста, в которых все символы, кроме одного одинаковы.