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

Самарский государственный архитектурно-строительный университет

Факультет информационных систем и технологий

Кафедра прикладной математики и вычислительной техники

 

О.В. Прохорова

Защита информации

Методические указания к практическим занятиям

Оглавление

1. Помехоустойчивые коды.. 3

2. Алгоритм кодирования и декодирования Хаффмена. 6

3. Дискреционная модель политики безопасности. 13

4. Подсистемы парольной аутентификации пользователей. 20

5. Методы криптографической защиты информации. 29

6. Вычисление контрольной суммы сообщения. 45

7. Ассиметричное шифрование. 49

Библиографический список. 57

 

 

Помехоустойчивые коды

Введем пространство сообщений в виде E(n, Um), где Um - алфавит, m - размерность алфавита, n - число символов из алфавита, образующих сообщение (слово) [1]. Такое пространство сообщений можно рассматривать как метрическое пространство, в котором расстояние между двумя сообщениями x и y, обозначаемое d (x, y) есть число различающихся символов в сообщениях x и y.

 

Пример 1.1. Пусть имеем алфавит U2 = {0,1} и пространство сообщений E(6, U2), в котором формируются сообщения: x = (0 1 0 1 0 0), y = (1 1 1 0 0 0). Расстояние по Хеммингу между этими сообщениями будет равно 3, то есть d (x, y) = 3.

Приведенное определение расстояния d(x,y) в пространстве сообщений удовлетворяет всем свойствам расстояния. В процессе передачи информации по каналам связи возможно искажение передаваемого сообщения. При использовании двоичного алфавита искажение может привести к тому, что в принятом сообщении какая-нибудь переданная единица сменит свое значение на ноль или наоборот ноль исказится и примет значение единица. Возникает вопрос, как построить коды, позволяющие обнаружить такие сбои при передаче информации и позволяющие восстановить значения искаженных разрядов. Назовем коды, обладающие свойством обнаружения сбоев и восстановления искаженных разрядов при передаче информации помехоустойчивыми.

Рассмотрим случай, когда в процессе передачи сообщения оно может исказиться не более чем в k разрядах. В пространстве сообщений E(n, U2) выделим подмножество Hk Í E(n, U2), обладающее тем свойством, что для " x, y Î Hk выполняется неравенство

 

	d (x, y) > k	(1.1)

Множество Hk назовем множеством осмысленных слов. Тогда любое x1 Ï Hk будет бессмысленным словом. Предположим, что при передаче слова x Î Hk оно исказилось и перешло в x1, но поскольку по условию искажение может произойти не более чем в k разрядах, то расстояние d(x, x1)£ k, следовательно, x1 Ï Hk и x1 есть бессмысленное слово. Таким образом, коды, удовлетворяющие условию (1.1), есть коды с обнаружением ошибки.

 

Пример 1.2. В пространстве сообщений E(3, U2) сформировать множество осмысленных слов.

Решение. Предлагается в качестве множества осмысленных слов H1 рассматривать множество { 000, 011, 110,101} c расстоянием между кодами 2. Тогда при k = 1 при передаче сообщения искажение в любом одном разряде превратит слово в бессмысленное.

Пример 1.3. В пространстве сообщений E(n-1, U2) сформировать множество осмысленных слов.

Коды с избыточностью – это коды, у которых количество осмысленных слов меньше общего числа возможных слов. Наличие избыточности является необходимым условием построения помехоустойчивых кодов. Рассмотрим построение кодов с обнаружением и исправлением ошибок, возникших при передаче сообщений. Предположим, что в процессе передачи информации может исказиться не более k разрядов кода. Множество осмысленных слов Hk Í E(n, U2) назначим таким образом, чтобы расстояние между его кодами подчинялось условию

 

	d (x, y) > 2k	(1.2)

для " x, y Î Hk. Пусть в результате искажения код x перешел в код x1, тогда d(x, x1)£ k. Запишем неравенство треугольника d(x, y) £ d (x, x1) + d (x1, y). Усилим неравенство: 2k < k + d(x1, y), что равносильно неравенству d(x1,y) > k. Последнее неравенство показывает, что расстояние от ошибочного слова x1 до слова x, подвергшегося искажению, меньше чем до любого другого осмысленного слова, тем самым позволяет восстановить правильное сообщение x. Коды, удовлетворяющие условию (1.2) называются кодами с исправлением ошибок.

 

Таблица 1.1. Задание на выполнение самостоятельной работы

В задании а равно номеру студента в списке группы + 1; b выбирается самостоятельно в [2,5]

1. В пространстве сообщений Е(a, b) назначить множество кодов с исправлением ошибок.   2. В пространстве сообщений Е(a, b) построить коды с обнаружением и исправлением ошибки.

2. Алгоритм кодирования и декодирования Хаффмена

Алгоритм Хаффмена [2] применяется при передаче информации по сети при удаленном доступе (протокол Тelnet). Предположим, что у нас есть алфавит из n символов. Нужно закодировать сообщение в виде строки бит. Присвоим каждому символу алфавита определенную последовательность бит (код). Затем соединим отдельные коды символов, составляющих сообщение, и получим кодировку сообщения. Пусть символам назначены следующие коды: A = 010; B = 100; C = 000; D = 111. Сообщение ABACCDA кодируется как 010100010000000111010.

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

 

Таблица 2.1. Назначение кодов, соответствующих частоте повторения символов

 

Символ	Частота	Код
А
B
C
D

 

 

При использовании этих кодов сообщение ABACCDA кодируется как 0 110 0 10 10 111 0, что требует лишь 13 бит. В очень длинных сообщениях, которые содержат символы, встречающиеся чрезвычайно редко, экономия существенна. Обычно коды создаются не на основе частоты вхождения символов в отдельно взятом сообщении, а на основе их частоты во всем множестве сообщений.

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

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

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

 

ACBD,7

 

A,3 CBD,4

 

 

C,2 BD,2

 

 

B,1 D,1

 

Рис. 2.1. Дерево Хаффмена

 

 

Такие деревья называются деревьями Хаффмена, по имени изобретателя этого метода кодирования. Как только дерево построено, код любого символа алфавита может быть определен просмотром дерева снизу вверх, начиная с листа, представляющего этот символ. Начальное значение кода – пустая строка. Каждый раз, когда мы поднимаемся по левой ветви, к коду слева приписывается 0; каждый раз при подъеме по правой ветви к коду слева приписывается 1, т.е. А имеет код 0; B имеет код 110 и т.д.

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

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

 

Таблица 2.2. Кодировки букв по частоте

Символ	A	B	C	D	E	F	G	H	I
Частота

 

Используя таблицу, построить бинарное дерево для кодирования и декодирования сообщения IHFBDEGCA.

Решение.

IHFBDEGCA,91

 

IHFBD,38 EGCA,53

 

I,15 HFBD,23 E,25 GCA,28

 

HFB,11 D,12 GC,13 A,15

 

HF,5 B,6 G,6 C,7

 

H,1 F,4

Рис. 2.2. Дерево Хаффмена для рассматриваемой задачи

 

После построения дерева проведем кодировку символов. Оформим результат в виде таблицы.

 

Таблица 2.3. Кодировки букв по частоте

Символ	A	B	C	D	E	F	G	H	I
Код

 

 

Учитывая результат кодировки, можно декодировать любое сообщение из заданного набора символов. Например, имеем код сообщения 1110100010111011, необходимо представить его в виде символов:

 

1110100010111011

 

110100010111011

 

10100010111011

 

 

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

 

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

· Возьмите свои ФИО, подсчитайте частоту встречающихся символов.

· Постройте дерево Хаффмена. Определите коды символов.

· Составьте новое слово из символов полученного алфавита,

· Закодируйте слово.

· Переправьте закодированное слово для декодирования вместе со словарем и частотой букв.

· Получите для декодирования словарь и код, декодируйте сообщение.

 

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

1. Что такое помехоустойчивые коды?

2. Чем определяется расстояние по Хеммингу между двумя сообщениями?

3. В чем отличие кодов с обнаружением ошибки и кодов с исправлением ошибки?

4. В чем заключается принцип построения дерева Хаффмена?

5. Что необходимо для декодирования по алгоритму Хаффмена?

 

3. Дискреционная модель политики безопасности

 

 

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