Некоммерческое акционерное  общество
АЛМАТИНСКИЙ  УНИВЕРСИТЕТ  ЭНЕРГЕТИКИ  И СВЯЗИ
Кафедра компьютерных технологий
ОСНОВЫ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ

ЧАСТЬ 2
Методические указания по выполнению
лабораторных работ
для студентов специальности
5В070400 -  Вычислительная техника и программное обеспечение

Алматы 2014

СОСТАВИТЕЛИ: Б.М. Шайхин, А.Р. Оразаева, Г.С. Ыбытаева. Основы информационной безнопасности. Часть 2. Методические указания к выполнению лабораторных работ для студентов специальности 5В070400 -  Вычислительная техника и программное обеспечение. – Алматы: АУЭС, 2014. - 48 с.

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

Методические указания к выполнению лабораторных работ для студентов специальности 5В070400 - Вычислительная техника и программное обеспечение.

Ил. 30, табл. 19, библиогр. – 2 назв.

Рецензент: Ни А.Г.

Печатается по плану издания некоммерческого акционерного общества «Алматинский университет энергетики и связи» на 2014 г.

© НАО «Алматинский университет энергетики и связи», 2014 г.

Содержание

Введение	4
1 Лабораторная работа № 1. Шифрование методом скользящей перестановки	6
2 Лабораторная работа № 2. Изучение программных продуктов защиты информации. Программа PGP	18
3 Лабораторная работа № 3. Корректирующие коды. Коды Хэмминга	29
4 Лабораторная работа № 4. Корректирующие коды. Циклические коды	32
5 Лабораторная работа № 5. Методы сжатия по Шеннону и Хаффмену	36
6 Лабораторная работа № 6. LZW-сжатие	43
Список литературы	47

Введение

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

Данная работа включает 6 методических описаний лабораторных работ с комплектом исполняемых модулей.

Вторая часть включает лабораторные задания для исследования шифра скользящей перестановки; изучения пакета PGP (Pretty Good Privacy) – программного обеспечения для за­щиты конфиденциальной информации, исследования механизмов сохранения целостности информации с использованием кодов, исправляющих ошибки (коды Хэмминга и CRC-коды), и эффективному сжатию данных: алгоритмы сжатия по Шеннону – Фано, Хаффмену и LZW-сжатие.

При выполнении лабораторных заданий второй части предполага­ется рассмотрение следующих вопросов.

Исследование шифра скользящей перестановки с использованием программной реализации XY-Mover (лабораторная работа № 1).

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

Освоение средств программной системы PGP, предназначенных:

-для шифрования конфиденциальных ресурсов и разграничения доступа к ним;

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

-надежного уничтожения остаточной конфиденциальной инфор­мации;

-скрытия присутствия в компьютерной системе конфиденциаль­ной информации с помощью виртуального диска (лабораторная рабо­та № 2).

Ознакомление с общими принципами построения и использования корректирующих кодов для контроля целостности информации, распространяемой по телекоммуникационным каналам. Изуче­ние принципов построения кодов Хэмминга и циклических кодов (лабораторные работы № 3 и №4).

Рассмотрение статистических принципов сжатия информации с использованием методов Шеннона – Фано и Хаффмена (лаборатор­ная работа № №5).

Ознакомление с принципами сжатия информации с использованием метода LZW (Lempel – Ziv – Welch) (лабораторная работа № 6).

Лабораторная работа состоит из выполнения рабочего задания, оформление отчета и защиты проделанной работы.

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

Выполнение каждой лабораторной работы должно завершатся оформлением отчета, который должен содержать:

-     цель и задания работы;

-     краткие итоги теоретической подготовки;

-     результаты проделанной работы;

-     выводы по работе и список использованной литературы;

Выполненная работа и оформленный отчет защищается у преподавателя.

Отчет может быть оформлен в электронном виде.

1 Лабораторная работа № 1. Шифрование методом скользящей перестановки

Цель работы: исследование шифра скользящей перестановки с ис­пользованием программной реализации XY-Mover.

Задание:

1)  Для выполнения лабораторной работы на компьютере необходимо установить программный модуль XY-Mover.

2)  Выполнить начальные установки шифратора согласно своему варианту (см. таблицу 1.1).

3)  Загрузить файл для шифрования.

4)  Произвести шифрование информации с использованием шифра скользящей перестановки, сохранить шифртекст в файле.

5)  Описать в отчете процесс шифрования и расшифрования данных с использованием программы-эмулятора XY-Mover. Проанализировать полученные данные.

6)  Включить в отчет о лабораторной работе ответы на контрольные вопросы.

Таблица 1.1

Вариант	Параметры шифратора
	n1	n2
0	64	63
1	59	68
2	53	74
3	47	80
4	49	78
5	42	85
6	38	89
7	37	90
8	35	92
9	33	94

Описание лабораторной работы. Устойчивые закономерности откры­того текста и их использование при дешифровании шифров простой заме­ны и перестановки. Возможность дешифрования какого-либо шифра в значительной мере зависит от того, в какой степени криптографические преобразования разрушают вероятностно-статистические за­кономерности, присутствующие в открытом содержательном тексте. Так, в осмысленных текстах любого естественного языка различные буквы встречаются с разной частотой, при этом относительные часто­ты букв в различных текстах одного языка близки между собой. То же самое можно сказать и о частотах пар, троек букв открытого текста, Кроме того, любой естественный язык обладает так называемой избы­точностью, что позволяет с большой вероятностью «угадывать» смысл сообщения, даже если часть букв в сообщении не известна.

Таблицы относительных частот появления букв в тексте (см. таблицу 1.2) приводятся в разных книгах. Они получены на основе подсчетов ча­стот на больших объемах открытого текста. Учитывая, что для экспериментов берется различный исходный материал, значения вероятностей несколько отличаются между собой.

Таблица 1.2

1	а - 0,062	12	л - 0,035	23	ц - 0,004
2	б - 0,014	13	м - 0,026	24	ч - 0,012
3	в - 0,038	14	н - 0,053	25	ш - 0,006
4	г - 0,013	15	о - 0,090	26	щ - 0,003
5	д - 0,025	16	п - 0,023	27	ы - 0,016
6	е,е - 0,072	17	р - 0,040	28	ъ,ь - 0,014
7	ж - 0,077	18	с - 0,045	29	э - 0,003
8	з - 0,016	19	т - 0,053	30	ю - 0,006
9	и - 0,062	20	у - 0,021	31	я - 0,018
10	й - 0,010	21	ф - 0,002	32	-0,175
11	к - 0,028	22	х - 0,009

Если упорядочить буквы по убыванию вероятностей, то мы получим следующий вариационный ряд:

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

Например, в слове «СЕНОВАЛИТР» содержатся 10 наиболее часто встречающихся букв.

Частоты знаков алфавита зависят не только от языка, но и от характера текста. Так, в тексте по криптографии будет повышена вероятность букв «Ф», «Ш» из-за часто встречающихся слов «шифр», «криптогра­фия». В некоторых математических текстах может быть завышена частота буквы «Ф» из-за слов «функция», «функционал» и т.п. В стандартных текстовых файлах наиболее частым является символ «пробел». Частотная диаграмма содержательных текстов является устойчивой характе­ристикой текста. Из теории вероятностей следует, что при достаточно слабых ограничениях на вероятностные свойства случайного процесса справедлив закон больших чисел, т.е. относительные частоты  зна­ков сходятся по вероятности к значениям их вероятностей Р_к

.

Шифры перестановки и простой замены не полностью разрушают вероятностно-статистические свойства, имеющиеся в открытом общении.

При дешифровании текста, зашифрованного шифром простой замены, используют частотные характеристики открытого текста. Именно если подсчитать частоты встречаемости знаков в шифрован­ном тексте, упорядочить их по убыванию и сравнить с вариационным рядом вероятностей открытого текста, то эти две последовательности будут близки. Скорее всего на первом месте окажется пробел, далее будут следовать буквы «О», «Е», «А», «И».

Конечно, если текст не очень длинный, то не обязательно полное совпадение. Может оказаться на втором месте «О», а на третьем «Е», но в любом случае в первых и вторых рядах одинаковые буквы будут располагаться недалеко друг от друга, и чем ближе к началу (чем больше вероятность знаков), тем меньше будет расстояние между знаками.

Аналогичная картина наблюдается и для пар соседних букв, биграмм, открытого текста (наиболее частая биграмма русского от­крытого текста — СТ). Однако для получения устойчивой картины длина анализируемой последовательности должна быть достаточно большой. На сравнительно небольших отрезках открытого текста эта картина как-то смазана. Более устойчивой характеристикой биграмм является отсутствие в осмысленном тексте некоторых биграмм, как говорят, наличие запретных биграмм, имеющих вероятность, равную практически нулю.

Видели ли вы когда-нибудь в открытом тексте биграмму «ЪЬ» или биграммы вида «гласная» Ь, «пробел» Ь? Знание и использование ука­занных особенностей открытого текста значительно облегчает дешиф­рование шифра перестановки и замены.

Шифр перестановки. Положим X — множество открытых (содержательных) текстов в алфавите I. Длины всех возможных открытых тек­стов кратны величине Т. Множеством ключей является симметриче­ская группа подстановок S_T степени Т, для gS_T определим функцию шифрования f_g, положив для (i₁, i₂, …, i_T) X

f_g(i₁, i₂, …, i_T)= (i_g(1), i _g(2), …, i _g(T)),

доопределим f_g на остальных элементах из X по правилу: текст хX делится на отрезки длины Т и каждый отрезок длины Т шифрует­ся на ключе g по указанному выше закону шифрования. Последовательность, составленная из букв образов зашифрованных слов, является шифрованным текстом, соответствующим открытому тексту x и ключу g. Для шифрования текста длины, не кратной Т, его дополня­ют буквами до длины, кратной Т.

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

Рассмотрим пример дешифрования шифра перестановки восьми столбцов. Пусть шифротекст имеет следующий вид (см. таблицу 1.3).

Таблица 1.3

1	2	3	4	5	6	7	8
п	а	я		в		и	м
о	ч	ш	г		у		е
е	б	ж	л		е		о
м		ч		о	т	о	я
	е	г	е		у	с	щ
	а	к	ь	з	а	т	т
я	р	е		е	п		ь
	ю	3	в	а	н	в
о	й	а	в	е	ш	л
	е	- е	я	м		п	н
ь	р	р	н	з	е	е	е
3	а	м	а	н		а	к
ч	с	т	а		ь	а	н
о	я	л	м		а	л
о	ь	ч	х	т	а	т
в		е	о	а	л	е	п
о	е	р	м	т	ь	е
д	с	г	ы		о	а	т
е	б	в	н		ы
	а	у	и	н	з	н	л
	г	и	а	о	к	к	д
	а	о	б	д	г	н
	ж	а		е	д	я	д
х	л	и		е	м	о	а
к	р	т	д		ь	о	е
	ь	х	в	т	о	н
	л	е		е	д	а	ю
р		з	е	в		е	д
ш		в	а	е	н	е	н
т	и	й	е	в			д
		в		с	д

Сопоставим перестановки столбцов таблицы 8·8, при этом поставим на пересечении i-й строки и j-й столбца единицу, если j-я колонка после штатной перестановки должна следовать за i-й. Наша задача — восста­новить таблицу, отвечающую правильной перестановке столбцов.

Давайте теперь попарно пристраивать один столбец к другому. Если при этом в некоторых строках появляются запретные биграммы, то столбцы не могут в открытом тексте следовать друг за другом и соот­ветствующая клеточка зачеркивается. В нашем примере шестой стол­бец не может следовать за четвертым, так как иначе в тексте в первой строке будет подряд два пробела. Посмотрим, например, шестую стро­ку. Если бы четвертый столбец следовал за первым, то в тексте были бы слова, начинающиеся с «Ь».

После просмотра всех строк получим таблицу 1.4.

Таблица 1.4

	1		2	3	4	5	6	7	8
1	X		X		X	X	X		X
2			X		X		X
3				X					X
4	X		X		X		X	X	X
5	X					X	X	X	X
6	X	X			X		X	X
7	X				X	X	X	X	X
8	X	X				X	X	X	X

Если бы текст был подлиннее и строк было бы побольше, то в каж­дой строке и в каждом столбце осталось бы ровно по одной не зачерк­нутой клеточке и перестановка была бы восстановлена.

В таблице 1.4 только можно утверждать, что шестой столбец следует за третьим (обозначим это событие следующим образом: 3 6), если шестой столбец не является последним. Для шестого столбца может быть два варианта продолжения:

      8

      

365.

Нам надо рассмотреть оба и постараться отсеять ложный вари­ант. Если отсеять ложный вариант не удастся, то надо продолжать оба варианта

      84   1

     

36527.

В итоге получаем некоторое дерево возможного следования столб­цов в открытом тексте.

       7

                

36528417

     

     8    4   17

     

     4    17

   

     5

   

     27

   

     17.

Каждой ветви дерева соответствует некоторая перестановка столбцов.

Далее проверяем каждый вариант на осмысленность и получаем правильный вариант

36528417.

Заметим, что не обязательно было строить дерево до конца. Напри­мер, ветвь 36845 можно было отсеять сразу. Разве можно признать осмысленным фрагмент текста, приведенный в таблице 1.4?

Таблица 1.5

3	6	8	4	5
я		м		в
ш	у	е	г
ж	е	о	л
ч	т	я		о
г	у	щ	е	з
к	а	т	ь	е
е	а	т		а

Такая процедура отсечения ветвей была бы просто необходима, если бы строк было поменьше и дерево было бы соответственно го­раздо ветвистей. Предложенную процедуру легко автоматизировать и сделать пригодной для реализации на ЭВМ. Алгоритм дешифрова­нии должен состоять из следующих этапов:

1)  Предварительная работа. Анализируя достаточно представительный объем открытых текстов, построить множество запретных биграмм.

2)  Предварительная работа. Составить словарь всех возможных ν грамм для ν=2, 3,..., d, которые могут встретиться в открытом тексте. Число d выбирается, исходя из возможностей вычислительной техники.

3)  Построить таблицу 8·8. При этом перебираются последовательно все запретные биграммы и для каждой опробуемой биграммы — по­следовательно все строки. Если хотя бы в одной строке первый символ биграммы встречается в i-м столбце, а второй — в j-м, то клеточка i·j таблицы зачеркивается.

4)  Выбрать некоторый столбец в качестве начального.

5)  Начать процедуру построения дерева путем пристраивания к ис­ходному столбцу всех вариантов столбцов.    

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

7)  Для каждого из неотсеянных вариантов добавляем еще один столбец и проводим отсев ложных вариантов по словарю разрешен­ных 4-грамм.

Если словарь был построен только для d3, то отсев проводится путем проверки на допустимость 3-грамм, встретившихся в последних трех столбцах каждой строки. Продолжаем этот процесс до получения полной перестановки.

В таблице 1.5 приведен восстановленный для нашего примера текст.

Таблица 1.6

	1	2	3	4	5	6	7	8
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	т	ь		р	е	д	к	о
26	х	о	т	ь		в		н
27	е	д	е	л	ю		р	а
28	з		в		д	е	р	е
29	в	н	е		н	а	ш	е
30	й		в	и	д	е	т	ь
31	в	а	с

Дальнейшее развитие шифры перестановки получили осущест­влением идеи непрерывной локальной перестановки символов от­крытого текста под действием управляющей последовательности. Для осуществления перемешивания знаков открытого текста в памяти шифратора запоминаются отдельные знаки текста и прово­дится задержка их передачи в дискретном времени. Введем параметры n₁ и n₂ так, что п=п_х+п₂. В этих шифрах i-й знак передаваемого сообщения переставляется в шифрованном сообщении на j-е место, где i-n_i ≤ j≤ i + п₂.

Управляющую последовательность временем задержки стараются выбрать так, чтобы время задержки каждого символа было случайной величиной с равномерным распределением, т.е. вероятность каждого фиксированного значения времени задержки должна быть близка к 1/п.

 Рассмотрим схему шифрующего автомата, позволяющего при подходящей управляющей последовательности реализовать произвольный шифр скользящей пе­рестановки (см. рисунок 1.2).

На вход узла формирования задержки (УФЗ) в каждом такте t по­дается вектор ,

Узел формирования задержки является конечным автоматом , множеством состояний которого является множество всевозможных двоичных векторов — заполнений  нижнего накопителя. В такте t вырабатывается натуральное число — значение  задержки

.

Рисунок 1.1 - Схема реализации шифрующего автомата скользящей перестановки

При этом автомат переходит в следующее состояние:

,

где

=1,

.

Знаки открытого текста записываются на нижний накопитель. В линию в t-м такте посылается знак открытого текста, записанный в ячейке с номером . Состояния автомата  являются индикаторами, показывающими, какие из знаков открытого текста еще не считаны с нижнего накопителя.

Для зашифрования последовательности t_N,…, t₂, t₁ поступают следующим образом. Сначала записываем в нижний накопитель первые n₁ знаков открытого текста

(t_n1,…, t₁, 0,…, 0).

Одновременно автомат устанавливается в начальное состояние

=(0,...,0).

После этого автомат УФЗ начинает работать по описанному выше закону до тех пор, пока в накопитель не поступит последний знак t_N открытого текста. С прекращением подачи на накопитель знаков открытого текста происходит прекращение подачи единиц на накопитель-индикатор. В оставшиеся n₁ тактов производится счи­тывание записанной в накопителе информации.

При расшифровывании УФЗ работает по той же схеме, только вместо считывания необходимо организовывать запись информации во второй накопитель.

Рассмотрим особенности работы УФЗ. В каждом такте t (за исклю­чением последних n₁ тактов) в накопителе-индикаторе  записано ровно n₁ единиц. Поэтому в такте t величина задержки может прини­мать только одно из  n₁ значений в интервале {1,..., п}. В частном слу­чае, когда п = 1 либо n₁=n, УФЗ вырабатывает постоянно значения задержки  и  соответственно. Легко видеть, что результи­рующее преобразование открытого текста действительно будет шиф­ром скользящей перестановки. Условие  обеспечивает постоянное считывание во всех тактах, а условие =1 ограничивает величину задержки ≤n.

Пример 1

Примем п=7, n₁=3, п₂=4. На вход УФЗ на каждом шаге t работы шифрующего автомата подается вектор , получаемый в линейном регистре сдвига (JIPC) (см. рисунок 1.2).

Рисунок 1.2 - Линейный регистр сдвига

Будем обозначать на каждом шаге работы шифрующего автомата последователь­ность y₁, у₂,..., у_n (в нашем случае у₁, у₂,..., y₇), поступающую с JIPC, как «Y», а последовательность единиц х₁, х₂, ..., х_п (в нашем случае х₁, х₂, ..., х₇) как «1». В нижней строке будем записывать знаки открытого текста, находящиеся на данном шаге в нижнем на­копителе шифрующего автомата t₁, t₂,.... t_n (в нашем случае t₁, t₂,.... t₇). Рассмотрим по­шагово работу шифратора при конкретных условиях.

На каждом шаге, начиная с левого края и идя направо, мы искали первое совпадение в строках Y и 1 (1 в обеих строках) и для удобства обводили этот столбец. Элемент откры­того текста, который оказался в выбранном столбце, уходит в линию. Таким образом, в нашем примере последовательность, ушедшая в линию, имеет следующий вид:

t₂, t₄, t₅, t₆, t₁, t₇, t₃, t₈.

Описание программной реализации. Для выполнения лабораторной работы на компьютере необходимо установить программный модуль XY-Mover. Ниже представлены основные элементы программы:

1)  Строка меню. В данной программе меню состоит из трех пунктов: «ШИФРОВАНИЕ, ВИД, ПОМОЩЬ». Необходимый пункт меню можно выбрать, щелкнув по нему левой кнопкой мыши, или с помощью кнопок клавиатуры «вправо», «влево», нажав перед этим функциональную клавишу F10. После того как пользователь выбрал необходимый ему пункт меню, откроется ниспадающее подменю. Рассмотрим пункт меню подробнее.

а)  «ШИФРОВАНИЕ» — пункты ниспадающего меню можно выбрать либо левой кнопкой мыши, либо кнопками клавиатуры «↑», «↓». Рассмотрим подробнее пункты подменю:  

- «РЕДАКТИРОВАНИЕ ПАРАМЕТРОВ» — позволяет задать необходимые параметры в поле окна программы «Параметры шифратора»,

- «ШИФРОВАТЬ» — запускает процесс шифрования,

- «ДЕШИФРОВАНИЕ» — запускает процесс дешифрования,

- «ВЫХОД» — завершение работы программы;

б)  «ВИД» — этот пункт меню позволяет выбрать внешний вид программы. Ниже приводятся пункты подменю:

- «ПАРАМЕТРЫ» — позволяет использовать поле «Параметры шифратора», описанную ниже;

- «СХЕМА ШИФРАТОРА» — позволяет наблюдать структурную схему шифрующего автомата;

- «СТРОКА СОСТОЯНИЯ» — выбор этого пункта меню позволя­ет наблюдать строку состояния, описанную ниже.

2) Панель инструментов. Возможно, пользователю будет удобнее воспользоваться панелью инструментов (так называемыми кнопками) вместо работы с меню. Кнопки дублируют некоторые пункты меню, но выбрать кнопку гораздо удобнее, чем пункт подменю. Для этого не­обходимо щелкнуть по выбранной кнопке левой кнопкой мыши. Рассмотрим кнопки слева направо:

а)  А, позволяет получить результат, аналогичный пункту меню: «ВИД/ПАРАМЕТРЫ»;

б)  схема шифратора — позволяет получить результат, аналогичный пункту меню «ВИД/СХЕМА» шифратора;

в)  строка состояния — позволяет получить результат, аналогичный пункту меню: «ВИД/СТРОКА СОСТОЯНИЯ»;

г)   редактирование параметров — позволяет получить результат, ана­логичный пункту меню «ШИФРОВАНИЕ/РЕДАКТИРОВАНИЕ ПА­РАМЕТРОВ»;

д)  шифровать — позволяет получить результат, аналогичный пункту меню «ШИФРОВАНИЕ/ШИФРОВАТЬ»;

е)   «дешифровать» — позволяет получить результат, аналогичный пункту меню «ШИФРОВАНИЕ/ДЕШИФРОВАТЬ»;

ж)«прервать» — позволяет прервать процесс обработки данных (шифрование или дешифрование).

3) Строка состояния. Строка состояния находится в нижней части окна программы. На ней выводится информация о состоянии программы:

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

б)  завершено ... % — индикация объема выполненной работы при шифровании или расшифровании.

4) Описание полей окна программы:

а)  параметры шифратора:

- п₁ — число знаков, которые записываются в нижний накопитель первыми,

- п₂ — остальные знаки (всего их 127),

- отводы регистра — точки съема ЛPC,

- начальное заполнение — начальное заполнение ЛРС, которой пользователь может изменять;

б)  входной поток:

- поле, в котором отражается имя текстового файла, содержа­ние которого нужно шифровать/расшифровать,

- кнопка «Открыть» — при нажатии на эту кнопку открывается стандартное для Windows окно «ОТКРЫТИЕ ФАЙЛА»,

- текст - содержимое файла, открытого для шифрования/расшифрования,

- битовый поток - побитное представление символов выбранного файла;

в)  выходной поток:

- поле, в котором отражается имя текстового файла, содержание которого нужно расшифровать/шифровать,

- кнопка «Открыть» — при нажатии на эту кнопку открывается стандартное для Windows окно «ОТКРЫТИЕ ФАЙЛА»,

- текст — содержимое файла, открытого для расшифрования/ шифрования,

- битовый поток — побитное представление символов выбранного файла.

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

1)  Почему шифрование методом гаммирования является наиболее подходящим для высокоскоростных линий телекоммуникационной связи?

2)  Какие общие требования предъявляются к гамме шифра?

3)  Приведите пример, поясняющий работу шифрующего автомата скользящей перестановки при п = 5, п₁= 2, n₂= 3.

4)  Кратко опишите работу схемы реализации шифра скользящей перестановки.

5)  В чем заключается метод скользящей перестановки?

6)  Предложите свой метод перестановки. Укажите его достоинства и недостатки.

7)  Расскажите об особенностях системы "Рубикон".

8)  Попробуйте сделать сами перестановку, основанную на кубике Рубика. Сделайте ее модель.

2 Лабораторная работа № 2. Изучение программных продуктов защиты информации. Программа PGP

Цель работы: ознакомление с общими принципами построении и использования программных средств защиты информации, в частности, с программой PGP (Pretty Good Privacy).

Для выполнения лабораторной работы при отсутствии на компьютере программы PGP ее необходимо инсталлировать.

Инсталляционный файл прилагается к описанию лабораторной работы PGPfreeware602i.

Выбрать для установки только следующие компоненты:

-      PGP 6.0.2 Program Files;

-      PGP 6.0.2 User’s Manual;

-      Unconfigured PGP 6.0.2 Client Install;

-      PGP disk for Windows.

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

Освоение средств программной системы PGP, предназначенных:

-      для шифрования конфиденциальных ресурсов и разграничения доступа к ним;

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

-      надежного уничтожения остаточной конфиденциальной информации;

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

 

Задание.

1. Ознакомиться со сведениями о программе PGP.

2. Запустить программу PGPtools (с помощью меню ПУСК или значка PGPtray на панели задач), ознакомиться и отразить в отчете и о лабораторной работе состав программных средств, входящих в систему PGP (при необходимости воспользоваться справкой о системе PGP).

3. Создать криптографические ключи с помощью программы PGPkeys. Включить в отчет о лабораторной работе сведения о порядке создания ключей шифрования в системе PGP, а также копии используемыx при этом экранных форм, а также ответы на вопросы:

-     как обеспечивается случайность выбираемых криптографических ключей в системе PGP;

-     как и где хранится секретный ключ пользователя в системе PGP;

-     как может быть обеспечена в системе PGP возможность восстановления секретного ключа пользователя при его случайной утрате?

4. Изучить (на примере обычных текстовых файлов и файлов изображений) способы шифрования и расшифрования файлов с по­мощью функций Encrypt и Decrypt программы PGPtools. Включить в отчет о лабораторной работе сведения о порядке шифрования и рас­шифрования файлов в системе PGP, а также копии используемых при этом экранных форм и ответы на вопросы:

-     какие дополнительные параметры шифрования могут быть использованы, в чем их смысл и возможное применение (обязательно проверить на примере и результаты проверки отразить в отчете);

-     как генерируется, как и где хранится ключ симметричного шифрования файла в системе PGP;

-     как можно обеспечить доступ к зашифрованному файлу со стороны других пользователей;

-     изменяется ли и как размер файла после его шифрования (привести конкретные примеры для разных типов файлов)?

5. Изучить (на примере документов из своей папки) способы полу­чения и проверки электронной цифровой подписи под файлами с по­мощью функций Sign и Verify программы PGPtooIs. Включить в отчет сведения о порядке обеспечения аутентичности и целостности электрон­ных документов в системе PGP, а также копии используемых при этом экранных форм и ответы на вопросы:

-     какие дополнительные параметры получения электронной цифровой подписи могут быть использованы, в чем их смысл и возможное применение (обязательно проверить на примере и результаты провер­ки отразить в отчете);

-     какова реакция программы на нарушение целостности подпи­санного документа (обязательно проверить на примере и результаты проверки отразить в отчете)?

6. Изучить способы одновременного шифрования (расшифрования) и получения (проверки) электронной цифровой подписи в системе PGP с помощью функций Encrypt Sign и Decrypt/Verify программы PGPtooIs. Включить в отчет сведения о порядке одновременного обеспечения конфиденциальности, аутентичности и целостности электронных документов в этой системе, а также копии используемых при этом экранных форм.

7. Изучить способы надежного удаления файлов с конфиденциальной информацией с помощью функции Wipe программы PGPtooll. Включить в отчет сведения о порядке уничтожения конфиденциальных электронных документов в системе PGP, а также копии используемых при этом экранных форм.

8. Изучить способы надежного уничтожения остаточной информации, которая может содержать конфиденциальные сведения, с помощью функции Freespace Wipe программы PGPtooIs. Включить в отчет сведения о назначении и порядке использования этой функции программу, копии используемых в ней экранных форм и ответы на вопросы:

-     как достигается надежное уничтожение остаточной конфиденциальной информации в системе PGP;

-     является ли подобный метод уничтожения абсолютно надежным и, если нет, как может быть обеспечено абсолютно надежное уничтожение остаточной информации?

9. Изучить способы быстрого выполнения функций системы PGР с помощью программы PGPtray, ярлык которой размещен в правой части панели задач. Включить в отчет сведения о назначении и порядке использования этой программы, а также копии используемых экранных форм.

10. Изучить способы управления настройками системы PGP при ее использовании в организациях с помощью программы PGPadmin (пройти все шаги диалога с мастером вплоть до последнего, на кото­ром вместо кнопки «Save» нажать кнопку «Отмена»). Включить в отчет сведения о возможностях и порядке администрирования системы PGP, копии используемых при этом экранных форм и ответы на вопросы:

-     какие функции по управлению шифрованием и обеспечением целостности информационных ресурсов предоставляет администратору программа PGPadmin;

-     какие возможности предоставляет программа PGPadmin по управ­лению доступными для пользователей функциями программы PGP и где сохраняется подобная информация?

11. Включить в отчет о лабораторной работе ответы на контрольные вопросы.

 

Описание лабораторной работы.

Основные задачи программы PGP шифровать файлы и почтовые сообщения, заверять их электронными подписями, полностью уничтожать файлы на диске. Программа PGР предоставляет также следующие возможности:

-      хранение открытых ключей на удаленном сервере;

-      использование трех симметричных алгоритмов шифрования и двух асимметричных;

-      четыре способа запуска: E-mail plugins, PGPtray, PGPtools, контекстное меню;

-      разделение ключей;

-      установка уровня валидности ключа и доверия владельцу ключа.

PGPkeys. Это программа, входящая в состав PGP 6.0 и обеспечивающая работу с ключами (см. рисунок 2.1).

Рисунок 2.1 - Окно PGPkeys

В меню «FILE» содержатся две команды, одна из которых «EXIT», дру­гая — «SEND KEY SHARES» позволяет послать локальную копию раз­деленного ключа по сети.

Меню EDIT, кроме обычных команд содержит команду «PREFERENCES», которая служит для задания настроек программы (см. рисунок 2.2).

Рисунок 2.2 - Окно PGP Preferences

С помощью меню «VIEW» можно задать отображаемые на экране свойства ключей.

Команды меню «KEYS»:

«SIGN» — позволяет подписать своим закрытым ключом открытые ключи других пользователей. Тем самым вы можете показать, что до­веряете владельцу используемого ключа, т.е. ключ действительно при­надлежит владельцу. При этом можно задать модификаторы:

1) Non Exportable — для локального набора ключей;

2) Exportable — заверен­ный ключ отсылается на сервер;

3) Meta-introducer Non-Exportable — доверяете не только владельцу, но и любому доверенному им ключу;

4) Trusted Introducer Exportable — вы доверяете владельцу подписывать ключи (см. рисунок 2.3);

Рисунок 2.3 - Окно PGP Sign Key

«SET AS DEFAULT KEY» — назначить данный ключ ключом по умолчанию;

«ADD NAME/PHOTO/REVOKER» — позволяет добавить к свой­ствам ключа имя владельца, имеющего право объявить ваш ключ недействительным;

«REVOKE» — объявить ключ недействительным;

«REVERIFY SIGNATURES» — проверить сигнатуру (правильность) ключа;

«NEW KEY» — добавить новый ключ;

«SHARE SPLIT» — разделить ключ между несколькими вла­дельцами;

«IMPORT/EXPORT» — импортировать/экспортировать ключ из/в текстовый файл;

«KEY PROPERTIES» — свойства (при этом можно задать степень доверия, валидность ключа) (см. рисунки 2.4, 2.5);

Рисунок 2.4 - Окно Key Generation Wizard

Рисунок 2.5 - Окна установки свойств ключа

«SERVER» — в этом меню сосредоточены команды для работы с удаленным сервером ключей;

«SEND ТО» — позволяет послать ключи на выбираемый сервер (см. рисунок 2.6);

«SEARCH» — с помощью этой команды можно попытаться найти на удаленном сервере ключ, задав соответствующие параметры (см. рисунок 2.7);

«UPDATE» — позволяет обновить выбранный ключ, получив информацию с сервера;

Рисунок 2.6 - Соединение с удаленным сервером

Рисунок 2.7 - Поиск ключа на удаленном сервере

«GROUPS «— в этом меню содержатся команды для работы с группами;

«NEW GROUP», «SHOW GROUPS», «IMPORT GROUPS» - позволяют соответственно добавить группу, показать группы, импортировать группы из файла. Объединение владельцев ключей в группы позволяет легко и просто шифровать сообщения для отправки всем членам группы;

«HELP» — стандартное для Windows, позволяет получить справку.

PGPtray. Загружается при запуске Windows. Для активизации меню достаточно нажать кнопкой мыши на значок рядом с часами (см. рисунок 2.8).

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

Если в используемом почтовом клиенте нет встроенных команд PGP, то можно работать с помощью PGPtray. Например, для подиси письма достаточно скопировать его в буфер и исполнить команду Sign Clipboard, а затем вставить в тело письма уже подписанный текст (см. рисунок 2.9).

Рисунок 2.8 - Запуск PGP с использованием значка на панели задач

Рисунок 2.9 - Пример отправки письма с цифровой подписью

Аналогично получателю письма достаточно скопировать получен­ное письмо в буфер обмена и выбрать команду «DECRIPT/VERIFY CLIPBOARD». Естественно, в коллекции ключей должен быть открытый ключ владельца, подписавшего письмо (см. рисунки 2.10, 2.11).

РGPtools. Этот компонент программы PGP представляет собой небольшую панель с кнопками, позволяющими выполнить нужное действие: открыть PGPkeys, зашифровать, подписать, зашифровать и под­писать одновременно, расшифровать/проверить подпись, затереть файл, затереть неиспользуемое дисковое пространство (см. рисунок 2.12).

Рисунок 2.10 - Пример получения письма с цифровой подписью

Рисунок 2.11 - Результаты проверки подписи

Рисунок 2.12 - Компоненты панели PGPtools

Альтернативой программы PGPtools могут служить команды, добавляющиеся при инсталляции PGP в контекстное меню работы с файлами и меню «ФАЙЛ» Проводника Windows.

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

1)  Как выбрать длину криптографического ключа в системе PGP?

2)  В чем достоинства и недостатки криптографических методов защиты информации?

3)  Какие компьютерные системы называются безопасными?

4)  В чем заключаются основные требования к защищенности компьютерных систем?

5)  Для выполнения каких требований к защищенности компьютерных систем могут применяться криптографические методы защиты?

6)  Насколько, на ваш взгляд, надежны методы криптографической защиты информации, используемые в программе PGP?

7)  Какими основными функциями защиты информации обладает программа PGP?

8)  Какой принцип лежит в основе функции надежного уничтожения остаточной конфиденциальной информации программы PGP?

3 Лабораторная работа № 3. Корректирующие коды. Коды Хэмминга

Цель работы: ознакомление с общими принципами построения и использования корректирующих кодов для контроля целостно­сти информации, распространяемой по телекоммуникационным каналам.

Примечание. Для выполнения лабораторной работы на компьютере необходим» установить файл Hemming.exe, который находится в архиве Код Хэмминга.rar.

Задание.

1.  Закодировать с помощью кода Хэмминга предложенный алфавит (варианты указаны в таблице 3.1).

2.  В каждую строку таблицы с закодированной информацией вне­сти одиночную ошибку, зафиксировать в кодовой таблице результат декодирования.

3.  В последние две строки таблицы с закодированной информацией внести двойные ошибки, зафиксировать в кодовой таблице результат      декодирования.

4.  Проанализировать полученные результаты и сформулировать аргументированные выводы.

Описать полученный код Хэмминга:

-      количество контрольных и информационных разрядов и их но­мера;

-      избыточность кода;

-      относительная избыточность;

-      минимальное кодовое расстояние;

-      оценить корректирующую способность полученного кода.

5.  Составить из предложенного алфавита слово длиной не менее пяти символов и закодировать его с помощью полученного кода Хэм­минга. Подсчитать длину исходного текста (кодировка ASCII) и зако­дированного текста (код Хэмминга).

6.  Представить краткий теоретический материал, в котором описать способ кодирования и декодирования информации с помощью кода Хэмминга.

7.  Привести итоги проведенных экспериментов по кодированию с помощью программы Hemming.exe.

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

9.  Привести в отчете ответы на контрольные вопросы в соответ­ствии с номером варианта, указанным преподавателем (см. таблицу 3.1).

Таблица 3.1

Номер варианта	Исходный алфавит
1,5,9, 13,17	Кириллица А... М
2,6, 10, 14, 18,22	Кириллица О ... Я
3,7, 11, 15, 19, 23, 27	Латиница А... N
4, 8, 12, 16, 20, 24, 28	Латиница О... Z
21,25,29, 26, 30	Десятичные цифры 0 ... 9

Описание лабораторной работы.

Программа предназначена для ко­дирования символов по алгоритму Хэмминга. Главное окно програм­мы представлено на рисунке 3.1.

Рисунок 3.1 - Главное окно программы

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

Процессы кодирования и декодирования изображены на рисунке 3.2.

Рисунок 3.2 - Процесс кодирования и декодирования

Светло-серым цветом отмечены контрольные биты, темно-серым — бит общей четности. В полученный код можно вносить ошибки. Оди­ночные ошибки могут быть исправлены, двойные — обнаруживаются без исправления. Если ошибка была исправлена, то указывается, в ка­ком бите она была допущена. Затем символ декодируется. Процесс ис­правления одиночной ошибки представлен на рисунке 3.3.

Рисунок 3.3 - Процесс исправления одиночной ошибки

Если возникает ошибка двойной или более кратности — выводится сообщение о невозможности исправления кода.

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

1)  Что представляет собой код Хэмминга?

2)  Как используется код Хэмминга?

3)  Как составляется код Хэмминга?

4)  Какие ошибки можно исправить с помощью кода Хэмминга?

5)  От каких свойств кода зависит его корректирующая способность?

6)  Какие ошибки могут возникнуть при составлении кода Хэмминга?

7)  Недостатки при составлении кода Хэмминга?

8)  Преимущества  кода Хэмминга?

4 Лабораторная работа № 4. Корректирующие коды. Циклические коды

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

Примечание. Для выполнения лабораторной работы на компьютере необходимо установить файл CyclicCode74.exe из архива Циклический код.rar.

 

Задание.

1.  Получить систематический циклический код, используя приве­денные в таблице 4.1 порождающие полиномы, в соответствии с вари­антом, указанным преподавателем.

Таблица 4.1

Номер варианта	Порождающий полином третьей степени
1,7, 13, 19,25	1011
2, 8, 14, 20, 26	1101
3,9, 15,21,27	1011
4, 10,16, 22, 28	1101
5, 11, 17,23,29	1011
6, 12, 18, 24, 30	1101

2. Представить в отчете краткий теоретический материал, в кото­ром описать способ кодирования и декодирования информации с по­мощью циклического кода.

3. Привести итоги проведенных экспериментов по кодированию с помощью программы  CyclicCode74.exe.

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

5. Привести в отчете ответы на контрольные задания в соответствии с номером варианта, указанным преподавателем (см. таблицу 4.2).

 

Таблица 4.2

Номер варианта	Число
1, 16	1
2, 17	2
3, 18	3
4, 19	4
5,20	5
6,21	6
7,22	7
8, 23	8
9,24	9
10, 25	10
11,26	11
12, 27	12
13,28	13
14, 29	14
15, 30	15

 

Описание лабораторной работы.

Программа предназначена для изу­чения принципов построения ациклических кодов.

1.  Изучить сведения о программе кодирования информации с ис­пользованием циклического кода (папка «ДОКУМЕНТАЦИЯ»). За­пустить программу кодирования (папка «ИСПОЛНЯЕМЫЙ МО­ДУЛЬ», файл CyclicCode74.exe). Главное окно программы представлено на рисунке 4.1.

Рисунок 4.1 - Главное окно программы

2.  Закодировать с помощью циклического кода предложенный ва­риант (см. таблицу 4.1). Для этого в строку «1. Введите число X [0—15]» ввести заданное число (см. рисунок 4.2). Кодовую таблицу сохранить и перенести в личную папку (одновременно нажать Ctrl+Alt+PrtScSysRq, затем Ctrl+V).

Рисунок 4.2 - Пример заполнения полей главного окна программы

3.       Проанализировать полученные результаты и сформулировать ар­гументированные выводы.

                                                                                                       01234567

Пример. Рассмотрим кодирование восьмизначного числа 00011111. Пусть для кодирования задан порождающий полином третьей степени

Р(1,0) = 1101,

Р(х)= 1 +х+х³.

Делим х³  G (х) на Р(х), где информационный полином G(x) = x³ +х⁴ + х⁵ +х⁶ + х⁷:

х³ G(х) = х⁶+х⁷+х⁸+х⁹+х¹⁰,

 

х¹⁰ +х⁹ + х⁸ +х⁷ + х⁶        I  х³ +х + 1       

х¹⁰ + х⁸ + х⁷                  I  х⁷ + х⁶ + х⁴+х²+х+1

х⁹ +х⁶

х⁹ + х⁷+х⁶

        х⁷

        х⁷ +х⁵ + х⁴

              х⁵ +х⁴

              х⁵ + х³+х²

                     х⁴ +х³ +х²

                     х⁴ +х² +х

                            х³ +х

                            х³ +х+ 1

                                        R(х) =1.

Находим значение кодового полинома F(x):

F(x) = (х⁶ + x ⁷ + x ⁸ + x ⁹ +х¹⁰) Å 1.

Таким образом, окончательно кодовая комбинация F(x) имеет вид:

                                           012345678910

                                                    10000011111

                                      Контрольные разряды         → 100         

                                                                                          10000011111.

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

1)   Укажите различия понятий: кодирование информации, шифрование информации.

2)  Определите понятия: равномерные коды, неравномерные коды, префиксное кодирование, разделимое кодирование, систематические коды, несистематические коды.

3)  От каких характеристик кода зависит его корректирующая способность?

4)  Сравните коды Хэмминга и циклические коды по эффективности контроля целостности информации.

5)  Эффективность применения корректирующих кодов.

6)  Приведите пример корректирующих кодов.

7)  Какие бывают алгебраические системы?

8)  Приведите ряд свойств, характеризующих корректирующую способность циклических кодов.

5 Лабораторная работа № 5. Методы сжатия по Шеннону и Хаффмену

Цель работы: ознакомление со статистическими принципами сжатия информации с использованием методов Шеннона — Фано и Хаффмена.

Примечание. Для выполнения лабораторной работы на компьютере необходимо установить файл Shannon-Huffman.exe, который находится в архиве Методы сжатия по Шеннону и Хаффмену.гаг.

Задание.

1. Ознакомиться со сведениями о программе Shannon-Huffman.exe  и рассмотреть примеры эффективного кодировании информации.

2.  Запустить программу Shannon-Huffman.exe, предназначенную для демонстрации методов сжатия информации с использованием ал­горитмов  Шеннона — Фано и Хаффмена.

3.  Выполнить следующие задания:

1)  число символов алфавита к = т (т — номер варианта). Соста­вить такое исходное сообщение, чтобы:

а)   символы алфавита встречались в сообщении с равными вероятностями;

б)   символы алфавита встречались в сообщении с разными  вероятностями;

2)  ввести произвольный связный текст на русском языке. Это может быть пословица, стихотворение или произвольный текст. Используя результаты работы программы, следует проанализировать алфавит введенного сообщения: подсчи­тать количество символов алфавита, значение энтропии Н, среднее количество символов на знак L при целочисленном кодировании.

4. Сохранить в отчете экранные формы, демонстрирующие процесс сжатия информации.

5. Отчет по лабораторной работе должен содержать результаты ана­лиза программы Shannon- Huffman.exe при кодировании; алгоритм по­строения кода Хаффмена и Шеннона с применением знаний по дан­ной тематике; результаты сравнения различных методов кодирования; выводы об эффективности используемых методов сжатия.

6. Включить в отчет о лабораторной работе выполненные задания № 1-3.

Варианты заданий.

Задание 1. Сообщение состоит из последовательности двух букв А и В, вероятности появления каждой из которых не зависят от того, какая была передана раньше, и равны 0,8 и 0,2 соответственно. Произведите кодирование по методу Шеннона:

а) отдельных букв;

б) блоков, состоящих из двухбуквенных сочетаний;

в) блоков, состо­ящих из трехбуквенных сочетаний.

Сравните полученные коды по их эффективности.

Задание 2. Составьте текст, который бы соответствовал данным, при­веденным в таблице 5.1. Используя программу Shannon- Huffman.exe, за­кодируйте текст методом Хаффмена.

Таблица 5.1

Номер варианта	Вероятность появления символов	Символ	Число символов
1,5, 7, 3, 9, 12, 14, 18, 28	0,333333333	о	2
	0,166666667	г	1
	0,166666667	р	1
	0,166666667	д	1
	0,166666667	а	1
2, 4, 6, 8, 16, 21,20, 22, 24, 30	0,25	е	2
	0,25	т	2
	0,125	о	1
	0,125	п	1
	0,125	р	1
	0,125	а	1
11, 13, 15, 10, 17, 19, 23, 25	0,25	р	2
	0,25	а	2
	0,25	с	2
	0,125	т	1
	0,125	е	1

 

Задание 3. Для вариантов а, б, в, приведенных на рисунке 5.1 и в таблице 5.2, составьте код Хаффмена. Рассчитайте среднее количе­ство символов на знак L;  избыточности (L- Н) и относительной избы­точности полученного кода (L - H)/L. Сравните полученные значения с L, Н, (L - Н) для кода Шеннона, сделайте выводы.

а

б

в

Рисунок 5.1 - Варианты заданий

Таблица 5.2

Номер варианта	Задание
1, 5, 7, 3, 9, 12, 14, 18, 28	Задание 3.Вариант а
2, 4, 6, 8, 20, 22, 23, 24, 25, 30	Задание 3. Вариант б
11, 13, 15, 16, 21, 10, 17, 19	Задание 3. Вариант в

Описание лабораторной работы. Работа выполняется на персональ­ном компьютере с использованием программы Shannon-Huffman.exe. Программа предназначена для демонстрации методов сжатия инфор­мации по алгоритмам Шеннона-Фано и Хаффмена (см. рисунок 5.2).

Рисунок 5.2 - Главное окно программы

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

В окне программы ИСХОДНЫЙ ТЕКСТ записывается сообще­ние произвольной длины (или загружается сообщение из заранее под­готовленного файла в формате .txt). Затем необходимо указать число символов, кодируемых за один раз.

Для подсчета вероятности появления букв во введенном сообще­нии Р, определения энтропии источника сообщений Н, среднего чис­ла символов при кодировании одной буквы сообщения L необходимо выбрать закладку АНАЛИЗ.

Для определения эффективности кодирования рассчитывается из­быточность кода (L — H).

Кратко ознакомиться со сведениями о программе вы можете, вы­брав закладку ПОМОЩЬ (см. рисунок 5.3).

Рисунок 5.3 - Просмотр сведений о программе

Чтобы выйти из программы, достаточно выбрать закладку «ФАЙЛ» и далее «ВЫХОД».

Пример 1. Исходное сообщение аббвввггггдддддеееее, состоящее из символов ше­стибуквенного алфавита А = {а, б, в, г, д, е), закодируем методом Хаффмена.

Определяем вероятность появления символа в исходном сообщении:

P=n/N,

где n — число повторов символа в сообщении; 

      N — длина сообщения.

Выпишем в столбец все символы алфавита в порядке убывания вероятности их появления в тексте (см. таблицу 5.3)

Таблица  5.3

Символ	Число повторений символов в данном сообщении	Вероятность появления символов
д	5	0,25
е	5	0,25
г	4	0,20
в	3	0,15
б	2	0,10
а	1	0,05

Последовательно объединяя два символа с наименьшими вероятностями появления символов новый составной символ, вероятность появления которого полагается равной сумме вероятностей составляющих его символов, построим дерево, каждый узел кото­рого имеет суммарную вероятность всех узлов, находящихся ниже него. Проследим путь к каждому листу дерева, помечая направление к каждому узлу (например, направо — 0, налево — 1):

Среднее количество символов на букву сообщения:

L =  = 2 • 2 • 0,25 + 2 • 0,20 + 3 • 0,15 + 4 • (0,10 + 0,05) = 2,45,

где  n(i) — количество знаков в кодовой комбинации  i-го символа алфавита;

       Р(i) — вероятность появления i-го символа алфавита.

Энтропия:

H == 2,425.

Значение избыточности кода:

 (L-H) = 0,025.

Пример 2. Закодируем исходное сообщение методом Шеннона.

Выпишем в столбец все символы в порядке убывания вероятности появления их в тексте. Последовательно делим множество символов на два подмножества так, чтобы сумма вероятностей появления символов одного подмножества была примерно равна сумме вероятностей появления символов другого. Для нижнего подмножества каждому символу приписываем 0, для верхнего - 1. Дальнейшие разбиения повторяются до тех пор, пока все подмножества не будут состоять из одного элемента (см. таблицу 5.4).

Таблица 5.4

Символ	Число повторений символов в данном сообщении	Вероятность появления символов	Код Шеннона
д	5	0,25	1	1
е	5	0,25	1	0
г	4	0,20	0	1	1
в	3	0,15	0	1	0
б	2	0,10	0	0	1
а	1	0,05	0	0	0

Среднее количество символов на букву сообщения:

L = = 0,25 • 2 + 0,25 • 2 + 0,2 • 3+0,15 • 3 +0,1 •  3 + 0,25 • 3 = 2,5.

Энтропия:

H == 2,425.

Значение избыточности кода:

 (L-H) = 0,075.

Сравниваем полученные данные с результатами работы программы (см. рисунок 5.4).

Рисунок 5.4 - Пример кодирования методом Шеннона

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

1)  Какие коды позволяют производить однозначное декодирование даже без использования разделительного символа? Приведите примеры таких кодов.

2)  Назовите условия построения оптимальных кодов.

3)  С какой целью используются эффективные коды и какие из них вам известны?

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

5)  Какие коды позволяют производить однозначное декодирование даже без пробела? Приведите примеры таких кодов.

6)  До какого предела может быть уменьшена средняя длина кодовой комбинации?

7)  Сформулируйте основные теоремы кодирования.

8)  Назовите причины использования блочного кодирования.

9)  Перечислите основные методы сжатия информации.

10)  Как осуществляется сжатие методом лексического кодирования?

6 Лабораторная работа № 6. LZW-сжатие

Цель работы: ознакомление с принципами сжатия информации ме­тодом LZW (Lempel-Ziv-Welch).

Примечание. Для выполнения лабораторной работы на компьютере необходимо установить файл LZW.exe.

Задание.

1.  Сжать и затем распаковать исходные строки символов латинского алфавита, которые набираются непосредственно в окне программы. Сохранить в отчете экранные формы, демонстрирующие процесс cжатия и распаковки информации. Проанализировать сделанную работу  и сделать выводы об эффективности алгоритма сжатия и распаковки.

2.  Сжать и затем распаковать исходные строки символов кириллического алфавита, которые набираются непосредственно в окне программы. Сохранить в отчете экранные формы, демонстрирующие процесс сжатия и распаковки информации. Проанализировать сде­ланную работу и сделать выводы об эффективности алгоритма сжатия и распаковки.

3.  Сжать и затем распаковать исходные строки чисел, которые на­бираются непосредственно в окне программы. Сохранить в отчете экранные формы, демонстрирующие процесс сжатия и распаковки информации. Проанализировать сделанную работу и сделать выводы об эффективности алгоритма сжатия и распаковки.

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

5.  Сжать и затем распаковать исходные строки произвольных сим­волов, которые набираются непосредственно в окне программы. Со­хранить в отчете экранные формы, демонстрирующие процесс сжа­тия и распаковки информации. Проанализировать сделанную работу и сделать выводы об эффективности алгоритма сжатия и распаковки.

6.  Включить в отчет:

-     результаты сжатия и распаковки текстов (варианты указаны в таблице 6.1) с помощью программы LZW-сжатия;

-     сохранить в отчете кодовую таблицу в виде таблицы или рисунка;

-     проанализировать полученные результаты и сформулировать ар­гументированные выводы.

Таблица 6.1

Номер варианта	Номер задания к лабораторной работе
	№ 1	№ 2	№ 3	№ 4	№ 5
1	Program	Информация	612534712	X+Y+Z-12=5	!!A/b/C/dE@?
2	Processor	Математика	954723890	2·X+Y+Z=2	ЪС<л<ш·/dE?
3	Operation	Язык	410125935	X·X+2·Y-3	[4Pu/t%/3$1$
4	Information	Вычисления	181952471	Y·Y+Z=4·X	Ё1?QяЧ·/!Д/?
5	Mathematics	Общество	365412389	X+4Y+Z-2+1	ЙрТиV{G}%
6	Language	Технология	113212598	X+2Y+5·Z=3	ёЮВ&<h>@
7	Company	Кодирование	725847391	5·X+Y+8·Z=5	ЖО[Д]m/я/12
8	Encoding	Информатика	820191856	X-6·Y-3·Z=2	ВН!(И)13№
9	Informatics	Обеспечение	100258741	X-2·Y+7·Z-9	Б!15fЛ2ыф»
10	Software	Операция	101296752	8·X/Y+Z/2=5	У4?-+/25/8?8
11	Editor	Редактор	496123578	5·X/2+Y/12+Z	uФ/z-1/2+3#
12	Table	Процессор	123457890	X/5+5Y+Z/12	Г@14^5D/G
13	Security	Таблица	154789123	7·X>Y+2·8Z	г13#&7Fоэ,
14	Cybernetics	Безопасность	571236984	X·X4·Y<Z+5	ЩП/‘ы’45·7
15	Knowledge	Знания	423987067	X+3·Y>Z+27	i5(B)<px)/Й
16	Computer	Кибернетика	433129851	X/2+2·Y>3·Z	шЁ8впо/тп5?
17	System	Компьютер	184569347	7X+Y-Z/2>45	bP лQas156+
18	Swindle	Система	189242578	Y<5·X/3+Z-2	Z~+258|=[f]
19	Logic	Мошенничество	213459632	2·Z>4·X+5Y	C8&8вАъ/ё
20	Programming	Логика	214357980	X/5+Y/4+Z=5	n-q6&8%^
21	Hardware	Программирование	896124587	Y/4-2X+3Z=6	S?dkошй^·
22	Intellect	Техника	654932140	X+2>Z/4Y+2	P$&Ghgdku
23	Internet	Интеллект	781258743	X+7·Z<2Y+3	J5%jkЖЁ%
24	Translator	Интернет	834107892	2·X-7Z=2+Y	Fd&5&№
25	driver	Транслятор	417625877	6X·X+2·Y-3	Dfj&5·6-2

Описание лабораторной работы.

Лабораторная работа выполняется на персональном компьютере в среде программы  LZW.exe.

При запуске программы  LZW.exe  появляется окно, изображенное на рисунке 6.1, который содержит следующие компоненты:

-     строка текста, где вводится текст для сжатия;

-     строка кода, где выводится код сжатого текста;

-     строка кода, где выводится распакованный текст;

-     таблица выполнения кодирования программой.

Рисунок 6.1 - Главное окно программы

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

Для сжатия какого-либо текста следует выполнить следующие действия:

1) в строку текста «Введите текст» ввести текст для сжатия;

2) нажать кнопку «Сжать»; в строке «Код» появится код сжатого текста;

3) нажать кнопку «Распаковать»; в следующей строке появится рас­пакованный текст;

4) просмотреть таблицу выполнения программы сжатия и распа­ковки текста.

Пример. Исходный текст: RGSU!!!RGSU???; код сжатого текста: R G S U ! #260 #256 #258 ? #264; распакованный текст: RGSU!!!RGSU???

Процесс кодирования представлен на рисунке 6.2.

Рисунок 6.2 - Пример процесса кодирования

 

Примечание. LZW-сжатие выделяется среди прочих. Когда встречается с потоком данных, содержащим повторяющиеся строки любой структуры, уровень сжатия может достигать 50% и выше.

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

1)  В чем состоит принцип LZW-сжатия?

2)  Какие форматы файлов наиболее эффективно архивировать с помощью LZW-сжатия?

3)  В чем особенность процесса распаковки при использовании алгоритма LZW?

4)  Какими достоинствами и недостатками обладает алгоритм

5)  Опишите алгоритм сжатия LZW?

6)  Опишите процедуру LZW-распаковки.

7)  Что такое хэш-функция?

8)  Демонстрационная программа для LZW-алгоритма сжатия/распаковки данных.

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

1.  Шайхин Б.М., Байжанова Д.О. Основы информационной безопасности. Конспект лекций для студентов специальности 5В070400– Вычислительная техника и программное обеспечение. - Алматы: АУЭС, 2013. – 43 с.

2.  Шайхин Б.М., Оразаева А.Р., Ыбытаева Г.С., Жумартов М.А.. Основы информационной безнопасности. Методические указания к выполнению лабораторных работ для студентов специальности 5В070400 - Вычислительная техника и программное обеспечение. – Алматы: АУЭС, 2013. – 45 с.

3.  Вернер М. Основы кодирования : учебник для вузов. – М.: Техно­сфера, 2006.

4.  Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. – М.: Техносфера, 2006.

5.  Хохлов Г.И. Основы теории информации: учеб. пособие. – М.: Академия, 2008.

6.  Варфоломеев А.А. Основы информационной безопасности. Учебное пособие. – М.: РУДН, 2008. -412 с.

Сводный план  2014 г., поз. 246

Шайхин Берк Мырзахметович
Оразаева Айнур Ришатовна
Ыбытаева Галия Сейткалиевна

ОСНОВЫ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ

ЧАСТЬ 2

Методические указания по выполнению
лабораторных работ для студентов специальности
5В070400 -  Вычислительная техника и программное обеспечение

Редактор Л.Т. Сластихина
Специалист по стандартизации Н.К. Молдабекова

Подписано в печать _______
Тираж 50 экз.
Объем 3,0 уч.-изд.л.
Формат 60х84    1/16
Бумага типографская №1
Заказ 123 Цена  300 тн

Копировательно-множительное бюро
Некоммерческое акционерное общество
«Алматинский университет энергетики и связи»
050013, Алматы, Байтурсынулы, 126