Информационная безопасность / Информационная безопасность2006

Перестановка по маршрутам Гамильтона.

Такая сравнительно простая перестановка является по оценкам американских специалистов достаточно стойким шифром.

Исходный текст разбивается на группы по 8 букв. 1-ая операция — вписывание исходного текста в шаблон с 8-ю знакоместами с указанным на них порядком вписывания. Например текст «ШИФРУЙТЕ ПЕРЕСТАНОВКАМИ» вписываем без пробелов, а конец текст дополним до полноты шаблона буквами «А».

Рисунок 5.10

2-ая операция — последовательное повторение 5-ти разных маршрутов Гамильтона. На рисунках нам хватило 3-х маршрутов. Выписываем по этим маршрутам шифрограмму:

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

1-я перестановка 2-я перестановка 3-я перестановка

Для перестановки букв в группах по 8 количество разных перестановок (маршрутов) . Количество возможных перестановок быстро увеличивается с ростом длины группы перестановок.

Если злоумышленник угадаетдлину группы, то он может перебрать последовательно все возможные перестановки пока не найдёт осмысленную. Для малой длины группы это легко особенно с помощью ЭВМ. Посмотрим как усложняется этот пример с ростом длины группы.

Длина группы	Количество перестановок	Время просмотра их на ЭВМ со скоростью 1 перестановка/сек.
8	40320	11.2 часа
10	3628800	42 суток
12		5544 суток 15 лет

Количество Mперестановок для группы изNбукв равно:

Перестановки удобно задавать числовыми ключами (гаммами)

Так перестановки Гамильтона будут иметь вид:

	0	1	2	3	4	5	6	7	0	1	2	3	4	5	6	7	0	1	2	3	4	5	6	7
исх. текст	Ш	И	Ф	Р	У	Й	Т	Е	П	Е	Р	Е	С	Т	А	Н	О	В	К	А	М	И	А	А
ключи шифрования	3	2	4	5	0	1	7	6	1	4	2	3	0	5	7	6	3	4	2	7	0	5	1	6
шифротекст	У	Й	И	Ш	Ф	Р	Е	Т	С	П	Р	Е	Е	Т	Н	А	М	А	К	О	В	И	А	А
	0	1	2	3	4	5	6	7	0	1	2	3	4	5	6	7	0	1	2	3	4	5	6	7

Расшифрование производится в обратном порядке (двигаться в направлении обратном стрелке перестановки), т.е. ключи перестановки для расшифрования будут: Перепишем ключи шифрования в виде

Ключ шифрования:	03	12	24	35	40	51	67	76	03 — 0-е место исх.
Ключ расшифр.:	30	21	42	53	04	15	76	67	текста переставляется на 3-е место шифрограммы
Ключ шифрования:	04	15	23	30	42	53	67	76	- ключ шифрования, упорядоченный по 1-му знаку
Ключ расшифр.:	4	5	3	0	2	3	7	6

или так:

Очевидно, что две (разные) перестановки подряд не увеличивают стойкость шифра, т.к. эквивалентны некоторой одной.

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

Содержание