Стандарт шифровки ГОСТ 28147-89

ГОСТ 28147-89 — советский и российский стандарт симметричного шифрования, введённый в 1990 году, также является стандартом СНГ. Полное название — «ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования». Блочный шифроалгоритм. При использовании метода шифрования с гаммированием, может выполнять функции поточного шифроалгоритма.

По некоторым сведениям, история этого шифра гораздо более давняя. Алгоритм, положенный впоследствии в основу стандарта, родился, предположительно, в недрах Восьмого Главного управления КГБ СССР (ныне в структуре ФСБ), скорее всего, в одном из подведомственных ему закрытых НИИ, вероятно, ещё в 1970-х годах в рамках проектов создания программных и аппаратных реализаций шифра для различных компьютерных платформ.

С момента опубликования ГОСТа на нём стоял ограничительный гриф «Для служебного пользования», и формально шифр был объявлен «полностью открытым» только в мае 1994 года. История создания шифра и критерии разработчиков по состоянию на 2010 год не опубликованы.

ГОСТ 28147-89 отличается от DES числом циклов шифрования (32 вместо 16). Ключ состоит из 32 мерных векторов и i-ый ключ цикла k 32 мерный вектор. В ГОСТе используется 256 битовый ключ и объем ключевого пространства 2²⁵⁶ . Ни на одной из существующих ЭВМ подобрать ключ невозможно. По стойкости он превосходит DES в 10 раз.

 

Алгоритм обратимых методов(метод упаковки).

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

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

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

Пример: кол_около_колокола содержится в строке 5 символов алфавита: к, о, л, а, _

Всего символов в строке 18, отводимых бит на каждый символ 3, 3*18=54 бит

следовательно реализуем формулу 2^3-1.Значит достаточно 7 байтов, чтобы закодировать данное сообщение.

 

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

Алгоритм Хаффмана — алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью.

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

Например, код, состоящий из слов 0, 10 и 11, является префиксным, и сообщение 01001101110 можно разбить на слова единственным образом: 0 10 0 11 0 11 10

Этот метод кодирования состоит из двух основных этапов:

-Построение оптимального кодового дерева;

-Построение отображения код-символ на основе построенного дерева.

Алгоритм построения дерева Хаффмана:

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

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

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

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

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

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

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

 

Пример: кол_около_колокола

а -111; _ -110; л -10; к -01; о -00

0010. 0101. 1000. 0100. 1000. 1100. 1001. 0000. 1001. 0111

Ставим 0 в начале, чтобы на конце было 4 цифры.

2.5.8.4.12.9.0.9.7.

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

Код Хаффмана восстанавливается, даже если не сообщается длина кода каждого переданного символа.

Схема восстановления: маркер устанавливается в вершину дерева; сжимаемый массив читается слитно, если читаемый бит 0, то перемещаемся из вершины по верхнему ребру, если 1, то по нижнему ребру;

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