ГОСТ 28147-89 — советский и российский стандарт симметричного шифрования, введённый в 1990 году, также является стандартом СНГ. Полное название — «ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования». Блочный шифроалгоритм. При использовании метода шифрования с гаммированием, может выполнять функции поточного шифроалгоритма.
По некоторым сведениям, история этого шифра гораздо более давняя. Алгоритм, положенный впоследствии в основу стандарта, родился, предположительно, в недрах Восьмого Главного управления КГБ СССР (ныне в структуре ФСБ), скорее всего, в одном из подведомственных ему закрытых НИИ, вероятно, ещё в 1970-х годах в рамках проектов создания программных и аппаратных реализаций шифра для различных компьютерных платформ.
С момента опубликования ГОСТа на нём стоял ограничительный гриф «Для служебного пользования», и формально шифр был объявлен «полностью открытым» только в мае 1994 года. История создания шифра и критерии разработчиков по состоянию на 2010 год не опубликованы.
ГОСТ 28147-89 отличается от DES числом циклов шифрования (32 вместо 16). Ключ состоит из 32 мерных векторов и i-ый ключ цикла k 32 мерный вектор. В ГОСТе используется 256 битовый ключ и объем ключевого пространства 2256 . Ни на одной из существующих ЭВМ подобрать ключ невозможно. По стойкости он превосходит 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, то по нижнему ребру;
Читаем следующий бит перемещаемся до тех пор пока маркер не попадет а конечный узел дерева; дальше символ записывается в восстанавливающий массив и маркер устанавливается в вершину дерева и повторяет цикл.
