Министерство образования Российской Федерации
УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ
ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра телекоммуникационных систем

ИССЛЕДОВАНИЕ ОСНОВ КРИПТОГРАФИИ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ 
К лабораторной работе № 1 
По курсу «Защита информации в телекоммуникационных система»

Уфа 2004

	УСЛОВИЕ РАБОТЫ:
20 27 04 02 16 04 29 05 28 24 11 03 04 28 24 29 24 16 04 30 23 32 07 05 30 31 23 05 24 31 23 27 22 04 14 28 27 04 02 10 31 01 29 24 31 29 25 17 13 27 01 09 01 29 14 23 30 05 24 18 01 04 32 07 29 24 24 13 04 05 29 25 17 31 27 23 16 24 30 29 24 22 23 29 01 14 11 05 24 08 05 30 31 23 29 29 24 05 30 01 13 27 01 21 30 24 11 29 23 13 24 05 27 23 16 05 30 31 23 29 29 24 11 10 13 27 23 05 30 10 13 29 24 11 10 31 24 03 16 23 17 05 30 31 01 19 13 24 16 31 23

	ЦЕЛЬ РАБОТЫ: 
	Расшифровать зашифрованный текст, представленный шифром простой замены, при условии, что исходным является текст, составленный из букв русского алфавита без пробелов.

	РЕШЕНИЕ:

	Исполнитель наверняка  сталкивался с подобными шифрами при знакомстве с произведениями Эдгара Аллана По (рассказ "Золотой Жук") и Конана Артура Дойля (рассказ "Пляшущие человечки"), сформировав тем самым алгоритм для раскрытия подобных избыточных шифров простой замены.

	Предлагается несколько методов для выбора самого оптимального алгоритма.

	1. Прямой перебор с использованием словаря для расшифровки.
	2. Статистический метод расшифровки
	
	Первый метод был отклонен по причине не оптимальности, из-за большой трудоемкости.

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

	Метод вскрытия шифра простой однобуквенной замены основывается на том, что частотные характеристики n-грамм шифротекста и открытого текста одинаковы. При использовании априорных частотных характеристик можно определить исходный открытый текст. 
	В Приложении 1 приведены априорные частотные характеристики.

	Опишем алгоритм расшифрования:

1.	Подсчет частот встречаемости шифрообозначений, а также их сочетаний, таких как биграмм и триграмм подряд идущих текстов.
2.	Выявление шифробозначений, заменяющих гласные и согласные буквы.
3.	Выдвижение гипотез о значениях шифробозначений и их проверка. Восстановление исходного открытого текста.

	Зашифрованный текст состоит из 151 символа шифрообозначений.
	Подсчитаем частотные характеристики символов, биграмм, триграмм зашифрованого текста с использованием  программы на языке PHP (v 4.05) (Приложение 2).

	Явным лидером среди шифрообразований является значение 24,
Среди биграмм – 29 24, 05 30
Среди триграмм – 05 30 31.

	Выдвигаем гипотезу о том, что значение 24 определяет букву О,
тогда биграмма 29 24 определяет сочетание НО, согласно частоте встречаемости.
	И следовательно триграмма 05 30 31 может определять сочетание СТР или СТВ
(СТО не походит, т.к. буква О уже используется, согласно же информации о сочетаемости букв в русском языке мы предположим, что значение 31 обозначает букву Р или В)
	Получим:
20 27 04 02 16 04 Н С 28 О 11 03 04 28 О Н О 16 04 Т 23 32 07 С Т 31 23 С О 31 23 27 22 04 14 28 27 04 02 10 31 01 Н О 31 Н 25 17 13 27 01 09 01 Н 14 23 Т С О 18 01 04 32 07 Н О О 13 04 С Н 25 17 31 27 23 16 О Т Н О 22 23 Н 01 14 11 С О 08 С Т 31 23 Н Н О С Т 01 13 27 01 21 Т О 11 Н 23 13 О С 27 23 16 С Т 31 23 Н Н О 11 10 13 27 23 С Т 10 13 Н О 11 10 31 О 03 16 23 17 С Т 31 01 19 13 О 16 31 23

	Как видно мы не пока заменили значение 31 по причине неоднозначности. 
Внимательно анализируя полученный результат, можно заметить сочетание значения 23 перед буквой Н.
	Предположим, что 23 – это буква Е (данная гипотеза согласуется и с частотой встречаемости этого значения).

	Получим:
20 27 04 02 16 04 Н С 28 О 11 03 04 28 О Н О 16 04 Т Е 32 07 С Т 31 Е С О 31 Е 27 22 04 14 28 27 04 02 10 31 01 Н О 31 Н 25 17 13 27 01 09 01 Н 14 Е Т С О 18 01 04 32 07 Н О О 13 04 С Н 25 17 31 27 Е 16 О Т Н О 22 Е Н 01 14 11 С О 08 С Т 31 Е Н Н О С Т 01 13 27 01 21 Т О 11 Н Е 13 О С 27 Е 16 С Т 31 Е Н Н О 11 10 13 27 Е С Т 10 13 Н О 11 10 31 О 03 16 Е 17 С Т 31 01 19 13 О 16 31 Е

	Заметим, что сочетание С О 08 С Т 31 Е Н Н О С Т 01 можно расшифровать как СОБСТВЕННОСТИ, следовательно значения 08, 31, 01 определяют буквы Б, В, И.

	Получим:
20 27 04 02 16 04 Н С 28 О 11 03 04 28 О Н О 16 04 Т Е 32 07 С Т В Е С О В Е 27 22 04 14 28 27 04 02 10 В И Н О В Н 25 17 13 27 И 09 И Н 14 Е Т С О 18 И 04 32 07 Н О О 13 04 С Н 25 17 В 27 Е 16 О Т Н О 22 Е Н И 14 11 С О Б С Т В Е Н Н О С Т И 13 27 И 21 Т О 11 Н Е 13 О С 27 Е 16 С Т В Е Н Н О 11 10 13 27 Е С Т 10 13 Н О 11 10 В О 03 16 Е 17 С Т В И 19 13 О 16 В Е

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

	Ход расшифровки шифрообзначений последовательно отображен в таблице.

01	08	
И	Б	
29	24	05	30	23	31	28	27	04	14	16	13	03	17	20	02	11	32	07	10	25	18	21	19	
Н	О	С	Т	Е	В	К	Р	А	Я	Д	П	З	Й	Г	Ж	М	Л	Ь	У	Ы	Ц	Э	Ю	
09	22	
Ч	Ш	

	Получим:

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

	Итак, исходный текст выглядит так:

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

Список литературы

1.	Алферов А.П., Зубов А.Ю, Кузьмин А.С., Черемушкин А.В. Основы  криптографии: Учебное пособие. – М.: Гелиос АРВ, 2001. – 480 с., ил.
2.	Введение в криптографию / Под общ. ред. В.В. Ященко. – М.: МЦНМО, ”ЧеРо”, 1998. – 272с.
3.	Чмора А.Л. Современная прикладная криптография. – М.: Гелиос АРВ, 2001. – 256 с.: ил.
4.	Кастаньетто Дж., Рават Х., Шуман С., Сколло К., Велиаф Д. Профессиональное PHP программирование. – Пер. с англ. – СПб: Символ-Плюс, 2001. - 912 с., ил.