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

стоимость раскрутки сайта

Шифры, основанные на методе подстановки, сохраняют порядок символов, но подменяют их. Шифры, использующие метод перестановки, меняют порядок следования символов, но не изменяют сами символы. На рис. 8.2 показан простой перестановочный шифр с колоночной перестановкой. Ключом к шифру служит слово или фраза, не содержащая повторяющихся букв. В данном примере в каче­стве ключа используется слово MEGABUCK. Цель ключа — пронумеровать ко­лонки. Первой колонкой становится колонка под буквой, расположенной ближе всего к началу алфавита, и т. д. Открытый текст записывается горизонтально в строках. Шифрованный текст читается по колонкам, начиная с колонки с млад­шей ключевой буквой.

 

м	Е	G	А	В	у	С	К
7	4	5	1	2	8	3	6
Р	1	е	а	s	е	t	г
а	п	s	f	е	г	0	п
е	m	1	1	1	i	о	п
d	о	1	1	а	г	S	t
0	m	У	s	w	i	S	S
b	а	п	к	а	с	с	О
u	п	t	s	i	X	t	W
О	t	W	о	а	b	с	d

Открытый текст

pleasetransferonemilliondollarsto myswissbankaccountsixtwotwo

Зашифрованный текст

AFLLSKSOSELAWAIATOOSSCTCLNMOMANT ESILYNTWRNNTSOWDPAEDOBUOERIRICXB

 

Рис. 8.2. Перестановочный шифр

Чтобы взломать перестановочный шифр, криптоаналитик должен вначале по­нять, что он имеет дело именно с перестановочным шифром. Если взглянуть на частоту символов Е, Т, А, 0,1, N и т. д., легко заметить, что их частоты соответст­вуют нормальным частотам открытого текста. В таком случае очевидно, что этот шифр является перестановочным, так как каждая буква в таком шифре пред­ставляет сама себя.

Затем нужно угадать число колонок. Во многих случаях по контексту сооб­щения можно угадать слово или фразу. Например, предположим, что криптоана­литик подозревает, что где-то в сообщении должно встретиться словосочетание milliondollars. Обратите внимание, что в результате того, что эти слова присутст­вуют в исходном тексте, в шифрованном тексте встречаются биграммы МО, IL, LL, LA, IR и OS. Символ О следует за символом М (то есть они стоят рядом по вертикали в колонке 4), так как они разделены в предполагаемой фразе дистан­цией, равной длине ключа. Если бы использовался ключ длиной семь, тогда вме­сто перечисленных выше биграмм встречались бы следующие: MD, Ю, LL, LL, IA, OR и NS. Таким образом, для каждой длины ключа в шифрованном тексте об­разуется различный набор биграмм. Перебрав различные варианты, криптоана­литик часто довольно легко может определить длину ключа.

Остается узнать только порядок колонок. Если число колонок k невелико, мож­но перебрать все k(k - 1) возможных комбинаций пар соседних колонок, сравнивая частоты образующихся биграмм со статистическими характеристиками англий­ского языка. Пара с лучшим соответствием считается правильно позициониро­ванной. Затем все оставшиеся колонки по очереди проверяются в сочетании с уже найденной парой. Колонка, в которой биграммы и триграммы дают макси­мальное совпадение со статистикой, предполагается правильной. Весь процесс повторяется, пока не будет восстановлен порядок всех колонок. Есть шанс, что на данном этапе текст уже будет распознаваемым (например, если вместо слова million мы увидим milloin, то сразу станет ясно, где сделана ошибка).

Некоторые перестановочные шифры принимают блок фиксированной длины на входе и выдают блок фиксированной длины на выходе. Такие шифры полно­стью определяются списком, сообщающим порядок, в котором символы попада­ют в выходной блок. Например, шифр на рис. 8.2 можно рассматривать в виде шифра с 64-символьным блоком. Его выход описывается последовательностью

чисел 4, 12, 20, 28, 36, 44, 52, 60, 5, 13....... 62. Другими словами, четвертая входная

буква, а, первой появится на выходе, за ней последует двенадцатая, /, и т. д.