Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

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

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

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

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

^{Защита информации}

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

2013

Оглавление

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

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

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

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

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

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

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

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

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

Введем пространство сообщений в виде 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) построить коды с обнаружением и исправлением ошибки.