Методические указания к проведению лабораторной работы по курсу «Методы и средства защиты компьютерной информации»

КРИПТОГРАФИЧЕСКИЙ АЛГОРИТМ “МЕТОДОМ ПЕРЕСТАНОВОК”

Методические указания к проведению лабораторной работы по курсу «Методы и средства защиты компьютерной информации» для студентов направления 230100 «Информатика и вычислительная техника»

Цель работы

Ознакомление с историей становления криптографии, освоение алгоритма шифрования «двойными перестановками», криптоанализа сообщений, зашифрованных указанным алгоритмом.

ЗАЩИТа информации и криптография

В современных информационных технологиях крайне актуальной является защита информации от несанкционированного доступа [1-3].

Защитой информации человек занимается с древних времен. В работе Атанасиуса Кирхера «Новая и всеобщая многопись» рассматривались методы тайнописи, говоря современным языком криптографии.

Криптография ( от крипто… и …графия)– тайнопись, система изменения письма с целью сделать текст непонятным для непосвященных лиц.

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

Отцом криптографии считается великий архитектор Леон Батиста Альберти (1404-1472), который ввел многоалфавитные перестановки, а так же шифрирующие коды. Его книга, написанная в 1467 году, является первым содержательным трудом по криптографии. Чикко Симонетта, секретарь одного из герцогов династии Сфорца, в 1474г. учил как можно расшифровать простые шифры, основанные на перестановках, что было открыто также арабским ученым Аль-Кашанди около 1400 года. В 1518 г. появилась первая печатная книга о криптографии, написанная ученым аббатом из Вюрцбурга Тритемиусом. Она содержит первое упоминание о маскированной тайнописи и многоалфавитной перестановке при помощи изменяющегося ключа, представляющего собой периодическую последовательность подстановок Цезаря. В 1553 г. Джованни Баттиста Порта (1535-1615г.) уже систематически различает перестановки и подстановки. Ему впервые удалось расшифровать многоалфавитную шифровку. Представители семейства Ардженти при папском дворе, в особенности Маттео Ардженти, уже около 1600 г. умели затруднять работу расшифровщиков при помощи различных хитроумных приемов, употребляя, например, кодовые слова разной длины и омофоны-разные выбираемые по произволу кодовые слова для одного и того же знака.

Франсуа Виет, синьор Биготьерский, находившийся на службе у короля Франции Генриха IV, был отнюдь не единственным из математиков, занимавшихся криптографией. Когда Виет расшифровал одно испанское послание, Филипп V пожаловался папе римскому, что здесь не обошлось без черной магии. Однако пожаловался впустую – у папы самого советником был Джованни Баттиста Ардженти.

Наряду с традиционными применениями криптографии в политике и военном деле возникают неожиданно близкие к нашему времени задачи ее применения для охраны интеллектуальной собственности от преследования инквизицией или заимствования другими учеными [5].

Новые достижения принес 19-й век. Чарлз Уинстон предложил в 1854 г. шифровку биграммами. Лейбниц и Беббидж также занимались проблемами шифрования. Большое продвижение вперед удается в 1863 г. прусскому пехотному майору в отставке Фридриху В. Казински: он понял, как расшифровать многоалфавитный шифр с периодически повторяемым кодовым словом, основанный на подстановках. Крупный результат удается получить в 1883 г. Огюсту Керкхоффу, который в своей работе «Военная криптография» показывает, как можно расшифровать многоалфавитные шифры с длинным периодическим ключом. Некоторые из таких систем были расшифрованы. И лишь работы Жильбера С. Вернама, придумавшего в 1917 г. машину для кодировки телеграфных сообщений, способствовали нахождению очень надежной системы – шифровки по ключу, который выбирается совершенно случайно и не содержит никаких повторений (индивидуальный ключ).

Во время второй Мировой войны значительный вклад в развитие криптографии внесли Клод Элдвуд Шеннон и Владимир Александрович Котельников. В частности, под руководством В.А. Котельникова были разработаны системы шифрования, которые считаются неподдающимися криптоанализу.

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

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

ШИФРЫ ПЕРЕСТАНОВКИ

В простых шифрах, к которым относятся шифры перестановки, используются таблицы, которые дают простые шифрующие процедуры перестановки букв в сообщении. Ключом в них служат размер таблицы, фраза, задающая перестановку или специальная особенность таблиц. Перестановка без ключа — один из самых примитивных методов шифрования. Например, сообщение «НЕЯСНОЕ СТАНОВИТСЯ ЕЩЕ БОЛЕЕ НЕПОНЯТНЫМ» записывается в таблицу по столбцам. Пример для таблицы из 5 строк и 7 столбцов приведен на рис 1.

н	о	Н	с	Б	Н	я
Е	Е	0	я	0	Е	т
Я	С	В	Е	Л	П	н
С	т	и	Щ	Е	0	ы
Н	А	т	Е	Е	Н	м

Рис. 1. Таблица шифрования методом «перестановка без ключа»

После того, как открытый текст записан колонками, для образования шифровки он считывается по строкам. Если его записывать группами по 5 букв, то получится: НОНСБ НЯЕЕО ЯОЕТЯ СВЕЛП НСТИЩ ЕОЫНА ТЕЕНМ. Для использования этого шифра отправителю и получателю нужно договориться об общем ключе в виде размера таблицы. Объединение букв в группы не входит в ключ шифра и используется лишь для удобства записи не смыслового текста.

Более практический метод шифрования, называемый одиночной перестановкой по ключу, очень похож на предыдущий. Он отличается лишь тем, что колонки таблицы переставляются по ключевому слову, фразе или набору чисел длиной в строку таблицы. Используя в виде ключа слово ЛУНАТИК, получим следующие таблицы ( Рис. 2).

Л	У	Н	А	Т	И	К
4	7	5	1	6	2	3
Н	0	Н	С	Б	Н	я
Е	Е	0	Я	0	Е	т
Я	С	В	Е	Л	П	н
С	Т	И	Щ	Е	0	ы
Н	А	Т	Е	Е	Н	м

До перестановки

А	и	К	л	Н	Т	У
1	2	3	4	5	6	7
С	Н	я	Н	Н	Б	0
Я	Е	т	Е	0	0	Е
Е	П	н	Я	В	Л	С
Щ	0	ы	С	и	Е	Т
Е	Н	м	Н	т	Е	А

После перестановки

Рис. 2. Таблицы шифрования

В верхней строке таблицы «до перестановки» записан ключ, a номера под ключом определены по естественному порядку соответствующих букв ключа в алфавите. Если бы в ключе встретились одинаковые буквы, то они бы нумеровались слева направо. Ключ – это любая (цифровая или символьная) последовательность, позволяющая беспрепятственно расшифровать полученное сообщение. Чаще всего ключ известен только принимающей и передающей сообщение стороне и хранится в секрете. С другой стороны, для криптоаналитика ключ это цель его работы.

После шифрования получается: СНЯНН БОЯЕТ ЕООЕЕ ПНЯВЛ СЩОЫС ИЕТЕН МНТЕА. Для дополнительной скрытности можно повторно зашифровать сообщение, которое уже было зашифровано. Этот способ известен под названием двойная перестановка. Для этого размер второй таблицы подбирают так, чтобы длины ее строк и столбцов были другие, чем в первой таблице. Лучше всего, если они будут взаимно простыми. Кроме того, в первой таблице можно переставлять столбцы, а во второй строки. Наконец, можно заполнять таблицу зигзагом, змейкой, по спирали или каким-то другим способом. Такие способы заполнения таблицы если и не усиливают стойкость шифра, то делают процесс шифрования гораздо более занимательным.

Кроме одиночных перестановок используются еще двойные перестановки столбцов и строк таблицы с сообщением. При этом перестановки определяются отдельно для столбцов и отдельно для строк. В таблицу вписывается текст и переставляются столбцы, а потом - строки. При расшифровке порядок перестановок обратный. Насколько просто выполнить это шифрование показывает следующий пример ( Рис. 3):

	2	4	1	3
4	П	P	И	E
1	3	Ж	A	Ю
2		Ш	E	С
3	T	0	Г	0

Исходная таблица

	1	2	3	4
4	И	П	E	Р
1	A	3	Ю	Ж
2	E		С	Ш
3	Г	т	0	0

Перестановка столбцов

	1	2	3	4
1	A	3	Ю	Ж
2	E		с	Ш
3	Г	T	о	О
4	И	П	Е	Р

Перестановка строк

Рис. 3. Таблицы шифрования двойной перестановкой

Получается шифровка АЗЮЖЕ СШГГООИПЕР. Ключом к этому шифру служат номера столбцов 2413 и номера строк 4123 исходной таблицы. Число вариантов двойной перестановки тоже велико: для таблицы 3 х 3 их 36, для 4 х 4 их 576, а для 5x5 их уже 14400. Однако двойная перестановка очень слабый вид шифра, легко читаемый при любом размере таблицы шифрования.

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

Ключ – столбцы 2413, строки 4123. Переставляя столбы и строки в порядке, записанном в ключе, получаем исходное сообщение «ПРИЕЗЖАЮ ШЕСТОГО».

Вскрытие шифров перестановки

Криптоанализ – раздел криптологии, изучающий методы «вскрытия» (определения ключа или сообщения). При этом криптологи считают, что алгоритм шифрования известен, а ключ нет. Необходимо определить текст перехваченной шифровки.

Была перехвачена радиограмма противника АЗЮЖЕ СШГТООИПЕР. Известно (разведчики взяли «языка»), что противник использует для шифрования метод двойной перестановки в таблице 4х4. Ключи шифрования после взятия «языка» были изменены, и дешифровать шифровку не удалось. Поэтому криптоаналитику необходимо вскрыть шифровку.

Сообщение АЗЮЖЕ СШГТООИПЕР укладывается в таблицу 4х4 (Рис.4).

	1	2	3	4
1	A	3	Ю	Ж
2	E		с	Ш
3	Г	T	0	0
4	И	П	E	P

Рис. 4.Исходная таблица для «вскрытия» сообщения

Метод «вскрытия» шифров двойной перестановки основан на определении маловероятных сочетаний букв и нахождении на их основе истинной последовательности столбцов в шифровальной таблице.

Для расшифровки перехваченного сообщения необходимо определить вероятности следования двух букв разных столбцов и выбрать наиболее вероятную последовательность. Вероятность следования одного столбца за другим Рстолбца равна произведению вероятностей двухбуквенных комбинаций во всех n строках этих двух столбцов:

Рстолбца = Рстроки 1  Рстроки 2  …  Рстроки i  …  Рстроки n.

Для упрощения счета используют формулу:

log Рстолбца = log Рстроки 1 + log Рстроки 2 + … + log Рстроки n.

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

Таким образом, для «вскрытия» сообщений, зашифрованных методом двойной перестановки принято [5] использовать логарифмы числа встретившихся в текстах двухбуквенных комбинаций F(), которые приведены в таблице №1.

Для таблицы, приведенной на рис.4, получим следующие значения.

При следовании за первым столбцом второго, получим:

F(12) =F(A3) + F(Е ) + F(ГТ) + F(ИП)=7+9+0+5=21.

При следовании за первым столбцом третьего получим:

F(13) =F(АЮ) + F(ЕС) + F(ГО) + F(ИЕ) =6+8+8+8=30.

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

F(14) =F(АЖ) + F(ЕШ) + F(ГО) + F(ИР) =7+5+8+7=27.

Рассматривая все возможные варианты следования столбцов получим:

F(21) = F(ЗА) + F(_Е ) + F(ТГ) + F(ПИ) =8+7+1+7=23;

F(23) = F(ЗЮ) + F(_С) + F(ТО) + F(ПЕ) =0+9+9+8=26;

F(24) = F(ЗЖ) + F(_Ш) + F(ТО) + F(ПР) =1+5+9+9=24;

F(31) = F(ЮА) + F(СЕ) + F(ОГ) + F(ЕИ) =0+7+8+8=23;

F(32) = F(ЮЗ) + F(С_) + F(ОТ) + F(ЕП) =2+7+8+8=25;

F(34) = F(ЮЖ) + F(СШ) + F(ОО) + F(ЕР) =1+5+6+8=20;

F(41) = F(ЖA) + F(ШЕ) + F(ОГ) + F(РИ) =6+6+8+8=28;

F(42) = F(ЖЗ) + F(Ш_) + F(ОТ) + F(РП) =1+5+8+4=18;

F(43) = F(ЖЮ) + F(ШС) + F(ОО) + F(РЕ) =0+0+6+8=14.

На рис.5 приведен граф логарифмов частот следования столбцов друг за другом.

Таблица 1

Логарифмы числа встретившихся двухбуквенных комбинаций

	А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ь	Ы	Ь	Э	Ю	Я
А	2	7	8	6	7	7	7	7	4	7	7	7	8	8	3	7	6	7	8	2	6	6	7	7	5	5	0	0	0	0	6	7	9
Б	7	1	1	0	1	6	2	2	6	0	5	6	3	5	7	2	7	5	0	7	0	5	4	1	0	5	5	7	2	2	0	3	5
В	8	0	5	0	4	8	0	3	7	1	6	7	5	6	8	4	6	6	6	6	0	3	0	1	3	0	0	8	2	0	0	4	8
Г	6	0	1	1	6	5	0	0	6	0	4	5	4	4	8	0	7	0	0	6	0	0	1	2	0	0	0	0	0	0	0	0	4
Д	8	1	6	3	4	8	1	0	7	0	4	7	1	7	8	4	6	5	2	7	1	3	3	3	4	0	0	6	4	0	4	5	7
Е	5	5	6	7	8	6	6	6	4	7	7	8	8	9	6	5	8	8	9	3	3	6	5	6	5	6	0	0	1	1	5	5	9
Ж	6	0	0	0	6	7	2	1	7	0	5	0	2	7	1	0	1	2	1	3	0	0	0	0	0	0	0	0	2	0	0	0	2
3	8	4	6	2	6	4	1	1	6	1	5	5	6	6	7	1	5	0	0	6	0	0	2	1	0	0	2	6	2	0	0	4	6
И	6	6	7	6	6	8	5	7	7	7	7	6	8	8	5	5	7	8	8	1	5	7	7	7	6	3	0	1	0	0	6	7	9
И	0	0	3	0	3	0	0	0	0	0	3	6	5	4	0	0	0	6	6	0	0	0	1	2	3	0	0	0	0	0	0	0	8
К	8	1	5	1	1	6	5	2	7	1	2	7	0	5	8	0	7	6	6	7	0	0	6	0	1	0	0	0	0	0	0	0	7
Л	8	4	1	2	1	8	6	1	8	0	4	4	1	6	7	0	0	3	3	6	3	0	0	3	1	1	0	6	8	0	7	8	6
М	7	5	7	2	2	8	0	1	7	0	4	4	7	6	8	5	1	3	1	6	1	0	0	0	0	0	0	7	3	0	0	6	8
Н	9	0	3	3	6	8	1	1	9	0	6	0	1	7	8	0	0	5	7	6	5	2	5	3	0	0	0	8	5	0	4	6	7
О	2	8	8	8	8	6	7	7	6	8	7	8	8	7	6	7	8	8	8	3	2	5	6	7	6	5	0	0	1	5	2	5	9
П	7	0	0	0	0	8	0	4	7	0	3	6	1	4	8	4	9	4	5	6	2	0	1	0	0	0	0	4	5	3	0	4	4
Р	9	1	6	4	4	8	6	0	8	0	5	2	6	6	8	4	2	6	6	7	3	5	4	2	4	2	0	7	4	0	1	6	7
С	6	4	6	2	5	7	2	0	7	0	7	8	6	6	8	7	5	6	9	6	3	5	1	5	5	0	0	5	6	1	3	8	7
Т	8	2	7	1	4	8	0	0	8	0	6	4	5	6	9	3	8	8	4	6	0	0	0	4	0	2	1	7	8	0	1	5	8
У	3	4	4	6	6	7	6	5	3	3	6	5	5	6	0	6	7	7	7	1	5	5	0	6	3	6	0	0	0	0	7	4	8
Ф	6	0	0	0	0	5	0	0	6	0	0	2	2	0	6	0	4	0	3	5	4	0	0	0	0	0	0	1	0	0	0	0	2
Х	4	3	3	0	0	4	0	0	3	0	1	1	0	5	6	0	5	3	1	3	0	0	2	0	0	0	1	0	0	0	0	0	8
Ц	5	0	6	0	0	6	0	0	7	0	0	0	0	0	3	0	0	0	0	4	0	0	0	0	0	0	0	5	0	0	0	0	5
Ч	7	0	1	0	0	8	0	0	7	0	6	1	0	6	2	0	1	0	7	3	0	0	0	1	3	0	0	1	3	0	0	0	4
Ш	5	0	0	0	0	6	0	0	7	0	3	3	0	3	4	0	3	0	3	4	0	0	0	0	0	0	0	0	4	0	0	0	5
Щ	6	0	0	0	0	7	0	0	6	0	0	0	0	2	0	0	2	0	0	4	0	0	0	0	0	0	0	0	4	0	1	0	1
Ъ	0	0	0	0	0	4	0	0	0	0	0	0	0	0	0	0	O	O	O	O	O	O	O	O	O	O	O	O	O	0	0	3	2
Ы	1	4	7	3	5	7	1	5	1	7	5	5	6	2	1	5	5	5	6	0	0	7	0	5	4	1	0	1	0	0	0	1	8
Ь	0	1	0	0	0	3	0	7	1	0	6	0	4	7	1	0	0	6	4	0	0	0	0	1	6	1	0	0	0	0	6	2	8
Э	0	0	4	0	0	1	0	0	0	2	6	5	2	1	0	2	0	1	7	0	4	3	0	0	0	0	0	0	0	0	0	0	1
Ю	0	5	0	0	2	0	1	2	0	4	1	0	0	0	0	0	0	3	7	0	0	0	0	6	1	7	0	0	1	0	3	0	7
Я	0	1	5	2	5	6	2	5	0	2	2	3	6	5	0	1	4	4	7	0	0	4	4	3	0	4	0	0	0	0	6	4	9
	7	8	9	7	8	7	5	8	8	3	8	6	8	9	9	9	8	9	8	7	7	6	7	8	5	1	1	2	1	8	2	6	0

Рис. 5. Граф логарифмов частот следования столбцов.

Для дешифровки перехваченного сообщения необходимо найти такой порядок следования столбцов, чтобы получить максимальную сумму логарифмов (наиболее вероятное следование столбцов в исходном сообщении). Существует множество методов решения этой задачи (задачи коммивояжера) [6]. Самый простой – полный перебор вариантов. Самый быстрый был предложен в 1965 году Литтлом под названием «Метод ветвей и границ». Для простых случаев, как в данной лабораторной работе, целесообразно применить полный перебор. Результат решения приведен на рис.6.

Рис. 6. Подграф максимального пути.

Для полученного графа составляем возможные варианты таблиц (Рис.7).

	1	3	2	4
1	A	Ю	3	Ж
2	E	с		Ш
3	Г	о	T	0
4	И	E	П	P

	4	1	3	2
1	Ж	A	Ю	3
2	Ш	E	с
3	0	Г	о	T
4	P	И	E	П

	2	4	1	3
1	3	Ж	A	Ю
2		Ш	E	с
3	T	0	Г	о
4	П	P	И	E

	3	2	4	1
1	Ю	3	Ж	A
2	с		Ш	E
3	о	T	0	Г
4	E	П	P	И

Рис. 7. Варианты таблиц, составленных на основе подграфа максимального пути.

Текст в одной из них уже читается и, расставив строки в порядке (4123), получим расшифровку ПРИЕЗЖАЮ ШЕСТОГО (Рис.8).

	2	4	1	3
4	П	P	И	E
1	3	Ж	A	Ю
2		Ш	E	С
3	T	0	Г	0

Рис. 8. Расшифрованный текст.

ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ

Зашифровать предложение из 16 символов методом двойной перестановки и показать преподавателю.

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

Сравнить полученный и исходные ключи.

Разработать программы, позволяющие максимально автоматизировать процесс криптоанализа (автоматизированное рабочее место криптоаналитика).

СОДЕРЖАНИЕ ОТЧЕТА

Цель работы.

Результаты выполнения пунктов задания на лабораторную работу.

Схемы алгоритмов для автоматизированного рабочего места криптоаналитика, листинги разработанных программ.

Выводы по работе.

ЛИТЕРАТУРА

Белкин П.Ю. и др. Программно-аппаратные средства обеспечения информационной безопасности. Защита программ и данных. Уч. пос. для вузов. – М.: Радио и Связь, 1999. – 168 с.

Грушко А.А., Тимонин Е.Е. Теоретические основы защиты информации. – М.: Изд. Агенство «Яхтсмен» – 1996. – 192 с.

Торокин А.А. Основы инженерно-технической защиты информации. – М.: Изд. «Ось», 1998. – 336 с.

Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс.: в 2-х ч. Ч. 2: Пер. с нем. – М.: Мир, 1990. – 423 с.

Жельников В. Криптография от папируса до компьютера. – М., АВF, 1996. – 336 c.

Бондарев В.М., Рублинецкий В.И., Качко Е.Г. Основы программирования. – Харьков: Фолио, 1997. – 368 с.