Лабораторная работа № 9. Анализ шифра табличной перестановки

В шифрах табличной перестановки криптограмма (зашифрованный текст) может быть получена разными способами. Для открытого текста длиной N подбирается таблица размером m×n, m×n  N, символы текста записывается в ячейки таблицы. Запись может производиться как построчно, так и в столбец. В простейшем варианте текст из таблицы считывается в направлении, отличном от записи (например, по столбцам, если записывался по строкам).

Пример: Запишем фразу «ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ» в таблицу размером 7×5 по строкам (рис.44):

	1	2	3	4	5
1	т	е	р	м	и
2	н	а	т	о	р
3	п	р	и	б	ы
4	в	а	е	т	с
5	е	д	ь	м	о
6	г	о	в	п	о
7	л	н	о	ч	ь

Рис.44. Пример шифрующей таблицы

Выписав текст из таблицы по столбцам, получим шифр: «ТНПВЕГЛЕАРАДОНРТИЕЬВОМОБТМПЧИРЫСООЬ».

Для усиление шифра перед считыванием текста из таблицы возможна перестановка столбцов/строк таблицы, либо совместная перестановка строк и столбцов (двойная перестановка). Порядок считывания текста в этом случае может и не меняться.

Пример: В таблице на рис.44 переставим столбцы в порядке: 4-3-5-1-2 (рис.45), порядок считывания текста оставим тот же, что и порядок записи (по строкам).

	4	3	5	1	2
1	м	р	и	т	е
2	о	т	р	н	а
3	б	и	ы	п	р
4	т	е	с	в	а
5	м	ь	о	е	д
6	п	в	о	г	о
7	ч	о	ь	л	н

Рис.45. Пример шифрующей таблицы с перестановкой столбцов

Выписав текст из таблицы построчно, получим криптограмму: «МРИТЕОТРНАБИЫПРТЕСВАМЬОЕДПВОГОЧОЬЛН».

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

• записать текст криптограммы в таблицу в порядке ее считывания при шифровании (рис.45);

• переставить столбцы, чтобы они следовали в исходном порядке (рис.44);

• считать текст из таблицы в порядке его записи при шифровании.

Для выяснения правильного порядка следования столбцов может быть использован статистический анализ.

Появления букв в открытом тексте нельзя считать независимыми друг от друга. Для восстановления исходного порядка символов текста используется анализ их совместимости, в чем может помочь таблицы сочетаемости символов, а также таблица вероятностей (частот) появления двухбуквенных сочетаний (биграмм) в текстах естественного языка (URL: http://www.statsoft.ru/home/portal/exchange/textanalysis.htm).

Таблица сочетаемости букв (табл.1) содержит перечень букв, которые могут предшествовать, то есть находиться слева, и следовать, то есть находиться справа, от выбранной буквы. Вероятность предшествования и следования для гласных (Г) и согласных (С) неодинакова, она также указана в таблице (в процентах).

Таблица 1. Сочетаемость букв русского языка

Г	С	Слева	Буква	Справа	Г	С
3	97	л, д, к, т, в, р, н	А	л, н, с, т, р, в, к, м	12	88
80	20	я, е, у, и, а, о	Б	о, ы, е, а, р, у	81	19
68	32	я, т, а, е, и, о	В	о, а, и, ы, с, н, л, р	60	40
78	22	р, у, а, и, е, о	Г	о, а, р, л, и, в	69	31
72	28	р, я, у, а, и, е, о	д	е, а, и, о, н, у, р, в	68	32
19	81	м, и, л, д, т, р, н	Е	н, т, р, с, л, в, м, и	12	88
83	17	р, е, и, а, у, о	Ж	е, и, д, а, н	71	29
89	11	о, е, а, и	3	а, н, в, о, м, д	51	49
27	73	р, т, м, и, о, л, н	и	с, н, в, и, е, м, к, з	25	75
55	45	ь, в, е, о, а, и, с	к	о, а, и, р, у, т, л, е	73	27
77	23	г, в, ы, и, е, о, а	л	и, е, о, а, ь, я, ю, у	75	25
80	20	я, ы, а, и, е, о	м	и, е, о, у, а, н, п, ы	73	27
55	45	д, ь, н, о, а, и, е	н	о, а, и, е, ы, н, у	80	20
11	89	р, п, к, в, т, н	о	в, с, т, р, и, д, н, м	15	85
65	35	в, с, у, а, и, е, о	п	о, р, е, а, у, и, л	68	32
55	45	и, к, т, а, п, о, е	р	а, е, о, и, у, я ,ы, н	80	20
69	31	с, т, в, а, е, и, о	с	т, к, о, я, е, ь, с, н	32	68
57	43	ч, у, и, а, е, о, с	т	о, а, е, и, ь, в, р, с	63	37
15	85	п, т, к, д, н, м, р	У	т, п, с, д, н, ю, ж	16	84
70	30	н, а, е, о, и	ф	и, е, о, а, е, о, а	81	19
90	10	у, е, о, а, ы, и	X	о, и, с, н, в, п, р	43	57
69	31	е, ю, н, а, и	ц	и, е, а, ы	93	7
82	18	е, а, у, и, о	ч	е, и, т, н	66	34
67	33	ь, у, ы, е, о, а, и, в	ш	е, и, н, а, о, л	68	32

Окончание таблицы 1. Сочетаемость букв русского языка

Г	С	Слева	Буква	Справа	Г	С
84	16	е, б, а, я, ю	щ	е, и, а	97	3
0	100	м, р, т, с, б, в, н	ы	л, х, е, м, и, в, с, н	56	44
0	100	н, с, т, л	ь	н, к, в, п, с, е, о, и	24	76
14	86	с, ы, м, л, д, т, р, н	э	н, т, р, с, к	0	100
58	42	ь, о, а, и, л, у	ю	д, т, щ, ц, н, п	11	89
43	57	о, н, р, л, а, и, с	я	в, с, т, п, д, к, м, л	16	84

Отмечена еще одна устойчивая закономерность текстов на русском языке, связанная с чередованием гласных и согласных букв: после гласной чаще встречается согласная, а после согласной – гласная буква. Частоты встречаемости гласных/согласных букв в зависимости от предыдущей гласной/согласной приведены в табл.2.

Таблица 2. Чередование гласных и согласных

	Г	С	Всего
Г	6 588	38 310	44 898
С	38 296	16 806	55 102

Знание частот встречаемости пар букв (биграмм) позволяет легко вскрывать шифры табличной перестановки. Истинный порядок следования столбцов/строк в таблице можно восстановить, рассматривая и исключая маловероятные сочетания букв. Кроме того, на основе вероятностей появления биграмм можно рассчитать вероятность следования одного столбца (строки) шифрующей таблицы за другим.

Пусть известно, что криптограмма была получена следующим образом: текст записан в таблицу построчно, осуществлена перестановка столбцов. Тогда, для того, чтобы оценить вероятность p(i,j) следования столбца j непосредственно за столбцом i, надо для каждой строки рассмотреть сочетания символов из этих столбцов. Получим m вероятностей p(e_ki, e_kj) биграмм, где m – число строк шифрующей таблицы, e_ki, e_kj – символы, стоящие в шифрующей таблице на пересечении k строки и i, j столбца соответственно. Окончательно имеем:

Пользуясь этой формулой, можно вычислить вероятности следования друг за другом всех возможных пар столбцов p(i,j), i  j: i,j=1,…,n, n – число столбцов шифрующей таблицы. Если в исходном тексте j столбец действительно стоит после i-того, то вероятность p(i,j) должна быть, в принципе, больше вероятностей p(i,k), kj и p(k,j), ki. Руководствуясь этими соображениями, для таблиц небольшого размера можно не сложно восстановить истинный порядок следования столбцов.

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

• Если текст записывался построчно, то сначала надо восстановить истинный порядок следования столбцов, затем – строк.

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

При этом сама последовательность перестановок (что сначала переставлялось – столбцы или строки) оказывается не важна.

Задание

Дешифровать криптограммы, полученные методами столбцовой и двойной перестановки.

Указания к выполнению лабораторной работы

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

Технология выполнения задания

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

1. Выбрать текст криптограммы в соответствии с номером варианта (табл.3, выбор осуществляется по порядковому номеру в официальном списке группы).

Таблица 3. Варианты задания

	ОКЕСНВРП_ЫРЕАДЕЫН_В_РСИКО
	ДСЛИЕЗТЕА_Д_ЛЬЮВМИ_ _АОЧХК
	НМВИАИ_НЕВЕ_СМСТУОРДИАНКМ
	ЕДСЗЬНДЕ_МУБД_УЭ_КТЗЕМНАЫ
	СОНРЧОУО_ХДТ_ИЕИ_ВЗКАТРРИ
	_ОНКА_БНЫЕЦВЛЕ_К_ТГОАНЕИР
	НЗМАЕЕАА_Г_НОТВОССОТЬЯАЛС
	РППОЕААДТВЛ_ЕБЬЛНЫЕ_ПА_ВР
	ОПЗДЕП_ИХРДОТ_И_ВРИТЧ_САА
	ВКЫОСИРЙУ_ОЬВНЕ_СОАПНИОТС
	ПКТИРАОЛНАОИЧ_З_ЕСЬНЕЛНЖО
	ИПКСОЕ_ТСМНАЧИ_ОЕН_ГДЕЛА_
	АМВИННЬТЛЕАНЕ_ЙОВ_ОПХАРТО
	АРЫКЗЫ_КЙТНЛ_ААЫ_ОЛБКЫТРТ
	_ПАРИИВИАРЗ_БРА_ИСТЬЛТОЕК
	А_ЛНПАУВКЭИ_ЦИАКР_ОВОЕДРИ
	ЖВНОАН_АТЗОЬСН_ЫО_ФВИИКИЗ
	ОТВГОСЕЬЬТАДВ_С_ЬЗАТТЕЫАЧ
	ЯАМРИТ_ДЖЕХ_СВЕД_ТСУВЕТНО
	УЬБДТ_ОЕГТВ_ОЫКЭА_ВКАИУЦИ
	ЛТБЕИЛЖЫЕ_ _ОАПТЖРДУ_ЛМНОА
	ИПТКРРАФОГ_ВАИЯАЯ_ЖНУКАНА
	ПКЕЕРРПО_ЙУОТ_ИТПСУТЛЯЕИН
	ИЬЖЗНСД_ТУН_ЕТАНУВЕ_РЫГОЗ
	ЕОУРВА_НЬРИАДИЦЕПИ_РНШВЫЕ

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

Пример: Известно, что в шифре табличной перестановки произведена перестановка столбцов, текст записывался и выписывался из шифрующей таблицы построчно. Известно также, что при шифровании пробелы между словами сохранены (символ «_»). Необходимо дешифровать криптограмму «СВПООЗЛУЙЬСТЬ_ЕДПСКОКАОЙЗ».

2. Длина криптограммы – 25 символов, поэтому предположим, что она была записана с помощью таблицы 5×5. Для дальнейшего выполнения задания рекомендуется воспользоваться файлом «Перестановка.xlsx», реализующим расчет статистик для оценки порядка следования столбцов.

3. Запишем символы криптограммы построчно в шифрующую таблицу 5×5 (лист «Криптограмма»).

с	в	п	о	о
з	л	у	й	ь
с	т	ь	_	е
д	п	с	к	о
к	а	о	й	з

4. В таблице «Статистика (тыс) – порядок столбцов» на листе «Криптограмма» приведены значения получаемых для столбцов статистик. На листе «Частоты по столбцам» приведены частоты двухбуквенных сочетаний и расчет статистик (1) для соответствующих столбцов. Например, для последовательно следующих столбцов 1 и 2 (1-2) имеем двухбуквенные сочетания: св, зл, ст, дп, ка, которым соответствуют частоты 7, 1, 82, 3, 24. Результирующее значение статистики 41 328. Для облегчения визуального анализа на листе «Криптограмма» отображается значение статистики в тысячах (/1000), то есть 41.

	1	2	3	4	5
1	--	41	93	0	0
2	0	--	2	0	37 219
3	1	0	--	0	0
4	0	11	0	--	0
5	348	0	0	0	--

Для оценки возможности того, что столбец стоит на первом/последнем месте в шифрующей таблице могут быть использованы частоты биграмм вида «_e» и «е_», где е – символ столбца, стоящий соответственно на пересечении первой или последней строки (лист «Частоты биграмм»).

Из анализа значений статистик для нашего примера имеем наиболее вероятные последовательности столбцов: 1-3, 2-5, 5-1 и более слабые 1-2, 4-2, 3-1 (предположения о порядке следования столбцов можно указывать в области «Примечания» на листе «Криптограмма»).

На первом месте скорее всего стоят 3, 1 или 2 столбцы, а на последнем – 3 или 2.

5. Посмотрим на символы, стоящие в третьей строке: «сть_е». Скорее всего, мягкий знак стоит в конце слова. Поэтому предположим, что столбец 4 следует за столбцом 3. Учитывая результаты, полученные в предыдущем пункте, предположим следующий порядок столбцов: 3-4-2-5-1.

6. Зададим новый порядок следования столбцов, изменяя только номера (выделены красным шрифтом) столбцов таблицы «Перестановка столбцов - новый порядок» на листе «Криптограмма». Однако текст оказался не читаемым:

п	о	в	о	с
у	й	л	ь	з
ь	_	т	е	с
с	к	п	о	д
о	й	а	з	к

7. Снова обратим внимание на третью строку. Значение частот биграмм «ТЕ» - 31, «CE» - 25, «ЕС» - 37, «ЕТ» - 33. Скорее всего, «ь» стоит после сочетания «тес» и представляет окончание глагола «тесь». Переставим в конец столбцы с символами «ь» и «_», сохранив их порядок, то есть зададим новую последовательность столбцов 2-5-1-3-4.

Текст читается, это «ВОСПОЛЬЗУЙТЕСЬ ПОДСКАЗКОЙ».

8. После расшифровки текста показать его преподавателю.

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

9. Выбрать текст криптограммы в соответствии с номером варианта (табл.4, выбор осуществляется по порядковому номеру в официальном списке группы).

Таблица 4. Варианты задания

	СЯСЕ_ _ЛУНЫИАККННОГЯДУЧАТН
	МСЕЫ_ЛЫВЕНТОСАНТУЕИ_РЛПОБ
	АМНРИД_УЕБСЫ_ЕЙРСООКОТНВ_
	ОПЧУЛС_БООНЕВ_ОЖАЕОНЕЩЕИН
	ЕШИАНИРЛПГЕЧАВРВ_СЕЫНА_ЛО
	АРАВНРСВЕЕОАВ_ЗАНЯА_КМРЕИ
	А_ЛТАВЙООЛСО_ТВ_ШЕЕНЕСТ_Ь
	ФИ_ЗИММУЫНУУКБ_Е_ДЬШЫИВЧУ
	ВР_ЕСДЕИ_ТПХРОИ_ЗБУАДНУА_
	ЦТААЙПЕЕ_ТБГУРРСВЬЕ_ОРЗВВ
	АВАРНСЧАА_НЕДВЕДЕРПЕОЙ_ИС
	ДОПК_СОПАЛЕИНЛ_ГИНЙОИЖЕ_Т
	ЛУАЗИЯНСА_ДТДЕАИ_ШРФЕОНП_
	С_ОЯНВ_СЬСЛААВРЧЕАРТОГДЕС
	ЗШАФИПРАЛОЕНЖ_ОЬН_ДАРВОНА
	КЭЕ_ТДУМБ_ЬСЗЕДНЕЗМАОР_ТУ
	_ЕАЛЯРАНВЯАЧДА_ЕРПЕСАНВ_Ч
	_И_ЕНТРЗИ_ОКЕВНОДЛЕША_ИМР
	РОБДОЕВПС_МСХЬА_ _ИВПСНИОТ
	ЕСДНОГТЕАНН_НЕОВМР_ЕУНПТЕ
	_ЙЕСТОВО_НИИНЛАЕТИЖДСОПВ_
	НДИАЕОЫЛПНЕ_ _НВЕАНГТ_ИЗЛА
	П_БИРДЛЬНЕВ_ОП_ОПЗДЕВЫГЕА
	МДООИТЕЬ_СМТ_НАДТЕСУБЕХНО
	АИНАЛЖНОЛЕШФ_ЗИ_УАРОЬСНЕ_

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

Пример: Известно, что использован шифр двойной перестановки, текст записывался в шифрующую таблицу построчно. Дешифровать криптограмму «ЫОЕЧТТОУ_СНСОРЧТРНАИДЬН_Е».

10. Текст содержит 25 символов, что позволяет записать его в квадратную таблицу 5×5. Поскольку известно, что запись велась построчно, сначала следует восстановить порядок следования столбцов, а затем – строк. Для выполнения задания рекомендуется воспользоваться книгой «Двойная перестановка.xslx», содержащей расчет статистик.

11. Запишем криптограмму построчно в таблицу (лист «Криптограмма»).

ы	о	е	ч	т
т	о	у	_	с
н	с	о	р	ч
т	р	н	а	и
д	ь	н	_	е

12. Анализ статистик показывает, что наиболее вероятны следующие последовательности столбцов: 1-3, 2-4, 3-5, 4-3, 5‑1.

Проверка на первый последний столбец не проводится, так как порядок строк также изменен.

Предположим следующую последовательность следования столбцов: 2-4-3-5-1.

13. Переставим столбцы в указанном порядке, меняя номера столбцов таблицы «Перестановка столбцов – новый порядок» (выделены красным):

о	ч	е	т	ы
о	_	у	с	т
с	р	о	ч	н
р	а	н	и	т
ь	_	н	е	д

14. Полученный порядок столбцов, скорее всего, правильный, так как в строках таблицы получили вполне читаемые фрагменты текста «очеты», «срочн», «ранит». Приступим к перестановке строк.

Фрагмент «срочн» составляет, скорее всего, слово «срочно», таким образом, после 3 строки должна следовать 1 или 2 строка. После строки с фрагментом «ранит», скорее всего, идет строка, начинающаяся с мягкого знака – «ранить» (4-5).

На основании проверки строк на первую/последнюю (таблица «Частота биграмм - порядок строк») предположим, что 3 строка идет первой. Тогда порядок строк очевиден: 3-2-4-5-1.

15. Осуществим перестановку строк, задав новые номера строк в таблице «Перестановка строк – новый порядок» (выделены красным).

Текст читаем: «СРОЧНО УСТРАНИТЬ_НЕДОЧЕТЫ».

с	р	о	ч	н
о	_	у	с	т
р	а	н	и	т
ь	_	н	е	д
о	ч	е	т	ы

16. После расшифровки текста показать его преподавателю.

Контрольные вопросы:

1. Что является ключом (секретным параметром) шифра табличной перестановки?

(Ключом является размерность таблицы, а также порядок следования столбцов или строк, если они переставлялись при шифровании)

2. Что (столбцы или строки) следует переставлять для усиления шифра, если текст в шифрующую таблицу записывается по столбцам?

(Следует переставлять строки, так как в этом случае нарушается читаемость фрагмента текста в пределах столбца таблицы)

3. Почему значения статистик не могут точно определить порядок следования столбцов?

(Статистики отражают закономерности не данного конкретного текста, а, в пределе, всех текстов русского языка. Каждый конкретный текст может иметь свои индивидуальные особенности)