Алгоритмы шифрования и их программная реализация

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА

САМАРСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ ПУТЕЙ СООБЩЕНИЯ

Кафедра «Мехатроника в автоматизированных производствах»

МЕТОДЫ И СРЕДСТВА ЗАЩИТЫ КОМПЬЮТЕРНОЙ ИНФОРМАЦИИ

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

электротехнического факультета дневной и заочной формы обучения

Составитель: Тюмиков Д.К.

Самара 2007

Методы и средства защиты компьютерной информации. Методические указания для студентов электротехнического факультета дневной и заочной формы обучения.- Самара: СамГУПС, 2007.-…с.

Методические указания содержат набор лабораторных работ по изучению алгоритмов шифрования, таких как DES, AES, RC6, метод Хаффмана. Приведены краткое теоретическое описание алгоритмов шифрования и их программная реализация.

Составители: Тюмиков Д.К.

Лабораторная работа №1

Шифрование DES

Цель работы: научиться работать с алгоритмом шифрования DES.

Задачи: 1. Изучить работу алгоритма шифрования DES.

2.С помощью программы, предложенной ниже, зашифровать текст.

3.С помощью программы, предложенной ниже, расшифровать текст.

Теоретическое введение

Стандарт шифрования DES (Data Encryption Standard) был разработан в 1970-х годах, он базируется на алгоритме DEA.

Исходные идеи алгоритма шифрования данных DEA (data encryption algorithm) были предложены компанией IBM еще в 1960-х годах и базировались на идеях, описанных Клодом Шенноном в 1940-х годах. Первоначально эта методика шифрования называлась lucifer (разработчик Хорст Фейштель, название dea она получила лишь в 1976 году. Lucifer был первым блочным алгоритмом шифрования, он использовал блоки размером 128 бит и 128-битовый ключ. По существу этот алгоритм являлся прототипом DEA. В 1986 в Японии (NIT) разработан алгоритм FEAL(Fast data Encipherment ALgorithm), предназначенный для использования в факсах, модемах и телефонах (длина ключа до 128 бит). Существует и ряд других разработок.

DEA (ANSI x3.92-1981) оперирует с блоками данных размером 64 бита и использует ключ длиной 56 бит. Такая длина ключа соответствует 10¹⁷ комбинаций, что обеспечивало до недавнего времени достаточный уровень безопасности. В дальнейшем можно ожидать расширения ключа до 64 бит (например, LOKI) или вообще замены DES другим стандартом.

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

Вводится функция f, которая работает с 32-разрядными словами исходного текста (А) и использует в качестве параметра 48-разрядный ключ (J). Схеме работы функции f показана на рис 1. Сначала 32 входные разряда расширяются до 48, при этом некоторые разряды повторяются. Схема этого расширения показана ниже (номера соответствуют номерам бит исходного 32-разрядного кода).

32 1 2 3 4 5

4 5 6 7 8 9

8 9 10 11 12 13

12 13 14 15 16 17

16 17 18 19 20 21

20 21 22 23 24 25

24 25 26 27 28 29

28 29 30 31 32 1

Для полученного 48-разрядного кода и ключа выполняется операция исключающее ИЛИ (XOR). Результирующий 48-разрядный код преобразуется в 32-разрядный с помощью S-матриц. На выходе S-матриц осуществляется перестановка согласно схеме показанной ниже (числа представляют собой порядковые номера бит).

16 7 20 21

29 12 28 17

1 15 23 26

5 18 31 10

2 8 24 14

32 27 3 9

19 13 30 6

22 11 4 25

Рис.1. Алгоритм работы функции f

Преобразование начинается с перестановки бит (IP - Initial Permutation) в 64-разрядном блоке исходных данных. 58-ой бит становится первым, 50-ый - вторым и т.д. Схема перестановки битов показана ниже.

58 50 42 34 26 18 10 2

60 52 44 36 28 20 12 4

62 54 46 38 30 22 14 6

64 56 48 40 32 24 16 8

57 49 41 33 25 17 9 1

59 51 43 35 27 19 11 3

61 53 45 37 29 21 13 5

63 55 47 39 31 23 15 7

Полученный блок делится на две 32-разрядные части L₀ и R₀. Далее 16 раз повторяются следующие 4 процедуры:

· Преобразование ключа с учетом номера итерации i (перестановки разрядов с удалением 8 бит, в результате получается 48-разрядный ключ)

Пусть A=L_i, а J - преобразованный ключ. С помощью функции f(A,J) генерируется 32-разрядный выходной код.

Выполняется операция XOR для R_i f(A,J), результат обозначается R_i+1.

Выполняется операция присвоения L_i+1=R_i.

Структурная схема реализации алгоритма dea показана на рис.2.

Рис.2. Структурная схема реализации алгоритма DEA

Инверсная перестановка разрядов предполагает следующее размещение 64 бит зашифрованных данных (первым битом становится 40-ой, вторым 8-ой и т.д.).

40 8 48 16 56 24 64 32

39 7 47 15 55 23 63 31

38 6 46 14 54 22 62 30

37 5 45 13 53 21 61 29

36 4 44 12 52 20 60 28

35 3 43 11 51 19 59 27

34 2 42 10 50 18 58 26

33 1 41 9 49 17 57 25

S-матрицы представляют собой таблицы содержащие 4-ряда и 16 столбцов. Матрица S(1) представлена ниже (эта матрица, также как и те, что приведены в ссылке 2, являются рекомендуемыми).

No. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7

1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8

2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0

3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

Исходный 48-разрядный код делится на 8 групп по 6 разрядов. Первый и последний разряд в группе используется в качестве адреса строки, а средние 4 разряда - в качестве адреса столбца. В результате каждые 6 бит кода преобразуются в 4 бита, а весь 48-разрядный код в 32-разрядный (для этого нужно 8 S-матриц). Существуют разработки, позволяющие выполнять шифрование в рамках стандарта DES аппаратным образом, что обеспечивает довольно высокое быстродействие.

Преобразования ключей K_n (n=1,…,16; K_n = KS(n,key), где n - номер итерации) осуществляются согласно алгоритму, показанному на рис.3.

Рис 3. Алгоритм вычисления последовательности ключей K_n

Для описания алгоритма вычисления ключей K_n (функция KS) достаточно определить структуру “Выбора 1” и “Выбора 2”, а также задать схему сдвигов влево (табл.2). “Выбора 1” и “Выбора 2” представляют собой перестановки битов ключа (PC-1 и PC-2; табл.1). При необходимости биты 8, 16,…, 64 могут использоваться для контроля четности.

Для вычисления очередного значения ключа таблица делится на две части С0 и D0. В С0 войдут биты 57, 49, 41,…, 44 и 36, а в D0 - 63, 55, 47,…, 12 и 4. Так как схема сдвигов задана (табл.2) C1,D1; Cn, Dn и так далее могут быть легко получены из C0 и D0. Так, например, C3 и D3 получаются из C2 и D2 циклическим сдвигом влево на 2 разряда

Таблица 1

Таблица 2

Протокол

Рассмотрим работу алгоритма шифрования DES на примере следующей программы (рис.4.):

Рис.4. Главное окно программы

1. -в данной строке указывается путь к файлу file1.txt, который необходимо зашифровать. Содержимое данного файла следующее:

Рис.5. Окно с исходным текстом

Нажимаем кнопку «Зашифровать». В текущей папке появится файл с расширением .des.

2. -в данной строке указывается путь к файлу file1.txt.des, в котором находится зашифрованный текст. Содержимое данного файла следующее:



Рис.6. Окно с зашифрованным текстом

Для расшифровки следует нажать «Расшифровать». В текущей папке появится файл с расширением .src, в котором находится расшифрованный текст исходного файла.

Результат

Изучена работа алгоритма шифрования DES. Проведены операции шифрования и дешифрования.

Вопросы для самоконтроля

1. В каком году был разработан алгоритм шифрования DES?

2. На каком алгоритме базируется стандарт шифрования DES?

3. С помощью чего результирующий 48-разрядный код преобразуется в 32-разрядный?

4. На сколько групп и разрядов делится исходный 48-разрядный код?

Лабораторная работа №2

Шифрование DES

Цель работы: научиться работать с алгоритмом шифрования DES.

Задачи: 1. Изучить работу алгоритма шифрования DES.

2.С помощью программы, предложенной ниже, зашифровать текст.

3.С помощью программы, предложенной ниже, расшифровать текст.

Протокол

Рассмотрим работу алгоритма шифрования DES на примере следующей программы:

1.- в данной строке указывается текст, который необходимо зашифровать

2.- в данной строке указывается ключ для кодирования

Нажимаем на кнопку «Закодировать».

3.- в данной строке появляется зашифрованный текст.

Для его расшифровки в строке 4 указываем ключ и нажимаем кнопку «Раскодировать».

5.- в данной строке появляется расшифрованный исходный текст.

Результат

Изучена работа алгоритма шифрования DES. Проведены операции шифрования и дешифрования.

Вопросы для самоконтроля

1. В каком году был разработан алгоритм шифрования DES?

2. На каком алгоритме базируется стандарт шифрования DES?

3. С помощью чего результирующий 48-разрядный код преобразуется в 32-разрядный?

4. На сколько групп и разрядов делится исходный 48-разрядный код?

Лабораторная работа № 3

Шифрование RC6

Цель работы: научиться работать с алгоритмом шифрования RC6.

Задачи: 1. Изучить работу алгоритма шифрования RC6.

2.С помощью программы, предложенной ниже, зашифровать текст.

3.С помощью программы, предложенной ниже, расшифровать текст.

Теоретическое введение

RC6 является полностью параметризуемым семейством алгоритмов шифрования. RC6 правильнее указывать как RC6-w/r/b, где w - длина слова в битах, r - число раундов, b - длина ключа. Обычно используются значения w = 32 и r = 20.

Рис 1. Алгоритм RC6

Алгоритм является сетью Фейштеля с 4 ветвями смешанного типа: два четных подблока используются для одновременного изменения содержимого двух нечетных подблоков. Затем производится обычный для сети Фейштеля сдвиг на одно слово, что меняет четные и нечетные подблоки местами.

f (x) = x (2x + 1)
a + b - сложение целых по модулю 2w
a - b - вычитание целых по модулю 2w
a b - XOR w-битных слов
a Ч b - умножение целых по модулю 2w
a <<< b - ротация влево на b бит w-битного слова а
a >>> b - ротация вправо на b бит w-битного слова а
S [0, …, 2r + 3] - w-битные подключи раунда

Протокол

Программа для шифрования/дешифрования по алгоритму RС6.

Программа предназначена для шифрования/дешифрования по алгоритму RС6. Пользователем выбирается произвольный файл, после чего задается пароль и происходит шифрование, в результате которого невозможно просмотреть (прочитать) содержимое файла.

Имеется возможность обратного преобразования (дешифрования).

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

Рис.2. Главное окно программы

Для демонстрации работы программы создадим файл 1.txt

Рис.3. Исходный текст

После нажатия на кнопку «Открыть», в окне программы, указываем путь к файлу. Производимая операция- шифрование. Нажимаем кнопку «Преобразование», в появившемся окне вводим ключ и нажимаем «Шифровать». Шифрованный текст увидим в нижней части окна. При выполнении этой операции в текущей папке появляется файл: 1EnRC6.txt

Рис.4. Закодированный текст

При расшифровке данного файла в окне программы в поле «производимая операция» выбираем «дешифрование». Нажимаем кнопку «Преобразование», вводим ключ. При выполнении этой операции в текущей папке появляется файл: 1EnRC6DeRC6.txt



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

Результат

Изучена работа алгоритма шифрования RС6. Проведены операции шифрования и дешифрования.

Вопросы для самоконтроля

1. Какой сетью является алгоритм шифрования RС6?

2. На чем базируется алгоритм шифрования RС6?

Лабораторная работа №4

Шифрование АES

Цель работы: научиться работать с алгоритмом шифрования АES.

Задачи: 1. Изучить работу алгоритма шифрования АES.

2.С помощью программы, предложенной ниже, зашифровать текст.

3.С помощью программы, предложенной ниже, расшифровать текст.

Теоретическое введение

При разработке Rijnael во внимание принималось три критерия:

1)Устойчивость по отношению ко всем известным атакам

2)Быстрота исполнения и компактность кода на разных платформах

3)Простота алгоритма

Описание алгоритма.

Rijnael это блочный шифр с различной длиной блока шифрования и длиной ключа. Длины блока и ключа шифрования могут быть 128, 192 и 256 бит. Шифрование блока осуществляется за несколько раундов, так, например, при длине блока 128 бит и длине ключа 128 бит алгоритм включает 10 раундов.

Первому раунду предшествует операция добавления кругового ключа В отличие от DES, раунды Rijnael не обладают фейстелевской структурой. Вместо этого каждый раунд включает различные обратимые преобразования под названием слои. Схематически каждый раунд, кроме последнего, можно представить в виде 4 операций. Далее мы будем рассматривать вариант шифрования 128 битного блока при длине ключа 128 бит. При других длинах блока шифрования и длины ключа схема алгоритма не меняется, изменяются лишь некоторые константы реализации алгоритма (число раундов и прочее).

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

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

1.Замена байтов представляет собой нелинейную замену байтов, действующую на каждый байт состояния независимо. Таблица замены является обратимой и строится на основе произведения двух преобразований:

вычисляется “обратный байт” (обратимость понимается над полем GF(256), а 0 элемент отображается в себя).

К полученному байту применяется афинное преобразование:



Для выполнения обратной замены байтов применяется обратная таблица замены, которая получается следующим образом: сначала производится обратное афинное преобразование, а затем вычисляется обратный элемент над GF(256).

2.Под сдвигом строк понимается следующая операция:

Строки состояния циклически сдвигаются на различные смещения. Нулевая строка не сдвигается, первая сдвигается на 1 байт, вторая на 2 байта и третья на три байта (при других значениях длины блока значения смещений меняются).

Обратной операцией является циклический сдвиг в другую сторону.

3.Смешивание столбцов происходит следующим образом:

столбец состояния рассматривается как полином над GF(256) и умножается по модулю на фиксированный полином , где . Это преобразование обратимо, поскольку полином взаимно прост с .

Это преобразование можно записать в матричном виде: ,

Рисунок иллюстрирует действие данного преобразования:

Для выполнения обратного преобразования необходимо произвести умножение на полином .

4.Добавление ключа.

На этом этапе происходит с помощью битового сложения по модулю 2 круговой ключ складывается с состоянием.

=

Эта операция является обратной к самой себе.

Получение кругового ключа.

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

Полное число битов кругового ключа, необходимого для шифрования, равно длине блока умноженной на количество раундов плюс 1, те для блока длиной 128 бит и 10 раундов необходимо 1408 бит. Первые 128 бит кругового ключа совпадают с самим ключом.

Формирование ключа происходит следующим образом: первые четыре столбца (с номерами 0-3)совпадают с самим ключом, далее столбец с номером четыре получается из третьего с помощью следующей композиции преобразований:

,

далее для столбцов 5-7 имеем: . Дальнейший процесс определяется рекурсивно, меняется лишь константа С. Здесь SubByte - применение операции замены байт, а RotByte- сдвиг, преобразующий столбец (a,b,c,d) в (b,c,d,a).

Тогда весь процесс шифрования можно записать так:

Изначальное добавление кругового ключа

N-1 раунд

Последний раунд.

Алгоритм дешифрования

Выше было отмечена реализация обратного к каждому из преобразований раунда:

{

Добавление кругового ключа

Обратное смешивание столбцов

Обратный сдвиг строк

Обратная замена байт}

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

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

Протокол

Рассмотрим работу алгоритма шифрования АES на примере следующей программы (рис.1.):

Рис.1. Главное окно программы

В строке «Исходный файл» указываем название исходного файла, который необходимо зашифровать. Содержимое данного файла следующее:



Рис.2. Исходный текст

Нажимаем кнопку «Шифровать» и в окне «Конечный файл» отображается зашифрованный исходный текст. При выполнении этой операции в текущей папке появляется файл: EncodedFile.txt.

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

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



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

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

Результат

Изучена работа алгоритма шифрования АES. Проведены операции шифрования и дешифрования.

Вопросы для самоконтроля

1. Что такое АES?

2. Какими могут быть длина блока и ключа шифрования?

3. Что такое состояние и как его можно представить?

4. Что такое аффинное преобразование?

5. Какая операция понимается под сдвигом строк?

6. Каким образом происходит смешивание столбцов?

7. Как получается круговой ключ?

Лабораторная работа №5

Шифрование методом Хаффмана

Цель работы: научиться работать с методом шифрования Хаффмана.

Задачи: 1. Изучить работу метода шифрования Хаффмана.

2.С помощью программы, предложенной ниже, зашифровать текст.

3.С помощью программы, предложенной ниже, расшифровать текст.

Теоретическое введение

Битовые представления символов

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

В обычной двоичной записи числа каждая единичка имеет вес согласно своей позиции. Самая младшая весит 1, следующая 2 и т.д. В итоге само число равно сумме весов единичек в его записи.

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

Рис.1. Принципиальное различие таблиц весов для стандартного и специального представлений

Для примера, с которого начато данное сочинение, далее символы пронумерованы (начиная с 0) в порядке убывания и приведены искомые представления:

0) "1" - 00

1)"2" - 10

2)"3" - 01

3)"4" - 110

4)"5" - 111

Крайняя левая единичка хаффмановского представления весит 1 (и это единственно возможное значение для любых текстов и любых наборов длин). Следующая весит 2, последняя весит 1. Нетрудно проверить, что номер любого символа равен сумме весов в представлении этого символа.

Отсюда сразу видно преимущество: в декодировщике не нужно для каждого символа хранить его битовое представление. При считывании битов сжатого текста номер символа будет непосредственно вычисляться, и достаточно хранить только веса (не более 16 байтов, общих для всех символов исходного текста) и 256-байтовую таблицу соответствия символов и их внутренних номеров (образованных согласно убыванию частот).

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

Для сведения приведем алгоритм, который без хитростей перебором вычисляет битовые представления. Он хорош по объему (0.04 КБ), но не лучший по скорости, хотя и она измеряется в сотых долях секунды, и относительная неспешность выявляется только специальными экспериментами.

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

1.Полагаем рабочее двубайтовое значение R = 0.

2.Берем символ S с минимальной длиной представления L из тех символов, что еще не получили представление. Если такого нет, то процесс завершен.

3.От R в качестве представления для S берем L младших битов.

4.Увеличиваем R на 1. Если среди обслуженных есть символ с некой длиной M, чье представление совпадает с M младшими битами представления S, то переходим на п.3., иначе на п.2.

Попутно можно вычислить веса битов, если заметить, что вес старшей единички в представлении очередного символа S равен внутреннему номеру символа S минус веса предыдущих единичек в его представлении. (Полезно заметить, что при формировании битового представления символа от R откидываются только нулевые биты. Если вдруг это не так, то длины заданы неверно, и никакой кодировки не получится.)

Перейдем к основному алгоритму данного раздела. Как и с судьбоносной идеей Хаффмана, начнем со словесного описания, которое достаточно лаконично и сразу многое проясняет.

Пусть символы упорядочены по неубыванию длин представлений. Возьмем символы с максимальной длиной представлений. Их обязательно окажется четное число. Первой половине выбранных символов назначим в старший разряд 0, остальным 1. Этим разрядом в итоге и будут отличаться обе половины. Поэтому про вторую из них можно временно забыть, как и про старший, уже назначенный бит. а первая половина естественно присоединится к группе символов с меньшей на единицу разрядностью. В результате получаем ситуацию, идентичную исходной, но с меньшим количеством символов и меньшей максимальной длиной. Повторяем указанную процедуру до тех пор, пока не останутся 2 символа. Назначаем первому бит = 0 , второму 1. Затем возвращаемся по пройденному пути, заполняя пробелы простым дублированием.



Рис.2. Характерные фрагменты специального представления символов

Быстрый алгоритм попутно и легко выдает таблицу весов. Вес старшего из используемых разрядов равен половине числа символов с максимальной длиной представлений. И далее - согласно описанным идентичным ситуациям.

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

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

Первому символу назначаем в младший разряд 0, второму 1. Далее всякий раз имеем ситуацию: заполнено L битов для каждого из N символов. Из этих N только K последних символов (возможно и совпадение K=N) имеют длину представлений больше L. Назначаем 0 в L+1 -й разряд каждому из N тех же символов, и 1 следующим за ними K символам. Матрицу значений разрядов с 1 по L -й для символов с N-K+1 -го по N -й дублируем для аналогичных разрядов символов с N+1 -го по N+K -й. Конец по признаку K=0.

K - это и есть вес очередного разряда.

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

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

Перейдем к окончательному варианту алгоритма. (Его объем в кодах менее 0.05 КБ). Кроме того, что символы упорядочены по неубыванию заданных длин представлений, еще будем предполагать, что на месте каждого из искомых представлений уже лежат 16 нулевых битов, т.е. массив представлений M(i) обнулен. Это позволит не делать в общем-то излишние (но многочисленные) операции по назначению нулей в отдельные биты.

АЛГОРИТМ ВЫЧИСЛЕНИЯ БИТОВЫХ ПРЕДСТАВЛЕНИЙ СИМВОЛОВ

1.Полагаем Z=2, N=2, L=1, M(2)=1.

2.Вычисляем K - количество символов из первых N штук, чьи представления в итоге должны быть больше L. Если K=0, то конец алгоритма.

3.Полагаем M(i) = M(i-K)+Z для i от N+1 по N+K .

4.Увеличиваем N на K, увеличиваем L на 1, а Z удваиваем. Переход на п.2. КОНЕЦ алгоритма.

Напомним, что получаемые по ходу алгоритма величины K - это важные для последующих действий веса разрядов, их надо запасти в некоторый массив. Памяти теперь понадобится чуть больше, чем на этапе вычисления длин. Хотя исходные данные можно поместить в 128 байтов, но на выходе все равно желательно иметь те же 128 байтов с длинами и 512 байтов с представлениями символов (по 2 байта на каждый из 256 символов), чтобы без лишних хлопот закодировать исходный текст. При этом также можно использовать массив, в котором ранее поступили ненужные теперь количества вхождений символов. Можно побороться и здесь за экономию памяти, но для данного сочинения это не первоочередная задача. К тому же по сравнению с не хаффмановскими методами, используемая память микроскопически мала.

Расшифровка сжатого текста

Следующий алгоритм дешифровки может быть размещен в 0.04 КБ машинного кода. Он предполагает заданными: адрес сжатого текста, адрес вывода, адрес таблицы соответствия, адрес весов. В таблице соответствия не более 256 байтов. С ее помощью по формируемому в процессе расчета нашему внутреннему номеру в нужной позиции мы найдем общепринятое 8-битовое представление символа. В таблице весов не более 17 байтов, здесь указаны веса, начиная с младших разрядов, таблица должна завершаться нулем. Можно сказать, что указан и вес первого из неиспользуемых битов. (Исходный текст в 16 МБ может увеличить таблицу весов на 8 байтов и т.д.)

Еще, вообще говоря, нужен объем сжатого или развернутого текста, чтобы вовремя завершить процесс. Но иногда (скажем, при развертывании загрузочного модуля в оперативной памяти) здесь можно немного выгадать, если, например, разместить таблицу соответствия сразу за сжатым текстом. Тогда мы будем знать и адрес конца текста.

АЛГОРИТМ РАСШИФРОВКИ.

1.Установим рабочий адрес A на начало таблицы весов и обнулим однобайтовые счетчики P и R (беззнаковые числа от 0 до 255).

2.Читаем вес V по адресу A, увеличиваем A на 1, читаем вес W по адресу A.

Считываем очередной бит сжатого текста. Если он не 0, то увеличиваем P на V. Увеличиваем R на V.

3.Если W+P > R , то переход на п.2.

4.P - это и есть искомый внутренний номер символа. Выводим символ согласно таблице соответствия. Переходим на п.1 для расшифровки очередного символа. КОНЕЦ алгоритма.

Поясним, что алгоритм не требует проверок на исчерпание таблицы весов при подсчете внутреннего номера очередного символа. Наоборот, для большинства символов чтение не доходит до конца этой таблицы. Но если уж алгоритм добрался до конца таблицы, то условие W+P > R заведомо окажется невыполненным, поскольку в этом случае W=0, в R просуммированы все веса, а в P - только часть из них (для символа с максимальным внутренним номером окажется P=R).

Отсюда, в частности, следует, что сумма W+P в процессе вычислений никогда не может превзойти 255 и даже максимального из внутренних номеров символов (тогда для нее тоже достаточно однобайтовой ячейки).

Соотношение W+P > R получается из длинных теоретических выкладок, но его можно пояснить весьма просто. Если W+P не превосходит R, то очередная (еще не прочитанная) единичка дала бы двойное представление символа с номером W+P , поэтому для набранного P чтение сжатого текста необходимо прекратить. При W+P > R мы, наоборот, узнаем о существовании символа с внутренним номером W+P , который не укладывается в прочитанное количество разрядов, даже если все их заполнить единичками. В этом случае чтение надо продолжить, так как иначе мы заведомо не охватим все символы исходного текста, а не считанный вовремя разряд безнадежно испортит результат.

256-байтовая таблица соответствия допускает различные сжатия и может разворачиваться только в оперативной памяти непосредственно перед расшифровкой сжатого текста. В первые 4 бита положим длину битового представления того символа, который в общепринятом 8-битовом представлении имеет номер 0. В следующие 4 бита положим длину символа номер 1 и т.д. Таблица сожмется до 128 байтов.

Напомним, что мы ограничились текстами до 64 КБ. Так что четырех битов вполне достаточно для изображения всех возможных длин. А большинство реальных случаев охватывается диапазоном длин от 5 до 12, что позволяет ужать таблицу до 96 байтов. В ряде специфических областей достаточно еще вдвое меньшего диапазона, что доводит результат до 64 байтов.

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

Таблица весов тоже допускает более компактные формы. Можно использовать тот факт, что веса младших разрядов обычно геометрическую прогрессию, например: 1, 2, 4, 8, 6, 2. Тогда по оставшейся части таблицы, начинающейся с последнего члена прогрессии (в данном примере по записи 8, 6, 2) легко восстановить недостающую часть таблицы. Однако в отличие от таблицы соответствия здесь добавка машинных кодов, как правило, превосходит выгоду от сокращения таблицы весов. Поэтому добавка вполне уместна в дезархиваторе, являющемся отдельной программой, но она не годится для самораспаковывающихся программ (если, разумеется, они не вызывают программ дешифровки извне).

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

Протокол

Рассмотрим работу алгоритма шифрования методом Хаффмана на примере следующей программы (рис.3.):



Рис.3. Главное окно программы

Нажимаем кнопку «Открыть файл для чтения» и указываем путь к файлу, который нужно закодировать. Нажимаем кнопку «Открыть файл для записи» и указываем путь к файлу, в который запишется закодированный текст. Нажимаем кнопку «Закодировать». В файле, открытом для записи, появится:

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

Для того, чтобы раскодировать файл, нажимаем кнопку «Открыть файл для чтения» и указываем путь к файлу, который нужно раскодировать. Нажимаем кнопку «Открыть файл для записи» и указываем путь к файлу, в который запишется раскодированный текст. Нажимаем кнопку «Раскодировать». В файле, открытом для записи, появится раскодированный текст:

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

Результат

Изучена работа метода шифрования Хаффмана. Проведены операции шифрования и дешифрования.

Вопросы для самоконтроля

1. Что такое вес в методе Хаффмана?

2. Какой порядок алгоритма вычисления битовых представлений символов?

3. Какой порядок алгоритма расшифровки?

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

1. П.Б. Хорев. Методы и средства защиты информации в компьютерных системах. - М.: Издательство «ACADEMA» 2005 г.

2. http/:snoopy.falkor.gen.nz/~rae/des.html

3. www.cryptosoft.com/html/fips46-2.htm

4. http://www.compression.ru/download/articles/huff/nevesenko_2002/nevesenko_2002_huffman.html

Размещено на Allbest.ru

...