Главная | Обратная связь
МегаЛекции

Методическое пособие для выполнения лабораторных работ




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

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

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

 

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

ИНФОРМАЦИОННАЯ БЕЗОПАСНОСТЬ И Защита информации

Методическое пособие для выполнения лабораторных работ

Оглавление

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

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

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

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

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

6. Ассиметричное шифрование. 46

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

 

 

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

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

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

 

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

 

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

 

 

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

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

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

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

 

ACBD,7

       
   


 

A,3 CBD,4

 

 

C,2 BD,2

 

 

B,1 D,1

 

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

 

 

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

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

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

 

Таблица 1.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

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

 

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

 

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

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

 

 

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

 

1110100010111011

 

110100010111011

 

10100010111011

 

 

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

 





©2015- 2017 megalektsii.ru Права всех материалов защищены законодательством РФ.