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

Helgus ~ µастер ~ Kласс: Это незавершённая статья по ивентологии и её применениям

Шифр перестановки один из самых старых и часто встречаемых методов шифрования.

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

Примеры перестановок

Самая простая перестановка — написать исходный текст задом наперед и одновременно разбить шифрограмму на группы из нескольких букв. Пусть группа состоит из пяти букв. Например, из фразы

ПУСТЬ БУДЕТ ТАК, КАК МЫ ХОТЕЛИ

получится такой шифротекст:

ИЛЕТО ХЫМКА ККАТТ ЕДУБЪ ТСУП

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

ПУСТЬ-БУДЕТ-ТАККА-КМЫХО-ТЕЛИО.

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

ОИЛЕТ ОХЫМК АККАТ ТЕДУБ ЬТСУП

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

Во время Гражданской войны в США в ходу был такой шифр: исходную фразу писали в несколько строк. Например, по пятнадцать букв в каждой (с заполнением последней строки незначащими буквами).

П У С Т Ь Б У Д Е Т Т А К К А

К М Ы Х О Т Е Л И К Л М Н О П

После этого вертикальные столбцы по порядку писали в строку с разбивкой на пятерки букв:

ПКУМС ЫТХЬО БТУЕД ЛЕИТК ТЛАМК НКОАП [1].

Книжный шифр

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

Книжный шифр в современном варианте имеет несколько другой вид. Суть этого шифра состоит в замене букв на номер строки и номер этой буквы в строке в заранее оговоренной странице некоторой книги. Ключом такого шифра является книга и используемая страница в ней. Этот шифр оказался «долгожителем» и применялся даже во времена второй мировой войны.

На экране:

$i_1$ $i_2$ $i_3$ $i_4$ $i_5 <math>i_6$

М О С К В А

$i_5$ $i_2$ $i_3$ $i_1$ $i_4$ $i_6$

К О С В М А

Для расшифровки сообщения надо поменять строки в таблице местами и поставить в порядке возрастания числа

$i_1$ $i_2$ $i_3$ $i_4$ $i_5$ $i_6$

И Ч Е У Н К

$i_4$ $i_2$ $i_3$ $i_5$ $i_1$ $i_6$

У Ч Е Н И К [2].

Очевидно, что в данном примере существует $P_6 = 6! = 720$ возможных вариантов заполнения нижней строки.

Маршрутная перестановка

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

Например, можно вписывать исходное сообщение в прямоугольную таблицу, выбрав такой маршрут: по горизонтали, начиная с левого верхнего угла поочередно слева направо и справа налево. Выписывать же сообщение будем по другому маршруту: по вертикали, начиная с верхнего правого угла и двигаясь поочередно сверху вниз и снизу вверх [2]

Зашифруем, например, указанным способом фразу:

ПРИМЕРМАРШРУТНОЙПЕРЕСТАНОВКИ

используя прямоугольник размера четыре на семь:

П	Р	И	М	Е	Р	М
Н	Т	У	Р	Ш	Р	А
О	Й	П	Е	Р	Е	С
И	К	В	О	Н	А	Т

Зашифрованная фраза выглядит так:

МАСТАЕРРЕШРНОЕРМИУПВКЙТРПНОИ

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

В данном примере видно, что шифр состоит из двух перестановок:

• выбор маршрута, как вписывать сообщение в таблицу;

• выбор маршрута, записи шифр текста.

Так как можно произвольно вписывать буквы сообщения в таблицу, то мы получим маршрутов P(28)=28! в первой перестановке.

Во второй тоже 28!.

И в итоге получаем $28!*28!=(28!)^2$ вариантов шифрования одного сообщения. Но какое бы ни было число вариантов, шифр можно взломать.

Пример: Расшифровать АЗЮЖЕ СШГГООИПЕР

Пусть имеется шифровка АЗЮЖЕ СШГГООИПЕР, сообщение состоит из 16 символов включая пробел. Составим таблицу 4 на 4, и впишем в нее наше сообщение

	1	2	3	4
1	A	З	Ю	Ж
2	E		С	Ш
3	Г	T	О	О
4	И	П	E	P

Рассматривая маловероятные сочетания букв, легко найти истинную последовательность столбцов. Так, сочетание ГТ в 3 строке шифровки указывает на то, что после 1 столбца вряд ли следует 2 столбец. Рассчитаем статистически, какой столбец, скорее всего, следует за 1. Для этого воспользуемся таблицей логарифмов вероятностей пар букв (биграмм) русского текста.

Таблица логарифмов вероятностей биграмм русского текста

	А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	П	Т	Ь	Ы	Ь	Э	Ю	Я	Процент
А	2	7	8	6	7	7	7	7	4	7	7	7	8	8	3	7	6	7	8	2	6	6	7	7	5	5	0	0	0	0	6	7	9	71
Б	7	1	1	0	1	6	2	2	6	0	5	6	3	5	7	2	7	5	0	7	0	5	4	1	0	5	5	7	2	2	0	3	5	13
В	8	0	5	0	4	8	0	3	7	1	6	7	5	6	8	4	6	6	6	6	0	3	0	1	3	0	0	8	2	0	0	4	8	38
Г	6	0	1	1	6	5	0	0	6	0	4	5	4	4	8	0	7	0	0	6	0	0	1	2	0	0	0	0	0	0	0	0	4	10
Д	8	1	6	3	4	8	1	0		0	4	7	1	7	8	4	6	5	2	7	1	3	3	3	4	0	0	6	4	0	4	5	7	25
Е	5	5	6	7	8	6	6	6	4	7	7	8	8	9	6	5	8	8	9	3	3	6	5	6	5	6	0	0	1	1	5	5	9	73
Ж	6	0	0	0	6	7	2	1	7	0	5	0	2	7	1	0	1	2	1	3	0	0	0	0	0	0	0	0	2	0	0	0	2	8
3	8	4	6	2	6	4	1	1	6	1	5	5	6	6	7	1	5	0	0	6	0	0	2	1	0	0	2	6	2	0	0	4	6	14
И	6	6	7	6	6	8	5	7	7	7	7	6	8	8	5	5	7	8	8	1	5	7	7	7	6	3	0	1	0	0	6	7	9	64
Й	0	0	3	0	3	0	0	0	0	0	3	6	5	4	0	0	0	6	6	0	0	0	1	2	3	0	0	0	0	0	0	0	8	11
К	8	1	5	1	1	6	5	2	7	1	2	7	0	5	8	0	7	6	6	7	0	0	6	0	1	0	0	0	0	0	0	0	7	29
Л	8	4	1	2	1	8	6	1	8	0	4	4	1	6	7	0	0	3	3	6	3	0	0	3	1	1	0	6	8	0	7	8	6	31
М	7	5	7	2	2	8	0	1	7	0	4	4	7	6	8	5	1	3	1	6	1	0	0	0	0	0	0	7	3	0	0	6	8	32
Н	9	0	3	3	6	8	1	1	9	0	6	0	1	7	8	0	0	5	7	6	5	2	5	3	0	0	0	8	5	0	4	6	7	50
О	2	8	8	8	8	6	7	7	6	8	7	8	8	7	6	7	8	8	8	3	2	5	6	7	6	5	0	0	1	5	2	5	9	89
П	7	0	0	0	0	8	0	4	7	0	3	6	1	4	8	4	9	4	5	6	2	0	1	0	0	0	0	4	5	3	0	4	4	28
Р	9	1	6	4	4	8	6	0	8	0	5	2	6	6	8	4	2	6	6	7	3	5	4	2	4	2	0	7	4	0	1	6	7	48
С	6	4	6	2	5	7	2	0	7	0	7	8	6	6	8	7	5	6	9	6	3	5	1	5	5	0	0	5	6	1	3	8	7	43
Т	8	2	7	1	4	8	0	0	8	0	6	4	5	6	9	3	8	8	4	6	0	0	0	4	0	2	1	7	8	0	1	5	8	60
У	3	4	4	6	6	7	6	5	3	3	6	5	5	6	0	6	7	7	7	1	5	5	0	6	3	6	0	0	0	0	7	4	8	19
Ф	6	0	0	0	0	5	0	0	6	0	0	2	2	0	6	0	4	0	3	5	4	0	0	0	0	0	0	1	0	0	0	0	2	4
Х	4	3	3	0	0	4	0	0	3	0	1	1	0	5	6	0	5	3	1	3	0	0	2	0	0	0	1	0	0	0	0	0	8	6
Ц	5	0	6	0	0	6	0	0	7	0	0	0	0	0	3	0	0	0	0	4	0	0	0	0	0	0	0	5	0	0	0	0	5	6
Ч	7	0	1	0	0	8	0	0	7	0	6	1	0	6	2	0	1	0	7	3	0	0	0	1	3	0	0	1	3	0	0	0	4	12
Ш	5	0	0	0	0	6	0	0	7	0	3	3	0	3	4	0	3	0	3	4	0	0	0	0	0	0	0	0	4	0	0	0	5	3
Щ	6	0	0	0	0	7	0	0	6	0	0	0	0	2	0	0	2	0	0	4	0	0	0	0	0	0	0	0	4	0	1	0	1	3
Ъ	0	0	0	0	0	4	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	32	1
Ы	1	4	7	3	5	7	1	5	1	7	5	5	6	2	1	5	5	5	6	0	0	7	0	5	4	1	0	1	0	0	0	1	8	18
Ь	0	1	0	0	0	3	0	7	1	0	6	0	4	7	1	0	0	6	4	0	0	0	0	1	6	1	0	0	0	0	6	2	8	12
Э	0	0	4	0	0	1	0	0	0	2	6	5	2	1	0	2	0	1	7	0	4	3	0	0	0	0	0	0	0	0	0	0	1	4
Ю	0	5	0	0	2	0	1	2	0	4	1	0	0	0	0	0	0	3	7	0	0	0	0	6	1	7	0	0	1	0	3	0	7	6
Я	0	1	5	2	5	6	2	5	0	2	2	3	6	5	0	1	4	4	7	0	0	4	4	3	0	4	0	0	0	0	6	4	9	18
	7	8	9	7	8	7	5	8	8	3	8	6	8	9	9	9	8	9	8	7	7	6	7	8	5	1	1	2	1	8	2	6	0	138

Вероятность следования одного столбца за другим равна произведению вероятностей биграмм в строках этих столбцов. Поскольку в таблице даны логарифмы биграмм, то их достаточно суммировать, а потом выбрать сочетание столбцов с максимальной вероятностью. Для вероятностей следования за первым столбцом 2, 3 и 4 имеем выражения:

р (1-2) =р(A3) р(Е ) р(ГТ) р(ИП)=7+9+0+5=21

р (1-3) =р(АЮ) р(ЕС) р(ГО) р(ИЕ)=6+8+8+8=30

р (1-4 )=р(АЖ) р(ЕШ) р(ГО) р(ЯР)=7+5+8+7=27

В нашем случае наиболее вероятно, что после столбца 1 следует столбец 3, их вероятность наибольшая. Для такой небольшой таблицы шифрования, которую имеем, можно перебрать все варианты перестановок - их всего лишь 24. В случае большого числа столбцов целесообразно оценить вероятности пар сочетаний разных столбцов и решить оптимизационную задачу, которая укажет перестановку столбцов, дающую фрагменты естественного текста с большей вероятностью. В нашем случае наилучший результат достигается при расстановке столбцов (2413), что примерно вдвое по вероятностной оценке достовернее ближайшей к ней по вероятности расстановки (4132). После того, как столбцы шифровки расставлены, не составит труда правильно расставить и ее строки по смыслу фрагментов текста:

Сообщение после обратной перестановки

	2	4	1	3
1	З	Ж	A	Ю
2	_	Ш	E	С
3	T	О	Г	О
4	П	P	И	E

Текст в ней уже читается и, расставив строки в порядке (4123), получим расшифровку ПРИЕЗЖАЮ ШЕСТОГО.

Литература

1. Бабаш А.В., Шанкин Г.П. Криптография: аспекты защиты. М.: Солон – Р, 2002.

2. Ященко В.В., ред. Введение в криптографию. М: МЦНМО, 2000

См.также

• Криптография

---

Nomaan 10:57, 17 августа 2008 (UTC)