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

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

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

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

1.	ОКЕСНВРП_ЫРЕАДЕЫН_В_РСИКО
2.	ДСЛИЕЗТЕА_Д_ЛЬЮВМИ_ _АОЧХК
3.	НМВИАИ_НЕВЕ_СМСТУОРДИАНКМ
4.	ЕДСЗЬНДЕ_МУБД_УЭ_КТЗЕМНАЫ
5.	СОНРЧОУО_ХДТ_ИЕИ_ВЗКАТРРИ
6.	_ОНКА_БНЫЕЦВЛЕ_К_ТГОАНЕИР
7.	НЗМАЕЕАА_Г_НОТВОССОТЬЯАЛС
8.	РППОЕААДТВЛ_ЕБЬЛНЫЕ_ПА_ВР
9.	ОПЗДЕП_ИХРДОТ_И_ВРИТЧ_САА
10.	ВКЫОСИРЙУ_ОЬВНЕ_СОАПНИОТС
11.	ПКТИРАОЛНАОИЧ_З_ЕСЬНЕЛНЖО
12.	ИПКСОЕ_ТСМНАЧИ_ОЕН_ГДЕЛА_
13.	АМВИННЬТЛЕАНЕ_ЙОВ_ОПХАРТО
14.	АРЫКЗЫ_КЙТНЛ_ААЫ_ОЛБКЫТРТ
15.	_ПАРИИВИАРЗ_БРА_ИСТЬЛТОЕК
16.	А_ЛНПАУВКЭИ_ЦИАКР_ОВОЕДРИ
17.	ЖВНОАН_АТЗОЬСН_ЫО_ФВИИКИЗ
18.	ОТВГОСЕЬЬТАДВ_С_ЬЗАТТЕЫАЧ
19.	ЯАМРИТ_ДЖЕХ_СВЕД_ТСУВЕТНО
20.	УЬБДТ_ОЕГТВ_ОЫКЭА_ВКАИУЦИ
21.	ЛТБЕИЛЖЫЕ_ _ОАПТЖРДУ_ЛМНОА
22.	ИПТКРРАФОГ_ВАИЯАЯ_ЖНУКАНА
23.	ПКЕЕРРПО_ЙУОТ_ИТПСУТЛЯЕИН
24.	ИЬЖЗНСД_ТУН_ЕТАНУВЕ_РЫГОЗ
25.	ЕОУРВА_НЬРИАДИЦЕПИ_РНШВЫЕ

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

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

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

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

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

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


--
	--			37 219
		--
			--
				--

Для оценки возможности того, что столбец стоит на первом/последнем месте в шифрующей таблице могут быть использованы частоты биграмм вида «_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. Варианты задания

1.	СЯСЕ_ _ЛУНЫИАККННОГЯДУЧАТН
2.	МСЕЫ_ЛЫВЕНТОСАНТУЕИ_РЛПОБ
3.	АМНРИД_УЕБСЫ_ЕЙРСООКОТНВ_
4.	ОПЧУЛС_БООНЕВ_ОЖАЕОНЕЩЕИН
5.	ЕШИАНИРЛПГЕЧАВРВ_СЕЫНА_ЛО
6.	АРАВНРСВЕЕОАВ_ЗАНЯА_КМРЕИ
7.	А_ЛТАВЙООЛСО_ТВ_ШЕЕНЕСТ_Ь
8.	ФИ_ЗИММУЫНУУКБ_Е_ДЬШЫИВЧУ
9.	ВР_ЕСДЕИ_ТПХРОИ_ЗБУАДНУА_
10.	ЦТААЙПЕЕ_ТБГУРРСВЬЕ_ОРЗВВ
11.	АВАРНСЧАА_НЕДВЕДЕРПЕОЙ_ИС
12.	ДОПК_СОПАЛЕИНЛ_ГИНЙОИЖЕ_Т
13.	ЛУАЗИЯНСА_ДТДЕАИ_ШРФЕОНП_
14.	С_ОЯНВ_СЬСЛААВРЧЕАРТОГДЕС
15.	ЗШАФИПРАЛОЕНЖ_ОЬН_ДАРВОНА
16.	КЭЕ_ТДУМБ_ЬСЗЕДНЕЗМАОР_ТУ
17.	_ЕАЛЯРАНВЯАЧДА_ЕРПЕСАНВ_Ч
18.	_И_ЕНТРЗИ_ОКЕВНОДЛЕША_ИМР
19.	РОБДОЕВПС_МСХЬА_ _ИВПСНИОТ
20.	ЕСДНОГТЕАНН_НЕОВМР_ЕУНПТЕ
21.	_ЙЕСТОВО_НИИНЛАЕТИЖДСОПВ_
22.	НДИАЕОЫЛПНЕ_ _НВЕАНГТ_ИЗЛА
23.	П_БИРДЛЬНЕВ_ОП_ОПЗДЕВЫГЕА
24.	МДООИТЕЬ_СМТ_НАДТЕСУБЕХНО
25.	АИНАЛЖНОЛЕШФ_ЗИ_УАРОЬСНЕ_

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

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

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. Почему значения статистик не могут точно определить порядок следования столбцов?

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

Лабораторная работа №10. Криптоанализ шифра простой замены

Шифр простой (одноалфавитной) замены – один из древнейших. Прежде всего, выбирается нормативный алфавит – набор символов, которые будут использоваться для составления сообщений.

В качестве нормативного алфавита может использоваться, например, русский алфавит, исключая буквы «Ъ» и «Ё» и дополненный символом пробела. Выбранный нормативный алфавит состоит из 32 символов.

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

Пример. Пусть соответствие между нормативным и шифрующим алфавитом задано таблицей 5.

Таблица 5. Пример одноалфавитной замены

нормативный алфавит

…

алфавит шифрования

…

Зашифруем слово «ЗВЕЗДА»:

Исходное сообщение:	З	В	Е	З	Д	А
Криптограмма:	П	С	У	П	И	Ф

Криптоанализ шифра простой замены основан на использовании статистических закономерностей естественного языка. Так, например, известно, что в русском языке чаще всего встречается буквы «О», «А» и «Е», а наиболее редки «Ц», «Щ», «Э», «Ф» (без учета «Ё» и «Ъ»). Частоты букв русского языка в алфавите с символом пробела приведены в табл.6.

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

Таблица 6. Частоты символов русского языка (алфавит с пробелом)

Символ	Частота	Символ	Частота	Символ	Частота	Символ	Частота
-	0,175	Р	0,040	У	0,021	Х	0,009
О	0,089	В	0,038	Я	0,018	Ж	0,007
Е,Ё	0,072	Л	0,035	Ы	0,016	Ю	0,006
А	0,062	К	0,028	Ь,Ъ	0,014	Ш	0,006
И	0,062	М	0,026	Б	0,014	Ц	0,004
Т	0,053	Н	0,025	Г	0,013	Щ	0,003
Н	0,053	Д	0,025	Ч	0,012	Э	0,003
С	0,045	П	0,023	Й	0,010	Ф	0,002

Неравновероятность k-грамм (и даже слов) тесно связана с избыточностью текста на естественном языке – наличием в нем большого числа повторений отдельных фрагментов текста: корней, окончаний, суффиксов, слов и фраз. Для русского языка наиболее частыми фрагментами являются биграммы и триграммы:

СТ, НО, НЕ, ЕН, ТО, НА, ОВ, НИ, РА, ВО, КО, ПО

СТО, ЕНО, НОВ, ТОВ, ОВО, ОВА, ОГО, ПРО, АТЬ, ЕНИ

Следует, однако, отметить, что частоты появления символов в конкретном тексте могут отличаться от стандартных, в том числе, и достаточно существенно. Эти отличия могут проявиться тем сильнее, чем короче сообщение. Поэтому частотный анализ коротких сообщений иногда бывает весьма затруднителен.

Приведем некоторые советы по выполнению частотного анализа русских текстов:

1. Сначала следует подсчитать частоты появления каждого символа в криптограмме. Далее следует сопоставить полученные значения с таблицей стандартных частот русского языка (табл.6). Совпадение может быть не точным, однако возможно определить наиболее часто встречающиеся символы. Если нормативный алфавит включает пробел, то наиболее частый символ – это «_» (появляется с частотой более 15%), далее следуют гласные «О» и «Е». Можно предположить, что следующие по частоте символы – также гласные: «А» и «И». Также можно сделать предположение относительно наиболее редко встречающихся символов (менее 1%) – скорее всего, это согласные: «Х», «Ж», «Ш», «Ц», «Щ», «Ф», или «Э», «Ю».

2. Если, как это часто бывает, прямое сопоставление частот не приводит сразу к раскрытию текста сообщения, рекомендуется обратить внимание на пары повторяющихся букв. В русском языке чаще всего повторяются буквы нн, сс (в середине слов, перед окончанием); ии, ее, мм (как в середине слов, так и окончание), оо (только в середине слов), вв (в начале или в середине слов).

3. Если в шифр-тексте имеются пробелы между словами, то можно постараться определить слова, состоящие из одной, двух или трех букв. Таблица 7 содержит частотный список (в порядке убывания частоты появления в текстах) первых однобуквенных, двухбуквенных, трехбуквенных и четырехбуквенных лексем русского языка.

Таблица 7. Частотный список коротких лексем русского языка

Однобуквенные	Двухбуквенные	Трехбуквенные	Четырехбуквенные
в	не	за	что	год	быть
я	на	от	как	все	этот
с	он	же	это	его	весь
а	по	вы	они	еще	свой
к	но	ты	она	или	мочь
у	мы	бы	так	уже	себя
о	из	ее	для	вот	если

Лексема охватывает все словоформы (изменение слова по падежам и спряжение для глаголов). Полный частотный список лексем можно найти в «Новом частотном словаре русской лексики» (URL: http://dict.ruslang.ru/freq.php).

Следует обратить внимание и на слова-палиндромы (слова, читающиеся одинаково как слева направо, так и справа налево), слова с дефисами (табл.8).

Таблица 8. Слова-палиндромы, типичные слова с дефисами

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

4. При анализе криптограммы рекомендуется учитывать не только частность отдельных символов, но и сочетаемость отдельных букв (табл.1), гласных и согласных (табл.2), а если в тексте оставлены пробелы – то и частоты первых/последних букв. Так, например, в качестве первых букв слова чаще всего встречаются буквы «С», «П», «В», «Н», «О», «И», «М» и «К», первыми буквами не могут быть «Ы» и «Ь,Ъ», что отличается от данных общей частотной таблицы (табл.5).

Рассмотрим пример частотного анализа простой замены (можно воспользоваться файлом «Простая замена пример1.xlsx»). Пусть дан текст криптограммы «У Т Ц П А К П Щ Н С Щ Г А Л Й Ю Б Ш И А Р Б У Т Ц П Ф Б С Н Ы А Ш Й А Ь Й Л Б А Н С Й С Т Н С Т О Б Н Д Щ М Щ А Й Ш Й Ж Т Л Й А С Б Д Н С Й А Ш Щ А С Щ Ж Е Д Щ А Б Н Ж Т А Щ Ш А Р Щ Н С Й С Щ О Ш Щ А Р Ж Т Ш Ш И Г». Известно, что использован шифр простой замены, нормативный алфавит содержит пробел.

Подсчитаем частоты появления различных символов в криптограмме и сравним их со стандартными частотами (табл.9):

Таблица 9. Сопоставление частот символам криптограммы

Частоты появления символов в криптограмме
Символ	А	Щ	С	Й	Ш	Н	Б	Т	Ж	Д	Р	…
Частота	0,131	0,103	0,093	0,084	0,075	0,075	0,065	0,065	0,037	0,028	0,028
Стандартные частоты
Символ	_	О	Е	А	И	Н	Т	С	Р	В	Л	…
Частота	0,175	0,089	0,072	0,062	0,062	0,053	0,053	0,045	0,04	0,038	0,035

Заменим два наиболее часто встречающихся символа криптограммы: «А» - «_» и «Щ» - «О». Получим соответствие:

Обратим внимание на двухбуквенные слова «Ш Щ» и «Щ Ш», а также на сдвоенное «Ш Ш» в последнем слове. Поскольку «Щ» заменено на букву «О», то «Ш» может быть только буквой «Н» или «Т». Скорее всего это «Н», в этом случае последнее слово – прилагательное, а «НН» стоит перед окончанием. Сделаем замену «Ш» - «Н».

Можно предположить, что стоящее на конце седьмого слова сочетание «Щ М Щ» – это окончание «ОГО» прилагательного, тогда «М» - «Г». Если это так, то следующее за прилагательным слово – скорее всего, существительное мужского рода в родительном падеже, и окачивается на «А». Отсюда «Й» - «А». Данное предположение не противоречит таблице частот 9. Тогда:

Пятым словом является предлог «НА», поэтому следующее слово оканчивается, скорее всего, на «Е». Заменим «Б» - «Е».

Рассмотрим слово «АНА - - - А». Предположим, что это слово «АНАЛИЗА». Сделаем замены: «Ж» - «Л», «Т» - «И», «Л» - «З». Получили:

Слово «Е - ЛИ» – это, скорее всего «ЕСЛИ», последнее слово «- ЛИНН - -» похоже на «ДЛИННЫЙ», а в словосочетании «НА - АЗЕ» (АНАЛИЗА) – стоит слово «БАЗЕ». Сделаем соответствующие замены: «Н» - «С», «Р» - «Д», «И» - «Ы», «Г» - «Й», «Ь» - «Б».

Обратим внимание на слово «С - А - ИС - И - ЕС - ОГО» (АНАЛИЗА), что похоже на слово «СТАТИСТИЧЕСКОГО», если это так, то читается и слово «ДОС - А - О - НО» – «ДОСТАТОЧНО». Сделаем замены: «С» - «Т», «О» - «Ч», «Д» - «К». Получили:

Теперь, заметив, что первое и четвертое слова криптограммы имеют общую последовательность букв «УТЦП», и, исходя из контекста, не сложно сделать оставшиеся замены. Получили открытый тест: «ШИФР ПРОСТОЙ ЗАМЕНЫ ДЕШИФРУЕТСЯ НА БАЗЕ СТАТИСТИЧЕСКОГО АНАЛИЗА ТЕКСТА НО ТОЛЬКО ЕСЛИ ОН ДОСТАТОЧНО ДЛИННЫЙ».

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

Таблица 10. Ключ шифра простой замены из примера