1233

предполагается избыточность старшего бита в байте кода символа. Гарантированный коэффициент сжатия 0.875 может быть получен простым уплотнением.

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

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

Сжатие последовательностей одинаковых символов

(Run Length Encoding)

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

Метод основан на представлении последовательности одинаковых байтов в виде двух величин. Одна из них равна количеству повторяющихся символов, а вторая содержит код символа. Например, строка NNNMMMNNNNMMMMMMMM длиной 18 символов может быть записана в виде 3N3M4N8M, что дает значительное сокращение длины. Метод достаточно прост в реализации и лучше всего работает в составе системы, учитывающей типы данных, подлежащих сжатию. Например, двоичный файл может быть записан в виде набора одних только длин битовых строк. Сами элементы могут и не сохраняться, поскольку для двоичных данных существует лишь два возможных варианта состояний. Каждая новая величина в записи будет означать изменение состояния битовой строки. Таким образом, двоичная строка 111100011000001111 будет записана просто пятью числами 43254.

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

Программа, использующая метод сжатия последовательностей одинаковых символов, должна четко отслеживать последовательности единичной длины. Это может быть достигнуто с помощью небольшого увеличения объема сжимаемых данных. Если предположить, что мы работаем со стандартным 7- битным ASCII кодом на 8-битных системах, мы можем достаточно просто реализовать подобный алгоритм.

В случае последовательности длиной в один или два байта нужно просто записывать эти последовательности в выходной файл. Если длина последовательности равна трем байтам и более, следует записывать длину в первом байте, а сам символ -во втором байте выходного кода. Чтобы показать, что текущий байт содержит длину последовательности, нужно установить его старший бит (прибавить 128).

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

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

Алгоритм Хаффмана

Один из первых алгоритмов эффективного кодирования информации был предложен Д.А.Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды. Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину. Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). Алгоритм построения Н-дерева прост и элегантен.

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

2.Выбираются два свободных узла дерева с наименьшими весами.

3.Создается их родитель с весом, равным их суммарному весу.

4.Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.

5.Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой - бит 0.

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

Первая задача состоит в подсчете числа повторений каждой буквы алфавита в исходном тексте. Далее из списка удаляются те буквы, которые ни разу не встретились в тексте. Затем строится дерево кодирования. Лучше всего предварительно отсортировать получившийся список в порядке убывания частоты повторений символов. Построение дерева начнется от самого правого символа в списке. Частоты двух наиболее редко встречающихся символов суммируются, и результат записывается в узле дерева. Исходные частоты стали теперь "детьми" новой суммарной частоты. Если имеется более двух символов с минимальной частотой повторений, то нужно просто образовать из них самостоятельные пары. Если имеется нечетное количество наименьших значений частоты, то нужно объединить непарную величину со следующей наименьшей частотой.

По мере продолжения процесса построения "дети" становятся "внуками", "правнуками" - и так до тех пор, пока все дерево не

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

Допустим, у нас есть следующая таблица частот:

На первом шаге из листьев дерева выбираются два с наименьшими весами - Г и Д. Они присоединяются к новому узлу-родителю, вес которого устанавливается в 5 + 6 == 11. Затем узлы Г и Д удаляются из списка свободных. Узел Г соответствует ветви О родителя, узел Д - ветви 1.

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

Дерево кодирования Хаффмана после второго шага

На следующем шаге <наилегчайшей> парой оказываются узлы Б/В и Г/Д. Для них еще раз создается родитель, теперь уже с весом 24. Узел Б/В соответствует ветви 0 родителя, Г/Д - ветви 1.

На последнем шаге в списке свободных осталось только два узла - это А и узел (Б/В)/(Г/Д). В очередной раз создается родитель с весом 39 и бывшие свободными узлы присоединяются к разным его ветвям.

Поскольку свободным остался только один узел, то алгоритм построения дерева кодирования Хаффмана завершается. Н-дерево представлено на рис.

¦0-----------24------------1

Окончательное дерево кодирования Хаффмана

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

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

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

А0

Б100

В101

Г 110

Д111

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

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

Алгоритм Хаффмана (Huffman Encoding), или кодирование символами переменной длины, предлагает отказаться от обычного представления файлов в виде последовательностей 7- или 8-битных символов. Главный недостаток такого способа записи файлов состоит в том, что в нем не делается различий между кодированием символов, с разной частотой встречающихся в файлах. Так, наиболее частые в английском языке символы E и I, имеют ту же самую длину, что и относительно редкие Z, X или Q. Код переменной длины позволяет записывать наиболее часто встречающиеся символы и фразы всего лишь несколькими битами, в то время как редкие символы и фразы будут записаны более длинными битовыми строками.

Простейший способ кодирования информации символами переменной длины осуществляется при помощи таблицы соответствий (translation table). Например, анализируя любой английский текст, можно установить, что буква E встречается гораздо чаще, чем Z, а X и Q относятся к наиболее редко встречающимся. Таким образом, используя таблицу соответствий, мы можем закодировать каждую букву E меньшим числом бит, используя более длинный код для более редких букв.

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

Арифметическое кодирование

В 70-е годы у алгоритма Хаффмана появился достойный конкурент - арифметическое кодирование. Этот метод основан на идее

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

явления в сообщении. Положение интервала вероятности каждого символа не имеет значения. Важно только то, чтобы и кодер, и декодер располагали символы по одинаковым правилам. Распределим интервалы вероятности для символов нашего сообщения:

A1/10 [ 0.10, 0.20 [

B1/10 [ 0.20, 0.30 [

S1/10 [ 0.80, 0.90 [

T1/10 [ 0.90, 1.00 [

В общем виде алгоритм арифметического кодирования можно описать следующим образом (используя условный алгоритмический язык):

НижняяГраница := 0.0; ВерхняяГраница := 1.0;

Пока ((ОчереднойСимвол = ДайОчереднойСимвол) <> Конец) Интервал := ВерхняяГраница - НижняяГраница; ВерхняяГраница := НижняяГраница + Интервал *

ВерхняяГраницаИнтервалаДля(ОчереднойСимвол);

НижняяГраница := НижняяГраница + Интервал * НижняяГраницаИнтервалаДля(ОчереднойСимвол);

КонецПока;

Выдать(НижняяГраница);

Работа этого алгоритма на нашем примере будет выглядеть следующим

Таким образом, согласно нашей схеме, число 0.2572167752 однозначно кодирует сообщение "BILL_GATES".

В общем виде алгоритм арифметического декодирования можно описать следующим образом (используя условный алгоритмический язык):

Число := ПрочитатьЧисло();

Пока (Число <> 0.0)

Символ := НайтиСимволВИнтервалКоторогоПопадает(Число); Выдать(Символ);

Интервал := ВерхняяГраницаИнтервалаДля(Символ) - НижняяГраницаИнтервалаДля(Символ);

Число := Число - НижняяГраницаИнтервалаДля(Символ); Число := Число / Интервал;

КонецПока;

интервал которого оно попадает, этот символ выдается как раскодированный, а его влияние на число устраняется действиями, обратными действиям при кодировании.

Несмотря на то, что, на первый взгляд, алгоритм арифметического кодирования может работать на компьютерах с математическим сопроцессором, наилучшим образом он может быть реализован на основе стандартной 16 или 32-битовой целочисленной арифметики. Ранее было отмечено, что при работе алгоритм отслеживает верхнюю и нижнюю границы возможного выходного кода. Сразу после старта нижняя граница устанавливается в 0.0, а верхняя - в 1.0; но также отмечалось, что верхняя граница берется не включительно. Поэтому первое упрощение для работы алгоритма с целочисленной арифметикой - это замена 0.0 на 0x0000, а 1.0 - на 0xFFFF. Это заметно упрощает процессы кодирования и декодирования.

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

В процессе работы алгоритма может возникнуть ситуация, когда, например, верхняя граница равна 70000, а нижняя - 69999. Интервал между ними так мал, что все последующие итерации не изменят содержимое границ, а поскольку старшие цифры не совпадают, то алгоритм не будет выдавать цифр кода, то есть зациклится.

Для избежания такой ситуации алгоритм немного корректируется. Если две старшие цифры границ не совпадают, то, если они отличаются на единицу, проверим следующие по значимости цифры гра-

ниц. Если они равны 0 у верхней границы и 9 у нижней, значит алгоритм на пути к зацикливанию. Сделаем следующее: удалим вторые по значимости цифры границ и остальные менее значимые сдвинем влево. Затем увеличим специальный счетчик, чтобы запомнить то, что мы выбросили цифры.

Эти действия могут выглядеть, например, так:

Эти действия продолжаются до тех пор, пока старшие цифры границ не совпадут. Затем в выходной поток помещается совпавшая старшая цифра, а за ней равное счетчику количество 9 или 0, в зависимости от того, к цифре верхней или нижней границы сошлись старшие цифры.

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

Алгоритм Лемпела - Зива - Уэлча (LZW)

Словарем в данном алгоритме является потенциально бесконечный список уже просмотренных ФРАЗ. И кодер, и декодер начинают работу с почти пустого словаря, содержащего только одну закодированную строку - NULL строку. Когда кодер считывает очередной символ сообщения, символ добавляется к текущей строке. До тех пор пока текущая строка соответствует какой-либо фразе из словаря, процесс продолжается. Но рано или поздно текущая строка перестает соответствовать какой-либо фразе словаря. В этот момент, когда текущая строка представляет собой последнее совпадение со словарем плюс только что считанный символ сообщения, кодер выдает код, состоящий из индекса совпадения и следующего за ним символа, нарушившего совпадение строк. Кроме того, новая фраза, состоящая из индекса совпадения и следующего за ним символа, добавляется в словарь. В следующий раз, когда эта фраза появится в сообщении, она может быть использована для построения более длинной фразы, что повышает степень сжатия информации. LZW построен вокруг таблицы фраз (словаря), которая отображает строки символов сжимаемого сообщения в коды фиксированной длины. Таблица обладает так называемым свойством предшествования, то есть для каждой фразы словаря, состоящей из некоторой фразы w и символа К, фраза w тоже содержится в словаре. Если ячейки словаря полностью заполнены, кодирование перестает быть адаптивным (кодирование происходит исходя из уже существующих в словаре фраз).

Кодер LZW никогда не выдает сами символы сжимаемого сообще-

ния - только коды фраз.

Алгоритмы группы LZ (которые послужили основой для алгоритма LZW ) имеют существенный недостаток. Так как они используют в качестве словаря только небольшой фрагмент сообщения, то нет возможности кодировать повторяющиеся подстроки, расстояние между которыми в сообщении больше, чем размер словаря. Кроме того, алгоритмы ограничивают размер подстроки, которую можно закодировать. Очевидно, что указанные факторы снижают эффективность кодирования.

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

Алгоритм работы кодера LZW можно описать следующим образом:

Проинициализировать словарь односимвольными фразами, соответствующими символам входного алфавита (обычно это

256 ASCII символов)

Прочитать первый символ сообщения в текущую фразу w;

Шаг алгоритма:

Прочитать очередной символ сообщения К; Если КОНЕЦ_СООБЩЕНИЯ

Выдать код w; ВЫХОД;

Конец Если;

Если фраза wK уже есть в словаре Заменить w на код фразы wK; Повторить Шаг алгоритма

Иначе

Выдать код w; Добавить wK в словарь;

Повторить Шаг алгоритма; Конец Если;

Пример работы кодера LZW приведен в таблице.

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

Очевидно, что декодер LZW использует тот же словарь, что и кодер, строя его по аналогичным правилам при восстановлении сжатого сообщения. Каждый считываемый код разбивается с помощью словаря на предшествующую фразу w и символ К. Затем рекурсия продолжается для предшествующей фразы w до тех пор, пока она не окажется кодом одного символа, что и завершает декомпрессию этого кода. Обновление словаря происходит для каждого декодируемого кода, кроме первого. После завершения декодирования кода его последний символ, соединенный с предыдущей фразой, добавляется в словарь. Новая фраза получает то же значение кода (позицию в словаре), что присвоил ей кодер. Так шаг за шагом декодер восстанавливает тот словарь, который построил кодер.

Алгоритм декодирования LZW может быть описан следующим обра-

зом:

КОД = Прочитать первый код сообщения (); ПредыдущийКОД = КОД; Выдать символ К, у которого код ( К) == КОД;

Следующий код:

КОД = Прочитать очередной код сообщения(); Входной Код = КОД; Если КОНЕЦ_СООБЩЕНИЯ

ВЫХОД; Конец Если; Следующий символ:

Если КОД == код(wK) Выдать К;

КОД = код(w);

Повторить Следующий символ Иначе если КОД == код(К)

Выдать К; Добавить в словарь (ПредыдущийКОД, К);

ПредыдущийКОД = ВходнойКОД; Повторить СледующийКОД;

Конец Если;

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

Изменить порядок выдачи раскодированных символов несложно, для этого достаточно использовать стандартный LIFO стек.

Обработка исключительной ситуации несколько сложнее. Исключительная ситуация складывается тогда, когда кодер пытается закодировать сообщение KwKwK, где фраза Kw уже присутствует в словаре. Кодер выделит Kw, выдаст код (Kw) и добавит KwK в словарь.

Затем он выделит KwK и пошлет только что созданный код (KwK ). Декодер при получении кода (KwK) еще не добавил этот код к словарь, потому что еще не знает символ-расширение предыдущей фразы. Тем не менее, когда декодер встречает неизвестный ему код, он может определить, какой символ выдавать первым. Это символ-расшире- ние предыдущей фразы; он был последним раскодированным символом и будет последним символом текущей фразы.

Модифицированный алгоритм декодирования выглядит следующим образом:

КОД = Прочитать первый код сообщения(); ПредыдущийКОД = КОД; Выдать символ К, у которого код(К) == КОД; ПоследнийСимвол = К; Следующий код:

КОД = Прочитать очередной код сообщения(); ВходнойКОД = КОД; Если КОНЕЦ_СООБЩЕНИЯ

ВЫХОД; Конец Если;

Если Неизвестен(КОД) // Обработка исключительной ситуации Выдать (ПоследнийСимвол); КОД = ПредыдущийКОД;

ВходнойКОД = код(ПредыдущийКОД,ПоследнийСимвол); Конец Если;

Следующий символ: Если КОД == код(wK)

В_СТЕК( К ); КОД = код(w);

Повторить Следующий символ Иначе если КОД == код(К)

Выдать К; ПоследнийСимвол = К; Пока стек не пуст

Выдать ( ИЗ_СТЕКА() ); Конец пока;

Добавить в словарь (Предыдущий КОД, К); ПредыдущийКОД = Входной КОД; Повторить СледующийКОД;

Конец Если;

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

Система шифрования DES

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

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

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

·Сообщение отправлено вполне определенным лицом (тем, кто его подписал);

·Во время передачи сообщения не произошло никаких искажений

текста.

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

Одним из наиболее мощных алгоритмов шифрования данных на сегодняшний день является алгоритм DES (Data Encryption Standard), предназначенный для использования в государственных и правительственных учреждениях США для защиты от несанкционированного доступа важной, но несекретной информации. DES является наиболее распространенным алгоритмом, используемым в системах защиты коммерческой информации.

Основные достоинства алгоритма DES:

·Используется только один ключ длиной 56 битов;

·Зашифровав сообщение с помощью одного пакета, для расшифровки можно использовать любой другой;

·Относительная простота алгоритма обеспечивает высокую скорость обработки информации;

·Достаточно высокая стойкость алгоритма.

DES осуществляет шифрование 64-битовывх блоков данных с помощью 56-битового ключа. Дешифрование в DES является операцией обратной шифрованию и выполняется путем повторения операций шифрования в обратной последовательности.

Процесс шифрования заключается в начальной перестановке битов 64-битового блока, шестнадцати циклах шифрования и обратной перестановки битов.

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

Матрица начальной перестановки IP

Затем шестнадцать раз повторяется процедура шифрования получившегося в результате начальной перестановки блока с помощью функции f. Пусть Ti обозначает результат i-й итерации. Тогда

предположим, что Li=t1:t32, (первые 32 бита); Ri=t33..t64 (пос-

ледние 32 бита), т.е.,

Ti=LiRi

Тогда результатом i-й итерации будет:

Li=Ri-1; Ri=Li+f(Ri-1,Ki),

где + - операция исключающее ИЛИ;

Ki - i-е преобразование ключа шифрования.

Функция f выполняет операции над значением Ri-1 (результатом прошлой операции и текущим значением 48-битового ключа Ki (с отсечением лишних битов). После 16-й итерации левая и правая половины блока местами на меняются.

По окончании шифрования осуществляется восстановление позиций битов с помощью матрицы перестановок IP-1:

Матрицы перестановок IP-1

На каждой итерации массив Ri-1 с помощью таблицы распределения Е расширяется до 48 битов.

Таблица распределения Е

Полученный результат (обозначим его E(Ri-1)) складывается по модулю 2 (операция XOR) с текущим значением ключа Ki и затем разбивается на восемь 6-битовых блоков B1:B8.

То есть:

E(Ri-1) + Ki = B1B2:B8.

Далее каждый из этих блоков используется как номер элемента в матрицах S1..S8, содержащих четырехбитовые значения:

100 15 07 04 14 02 13 01 10 06 12 11 09 05 03 08

204 01 14 08 13 06 02 11 15 12 09 07 03 10 05 00

315 12 08 02 04 09 01 07 05 11 03 14 10 00 06 13

103 13 04 07 15 02 08 14 12 00 01 10 06 09 11 05

200 14 07 11 10 04 13 01 05 08 12 06 09 03 02 15

313 08 10 01 03 15 04 02 11 06 07 12 00 05 14 09

113 07 00 09 03 04 06 10 02 08 05 14 12 11 15 01

213 06 04 09 08 15 03 00 11 01 02 12 05 10 14 07

301 10 13 00 06 09 08 07 04 15 14 03 11 05 02 12

113 08 11 05 06 15 00 03 04 07 02 12 01 10 14 09

210 06 09 00 12 11 07 13 15 01 03 14 05 02 08 04

303 15 00 06 10 01 13 08 09 04 05 11 12 07 02 14

114 11 02 12 04 07 13 01 05 00 15 10 03 09 08 06

204 02 01 11 10 13 07 08 15 09 12 05 06 03 00 14

311 08 12 07 01 14 02 13 06 15 00 09 10 04 05 03

110 15 04 02 07 12 09 05 06 01 13 14 00 11 03 08

209 14 15 05 02 08 12 03 07 00 04 10 01 13 11 06

304 03 02 12 09 05 15 10 11 14 01 07 06 00 08 13

113 00 11 07 04 09 01 10 14 03 05 12 02 15 08 06

201 04 11 13 12 03 07 14 10 15 06 08 00 05 09 02

306 11 13 08 01 04 10 07 09 05 00 15 14 02 03 12

101 15 13 08 10 03 07 04 12 05 06 11 00 14 09 02

207 11 04 01 09 12 14 02 00 06 10 13 15 03 05 08

302 01 14 07 04 10 08 13 15 12 09 00 03 05 06 11

Таким образом,

f(Ri-1,Ki) = P(S1(B1),..S8(B8)).

В результате, применив операцию выбора к каждому из блоков, получим

S1(B1)S2(B2)S3(B3)..S8(B8)

Этот 32-битовый блок (матрицы Sj содержат 4-битовые значения) преобразуется с помощью матрицы перестановки Р:

Матрица перестановки битов Р

Выбор элемента в матрице Sj осуществляется следующим образом. Пусть на вход поступает 6-битовый блок Bj=b1b2b3b4b5b6, тогда двухбитовое число b1b6 выбирает строку матрицы, а b2b3b4b5 - номер столбца. Результатом Sj(Bj) будет 4-битовое число, расположенное по указанному адресу.

На каждой итерации используется новое значение ключа Ki, которое вычисляется из начального ключа К. К представляет собой 64битовый блок с восемью битами контроля по четности, расположенны-

ми в позициях 8, 16, 24, 32, 40, 48, 56, 64.

Для удаления контрольных битов и подготовки ключа к работе используется матрица РС-1:

Матрица первоначальной подготовки ключа PC-1

Результат преобразования РС-1(К) разбивается на две половины C0 и D0 по 28 битов каждая. После этого блоки C0 и D0 на каждой итерации последовательно сдвигаются влево. Пусть Ci и Di обозначают значения, полученные после i-й операции:

Ci=LSi(Ci-1) D=LSi(Di-1),

Полученное значение вновь "перемешивается" в соответствии с матрицей PC-2:

Матрица завершающей обработки ключа PC-2

Таким образом:

Ki= PC-2(CiDi)

Восстановление исходного текста осуществляется по этому алгоритму, но вначале используется ключ К16, затем - К15 и так далее. То есть, сначала проводится перестановка битов в соответствии с матрицей обратной перестановки IP-1, потом следуют 16 циклов шифрования с обратной последовательностью ключей, и наконец, преобразование по матрице начальной перестановки IP.

Для наиболее полного удовлетворения всем требованиям, предъявляемым к коммерческим системам шифрования, реализованы несколько режимов работы алгоритма DES. Наиболее широкое распространение получили режимы:

·Электронный шифрблокнот (Electronic Codebook) - ECB;

·Цепочка цифровых блоков (Cipher Block Chaining) - CBC;

·Цифровая обратная связь (Cipher Feedback) - CFB;

·Внешняя обратная связь (Output Feedback) - OFB.

DES-ECB

Длинный файл разбивается на 64-битовые отрезки (8 байтов). Каждый из этих блоков кодируется независимо с использованием одного и того же ключа шифрования. Основное достоинство этого алгоритма - простота реализации. Недостаток - относительно слабая устойчивость против квалифицированных криптоаналитиков.

DES-CBC

В этом режиме исходный файл М разбивается на 64-битовые блоки: М=М1М2:Мn. Тогда для всех i=1,N (N-число блоков) результат шифрования Ci будет определяться следующим образом:

C0=начальное значение

Ci=DES(Mi XOR Ci-1)

Дешифрование выполняется в обратном порядке.

C0=начальное значение

Mi=Ci-1 XOR DES (Ci)

Достоинство данного режима состоит в том, что он не позволяет накапливаться ошибкам при передаче. Блок Mi является функцией только Ci-1 и Ci. Поэтому ошибка при передаче приведет к потере только двух блоков исходного текста.

DES-CFB

В этом режиме размер блока отличается от 64. Файл, подлежащий шифрованию (дешифрованию), считывается последовательными блоками длиной t битов (t=1,64). 64-битовый регистр сдвига инициализируется строкой S0, которая может быть либо заполнена пробелами, либо в нее записывается исходное значение ключа К. Предположим, что

в результате разбиения на блоки, мы получили N блоков, длиной по t битов каждый (остаток дописывается нулями или пробелами). Тогда для любого i=1,N:

Ci=Mi XOR Pi,

где Pi означает t старших битов предыдущего зашифрованного блока. Обновление сдвигового регистра осуществляется путем удаления его старших N битов и дописывания Ci справа.

Восстановление зашифрованных данных проводится аналогично: Pi и Ci вычисляются следующим образом.

Mi=Ci XOR Pi,

DES-OFB

Режим OFB также использует переменный размер блока и сдвиговый регистр, инициализируемый аналогично режиму CFB. Но в этот раз для каждого сеанса шифрования данных необходимо использовать новое начальное состояние регистра S0, которое должно пересылаться по каналу открытым текстом.

Положим M=M1M2:Mn. Для всех i=1,N,

Ci=Mi XOR Pi

где Pi - старшие t битов операции DES(Si-1). Отличие от режима CFB состоит в методе обновления сдвигового регистра. В данном случае это осуществляется путем отбрасывания старших t битов и дописывания справа Pi.

Для системы шифрования типа DES может быть реализован алгоритм электронной подписи.

Исходный текст разделяется в соответствии с алгоритмом на блоки по 64 бит каждый. Первый блок исходного текста складывается по модулю два (операция XOR) с начальным вектором, затем зашифровывается с помощью секретного ключа, известного как отправителю, так и получателю сообщения. Полученный 64-битовый блок, в свою очередь, складывается по модулю два со вторым блоком исходного текста и снова шифруется Получается второй 64-битовый блок и операция повторяется до окончания исходного текста. Полученное в результате такой процедуры 64-битовое число является функцией секретного ключа, начального вектора и каждого бита сообщения, вне зависимости от длины последнего. Это число носит название MAC (message authentication code) и дописывается к зашифрованному сообщению, формируя таким образом как бы печать на конверте. Полученное "запечатанное" сообщение передается по каналу связи. Получатель расшифровывает сообщение и, зная секретный ключ и начальное значение вектора, вычисляет свое значение MAC. Если оба кода совпадают, то сообщение передано верно.

КОМПИЛЯТОРЫ

Литература

1. Хендрикс Д. Компилятор языка Си для микроЭВМ: Пер. с

англ. - М.: Радио и связь, 1989. - 240 с.

2.Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции: Пер. с англ./В 2-х томах. - М.: Мир, 1978.

3.Касьянов В.Н., Поттосин И.В. Методы трансляции. - Новосибирск, 1979 - 92 с.

3.Касьянов В.Н., Поттосин И.В. Методы трансляции. - Новосибирск: НГУ, 1978.

Компиляция - поиск соответствия написанных программистом предложений структурам, определенным грамматикой и генерация кода для каждого предложения. Грамматика определяет форму (синтаксис) допустимых предложений языка.

Предложения исходной программы представляют в виде последовательности лексем: ключевых слов, имен переменных, знаков операций и т.п. Просмотр текста, распознавание и классификация лексем называется лексическим анализом. Модуль компилятора, который выполняет данную функцию, называется сканером или лексическим анализатором. После выделения лексем возможна классификация предложений языка по принадлежности к некоторой конструкции - операторам описания, действия - т.е. синтаксический анализ. Последним шагом является генерация объектного кода с учетом семантических (смысловых) правил языка. Кроме объектного кода возможно получение ассемблерного текста программы.

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

ГРАММАТИКА

Грамматика языка программирования - это формальное описание его синтаксиса. Широко распространенной формой записи грамматики является форма Бэкуса-Наура (БНФ). Грамматика в форме БН состоит из множества правил вывода, каждое их которых описывает синтаксис некоторой конструкции языка. Например, рассмотрим фрагмент грамматики подмножества языка Паскаль:

1. <prog>::=PROGRAM <prog_name> VAR <dec_list> BEGIN <stmt_list> END.

2.<prog_name>::= id

3.<dec_list>::= <dec>¦<dec_list>;<dec>

4.<dec>::= <id_list>:<type>

5.<type>::= INTEGER

6.<id_list>::= id¦<id_list>,id

7.<stmt_list>::= <stmt>¦<stmt_list>;<stmt>

8.<stmt>::= <assign>¦<for>¦<if>¦<body>

9.<assign>::= id:=<exp>

10.<exp>::= <term>¦<exp> + <term>¦<exp> - <term>

11.<term>::= <factor>¦<term> * <factor>¦<term> DIV <factor>

12.<factor>::= id¦const>(<exp>)

....

n. <body>::=<stmt>¦BEGIN <stmt_list> END

Строки символов в <> называются нетерминальными символами,

т.е. именами конструкций. То, что не заключено в <>, называется терминальными символами или лексемами (id, const) и т.п.

Первое правило определяет общую структуру программы на Паскале. В данном подмножестве разрешено описание переменных в разделе VAR и операторов в блоке BEGIN END. Элементы правила требуют дальнейшей детализации.

Второе правило раскрывает структуру конструкции <prog_name>. Лексема id представляет произвольный идентификатор (имя).

Третье правило служит для задания списка описаний переменных <dec_list>. Элементами списка могут быть либо отдельные нетерминальные символы <dec>, либо разделенные символом ';' список <dec_list> и <dec>. Заметим, что большинство правил вывода являются рекурсивными, т.е. определяются в терминах самих себя.

Правило для записи переменной <dec> строится из списка идентификаторов <id_list>, двоеточия и конструкции <type>, которая для простоты включает только одно значение INTEGER.

Правило <id_list> совпадает с правилом <dec_list>. Однако разделителем в списке идентификаторов является ','.

Описание набора операторов программы <stmt_list> приведено в седьмом правиле. Оператор <stmt> может присутствовать в одном из четырех вариантов: присваивания <assign>, цикла <for>, усло-

вия <if> и блока <body>.

Оператор присваивания в левой части содержит лексему идентификатора переменной, а в правой - правило для задания выражения <exp>. Выражение состоит из отдельных термов (операндов) <term> или из термов, соединенных операциями + и -. Термом может быть <factor> в виде идентификатора, константы или выражения в скобках, а также другой терм, умноженный ('*') или деленный ('/') на <factor>. Обратим внимание на то, что умножение и деление выполняется перед сложением и вычитанием, т.е. * и / имеют более высокий ранг. Аналогичным образом строятся нетерминальные символы других операторов.

Операторный блок <body> записан как дизъюнкция оператора

<stmt> и <stmt_list> в операторных скобках BEGIN END .

ЛЕКСИЧЕСКИЙ АНАЛИЗ

Точный перечень лексем, которые необходимо распознавать, зависит от языка программирования и от применяемой грамматики. Каждая лексема представляется кодом (целым числом), например:

PROGRAM 1

VAR 2

BEGIN 3

...

id 22 INTEGER 23

Зарезервированные слова, знаки операций, скобки требуют указания только кода. Для идентификаторов и констант необходимо указывать дополнительную информацию - атрибуты (тип, имя, значения, класс хранения и т.п.). Атрибуты хранятся в таблице символов. Спецификатором лексемы в данном случае является указатель на соответствующий элемент таблицы символов. Пополнение таблицы осуществляется по мере появления новых объектов программы. Сложной задачей является обеспечение приемлемого времени просмотра таблицы символов. Для каждого элемента таблицы строится ХЭШ-функция, значение которой однозначно определяет место элемента в таблице. ХЭШ-функции ключевых лексем вычисляются заранее

ипомещаются в неизменяемую часть таблицы.

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

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

СИНТАКСИЧЕСКИЙ АНАЛИЗ

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

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

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

и т.д.

Для многих пар лексем отношение предшествования не существует, т.к. соответствующие пары не могут находится рядом. Если подобная комбинация лексем встречается а тексте, то она рассматривается как синтаксическая ошибка.

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

Для отношений предшествования возможно нарушение правил арифметического отношения. Например, ; > END но END > ;

Применим метод к оператору присваивания