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

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

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

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

ГОСТ 28147-89 — блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Основа алгоритма шифра — Сеть Фейстеля. Базовым режимом шифрования по ГОСТ 28147-89 является режим простой замены (определены также более сложные режимы гаммирование, гаммирование с обратной связью и режим имитовставки). Для зашифрования в этом режиме открытый текст сначала разбивается на две половины (младшие биты — A, старшие биты — B[2]). На i-ом цикле используется подключ Ki:

Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: K1…K8.

Ключи K9…K24 являются циклическим повторением ключей K1…K8 (нумеруются от младших битов к старшим). Ключи K25…K32 являются ключами K1…K8, идущими в обратном порядке.

После выполнения всех 32 раундов алгоритма, блоки A33 и B33 склеиваются (обратите внимание, что старшим битом становится A33, а младшим — B33) — результат есть результат работы алгоритма.

Расшифрование выполняется так же, как и зашифрование, но инвертируется порядок подключей Ki.

 

 

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

 

 

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

а -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, то по нижнему ребру;

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