ГОСТ 28147-89

ГОСТ 28147-89

Сеть Фейстеля

Создатель:: КГБ, 8-е управление

Создан:: безымянными разработчиками

Опубликован:: 1990 г.

Размер ключа:: 256 битов

Размер блока:: 64 бита

Число раундов:: 32/16

Шаблон: п·о·и

Форма: о·с

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

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

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

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

О стандартеПравить

Цитата из текста стандарта:

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

Описание алгоритмаПравить

Схема режимов работы алгоритма

Алгоритм ГОСТ 28147-89 имеет четыре режима работы. Из них три режима шифрования:

режим простой замены;
режим гаммирования;
режим гаммирования с обратной связью;

и режим выработки имитовставки. Все они основываются на трёх базовых циклах, обозначаемых «32-З», «32-Р» и «16-З». Базовые циклы же по сути являются многократным повторением процедуры, называемой основным шагом криптопреобразования. В их обозначении число (32 или 16) указывает на число повторений основного шага, буква (З или Р) указывает на разновидность порядка использования элементов ключа.

Ключевая информацияПравить

Ключевая информация алгоритма состоит из двух структур данных: ключа и таблицы замен.

Ключ, имеющий размер 256 двоичных ячеек (битов), представляется как массив из восьми 32-битовых элементов. Элементы ключа в порядке, определяемом базовым циклом, используются основным шагом.
Таблица замен является матрицей размером 8 на 16 из 4-битовых элементов. Строки таблицы, называемые узлами замен, содержат различные значения, при этом каждый узел содержит 16 различных чисел от 0 до 15. Таблица замен используется основным шагом на этапе замены. Является долговременным ключевым элементом, общим для сети ЭВМ.

Три уровня структуры алгоритмаПравить

Блок-схема основного шага

Таким образом, структура алгоритма ГОСТ 28147-89 делится на три уровня:

основной шаг;
базовые циклы;
режимы работы алгоритма.

Кратко рассмотрим их в отдельности.

Основной шагПравить

Основной шаг принимает на входе два параметра: 64-битовый блок данных и 32-битовый элемент ключа, а также использует всю таблицу замен. 64-битовый блок делится на две части по 32 бита. Первая часть и 32-битовый входной параметр представляются как беззнаковые 32-битовые числа и складываются по модулю 2³². Результат представляется как массив из восьми 4-битовых блоков, каждый из них заменяется на значение ячейки таблицы замен из строки с номером, равным номеру 4-битового блока, и столбца с номером, равным значению 4-битового блока (счёт с 0). Полученное значение подвергается циклическому сдвигу в сторону старших разрядов на 11 битов. Далее оно поразрядно складывается по модулю 2 со второй частью входного 64-битового блока. Затем полученное значение ставится на место второй части 64-битового блока, а вторая часть — на место первой. Полученный блок возвращается в качестве результата.

Три базовых циклаПравить

Базовый цикл представляет собой многократное повторение основного шага. На вход поступает 64-битовый блок, который определённое число раз поступает на вход основного шага и принимает значение, возвращаемое им. Возвращается базовым циклом последнее значение блока. Вторыми параметрами основного шага являются элементы ключа. Отличаются циклы числом повторений основного шага и порядком использования элементов ключа. Для цикла «32-З» порядок следующий: трижды используются элементы ключа с первого по последний и один раз с последнего по первый; для цикла «32-Р»: один раз используются элементы ключа с первого по последний и три раза — с последнего по первый; для цикла «16-З»: дважды используются элементы ключа с первого по последний.

Режимы работы алгоритмаПравить

Алгоритм ГОСТ 28147-89 имеет четыре режима работы.

Режим простой замены принимает на вход данные, размер которых кратен 64-м битам. Результатом шифрования является входной текст, преобразованный блоками по 64 бита в случае зашифрования циклом «32-З», а в случае расшифрования — циклом «32-Р».
Режим гаммирования принимает на вход данные любого размера, а также дополнительный 64-битовый параметр — синхропосылку. В ходе работы синхропосылка преобразуется в цикле «32-З», результат делится на две части. Первая часть складывается по модулю 2³² с постоянным значением 1010101₁₆. Если вторая часть равна 2³²-1, то её значение не меняется, иначе она складывается по модулю 2³²-1 с постоянным значением 1010104₁₆. Полученное объединением обеих преобразованных частей значение, называемое гаммой шифра, поступает в цикл «32-З», его результат порязрядно складывается по модулю 2 с 64-разрядным блоком входных данных. Если последний меньше 64-х разрядов, то лишние разряды полученного значения отбрасываются. Полученное значение подаётся на выход. Если ещё имеются входящие данные, то действие повторяется: составленный из 32-разрядных частей блок преобразуется по частям и так далее.
Режим гаммирования с обратной связью также принимает на вход данные любого размера и синхропосылку. Блок входных данных поразрядно складывается по модулю 2 с результатом преобразования в цикле «32-З» синхропосылки. Полученное значение подаётся на выход. Значение синхропосылки заменяется в случае зашифрования выходным блоком, а в случае расшифрования — входным, то есть зашифрованным. Если последний блок входящих данных меньше 64 разрядов, то лишние разряды гаммы (выхода цикла «32-З») отбрасываются. Если ещё имеются входящие данные, то действие повторяется: из результата зашифрования заменённого значения образуется гамма шифра и т.д.
Режим выработки имитовставки принимает на вход данные, размер которых составляет не меньше двух полных 64-разрядных блоков, а возвращает 64-разрядный блок данных, называемый имитовставкой. Временное 64-битовое значение устанавливается в 0, далее, пока имеются входные данные, оно поразрядно складывается по модулю 2 с результатом выполнения цикла «16-З», на вход которого подаётся блок входных данных. После окончания входных данных временное значение возвращается как результат.

Преимущества и недостаткиПравить

КриптоанализПравить

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

Тем не менее, интересны некоторые работы в этой области^[1]:

одна из первых открытых работ, в которых был проведен анализ алгоритма, посвящена атакам, использующим слабости процедуры расширения ключа ряда известных алгоритмов шифрования; в частности, полнораундовый алгоритм ГОСТ 28147-89 может быть вскрыт с помощью дифференциального криптоанализа на связанных ключах, но только в случае использования слабых таблиц замен;
отечественные ученые А.Г. Ростовцев и Е.Б. Маховенко в 2001 г. в своей работе^[2] предложили принципиально новый метод криптоанализа (по мнению авторов, существенно более эффективный, чем линейный и дифференциальный криптоанализ^[3]) путём формования целевой функции от известного открытого текста, соответствующего ему шифртекста и искомого значения ключа и нахождения её экстремума, соответствующего истинному значению ключа. Они же нашли большой класс слабых ключей.
в 2004 г. группа специалистов из Кореи предложила атаку, с помощью которой, используя дифференциальный криптоанализ на связанных ключах, можно получить с вероятностью 91,7 % 12 битов секретного ключа^[4]. Для атаки требуется 2³⁵ выбранных открытых текстов и 2³⁶ операций шифрования. Как видно, данная атака, практически, бесполезна для реального вскрытия алгоритма.
В мае 2011 года появились сообщения о существовании атаки на данный шифр, имеющей сложность в 2⁸ (256) раз меньше сложности прямого перебора ключей при условии наличия 2⁶⁴ пар открытый текст/закрытый текст^[5]^[6]. Данная атака не может быть осуществлена на практике ввиду слишком высокой вычислительной сложности.

Неопределённость таблицы заменПравить

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

Иногда предполагается, что таблица замен может служить частью ключа, увеличивая его длину, однако есть сведения^[7], что таблицу возможно вычислить с достаточно небольшой сложностью.

Пример таблицы замен^[8]^[9]:

Номер узла замен	Значение
1	4	A	9	2	D	8	0	E	6	B	1	C	7	F	5	3
2	E	B	4	C	6	D	F	A	2	3	8	1	0	7	5	9
3	5	8	1	D	A	3	4	2	E	F	C	7	6	0	9	B
4	7	D	A	1	0	8	9	F	E	4	6	C	B	2	5	3
5	6	C	7	1	5	F	D	8	4	A	9	E	0	3	B	2
6	4	B	A	0	7	2	1	D	3	6	8	5	9	C	F	E
7	D	B	4	1	3	F	5	9	0	A	E	7	6	8	2	C
8	1	F	D	0	5	7	A	4	9	2	3	E	6	B	8	C

Актуальность алгоритмаПравить

Алгоритм, закреплённый в стандарте ГОСТ, долгое время верно служил нуждам государства и страны. Тем не менее, в общенародное пользование он поступил уже перед самой гибелью последнего на данный момент русского государства — СССР.

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

Но нельзя забывать о том, что это не собственность групп людей, назвавшихся властью, а собственность русского народа. Благодаря отличным показателям шифра как такового он используется и простыми людьми в своих целях, притом алгоритм весьма распространён и известен даже зарубежом (хотя нерусь и называет его «аналогом DES»^[10], ихний устаревший шифр не годится ни в какое сравнение с нашим). В этом заключается другая причина его актуальности.

Поэтому можно сделать вывод о высокой актуальности алгоритма ГОСТ 28147-89, которая не убавится в ближайшем будущем. Также следует заметить, что этот алгоритм используется в алгоритме хэширования ГОСТ Р 34.11-94, который, в свою очередь, используется в алгоритме цифровой подписи ГОСТ Р 34.10-2001 (в том числе и в его устаревшей версии 1994-го года).

Примеры шифрования и реализацииПравить

Возьмём для демонстрации работы шифра^[11] таблицу замен, приведённую выше, и следующий, выбранный случайно, ключ: E2C104F9 E41D7CDE 7FE5E857 060265B4 281CCC85 2E2C929A 47464503 E00CE510. В качестве шифруемого текста возьмём «Слава России!», записанное Уникодом: 0421 043B 0430 0432 0430 0020 0420 043E 0441 0441 0438 0438 0021. В побайтовом написании это будет выглядеть так:

[21][04][3B][04][30][04][32][04][30][04][20][00][20][04][3E][04][41][04][41][04][38][04][38][04][21][00].

Возьмём и синхропосылку, тоже выбранную случайно:

[71][3F][A2][D7][B5][84][29][5C].

Представленный исходный код реализации алгоритма написан на языке Глагол.

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

 ПЕР 
   Ключ: РЯД 8 ИЗ ЦЕЛ; 
   ТаблицаЗамен: РЯД 8, 16 ИЗ ЯЧЦЕЛ;

Далее идут вспомогательные задачи: БеззнСлжПоМод32 для сложения по модулю 2³², ИсклИЛИ для побитового сложения по модулю 2 для 4-байтовых и ИсклИЛИШир — 8-байтовых блоков, используемые в коде, но не встроенные в язык.

Основной шагПравить

На вход поступает блок текста размером 8 байтов:

[21][04][3B][04][30][04][32][04];

и элемент ключа, размером 4 байта:

[F9][04][C1][E2].

Поступивший блок текста делится на две части:

[21][04][3B][04] и [30][04][32][04].

Первую складываем по модулю 2³² с полученным элементом ключа, в результате получаем

[1A][08][FC][E6].

Далее, в этом блоке производятся замены с использованием таблицы замен. Заменяются соответственно:

[A] на [1], [1] на [B], [9] на [F], [0] на [7], [C] на [0], [F] на [E], [6] на [5] и [E] на [8].

В итоге получаем

[B1][7F][E0][85].

Далее производится циклический сдвиг полученного значения в сторону старших разрядов на 11 битов:

[2F][8C][FD][03].

Это значение складывается поразрядно по модулю 2 со второй частью поступившего на вход 8-битового блока, в итоге получается

[1F][88][CF][07].

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

[1F][88][CF][07][21][04][3B][04]

и будет результатом выполнения шага.

Задача, целью которой является выполнение замены по таблице замен, на вход она принимает по байту блока, в котором происходит замена, и номер узла замен:

 ЗАДАЧА Замена(стр: ЯЧЦЕЛ; яч: ОБХОД.Ячейка): ЯЧЦЕЛ; 
 ПЕР 
   п1, п2, п3: ЦЕЛ; результат: ЯЧЦЕЛ;
 УКАЗ 
   п1 := 0; п2 := 0;
   ОБХОД.Образ(
     ОБХОД.ПолучитьАдрес(яч),
     ОБХОД.ПолучитьАдрес(п1),
     1); 
   п1 := Асм.Сдвиг(п1, 4);
   ОБХОД.Образ(
     ОБХОД.ПолучитьАдрес(п1),
     ОБХОД.ПолучитьАдрес(п2),
     1); 
   п2 := Асм.Сдвиг(п2, -4); п1 := Асм.Сдвиг(п1, -8); 
   п3 := ТаблицаЗамен[стр*2, п2] + Асм.Сдвиг(ТаблицаЗамен[стр*2+1, п1], 4); 
   ОБХОД.Образ(
     ОБХОД.ПолучитьАдрес(п3),
     ОБХОД.ПолучитьАдрес(результат),
     1); 
   ВОЗВРАТ результат
 КОН Замена;

Собственно основной шаг:

 ЗАДАЧА ОсновнойШаг(N: ШИРЦЕЛ; X: ЦЕЛ): ШИРЦЕЛ; 
 ПЕР 
   N1, N2, S: ЦЕЛ; 
   сч: ЯЧЦЕЛ; 
   ячейка: ЯЧЦЕЛ; 
   результат: ШИРЦЕЛ; 
 УКАЗ 
   ОБХОД.Образ(
     ОБХОД.ПолучитьАдрес(N),
     ОБХОД.ПолучитьАдрес(N1),
     4); 
   ОБХОД.Образ(
     ОБХОД.ПолучитьАдрес(N)+4,
     ОБХОД.ПолучитьАдрес(N2),
     4); 
   S := БеззнСлжПоМод32(N1, X); 
   ОТ сч := 0 ДО 3 ВЫП 
     ОБХОД.Образ(
       ОБХОД.ПолучитьАдрес(S)+сч,
       ОБХОД.ПолучитьАдрес(ячейка),
       1); 
     ячейка := Замена(сч, ячейка); 
     ОБХОД.Образ(
       ОБХОД.ПолучитьАдрес(ячейка),
       ОБХОД.ПолучитьАдрес(S)+сч,
       1) 
   КОН; 
   S := Асм.Вращение(S, 11); 
   S := ИсклИЛИ(S, N2); 
   N2 := N1; N1 := S; 
   ОБХОД.Образ(
     ОБХОД.ПолучитьАдрес(N1),
     ОБХОД.ПолучитьАдрес(результат),
     4); 
   ОБХОД.Образ(
     ОБХОД.ПолучитьАдрес(N2),
     ОБХОД.ПолучитьАдрес(результат)+4,
     4); 
   ВОЗВРАТ результат 
 КОН ОсновнойШаг;

Базовые циклыПравить

32-З

На вход цикла поступает 8-байтовый блок:

[21][04][3B][04][30][04][32][04].

В ходе выполнения цикла 32 раза выполняется основной шаг. На его вход поступает сперва входное значение цикла, далее — результат выполнения предыдущего основного шага. Для выполнения основного шага элементы ключа выбираются три раза с первого по последний и один раз с последнего по первый, то есть при нумерации с нуля порядок будет такой: 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 7, 6, 5, 4, 3, 2, 1, 0. Таким образом, в первый шаг поступает элемент ключа

[F9][04][C1][E2],

а в результате выполнения шага имеем значение

[1F][88][CF][07][21][04][3B][04].

Теперь оно берётся для следующего шага, для которого берётся элемент ключа

[DE][7C][1D][E4],

и так далее. Результат выполнения последнего, 32-го основного шага,

[D8][4F][A2][5C][08][90][F2][8E],

возвращается в качестве результата цикла.

Эта задача реализована при помощи циклов, при которых значение переменной-счётчика соответствует номеру элемента ключа.

 ЗАДАЧА Зашифрование(N: ШИРЦЕЛ): ШИРЦЕЛ; 
 ПЕР 
   сч1, сч2: ЯЧЦЕЛ; 
   память: ЦЕЛ; 
 УКАЗ 
   ОТ сч1 := 1 ДО 3 ВЫП 
     ОТ сч2 := 0 ДО 7 ВЫП 
       N := ОсновнойШаг(N, Ключ[сч2]) 
     КОН 
   КОН; 
   ОТ сч1 := 7 ДО 0 ПО -1 ВЫП 
     N := ОсновнойШаг(N, Ключ[сч1]) 
   КОН; 
   ОБХОД.Образ(
     ОБХОД.ПолучитьАдрес(N),
     ОБХОД.ПолучитьАдрес(память),
     4); 
   ОБХОД.Образ(
     ОБХОД.ПолучитьАдрес(N)+4,
     ОБХОД.ПолучитьАдрес(N),
     4); 
   ОБХОД.Образ(
     ОБХОД.ПолучитьАдрес(память),
     ОБХОД.ПолучитьАдрес(N)+4,
     4); 
   ВОЗВРАТ N 
 КОН Зашифрование;

32-Р

От предыдущего рассмотренного цикла этот отличается лишь порядком использования элементов ключа: один раз они берутся с первого по последний и три раза с последнего по первый, то есть при нумерации с нуля порядок такой: 0, 1, 2, 3, 4, 5, 6, 7, 7, 6, 5, 4, 3, 2, 1, 0, 7, 6, 5, 4, 3, 2, 1, 0, 7, 6, 5, 4, 3, 2, 1, 0. Таким образом, в первый шаг поступает входное значение цикла

[D8][4F][A2][5C][08][90][F2][8E]

и элемент ключа

[F9][04][C1][E2].

Результатом будет значение

[68][40][A1][02][D8][4F][A2][5C],

которое поступает на вход следующего шага вместе с элементом ключа

[DE][7C][1D][E4],

и так далее. Результат выполнения последнего основного шага

[21][04][3B][04][30][04][32][04]

также, как и в предыдущем цикле, будет результатом этого цикла.

Таким же образом реализована и эта задача. Следует заметить, что циклы «32-З» и «32-Р» являются взаимно обратными. Тем не менее, стандарт предписывает использовать для зашифрования именно «32-З», а для расшифрования «32-Р».

 ЗАДАЧА Расшифрование(N: ШИРЦЕЛ): ШИРЦЕЛ; 
 ПЕР 
   сч1, сч2: ЯЧЦЕЛ; 
   память: ЦЕЛ; 
 УКАЗ 
   ОТ сч1 := 0 ДО 7 ВЫП 
     N := ОсновнойШаг(N, Ключ[сч1]) 
   КОН; 
   ОТ сч1 := 1 ДО 3 ВЫП 
     ОТ сч2 := 7 ДО 0 ПО -1 ВЫП 
       N := ОсновнойШаг(N, Ключ[сч2]) 
     КОН 
   КОН; 
   ОБХОД.Образ(
     ОБХОД.ПолучитьАдрес(N),
     ОБХОД.ПолучитьАдрес(память),
     4); 
   ОБХОД.Образ(
     ОБХОД.ПолучитьАдрес(N)+4,
     ОБХОД.ПолучитьАдрес(N),
     4); 
   ОБХОД.Образ(
     ОБХОД.ПолучитьАдрес(память),
     ОБХОД.ПолучитьАдрес(N)+4,
     4); 
   ВОЗВРАТ N 
 КОН Расшифрование;

16-З

В отличие от двух предыдущих циклов, в этом основной шаг вызывается только 16 раз. Элементы ключа используются два раза с первого по последний, то есть порядок при нумерации элементов с нуля такой: 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7. В остальном порядок выполнения цикла такой же, как и в описанных выше. На вход поступает значение

[21][04][3B][04][30][04][32][04],

которое передаётся первому основному шагу с ключём

[F9][04][C1][E2].

Результат последнего шага,

[97][EB][F9][BD][7E][28][84][27],

есть результат цикла.

Задача, реализующая цикл выработки имитовставки, ещё проще предыдущих двух. Цикл «16-З» повторяет первые 16 итераций «32-З».

 ЗАДАЧА ВыработкаИмитовставки(N: ШИРЦЕЛ): ШИРЦЕЛ; 
 ПЕР 
   сч1, сч2: ЯЧЦЕЛ; 
 УКАЗ 
   ОТ сч1 := 1 ДО 2 ВЫП 
     ОТ сч2 := 0 ДО 7 ВЫП 
       N := ОсновнойШаг(N, Ключ[сч2]) 
     КОН 
   КОН; 
   ВОЗВРАТ N 
 КОН ВыработкаИмитовставки;

Режимы работы алгоритмаПравить

Простая замена

Для шифрования в режиме простой замены размер данных должен быть кратен 8. Выбранный текст на два байта больше, так что последний знак («!») уберём. В итоге размер текста равен 24.

Зашифрование

Зашифрование в этом режиме заключается в преобразовании каждого 8-байтового блока текста в цикле 32-З. Итак, первый блок

[21][04][3B][04][30][04][32][04]

преобразуется в цикле 32-З, результатом чего будет значение

[D8][4F][A2][5C][08][90][F2][8E],

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

[30][04][20][00][20][04][3E][04]

имеем

[5E][02][45][3E][9B][17][04][B4]

и с третьим блоком открытого текста

[41][04][41][04][38][04][38][04]

получаем

[00][06][EF][13][EA][93][DD][6B].

В результате мы имеем зашифрованный текст:

[D8][4F][A2][5C][08][90][F2][8E][5E][02][45][3E][9B][17][04][B4][00][06][EF][13][EA][93][DD][6B].

Открывается входной файл для чтения и выходной для записи. Ихние названия передаются в качестве параметров задачи. Проверяется, чтобы размер файла был кратен 8. Блоками по 8 байтов читается входной файл, шифруется и пишется в выходной.

 ЗАДАЧА ПростаяЗаменаЗ(вхФайл-, выхФайл-: РЯД ИЗ ЗНАК); 
 ПЕР 
   текБлок: ШИРЦЕЛ; 
   сч: ЦЕЛ; 
   чп: Читать.Поток; 
   пп: Писать.Поток; 
   размер: ЦЕЛ; 
 УКАЗ 
   размер := Файл.Размер(вхФайл); 
   ЕСЛИ размер ОСТАТОК 8 # 0 ТО
     Вывод.Цепь("^Ошибка: размер файла не кратен 8.^"); СТОП(0)
   КОН; 
   чп := Читать.Открыть(вхФайл); 
   пп := Писать.Открыть(выхФайл);  
   ОТ сч := 1 ДО размер ДЕЛИТЬ 8 ВЫП 
     Читать.Ячейки(чп, текБлок, 8); 
     текБлок := Зашифрование(текБлок); 
     Писать.Ячейки(пп, текБлок, 8) 
   КОН; 
   Писать.Закрыть(пп); Читать.Закрыть(чп) 
 КОН ПростаяЗаменаЗ;

Расшифрование

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

[D8][4F][A2][5C][08][90][F2][8E]

подаётся в цикл 32-Р, который выполняет преобразование обратное тому, которое было выполнено циклом 32-З. Получаем блок открытого текста

[21][04][3B][04][30][04][32][04].

Второй блок

[5E][02][45][3E][9B][17][04][B4]

даёт после преобразования

[30][04][20][00][20][04][3E][04],

а из третьего

[00][06][EF][13][EA][93][DD][6B],

получаем

[41][04][41][04][38][04][38][04].

В итоге имеем

[21][04][3B][04][30][04][32][04][30][04][20][00][20][04][3E][04][41][04][41][04][38][04][38][04],

то есть тот самый текст, который был зашифрован.

Задача устроена также, как и предыдущая, но 8-байтовый блок преобразуется в цикле «32-Р», а не «32-З». Надо заметить, что шифрование в режиме простой замены на практике используется обычно только для ключей и таблиц замен.

 ЗАДАЧА ПростаяЗаменаР(вхФайл-, выхФайл-: РЯД ИЗ ЗНАК); 
 ПЕР 
   текБлок: ШИРЦЕЛ; 
   сч: ЦЕЛ; 
   чп: Читать.Поток; 
   пп: Писать.Поток; 
   размер: ЦЕЛ; 
 УКАЗ 
   размер := Файл.Размер(вхФайл); 
   ЕСЛИ размер ОСТАТОК 8 # 0 ТО
     Вывод.Цепь("^Ошибка: размер файла не кратен 8.^"); СТОП(0)
   КОН; 
   чп := Читать.Открыть(вхФайл); 
   пп := Писать.Открыть(выхФайл);  
   ОТ сч := 1 ДО размер ДЕЛИТЬ 8 ВЫП 
     Читать.Ячейки(чп, текБлок, 8); 
     текБлок := Расшифрование(текБлок); 
     Писать.Ячейки(пп, текБлок, 8) 
   КОН; 
   Писать.Закрыть(пп); Читать.Закрыть(чп) 
 КОН ПростаяЗаменаР;

Гаммирование

Синхропосылка преобразуется в цикле 32-З, в итоге получаем

[8F][10][73][84][19][18][5C][2C].

Этот блок делится на две части по 4 байта:

[8F][10][73][84] и [19][18][5C][2C].

Первая часть преобразуется по формуле (Значение + 1010104₁₆) ОСТАТОК 2³² (то есть складывается со значением 1010104₁₆ по модулю 2³²), вторая часть — по формуле (Значение + 1010101₁₆ - 1) ОСТАТОК (2³² - 1) + 1, где «Значение» — значение части, «ОСТАТОК» - операция взятия остатка от деления. В результате получаем

[90][11][74][85] и [1D][19][5D][2D].

Эти значения объединяются обратно в 8-байтовый блок

[90][11][74][85][1D][19][5D][2D],

результат преобразования которого в цикле 32-З

[8F][12][BA][93][4A][BB][A4][20]

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

[21][04][3B][04][30][04][32][04],

в результате чего имеем блок зашифрованного текста

[AE][16][81][97][7A][BF][96][24].

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

[91][12][75][86] и [21][1A][5E][2E].

Они объединяются в блок

[91][12][75][86][21][1A][5E][2E],

значение которого передаётся в цикл 32-З, результатом которого становится

[B2][90][DC][04][87][DE][18][DC].

Очередной входной блок

[30][04][20][00][20][04][3E][04]

также складывается поразрядно по модулю 2 с результатом выполнения цикла 32-З, в итоге имеем следующий блок зашифрованного текста:

[82][94][FC][04][A7][DA][26][D8].

Дальше операция повторяется. Берётся 8-байтовое значение, части которого преобразуются по указанным выше формулам, в итоге преобразования имеем новое значение этого блока

[92][13][76][87][25][1B][5F][2F],

которое поступает в цикл 32-З, результатом которого получаем

[25][F2][4E][84][51][CA][39][1E].

Складываем его поразрядно по модулю 2 с входным текстом

[41][04][41][04][38][04][38][04],

в итоге имеем зашифрованный блок

[64][F6][0F][80][69][CE][01][1A].

Снова операции повторяются, после преобразования вышеупомянутого блока по формулам имеем

[93][14][77][88][29][1C][60][30],

это значение зашифровывается в 32-З:

[BA][CF][6A][3E][23][BF][B4][72].

Очередной входной блок, однако, не является полным, его длина составляет 2 байта:

[21][00].

В таком случае от результата цикла 32-З берётся часть, равная длине блока, в нашем случае — 2:

[BA][CF];

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

[9B][CF].

В итоге имеем

[AE][16][81][97][7A][BF][96][24][82][94][FC][04][A7][DA][26][D8][64][F6][0F][80][69][CE][01][1A][9B][CF].

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

Гаммирование по своей сути является наложением по определённому закону некоторой последовательности данных, называемой гаммой. В данном алгоритме в качестве этого закона используется побитное сложение по модулю 2. Для выработки гаммы используется реккурентный генератор последовательности чисел, вырабатывающий блоки по 8 байтов. Являясь реккурентной функцией, он использует в качестве параметра предыдущий блок выработанной последовательности. Начальным заполнением является синхропосылка. Блоком гаммы становится блок, выработанный генератором, преобразованный в цикле «32-З». Также криптографическая гамма может использоваться для получения псевдослучайных данных, которые, например, можно использовать в качестве ключей.

 ЗАДАЧА Гаммирование(
   вхФайл-, выхФайл-: РЯД ИЗ ЗНАК;
   S: ШИРЦЕЛ
 ); 
 ПОСТ 
   C1 = 1010101H; 
   C2 = 1010104H; 
 ПЕР 
   S1, S2: ЦЕЛ; пам: ШИРЦЕЛ; доппам: ЦЕЛ; 
   сч: ЦЕЛ; 
   пяч: ЯЧЦЕЛ; 
   чп: Читать.Поток; 
   пп: Писать.Поток; 
   размер: ЦЕЛ; 
 УКАЗ 
   размер := Файл.Размер(вхФайл); 
   чп := Читать.Открыть(вхФайл); 
   пп := Писать.Открыть(выхФайл); 
   S := Зашифрование(S); 
   ОБХОД.Образ(
     ОБХОД.ПолучитьАдрес(S),
     ОБХОД.ПолучитьАдрес(S1),
     4); 
   ОБХОД.Образ(
     ОБХОД.ПолучитьАдрес(S)+4,
     ОБХОД.ПолучитьАдрес(S2),
     4); 
   ОТ сч := 1 ДО размер ДЕЛИТЬ 8 ВЫП 
     S1 := БеззнСлжПоМод32(S1, C1); 
     ЕСЛИ (S2 < 0) И (S2 > -1-C2) ТО
       УВЕЛИЧИТЬ(S2)
     КОН; 
     S2 := БеззнСлжПоМод32(S2, C2); 
     ОБХОД.Образ(
       ОБХОД.ПолучитьАдрес(S1),
       ОБХОД.ПолучитьАдрес(S),
       4); 
     ОБХОД.Образ(
       ОБХОД.ПолучитьАдрес(S2),
       ОБХОД.ПолучитьАдрес(S)+4,
       4); 
     S := Зашифрование(S); 
     Читать.Ячейки(чп, пам, 8); 
     пам := ИсклИЛИШир(пам, S); 
     Писать.Ячейки(пп, пам, 8) 
   КОН; 
   ЕСЛИ размер ОСТАТОК 8 # 0 ТО 
     S1 := БеззнСлжПоМод32(S1, C1); 
     ЕСЛИ (S2 < 0) И (S2 > -1-C2) ТО
       УВЕЛИЧИТЬ(S2)
     КОН; 
     S2 := БеззнСлжПоМод32(S2, C2); 
     ОБХОД.Образ(
       ОБХОД.ПолучитьАдрес(S1),
       ОБХОД.ПолучитьАдрес(S),
       4); 
     ОБХОД.Образ(
       ОБХОД.ПолучитьАдрес(S2),
       ОБХОД.ПолучитьАдрес(S)+4,
       4); 
     S := Зашифрование(S); 
     ОТ сч := 0 ДО размер ОСТАТОК 8 - 1 ВЫП 
       ОБХОД.Образ(
         ОБХОД.ПолучитьАдрес(S)+сч,
         ОБХОД.ПолучитьАдрес(пяч),
         1); 
       доппам := 0; Читать.Ячейки(чп, доппам, 1); 
       доппам := ИсклИЛИ(доппам, пяч); 
       Писать.Ячейки(пп, доппам, 1) 
     КОН 
   КОН; 
   Писать.Закрыть(пп); Читать.Закрыть(чп) 
 КОН Гаммирование;

Гаммирование с обратной связью

Синхропосылка зашифровывается циклом 32-З:

[8F][10][73][84][19][18][5C][2C],

после чего поразрядно складывается по модулю 2 с открытым текстом

[21][04][3B][04][30][04][32][04],

в результате получаем блок зашифрованного текста

[AE][14][48][80][29][1C][6E][28].

Далее значение блока зашифрованного текста подаётся в цикл 32-З, результат выполнения которого,

[7E][09][2F][0B][2A][A9][55][F8],

складывается поразрядно с очередным входным блоком данных

[30][04][20][00][20][04][3E][04],

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

[4E][0D][0F][0B][0A][AD][6B][FC].

После чего операция повторяется, значение блока зашифрованных данных поступает в цикл 32-З, в итоге получаем

[F4][21][1E][C4][F3][C3][EF][1D],

который поразрядно складывается по модулю 2 с открытым текстом

[41][04][41][04][38][04][38][04],

в итоге имеем блок зашифрованного текста

[B5][25][5F][C0][CB][C7][D7][19].

Его значение преобразуется в цикле 32-З, получаем

[79][02][15][FD][91][B8][1D][37].

Последний входной блок,

[21][00],

занимает меньше 8 байтов, поэтому от результата выполнения цикла берём столько же байтов, сколько составляют последний входящий блок:

[79][02].

После их поразрядного сложения по модулю 32 получаем последний блок зашифрованного текста:

[58][02].

В итоге имеем

[AE][14][48][80][29][1C][6E][28][4E][0D][0F][0B][0A][AD][6B][FC][B5][25][5F][C0][CB][C7][D7][19][58][02].

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

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

 ЗАДАЧА ГаммированиеСОбратнойСвязью(
   вхФайл-, выхФайл-: РЯД ИЗ ЗНАК;
   S: ШИРЦЕЛ;
   расшифрование: КЛЮЧ
 ); 
 ПЕР 
   пам: ШИРЦЕЛ; доппам: ЦЕЛ; 
   сч: ЦЕЛ; 
   пяч: ЯЧЦЕЛ; 
   чп: Читать.Поток; 
   пп: Писать.Поток; 
   размер: ЦЕЛ; 
 УКАЗ 
   размер := Файл.Размер(вхФайл); 
   чп := Читать.Открыть(вхФайл); 
   пп := Писать.Открыть(выхФайл);  
   ОТ сч := 1 ДО размер ДЕЛИТЬ 8 ВЫП 
     S := Зашифрование(S); 
     Читать.Ячейки(чп, пам, 8); 
     S := ИсклИЛИШир(S, пам); 
     Писать.Ячейки(пп, S, 8); 
     ЕСЛИ расшифрование ТО S := пам КОН 
   КОН; 
   ЕСЛИ размер ОСТАТОК 8 # 0 ТО 
     S := Зашифрование(S); 
     ОТ сч := 0 ДО размер ОСТАТОК 8 - 1 ВЫП 
       ОБХОД.Образ(
         ОБХОД.ПолучитьАдрес(S)+сч,
         ОБХОД.ПолучитьАдрес(пяч),
         1); 
       доппам := 0; Читать.Ячейки(чп, доппам, 1); 
       доппам := ИсклИЛИ(доппам, пяч); 
       Писать.Ячейки(пп, доппам, 1) 
     КОН 
   КОН; 
   Писать.Закрыть(пп); Читать.Закрыть(чп) 
 КОН ГаммированиеСОбратнойСвязью;

Выработка имитовставки

Блок открытого текста, размером в 8 байтов,

[21][04][3B][04][30][04][32][04],

преобразуется в цикле 16-З, получаем

[97][EB][F9][BD][7E][28][84][27].

Далее это значение складывается поразрядно по модулю 2 со следующим блоком открытого текста

[30][04][20][00][20][04][3E][04],

в результате чего имеем

[A7][EF][D9][BD][5E][2C][BA][23].

Это значение преобразуется в цикле 16-З и так далее. Выход последнего цикла 16-З и будет имитовставкой. Притом, если последний блок открытого текста меньше 8 байтов, то он дополняется нулями (которые в операции двоичного побитового сложения роли не играют). В итоге имеем

[01][D6][22][7B][6F][CD][86][4D],

то есть имитовставка равна 4D86CD6F7B22D601.

Особняком стоит режим выработки имитовставки. Хотя он использует те же параметры, что и предыдущие режимы, в отличие от них он предназначен не для шифрования, а для проверки целостности данных. При этом вероятность навязывания ложных данных зависит от длины блока, взятого в качестве имитовставки, и определяется как 2^-|I|, где |I| - длина имитовставки в битах.

 ЗАДАЧА Имитовставка(имяФайла-: РЯД ИЗ ЗНАК): ШИРЦЕЛ; 
 ПЕР 
   S: ШИРЦЕЛ; 
   пам: ШИРЦЕЛ; 
   поток: Читать.Поток; 
 УКАЗ 
   поток := Читать.Открыть(имяФайла); 
   ЕСЛИ поток = ПУСТО ТО
     Вывод.Цепь("^Ошибка: невозможно открыть файл.^"); СТОП(0)
   КОН; 
   S := 0; 
   ПОКА НЕ Читать.Конец(поток) ВЫП 
     Читать.Ячейки(поток, пам, 8); 
     S := ИсклИЛИШир(пам, S); 
     S := ВыработкаИмитовставки(S) 
   КОН; 
   Читать.Закрыть(поток); 
   ВОЗВРАТ S 
 КОН Имитовставка;

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

ПримечанияПравить

↑ http://www.cio-world.ru/techniques/328198/
↑ Ростовцев А.Г., Маховенко Е.Б. Два подхода к анализу блочных шифров. // http://www.ssl.stu.neva.ru – Проблемы информационной безопасности. Компьютерные системы. – 2002 – № 1.
↑ Ростовцев А.Г., Маховенко Е.Б., Филиппов А.С., Чечулин А.А. О стойкости ГОСТ 28147-89. // http://www.ssl.stu.neva.ru – СПбГПУ.
↑ http://www.springerlink.com/content/dwl344fg8xduwt46/
↑ Security Evaluation of GOST 28147-89 In View Of International Standardisation. Cryptology ePrint Archive: Report 2011/211
↑ SecurityLab: Взломан блочный шифр ГОСТ 28147-89
↑ http://citeseer.ist.psu.edu/saarinen98chosen.html
↑ Эта таблица замен приведена в тексте стандарта ГОСТ Р 34.11-94 в проверочном примере
↑ Согласно данным книги Б. Шнайера «Прикладная криптография», эти же блоки используются также Центральным банком Эрэфии
↑ А презренно называть наши разработки «аналогами» своих (с намёком на копирование), зачастую самими подло скопированных, западные деятели очень любят.
↑ Для этой цели удобнее использовать специальную программу, размещённую на сайте gostshifr.url.ph.

СсылкиПравить

[1] ttp://www.cio-world.ru/techniques/328198/

[2] Ростовцев А.Г., Маховенко Е.Б. Два подхода к анализу блочных шифров. // http://www.ssl.stu.neva.ru – Проблемы информационной безопасности. Компьютерные системы. – 2002 – № 1.

[3] Ростовцев А.Г., Маховенко Е.Б., Филиппов А.С., Чечулин А.А. О стойкости ГОСТ 28147-89. // http://www.ssl.stu.neva.ru – СПбГПУ.

[4] ttp://www.springerlink.com/content/dwl344fg8xduwt46/

[5] Security Evaluation of GOST 28147-89 In View Of International Standardisation. Cryptology ePrint Archive: Report 2011/211

[6] SecurityLab: Взломан блочный шифр ГОСТ 28147-89

[7] ttp://citeseer.ist.psu.edu/saarinen98chosen.html

[8] Эта таблица замен приведена в тексте стандарта ГОСТ Р 34.11-94 в проверочном примере

[9] Согласно данным книги Б. Шнайера «Прикладная криптография», эти же блоки используются также Центральным банком Эрэфии

[10] А презренно называть наши разработки «аналогами» своих (с намёком на копирование), зачастую самими подло скопированных, западные деятели очень любят.

[11] Для этой цели удобнее использовать специальную программу, размещённую на сайте gostshifr.url.ph.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Номер узла замен	Значение
1	4	A	9	2	D	8	0	E	6	B	1	C	7	F	5	3
2	E	B	4	C	6	D	F	A	2	3	8	1	0	7	5	9
3	5	8	1	D	A	3	4	2	E	F	C	7	6	0	9	B
4	7	D	A	1	0	8	9	F	E	4	6	C	B	2	5	3
5	6	C	7	1	5	F	D	8	4	A	9	E	0	3	B	2
6	4	B	A	0	7	2	1	D	3	6	8	5	9	C	F	E
7	D	B	4	1	3	F	5	9	0	A	E	7	6	8	2	C
8	1	F	D	0	5	7	A	4	9	2	3	E	6	B	8	C

Номер узла замен	Значение
1	4	A	9	2	D	8	0	E	6	B	1	C	7	F	5	3
2	E	B	4	C	6	D	F	A	2	3	8	1	0	7	5	9
3	5	8	1	D	A	3	4	2	E	F	C	7	6	0	9	B
4	7	D	A	1	0	8	9	F	E	4	6	C	B	2	5	3
5	6	C	7	1	5	F	D	8	4	A	9	E	0	3	B	2
6	4	B	A	0	7	2	1	D	3	6	8	5	9	C	F	E
7	D	B	4	1	3	F	5	9	0	A	E	7	6	8	2	C
8	1	F	D	0	5	7	A	4	9	2	3	E	6	B	8	C

Номер узла замен	Значение
1	4	A	9	2	D	8	0	E	6	B	1	C	7	F	5	3
2	E	B	4	C	6	D	F	A	2	3	8	1	0	7	5	9
3	5	8	1	D	A	3	4	2	E	F	C	7	6	0	9	B
4	7	D	A	1	0	8	9	F	E	4	6	C	B	2	5	3
5	6	C	7	1	5	F	D	8	4	A	9	E	0	3	B	2
6	4	B	A	0	7	2	1	D	3	6	8	5	9	C	F	E
7	D	B	4	1	3	F	5	9	0	A	E	7	6	8	2	C
8	1	F	D	0	5	7	A	4	9	2	3	E	6	B	8	C