Алгоритм гост 28147 89 является. Отечественный стандарт шифрования данных

Этот алгоритм является обязательным для применения в качестве алгорит­ма шифрования в государственных организациях РФ и ряде коммерческих .

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

Схема алгоритма показана на рис. 3.1 . Как видно, схема этого алгоритма достаточно проста, что однозначно упрощает его программ­ную или аппаратную реализацию.

Алгоритм ГОСТ 28147-89 шифрует информацию блоками по 64 бита, кото­рые разбиваются на два субблока по 32 бита (N1 и N2). Субблок N1 опре­деленным образом обрабатывается, после чего его значение складывается

со значением субблока N2 (сложение выполняется по модулю 2), затем суб­блоки меняются местами. Такое преобразование выполняется определенное количество раундов: 16 или 32 в зависимости от режима работы алгоритма (описаны далее). В каждом раунде выполняются следующие операции:

1. Наложение ключа. Содержимое субблока /VI складывается по модулю 2 32 с частью ключа Кх.

Ключ шифрования алгоритма ГОСТ 28147-89 имеет размерность 256 би­тов, а Кх— это его 32-битная часть, т. е. 256-битный ключ шифрования представляется в виде конкатенации 32-битных подключей (рис. 3.2):

Щ ATI, АГ2, Ю, АГ4, К5, Кб, К7.

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

Рис. 3.1. Схема алгоритма ГОСТ 28147-

Рис. 3.2. Ключ шифрования алгоритма ГОСТ 28147-89

2. Табличная замена. После наложения ключа субблок /VI разбивает­ся на 8 частей по 4 бита, значение каждой из которых по отдельности заменяется в соответствии с таблицей замены для данной части суб­блока. Табличные замены (Substitution box, S-box) часто используются в современных алгоритмах шифрования, поэтому стоит рассмотреть их подробнее.

Табличная замена используется таким образом: на вход подается блок данных определенной размерности (в этом случае — 4-битный), числовое представление которого определяет номер выходного значения. Напри­мер, имеем S-box следующего вида:

4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.

Пусть на вход пришел 4-битный блок «0100», т. е. значение 4. Согласно таблице, выходное значение будет равно 15, т.е. «1111» (0 заменяется на 4, 1 — на 11, значение 2 не изменяется и т. д.).

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

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

3. Побитовый циклический сдвиг влево на 11 битов.

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

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

□ режим простой замены;

□ режим гаммирования;

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

□ режим выработки имитоприставок.

Эти режимы несколько отличаются от общепринятых (описанных в разд. 1.4), поэтому стоит рассмотреть их подробнее.

Данные режимы имеют различное назначение, но используют одно и то же описанное выше шифрующее преобразование.

Режим простой замены

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

□ КО, Kl, К2, КЗ, К4, К5, Кб, АГ7, КО, ATI и т. д. — в раундах с 1-го по 24-й;

□ К1, Кб, К5, К4, КЗ, К2, К\, КО —в раундах с 25-го по 32-й.

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

□ КО, К\, К2, КЗ, К4, К5, Кб, КП — в раундах с 1-го по 8-й;

□ КП, Кб, К5, К4, КЗ, К2, К\, КО, К1, Кб и т. д. — в раундах с 9-го по 32-й.

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

Режим гаммирования

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

1. В регистры N1 и N2 записывается их начальное заполнение— 64-битная величина, называемая «синхропосылкой» (синхропосылка, практически, является аналогом вектора инициализации в режимах СВС, CFB и OFB).

2. Выполняется зашифровывание содержимого регистров /VI и N2 (в данном случае — синхропосылки) в режиме простой замены.

3. Содержимое N1 складывается по модулю (2 32 – 1) с константой CI = 2 24 + 2 16 + 2 8 + 4 , результат сложения записывается в регистр /VI.

4. Содержимое N2 складывается по модулю 2 с константой С2 = 2 24 + 2 16 + 2 8 +1, результат сложения записывается в регистр N2.

5. Содержимое регистров /VI и N2 подается на выход в качестве 64-битного блока гаммы шифра (т. е. в данном случае /VI и N2 образуют первый блок гаммы).

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

Для расшифровывания аналогичным образом выполняется выработка гаммы, затем снова применяется операция XOR к битам зашифрованного текста и гаммы.

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

В большинстве реализаций алгоритма ГОСТ 28147-89 синхропосылка не яв­ляется секретным элементом, однако синхропосылка может быть так же сек­ретна, как и ключ шифрования. В этом случае можно считать, что эффектив­ная длина ключа алгоритма (256 битов) увеличивается еще на 64 бита синхропосылки, которую можно рассматривать как дополнительный ключе­вой элемент.

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

В режиме гаммирования с обратной связью в качестве заполнения регистров /VI и Л/2, начиная со 2-го блока, используется не предыдущий блок гаммы, а результат зашифровывания предыдущего блока открытого текста (рис. 3.4). Первый же блок в данном режиме генерируется полностью аналогично пре­дыдущему.

Рис. 3.4. Выработка гаммы шифра в режиме гаммирования с обратной связью

Режим выработки имитоприставки

Имитоприставка — это криптографическая контрольная сумма, вычисляемая с использованием ключа шифрования и предназначенная для проверки цело­стности сообщений. Для ее вычисления существует специальный режим ал­горитма ГОСТ 28147-89.

Генерация имитоприставки выполняется следующим образом:

1. Первый 64-битный блок информации, для которой вычисляется имито­приставка, записывается в регистры N1 и N2 и зашифровывается в сокра­щенном режиме простой замены, в котором выполняются первые 16 раун­дов из 32.

2. Полученный результат суммируется по модулю 2 со следующим блоком информации с сохранением результата в N1 и N2.

3. М и N2 снова зашифровываются в сокращенном режиме простой замены и т. д. до последнего блока информации.

Имитоприставкой считается 64-битное результирующее содержимое регист­ров N1 и N2 или его часть. Чаще всего используется 32-битная имитопри­ставка, т. е. половина содержимого регистров. Этого достаточно, посколь­ку, как и любая контрольная сумма, имитоприставка предназначена, прежде всего, для защиты от случайных искажений информации. Для защиты же от преднамеренной модификации данных применяются другие криптогра­фические методы — в первую очередь электронная цифровая подпись {см. разд. 1.1).

Имитоприставка используется следующим образом:

1. При зашифровывании какой-либо информации вычисляется имитопри­ставка открытого текста и посылается вместе с шифртекстом.

2. После расшифровывания имитоприставка снова вычисляется и сравнива­ется с присланной.

3. Если вычисленная и присланная имитоприставки не совпадают— шифр-текст был искажен при передаче или использовались неверные ключи при расшифровывании.

Имитоприставка особенно полезна для проверки правильности расшиф­ровывания ключевой информации при использовании многоключевых схем.

Имитоприставка— это некоторый аналог кода аутентификации сообщений MAC, вычисляемого в режиме СВС; отличие состоит в том, что при вычис­лении имитоприставки не используется синхропосылка, тогда как при вы­числении MAC используется вектор инициализации.

Криптостойкость алгоритма

В 1994 г. описание алгоритма ГОСТ 28147-89 было переведено на англий­ский язык и опубликовано ; именно после этого стали появляться ре­зультаты его анализа, выполненного зарубежными специалистами; однако в течение значительного времени не было найдено каких-либо атак, прибли­жающихся к практически осуществимым .

□ большой длины ключа — 256 битов; вместе с секретной синхропосылкой эффективная длина ключа увеличивается до 320 битов;

□ 32 раундов преобразований; уже после 8 раундов достигается полный эф­фект рассеивания входных данных: изменение одного бита блока откры­того текста повлияет на все биты блока шифртекста, и наоборот, т. е. су­ществует многократный запас стойкости.

Рассмотрим результаты криптоанализа алгоритма ГОСТ 28147-89.

Анализ таблиц замен

Поскольку таблицы замен в стандарте не приведены, в ряде работ (на­пример, в ) высказывается предположение, что «компетентная органи­зация» может выдать как «хорошие», так и «плохие» таблицы замен. Однако в известнейший эксперт Брюс Шнайер называет такие предположения «слухами». Ясно, что криптостойкость алгоритма во многом зависит от свойств используемых таблиц замен, соответственно, существуют слабые таблицы замен (пример см. выше), применение которых может упростить вскрытие алгоритма. Тем не менее, возможность использования различных таблиц замен кажется весьма достойной идеей, в пользу которой можно при­вести два следующих факта из истории стандарта шифрования DES (подроб­ности см. в разд. 3.15):

□ атаки с помощью как линейного, так и дифференциального криптоанализа алгоритма DES используют конкретные особенности таблиц замен; при использовании других таблиц криптоанализ придется начинать сначала;

□ были предприняты попытки усилить DES против линейного и дифферен­циального криптоанализа путем использования более стойких таблиц за­мен; такие таблицы, действительно более стойкие, были предложены, на­пример, в алгоритме s 5 DES ; но, увы, заменить DES на s 5 DES было невозможно, поскольку таблицы замен жестко определены в стандарте , соответственно, реализации алгоритма наверняка не поддерживают возможность смены таблиц на другие.

В ряде работ (например, , и ) ошибочно делается вывод о том, что секретные таблицы замен алгоритма ГОСТ 28147-89 могут являться частью ключа и увеличивать его эффективную длину (что несущественно, поскольку алгоритм обладает весьма большим 256-битным ключом). Однако в работе доказано, что секретные таблицы замен могут быть вычислены с помощью следующей атаки, которая может быть применена практически:

1. Устанавливается нулевой ключ и выполняется поиск «нулевого вектора», т. е. значения z = /(0), где /() — функция раунда алгоритма. Этот этап занимает порядка 2 операций шифрования.

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

Модификации алгоритма и их анализ

В работе проведен криптоанализ модификаций алгоритма ГОСТ 28147-89:

□ алгоритма GOST-H, в котором, относительно оригинального алгоритма, изменен порядок использования подключей, а именно в раундах с 25-го по 32-й подключи используются в прямом порядке, т. е. точно так же, как и в предыдущих раундах алгоритма;

□ 20-раундового алгоритма GOST®, в раунде которого для наложения клю­ча используется операция XOR вместо сложения по модулю 2 32 .

По результатам анализа сделан вывод о том, что GOST-H и GOST© слабее исходного алгоритма ГОСТ 28147-89, поскольку оба имеют классы слабых ключей. Стоит отметить, что в части криптоанализа GOST© работа слово в слово повторяет раздел, посвященный криптоанализу алгоритма ГОСТ 28147-89, вышедшей в 2000 г. известной работы (без каких-либо ссылок на оригинал). Это ставит под сомнение профессионализм авторов ра­боты и остальные ее результаты.

Весьма интересная модификация алгоритма предложена в работе : таб­лицы S\…Ss обязательно должны быть различными; в каждом раунде алго­ритма должна выполняться их перестановка по определенному закону. Дан­ная перестановка может быть зависимой от ключа шифрования, а может быть и секретной (т. е. являться частью ключа шифрования большего размера по сравнению с исходным 256-битным ключом). Оба этих варианта, по мнению их авторов, существенно усиливают стойкость алгоритма против линейного и дифференциального криптоанализа.

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

Анализ полнораундового алгоритма

Существуют атаки и на полнораундовый ГОСТ 28147-89 без каких-либо мо­дификаций. Одна из первых открытых работ, в которых был проведен анализ алгоритма,— широко известная работа — посвящена атакам, исполь­зующим слабости процедуры расширения ключа ряда известных алгоритмов шифрования. В частности, полнораундовый алгоритм ГОСТ 28147-89 может быть вскрыт с помощью дифференциального криптоанализа на связанных ключах, но только в случае использования слабых таблиц замен. 24-раундовый вариант алгоритма (в котором отсутствуют первые 8 раундов) вскрывается аналогичным образом при любых таблицах замен, однако сильные таблицы замен (например, приведенная в ) делают такую атаку абсолютно непрак­тичной.

Отечественные ученые А. Г. Ростовцев и Е. Б. Маховенко в 2001 г. в работе предложили принципиально новый метод криптоанализа (по мнению авторов, существенно более эффективный, чем линейный и дифференциаль­ный криптоанализ ) путем формирования целевой функции от известного открытого текста, соответствующего ему шифртекста и искомого значения ключа и нахождения ее экстремума, соответствующего истинному значению ключа. Они же нашли большой класс слабых ключей алгоритма ГОСТ 28147-89, которые позволяют вскрыть алгоритм с помощью всего 4-х выбранных от­крытых текстов и соответствующих им шифртекстов с достаточно низкой сложностью. Криптоанализ алгоритма продолжен в работе .

В 2004 г. группа специалистов из Кореи предложила атаку, с помощью кото­рой, используя дифференциальный криптоанализ на связанных ключах, мож­но получить с вероятностью 91,7 % 12 битов секретного ключа . Для атаки требуется 2 35 выбранных открытых текстов и 2 36 операций шифрова­ния. Как видно, данная атака, практически, бесполезна для реального вскры­тия алгоритма.

Краткое описание шифра

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

ГОСТ 28147-89 - блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Основа алгоритма шифра - Сеть Фейстеля. Базовым режимом шифрования по ГОСТ 28147-89 является режим простой замены (определены также более сложные режимы гаммирование, гаммирование с обратной связью и режим имитовставки).

Принцип работы алгоритма

Алгоритм принципиально не отличается от DES. В нем также происходят циклы шифрования (их 32) по схеме Фейстеля (Рис. 2.9.).

Рис. 2.9. Раунды шифрования алгоритма ГОСТ 28147-89.

Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: k 1 …k 8 . Ключи k 9 …k 24 являются циклическим повторением ключей k 1 …k 8 (нумеруются от младших битов к старшим). Ключи k 25 …k 32 являются ключами k 1 …k 8 , идущими в обратном порядке.

После выполнения всех 32 раундов алгоритма, блоки A 33 и B 33 склеиваются (следует обратить внимание на то, что старшим битом становится A 33 , а младшим - B 33) – результат есть результат работы алгоритма.

Функция f (A i ,K i ) вычисляется следующим образом: A i и K i складываются по модулю 2 32 , затем результат разбивается на восемь 4-битовых подпоследовательностей, каждая из которых поступает на вход своего узла таблицы замен (в порядке возрастания старшинства битов), называемого ниже S-блоком . Общее количество S-блоков ГОСТа - восемь, т. е. столько же, сколько и подпоследовательностей. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Первая 4-битная подпоследовательность попадает на вход первого S-блока, вторая - на вход второго и т. д. Выходы всех восьми S-блоков объединяются в 32-битное слово, затем всё слово циклически сдвигается влево (к старшим разрядам) на 11 битов. Все восемь S-блоков могут быть различными. Фактически, они могут являться дополнительным ключевым материалом, но чаще являются параметром схемы, общим для определенной группы пользователей. В тексте стандарта указывается, что поставка заполнения узлов замены (S-блоков) производится в установленном порядке, т.е. разработчиком алгоритма. Сообщество российских разработчиков СКЗИ согласовала используемые в Интернет узлы замены.

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

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

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

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

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

3. Режим гаммирования с обратной связью также принимает на вход данные любого размера и синхропосылку. Блок входных данных поразрядно складывается по модулю 2 с результатом преобразования в цикле «32-З» синхропосылки. Полученное значение подаётся на выход. Значение синхропосылки заменяется в случае зашифрования выходным блоком, а в случае расшифрования - входным, то есть зашифрованным. Если последний блок входящих данных меньше 64 разрядов, то лишние разряды гаммы (выхода цикла «32-З») отбрасываются. Если ещё имеются входящие данные, то действие повторяется: из результата зашифрования заменённого значения образуется гамма шифра и т.д.

4. Режим выработки имитовставки принимает на вход данные, размер которых составляет не меньше двух полных 64-разрядных блоков, а возвращает 64-разрядный блок данных, называемый имитовставкой. Временное 64-битовое значение устанавливается в 0, далее, пока имеются входные данные, оно поразрядно складывается по модулю 2 с результатом выполнения цикла «16-З», на вход которого подаётся блок входных данных. После окончания входных данных временное значение возвращается как результат.

Криптоанализ шифра

В шифре ГОСТ 28147-89 используется 256-битовый ключ и объем ключевого пространства составляет 2 256 . Ни на одном из существующих в настоящее время компьютере общего применения нельзя подобрать ключ за время, меньшее многих сотен лет. Российский стандарт ГОСТ 28147-89 проектировался с большим запасом и по стойкости на много порядков превосходит американский стандарт DES с его реальным размером ключа в 56 бит и объемом ключевого пространства всего 2 56 .

Существуют атаки и на полнораундовый ГОСТ 28147-89 без каких-либо модификаций. Одна из первых открытых работ, в которых был проведен анализ алгоритма, использует слабости процедуры расширения ключа ряда известных алгоритмов шифрования. В частности, полнораундовый алгоритм ГОСТ 28147-89 может быть вскрыт с помощью дифференциального криптоанализа на связанных ключах, но только в случае использования слабых таблиц замен. 24-раундовый вариант алгоритма (в котором отсутствуют первые 8 раундов) вскрывается аналогичным образом при любых таблицах замен, однако, сильные таблицы замен делают такую атаку абсолютно непрактичной.

Отечественные ученые А.Г. Ростовцев и Е.Б. Маховенко в 2001 г. предложили принципиально новый метод криптоанализа путем формирования целевой функции от известного открытого текста, соответствующего ему шифртекста и искомого значения ключа и нахождения ее экстремума, соответствующего истинному значению ключа. Они же нашли большой класс слабых ключей алгоритма ГОСТ 28147-89, которые позволяют вскрыть алгоритм с помощью всего 4-х выбранных открытых текстов и соответствующих им шифротекстов с достаточно низкой сложностью.

В 2004 году группа специалистов из Кореи предложила атаку, с помощью которой, используя дифференциальный криптоанализ на связанных ключах, можно получить с вероятностью 91,7% 12 бит секретного ключа. Для атаки требуется 2 35 выбранных открытых текстов и 2 36 операций шифрования. Как видно, данная атака практически бесполезна для реального вскрытия алгоритма.

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

Известный исследователь, основоположник алгебраического криптоанализа Николя Куртуа утверждает, что блочный шифр ГОСТ, который в ближайшее время должен был стать международным стандартом, фактически взломан и ожидает в дальнейшем множества публикаций, которые должны развить его идеи о нестойкости этого алгоритма.

Далее приведены краткие выдержки из этой работы, которую можно рассматривать как алармистский выпад в разгаре международной стандартизации (схожими преувеличениями автор был известен и в отношении AES, однако его работы тогда оказали большое теоретическое влияние на криптоанализ, но так и не привели на сегодняшний момент к практическим атакам на сам AES). Но, возможно, это и реальное предупреждение о начале этапа "пикирующего в штопор самолёта", которое может закончиться крахом национального стандарта шифрования, как это было с алгоритмом хэширования SHA-1 и алгоритмом хэширования "де-факто" MD5.

ГОСТ 28147-89 был стандартизирован в 1989 году и впервые стал официальным стандартом защиты конфиденциальной информации, но спецификация шифра оставалась закрытой. В 1994 году стандарт был рассекречен, опубликован и переведён на английский язык. По аналогии с AES (и в отличие от DES), ГОСТ допущен к защите секретной информации без ограничений, в соответствии с тем, как это указано в российском стандарте. Т.о. ГОСТ — это не аналог DES, а конкурент 3-DES с тремя независимыми ключами или AES-256. Очевидно, что ГОСТ — это достаточно серьёзный шифр, удовлетворяющий военным критериям, созданный с расчётом на самые серьёзные применения. По крайней мере два набора S-блоков ГОСТа были идентифицированы на основе приложений, используемых российскими банками. Эти банки нуждаются в проведении секретных коммуникаций с сотнями филиалов и защите миллиардов долларов от мошеннических хищений.

ГОСТ — это блочный шифр с простой структурой Файстеля, с размером блока 64 бита, 256-битным ключом и 32 раундами. Каждый раунд содержит сложение с ключом по модулю 2^32, набор из восьми 4-битных S-блоков и простой циклический сдвиг на 11 битов. Особенностью ГОСТа является возможность хранения S-блоков в секрете, что можно представить как второй ключ, увеличивающий эффективный ключевой материал до 610 битов. Один набор S-блоков был опубликован в 1994 году в рамках спецификации хэш-функции ГОСТ-Р 34.11-94 и, как писал Шнайер, использовался Центральным Банком Российской Федерации. Он также вошёл в стандарт RFC4357 в части "id-GostR3411-94-CryptoProParamSet". В исходных кодах в конце книги Шнайера была ошибка (в порядке S-блоков). Наиболее точную эталонную реализацию исконно российского происхождения сейчас можно встретить в библиотеке OpenSSL. Если где-то применяются секретные S-блоки, то они могут быть извлечены из программных реализаций и из микросхем, по факту чего были опубликованы соответствующие работы.

ГОСТ — серьёзный конкурент

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

Неудивительно, что ГОСТ стал интернет-стандартом, в частности, он включён во многие криптобиблиотеки, такие как OpenSSL и Crypto++, и становится всё популярнее за пределами страны своего происхождения. В 2010 году ГОСТ был заявлен на стандартизацию ISO как всемирный стандарт шифрования. Крайне малое количество алгоритмов смогли стать международными стандартами. ISO/IEC 18033-3:2010 описывает следующие алгоритмы: четыре 64-битных шифра — TDEA, MISTY1, CAST-128, HIGHT — и три 128-битных шифра — AES, Camellia, SEED. ГОСТ предлагается добавить в этот же самый стандарт ISO/IEC 18033-3.

Впервые в истории промышленной стандартизации мы имеем дело со столь конкурентоспособным алгоритмом в терминах оптимальности между стоимостью и уровнем безопасности. ГОСТ имеет за собой 20 лет попыток криптоанализа и до недавних пор его безопасность военного уровня не подвергалась сомнению.

Как стало недавно известно автору из приватной переписки, большинство стран высказались против ГОСТа на голосовании ISO в Сингапуре, однако результаты этого голосования будут ещё рассматриваться на пленарном заседании ISO SC27, так что ГОСТ всё ещё находится в процессе стандартизации на момент публикации этой работы.

Мнения экспертов по поводу ГОСТ

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

Все, кому знаком закон Мура, понимают, что, в теории, 256-битные ключи останутся безопасными по крайней мере 200 лет. ГОСТ был широко исследован ведущими экспертами в области криптографии, известными в области анализа блочных шифров, такими как Шнайер, Бирюков, Данкельман, Вагнер, множеством австралийских, японских и российских учёных, экспертами по криптографии от ISO, и все исследователи высказывались, что всё выглядит так, что он он может быть или должен быть безопасным. Хотя широкого понимания достигло мнение, что сама по себе структура ГОСТа крайне слаба, например, по сравнению с DES, в частности, диффузия не настолько хороша, однако это всегда обуславливалось тем, что это должно компенсироваться большим числом раундов (32), а также дополнительной нелинейностью и диффузией, обеспечиваемой сложением по модулю.

Бирюков и Вагнер писали: "Большое число раундов (32) и хорошо изученная конструкция Фейстеля, сочетаемая с последовательными Шенноновскими подстановками-перестановками, обеспечивают солидную основу безопасности ГОСТ". В той же самой работе мы читаем: "после значительных затрат времени и усилий, никакого прогресса в криптоанализе стандарта в открытой литературе достигнуто не было". Таким образом, не было никаких существенных атак, которые позволяли бы дешифрование или восстановление ключа в реалистичном сценарии, когда ГОСТ используется в шифровании со множеством разных случайных ключей. В противоположность этому, известно очень много работ по атакам на слабые ключи в ГОСТ, атаки со связанными ключами, атаки на восстановление секретных S-блоков. На Crypto-2008 был представлен взлом хэш-функции, основанной на этом шифре. Во всех атаках атакующий имеет значительно больший уровень свободы, чем ему обычно допускается. В традиционных применениях шифрования с использованием случайно выбираемых ключей до настоящего момента никаких серьёзных криптографических атак на ГОСТ найдено не было, что в 2010 году выражалось итоговой фразой: "несмотря на существенные усилия криптоаналитиков за прошедшие 20 лет, ГОСТ всё ещё не взломан" (Axel Poschmann, San Ling, and Huaxiong Wang: 256 Bit Standardized Crypto for 650 GE GOST Revisited, In CHES 2010, LNCS 6225, pp. 219-233, 2010).

Линейный и дифференциальный анализ ГОСТ

В широкоизвестной книге Шнайера мы читаем: "Против дифференциального и линейного криптоанализа ГОСТ вероятно более устойчив, чем DES". Основную оценку безопасности ГОСТа дали в 2000 году Габидулин и др. Их результаты очень впечатляющи: при заложенном уровне безопасности 2^256, достаточно пяти раундов для защиты ГОСТа от линейного криптоанализа. Более того, даже при замене S-блоков на тождественные и единственной нелинейной операции шифра — сложения по модулю 2^32 — шифр всё равно стоек против линейного криптоанализа после 6 раундов из 32. Дифференциальный криптоанализ ГОСТа выглядит сравнительно более лёгким и привлекает больше внимания. Для 2^128 уровня безопасности исследователи (Vitaly V. Shorin, Vadim V. Jelezniakov and Ernst M. Gabidulin: Linear and Differential Cryptanalysis of Russian GOST, Preprint submitted to Elsevier Preprint, 4 April 2001) предполагали достаточную стойкость на уровне 7 раундов. По их утверждению, взлом ГОСТа более чем на пяти раундах "крайне труден". Более того, двое японских исследователей показали, что классическая прямая дифференциальная атака с одной дифференциальной характеристикой имеет крайне малую вероятность для прохождения через большое число раундов. На основе факта изучения достаточно "хорошей" итеративной дифференциальной характеристики для ограниченного числа раундов (которая сама по себе имеет вероятность прохождения не лучше 2-11.4 на раунд), получено значения множества подходящих ключей менее половины. Для полнораундового ГОСТа такая атака с единственной характеристикой будет работать лишь с ничтожно малой частью ключей порядка 2-62 (и даже в этой малой части она будет иметь вероятность прохождения не более 2-360).

Более сложные атаки включают множества дифференциалов, следующих определённым паттернам, например с использованием отдельных S-блоков, имеющих нулевые дифференциалы, в то время как на других битах имеются ненулевые. Речь об атаках-различителях, основанных на плохих диффузионных свойствах ГОСТа. Лучшая из таких атак работает против 17 раундов ГОСТа, зависит от ключа и имеет сама по себе на выходе крайне слабый различитель от случайных данных, чтобы его как-то можно было использовать для получения информации о ключе.

Атаки скольжения и отражения

Согласно Бирюкову и Вагнеру, структура ГОСТа, включающая обратный порядок подключей в последних раундах, делает его стойким против атак скольжения (т.н. "слайд-атаки"). Однако из-за наличия большой величины самоподобия в шифре, это позволяет проводить атаки инверсии ключей на комбинации неподвижных точек и свойства "отражения" (т.н. "рефлективные атаки") для определённых слабых ключей. Сложность этой атаки 2^192 и 2^32 подобранных открытых текстов.

Последние результаты

Новые атаки также используют отражение и фактически взломали ГОСТ, что и было представлено на конференции FSE 2011. Эти атаки также были открыты независимо автором данной работы. Атака требует 2^132 байтов памяти, что фактически хуже, чем более медленные атаки с меньшим требованием к памяти.

Множество новых атак на основе самоподобия работают против всех ключей ГОСТа и позволяют взламывать полнораундовый ГОСТ с 256-битным ключом, а не только для слабых ключей, как было ранее. Все эти атаки требуют значительно меньше памяти и они значительно быстрее.

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

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

Алгебраические атаки на блочные и потоковые шифры могут быть представлены в виде проблемы решения большой системы Булевых алгебраических уравнений, которая следует геометрии и структуре частной криптографической схемы. Сама идея восходит к Шеннону. На практике была представлена для DES (впервые представлена автором данной работы) как метод формального кодирования и может взламывать 6 раундов всего на одном известном открытом тексте. Манипуляция с уравнениями происходит на основе алгоритмов XL, базисов Грёбнера, метода ElimLin, SAT-решателей.

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

Как взломать ГОСТ?

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

Практический результат пока скромен: 2^64 известных открытых текста и 2^64 памяти для хранения пар "открытый текст/шифртекст" позволяют взломать ГОСТ в 2^8 быстрее, чем простой перебор. Но в плане криптоанализа это делает полностью справедливым утверждение о том, что "ГОСТ взломан".

Выводы

ГОСТ спроектирован на обеспечение военного уровня безопасности на 200 лет вперёд. Большинство ведущих экспертов, изучавших ГОСТ, приходили к соглашению о том, что "несмотря на значительные криптоаналитические усилия на протяжении 20 лет, ГОСТ всё ещё не взломан". В 2010 году ГОСТ продвигают в ISO 18033 в качестве мирового стандарта шифрования.

Основа идей об алгебраическом криптоанализе возникла более 60 лет назад. Но только лишь за последние 10 лет были разработаны эффективные программные средства (частичного) решения множества NP-полных проблем. Было взломано некоторое число потоковых шифров. Только один блочный шифр был взломан этим методом — сам по себе слабый KeeLoq. В этой работе автор взламывает важный, реально используемый шифр ГОСТ. Он отмечает, что это первый случай в истории, когда алгебраическим криптоанализом был взломан стандартизированный государственный шифр.

Простая атака "MITM с отражением" на ГОСТ уже представлена на конференции FSE 2011. В работе же, рассматриваемой в данной статье, представлена другая атака лишь для иллюстрации факта того, как много атак на ГОСТ уже появилось сейчас, многие из которых быстрее, а сама алгебраическая атака требует намного меньше памяти и открывает практически неисчерпаемое пространство возможностей для противника, атакующего шифр разными способами. Также в данной работе показано отсутствие необходимости использования свойства отражения для взлома.

Автор утверждает: очевидно, что ГОСТ имеет серьёзные изъяны и теперь не обеспечивает уровня стойкости, требуемого ISO. Множество атак на ГОСТ представлено в рамках подтверждения парадигмы редуцирования алгебраической сложности.

Напоследок исследователь особенно отмечает некоторые факты, которые пока недоступны читателю, но известны исследователю, являющиеся важными в ходе процесса стандартизации ISO. Данная атака — не просто "сертификационная" атака на ГОСТ, которая быстрее перебора грубой силой. Фактически, стандартизация ГОСТа сейчас была бы крайне опасной и безответственной. Это так потому, что некоторые из атак возможны к осуществлению на практике. Некоторые ключи ГОСТа на практике даже могут быть дешифрованы, будь они слабые ключи или ключи из частных реальных применений ГОСТа. В предыдущей работе автор приводит детальное рассмотрение случаев возможности практических атак. Важно также то, что "это первый случай в истории, когда серьёзный стандартизированный блочный шифр, созданный для защиты секретов военного уровня и предназначенный для защиты документов государственной тайны для правительств, крупных банков и других организаций, оказался взломан математической атакой".

Алгоритм шифрования ГОСТ 28147-89, его использование и программная реализация для компьютеров платформы Intel x86.

Андрей Винокуров

Описание алгоритма.

Термины и обозначения.

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

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

Элементы данных в данной статье обозначаются заглавными латинскими буквами с наклонным начертанием (например, X ). Через |X | обозначается размер элемента данных X в битах. Таким образом, если интерпретировать элемент данных X как целое неотрицательное число, можно записать следующее неравенство:.

Если элемент данных состоит из нескольких элементов меньшего размера, то этот факт обозначается следующим образом: X =(X 0 ,X 1 ,…,X n –1)=X 0 ||X 1 ||…||X n –1 . Процедура объединения нескольких элементов данных в один называется конкатенацией данных и обозначается символом «||». Естественно, для размеров элементов данных должно выполняться следующее соотношение: |X |=|X 0 |+|X 1 |+…+|X n -1 |. При задании сложных элементов данных и операции конкатенации составляющие элементы данных перечисляются в порядке возрастания старшинства. Иными словами, если интерпретировать составной элемент и все входящие в него элементы данных как целые числа без знака, то можно записать следующее равенство:

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

X =(x 0 ,x 1 ,…,x n –1)=x 0 +2 1 ·x 1 +…+2 n –1 ·x n –1 .

Таким образом, если вы обратили внимание, для ГОСТа принята т.н. «little-endian» нумерация разрядов, т.е. внутри многоразрядных слов данных отдельные двоичные разряды и их группы с меньшими номерами являются менее значимыми. Об этом прямо говорится в пункте 1.3 стандарта: «При сложении и циклическом сдвиге двоичных векторов старшими разрядами считаются разряды накопителей с большими номерами». Далее, пункты стандарта 1.4, 2.1.1 и другие предписывают начинать заполнение данными регистров-накопителей виртуального шифрующего устройства с младших, т.е. менее значимых разрядов. Точно такой же порядок нумерации принят в микропроцессорной архитектуре Intel x86, именно поэтому при программной реализации шифра на данной архитектуре никаких дополнительных перестановок разрядов внутри слов данных не требуется.

Если над элементами данных выполняется некоторая операция, имеющая логический смысл, то предполагается, что данная операция выполняется над соответствующими битами элементов. Иными словами A B =(a 0 b 0 ,a 1 b 1 ,…,a n –1 b n –1), где n =|A |=|B |, а символом « » обозначается произвольная бинарная логическая операция; как правило, имеется в виду операция исключающего или , она же – операция суммирования по модулю 2:

Логика построения шифра и структура ключевой информации ГОСТа.

Если внимательно изучить оригинал ГОСТ 28147–89, можно заметить, что в нем содержится описание алгоритмов нескольких уровней. На самом верхнем находятся практические алгоритмы, предназначенные для шифрования массивов данных и выработки для них имитовставки. Все они опираются на три алгоритма низшего уровня, называемые в тексте ГОСТа циклами . Эти фундаментальные алгоритмы упоминаются в данной статье как базовые циклы , чтобы отличать их от всех прочих циклов. Они имеют следующие названия и обозначения, последние приведены в скобках и смысл их будет объяснен позже:

• цикл зашифрования (32-З);
• цикл расшифрования (32-Р);
• цикл выработки имитовставки (16-З).

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

Таким образом, чтобы разобраться в ГОСТе, надо понять три следующие вещи:

• что такое основной шаг криптопреобразования;
• как из основных шагов складываются базовые циклы;
• как из трех базовых циклов складываются все практические алгоритмы ГОСТа.

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

Основной шаг криптопреобразования.

Основной шаг криптопреобразования по своей сути является оператором, определяющим преобразование 64-битового блока данных. Дополнительным параметром этого оператора является 32-битовый блок, в качестве которого используется какой-либо элемент ключа. Схема алгоритма основного шага приведена на рисунке 1.

Рисунок 1. Схема основного шага криптопреобразования алгоритма ГОСТ 28147-89.

Ниже даны пояснения к алгоритму основного шага:

Шаг 0

• N – преобразуемый 64-битовый блок данных, в ходе выполнения шага его младшая (N 1) и старшая (N 2) части обрабатываются как отдельные 32-битовые целые числа без знака. Таким образом, можно записать N= (N 1 ,N 2).
• X – 32-битовый элемент ключа;

Шаг 1

Сложение с ключом. Младшая половина преобразуемого блока складывается по модулю 2 32 с используемым на шаге элементом ключа, результат передается на следующий шаг;

Шаг 2

Поблочная замена. 32-битовое значение, полученное на предыдущем шаге, интерпретируется как массив из восьми 4-битовых блоков кода: S= (S 0 , S 1 , S 2 , S 3 , S 4 , S 5 , S 6 , S 7), причем S 0 содержит 4 самых младших, а S 7 – 4 самых старших бита S .

Далее значение каждого из восьми блоков заменяется новым, которое выбирается по таблице замен следующим образом: значение блока S i меняется на S i -тый по порядку элемент (нумерация с нуля) i -того узла замены (т.е. i -той строки таблицы замен, нумерация также с нуля). Другими словами, в качестве замены для значения блока выбирается элемент из таблицы замен с номером строки, равным номеру заменяемого блока, и номером столбца, равным значению заменяемого блока как 4-битового целого неотрицательного числа. Отсюда становится понятным размер таблицы замен: число строк в ней равно числу 4-битовых элементов в 32-битовом блоке данных, то есть восьми, а число столбцов равно числу различных значений 4-битового блока данных, равному как известно 2 4 , шестнадцати.

Шаг 3

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

Шаг 4

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

Шаг 5

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

Шаг 6

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

Базовые циклы криптографических преобразований.

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

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

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

Цикл зашифрования 32-З:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 .

Рисунок 2а. Схема цикла зашифрования 32-З

Цикл расшифрования 32-Р:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 .

Рисунок 2б. Схема цикла расшифрования 32-Р

Цикл выработки имитовставки 16-З:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 .

Рисунок 2в. Схема цикла выработки имитовставки 16-З.

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

Цикл расшифрования должен быть обратным циклу зашифрования, то есть последовательное применение этих двух циклов к произвольному блоку должно дать в итоге исходный блок, что отражается следующим соотношением: Ц 32-Р (Ц 32-З (T ))=T , где T – произвольный 64-битовый блок данных, Ц X (T ) – результат выполнения цикла X над блоком данных T . Для выполнения этого условия для алгоритмов, подобных ГОСТу, необходимо и достаточно, чтобы порядок использования ключевых элементов соответствующими циклами был взаимно обратным. В справедливости записанного условия для рассматриваемого случая легко убедиться, сравнив приведенные выше последовательности для циклов 32-З и 32-Р. Из сказанного вытекает одно интересное следствие: свойство цикла быть обратным другому циклу является взаимным, то есть цикл 32-З является обратным по отношению к циклу 32-Р. Другими словами, зашифрование блока данных теоретически может быть выполнено с помощью цикла расшифрования, в этом случае расшифрование блока данных должно быть выполнено циклом зашифрования. Из двух взаимно обратных циклов любой может быть использован для зашифрования, тогда второй должен быть использован для расшифрования данных, однако стандарт ГОСТ28147-89 закрепляет роли за циклами и не предоставляет пользователю права выбора в этом вопросе.

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

Схемы базовых циклов приведены на рисунках 2а-в. Каждый из них принимает в качестве аргумента и возвращает в качестве результата 64-битовый блок данных, обозначенный на схемах N . Символ Шаг(N ,X ) обозначает выполнение основного шага криптопреобразования для блока данных N с использованием ключевого элемента X . Между циклами шифрования и вычисления имитовставки есть еще одно отличие, не упомянутое выше: в конце базовых циклов шифрования старшая и младшая часть блока результата меняются местами, это необходимо для их взаимной обратимости.

Основные режимы шифрования.

ГОСТ 28147-89 предусматривает три следующих режима шифрования данных:

• простая замена,
• гаммирование,
• гаммирование с обратной связью,

и один дополнительный режим выработки имитовставки.

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

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

T о,T ш – массивы соответственно открытых и зашифрованных данных;

, – i - тые по порядку 64-битовые блоки соответственно открытых и зашифрованных данных:, , последний блок может быть неполным: ;

n – число 64-битовых блоков в массиве данных;

Ц X – функция преобразования 64-битового блока данных по алгоритму базового цикла «X».

Теперь опишем основные режимы шифрования:

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

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

Рисунок. 3а. Алгоритм зашифрования данных в режиме простой замены

Рисунок. 3б. Алгоритм расшифрования данных в режиме простой замены

Размер массива открытых или зашифрованных данных, подвергающийся соответственно зашифрованию или расшифрованию, должен быть кратен 64 битам: | T о |=| T ш |=64· n , после выполнения операции размер полученного массива данных не изменяется.

Режим шифрования простой заменой имеет следующие особенности:

• Так как блоки данных шифруются независимо друг от друга и от их позиции в массиве данных, при зашифровании двух одинаковых блоков открытого текста получаются одинаковые блоки шифртекста и наоборот. Отмеченное свойство позволит криптоаналитику сделать заключение о тождественности блоков исходных данных, если в массиве зашифрованных данных ему встретились идентичные блоки, что является недопустимым для серьезного шифра.
• Если длина шифруемого массива данных не кратна 8 байтам или 64 битам, возникает проблема, чем и как дополнять последний неполный блок данных массива до полных 64 бит. Эта задача не так проста, как кажется на первый взгляд. Очевидные решения типа «дополнить неполный блок нулевыми битами» или, более обще, «дополнить неполный блок фиксированной комбинацией нулевых и единичных битов» могут при определенных условиях дать в руки криптоаналитика возможность методами перебора определить содержимое этого самого неполного блока, и этот факт означает снижение стойкости шифра. Кроме того, длина шифртекста при этом изменится, увеличившись до ближайшего целого, кратного 64 битам, что часто бывает нежелательным.

На первый взгляд, перечисленные выше особенности делают практически невозможным использование режима простой замены, ведь он может применяться только для шифрования массивов данных с размером кратным 64 битам, не содержащим повторяющихся 64-битовых блоков. Кажется, что для любых реальных данных гарантировать выполнение указанных условий невозможно. Это почти так, но есть одно очень важное исключение: вспомните, что размер ключа составляет 32 байта, а размер таблицы замен – 64 байта. Кроме того, наличие повторяющихся 8-байтовых блоков в ключе или таблице замен будет говорить об их весьма плохом качестве, поэтому в реальных ключевых элементах такого повторения быть не может. Таким образом, мы выяснили, что режим простой замены вполне подходит для шифрования ключевой информации, тем более, что прочие режимы для этой цели менее удобны, поскольку требуют наличия дополнительного синхронизирующего элемента данных – синхропосылки (см. следующий раздел). Наша догадка верна, ГОСТ предписывает использовать режим простой замены исключительно для шифрования ключевых данных.

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

Как же можно избавиться от недостатков режима простой замены? Для этого необходимо сделать возможным шифрование блоков с размером менее 64 бит и обеспечить зависимость блока шифртекста от его номера, иными словами, рандомизировать процесс шифрования. В ГОСТе это достигается двумя различными способами в двух режимах шифрования, предусматривающих гаммирование . Гаммирование – это наложение (снятие) на открытые (зашифрованные) данные криптографической гаммы, то есть последовательности элементов данных, вырабатываемых с помощью некоторого криптографического алгоритма, для получения зашифрованных (открытых) данных. Для наложения гаммы при зашифровании и ее снятия при расшифровании должны использоваться взаимно обратные бинарные операции, например, сложение и вычитание по модулю 2 64 для 64-битовых блоков данных. В ГОСТе для этой цели используется операция побитового сложения по модулю 2, поскольку она является обратной самой себе и, к тому же, наиболее просто реализуется аппаратно. Гаммирование решает обе упомянутые проблемы: во-первых, все элементы гаммы различны для реальных шифруемых массивов и, следовательно, результат зашифрования даже двух одинаковых блоков в одном массиве данных будет различным. Во-вторых, хотя элементы гаммы и вырабатываются одинаковыми порциями в 64 бита, использоваться может и часть такого блока с размером, равным размеру шифруемого блока.

Теперь перейдем непосредственно к описанию режима гаммирования. Гамма для этого режима получается следующим образом: с помощью некоторого алгоритмического рекуррентного генератора последовательности чисел (РГПЧ) вырабатываются 64-битовые блоки данных, которые далее подвергаются преобразованию по циклу 32-З, то есть зашифрованию в режиме простой замены, в результате получаются блоки гаммы. Благодаря тому, что наложение и снятие гаммы осуществляется при помощи одной и той же операции побитового исключающего или, алгоритмы зашифрования и расшифрования в режиме гаммирования идентичны, их общая схема приведена на рисунке 4.

РГПЧ, используемый для выработки гаммы, является рекуррентной функцией: – элементы рекуррентной последовательности, f – функция преобразования. Следовательно, неизбежно возникает вопрос о его инициализации, то есть об элементе В действительности, этот элемент данных является параметром алгоритма для режимов гаммирования, на схемах он обозначен как S , и называется в криптографии синхропосылкой , а в нашем ГОСТе – начальным заполнением одного из регистров шифрователя. По определенным соображениям разработчики ГОСТа решили использовать для инициализации РГПЧ не непосредственно синхропосылку, а результат ее преобразования по циклу 32-З: . Последовательность элементов, вырабатываемых РГПЧ, целиком зависит от его начального заполнения, то есть элементы этой последовательности являются функцией своего номера и начального заполнения РГПЧ: где f i (X )=f (f i –1 (X )), f 0 (X )=X . С учетом преобразования по алгоритму простой замены добавляется еще и зависимость от ключа:

где Г i – i -тый элемент гаммы, K – ключ.

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

Теперь подробно рассмотрим РГПЧ, используемый в ГОСТе для генерации элементов гаммы. Прежде всего, надо отметить, что к нему не предъявляются требования обеспечения каких-либо статистических характеристик вырабатываемой последовательности чисел. РГПЧ спроектирован разработчиками ГОСТа исходя из необходимости выполнения следующих условий:

• период повторения последовательности чисел, вырабатываемой РГПЧ, не должен сильно (в процентном отношении) отличаться от максимально возможного при заданном размере блока значения 2 64 ;
• соседние значения, вырабатываемые РГПЧ, должны отличаться друг от друга в каждом байте, иначе задача криптоаналитика будет упрощена;
• РГПЧ должен быть достаточно просто реализуем как аппаратно, так и программно на наиболее распространенных типах процессоров, большинство из которых, как известно, имеют разрядность 32 бита.

Исходя из перечисленных принципов, создатели ГОСТа спроектировали весьма удачный РГПЧ, имеющий следующие характеристики:

Где C 0 =1010101 16 ;

Где C 1 =1010104 16 ;

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

Второе выражение нуждается в комментариях, так как в тексте ГОСТа приведено нечто другое: , с тем же значением константы C 1 . Но далее в тексте стандарта дается комментарий, что, оказывается, под операцией взятия остатка по модулю 2 32 –1 там понимается не то же самое, что и в математике. Отличие заключается в том, что согласно ГОСТу (2 32 –1)mod (2 32 –1)=(2 32 –1), а не 0. На самом деле, это упрощает реализацию формулы, а математически корректное выражение для нее приведено выше.

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

Схема алгоритма шифрования в режиме гаммирования приведена на рисунке 4, ниже изложены пояснения к схеме:

Рисунок 4. Алгоритм зашифрования (расшифрования) данных в режиме гаммирования.

Шаг 0

Определяет исходные данные для основного шага криптопреобразования:

• T о(ш) – массив открытых (зашифрованных) данных произвольного размера, подвергаемый процедуре зашифрования (расшифрования), по ходу процедуры массив подвергается преобразованию порциями по 64 бита;
• S – синхропосылка , 64-битовый элемент данных, необходимый для инициализации генератора гаммы;

Шаг 1

Начальное преобразование синхропосылки, выполняемое для ее «рандомизации», то есть для устранения статистических закономерностей, присутствующих в ней, результат используется как начальное заполнение РГПЧ;

Шаг 2

Один шаг работы РГПЧ, реализующий его рекуррентный алгоритм. В ходе данного шага старшая (S 1) и младшая (S 0) части последовательности данных вырабатываются независимо друг от друга;

Шаг 3

Гаммирование. Очередной 64-битовый элемент, выработанный РГПЧ, подвергается процедуре зашифрования по циклу 32–З, результат используется как элемент гаммы для зашифрования (расшифрования) очередного блока открытых (зашифрованных) данных того же размера.

Шаг 4

Результат работы алгоритма – зашифрованный (расшифрованный) массив данных.

Ниже перечислены особенности гаммирования как режима шифрования:

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

• хранить или передавать синхропосылку вместе с зашифрованным массивом данных, что приведет к увеличению размера массива данных при зашифровании на размер синхропосылки, то есть на 8 байт;
• использовать предопределенное значение синхропосылки или вырабатывать ее синхронно источником и приемником по определенному закону, в этом случае изменение размера передаваемого или хранимого массива данных отсутствует;

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

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

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

где обозначает инвертированное по отношению к t значение бита ().

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

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

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

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

Рисунок 5. Алгоритм зашифрования (расшифрования) данных в режиме гаммирования с обратной связью.

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

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

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

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

Выработка имитовставки к массиву данных.

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

Для решения задачи обнаружения искажений в зашифрованном массиве данных с заданной вероятностью в ГОСТе предусмотрен дополнительный режим криптографического преобразования – выработка имитовставки. Имитовставка – это контрольная комбинация, зависящая от открытых данных и секретной ключевой информации. Целью использования имитовставки является обнаружение всех случайных или преднамеренных изменений в массиве информации. Проблема, изложенная в предыдущем пункте, может быть успешно решена с помощью добавления к шифрованным данным имитовставки. Для потенциального злоумышленника две следующие задачи практически неразрешимы, если он не владеет ключом:

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

Схема алгоритма выработки имитовставки приведена на рисунке 6.

Рисунок 6. Алгоритм выработки имитовставки для массива данных.

В качестве имитовставки берется часть блока, полученного на выходе, обычно – 32 его младших бита. При выборе размера имитовставки надо принимать во внимание, что вероятность успешного навязывания ложных данных равна величине 2 –| I | на одну попытку подбора, если в распоряжении злоумышленника нет более эффективного метода подбора, чем простое угадывание. При использовании имитовставки размером 32 бита эта вероятность равна

Обсуждение криптографических алгоритмов ГОСТа.

Криптографическая стойкость ГОСТа.

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

• можно ли вообще раскрыть данный шифр;
• если да, то насколько это трудно сделать практически;

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

Все современные криптосистемы построены по принципу Кирхгоффа, то есть секретность зашифрованных сообщений определяется секретностью ключа. Это значит, что даже если сам алгоритм шифрования известен криптоаналитику, тот, тем не менее, не в состоянии расшифровать сообщение, если не располагает соответствующим ключом. Шифр считается хорошо спроектированным, если нет способа вскрыть его более эффективным способом, чем полным перебором по всему ключевому пространству, т.е. по всем возможным значениям ключа. ГОСТ, вероятно, соответствует этому принципу – за годы интенсивных исследований не было предложено ни одного результативного способа его криптоанализа. В плане стойкости он на много порядков превосходит прежний американский стандарт шифрования, DES.

В ГОСТе используется 256-битовый ключ и объем ключевого пространства составляет 2 256 . Ни на одном из существующих в настоящее время или предполагаемых к реализации в недалеком будущем электронном устройстве нельзя подобрать ключ за время, меньшее многих сотен лет. Эта величина стала фактическим стандартом размера ключа для симметричных криптоалгоритмов в наши дни, – так, новый стандарт шифрования США также его поддерживает. Прежний же американский стандарт, DES с его реальным размером ключа в 56 бит и объемом ключевого пространства всего 2 56 уже не является достаточно стойким в свете возможностей современных вычислительных средств. Это было продемонстрировано в конце 90-х годов несколькими успешными попытками взлома DES переборным путем. Кроме того, DES оказался подвержен специальным способам криптоанализа, таким как дифференциальный и линейный. В этой связи DES может представлять скорее исследовательский или научный, чем практический интерес. В 1998 году его криптографическая слабость была признана официально, – национальный институт стандартов США рекомендовал использовать троекратное шифрование по DES. А в конце 2001 года был официально утвержден новый стандарт шифрования США, AES, построенный на иных принципах и свободный от недостатков своего предшественника .

Замечания по архитектуре ГОСТа.

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

Алгоритмы «основных шагов криптопреобразования» для шифров, подобных ГОСТу, построены идентичным образом, и эта архитектура называется сбалансированная сеть Файстеля (balanced Feistel network) по имени человека, впервые предложившего ее . Схема преобразования данных на одном цикле, или, как его принято называть, раунде , приведена на рисунке 7.

Рисунок 7. Содержание основного шага криптопреобразования для блочных шифров, подобных ГОСТу.

На вход основного шага подается блок четного размера, старшая и младшая половины которого обрабатываются отдельно друг от друга. В ходе преобразования младшая половина блока помещается на место старшей, а старшая, скомбинированная с помощью операции побитового « исключающего или » с результатом вычисления некоторой функции, на место младшей. Эта функция, принимающая в качестве аргумента младшую половину блока и элемент ключевой информации (X ), является содержательной частью шифра и называется его функцией шифрования . По разным соображениям оказалось выгодно разделить шифруемый блок на две одинаковые по размеру части: |N 1 |=|N 2 | – именно этот факт отражает слово «сбалансированная» в названии архитектуры. Впрочем, шифрующие несбалансированные сети также используются время от времени, хотя и не так часто, как сбалансированные. Кроме того, соображения стойкости шифра требуют, чтобы размер ключевого элемента не был меньше размера половины блока: в ГОСТе все три размера равны 32 битам.

Если применить сказанное к схеме основного шага алгоритма ГОСТ, станет очевидным, что блоки 1,2,3 алгоритма (см. рис. 1) определяют вычисление его функции шифрования, а блоки 4 и 5 задают формирование выходного блока основного шага исходя из содержимого входного блока и значения функции шифрования. Более подробно об архитектурах современных блочных шифров с секретным ключом можно прочитать в классических работах , или, в адаптированной форме, в моих работах .

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

Ни одна из рассмотренных автором реализаций DESа для платформы Intel x86 не достигает даже половины производительности предложенной вашему вниманию в настоящей статье реализации ГОСТа несмотря на вдвое более короткий цикл. Все сказанное выше свидетельствует о том, что разработчики ГОСТа учли как положительные, так и отрицательные стороны DESа, а также более реально оценили текущие и перспективные возможности криптоанализа. Впрочем, брать DES за основу при сравнении быстродействия реализаций шифров уже не актуально. У нового стандарта шифрования США дела с эффективностью обстоят гораздо лучше – при таком же как у ГОСТа размере ключа в 256 бит AES работает быстрее него примерно на 14% – это если сравнивать по числу «элементарных операций». Кроме того, ГОСТ практически не удается распараллелить, а у AES возможностей в этом плане намного больше. На некоторых архитектурах это преимущество AES может быть меньше, на других – больше. Так, на процессоре Intel Pentium оно достигает 28%. Подробности можно найти в .

Требования к качеству ключевой информации и источники ключей.

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

Исчерпывающий ответ на вопрос о критериях качества ключей и таблиц замен ГОСТа если и можно вообще где-либо получить, то только у разработчиков алгоритма. Соответствующие данные не были опубликованы в открытой печати. Однако согласно установленному порядку, для шифрования информации, имеющей гриф, должны быть использованы ключевые данные, полученные от уполномоченной организации. Косвенным образом это может свидетельствовать о наличии методик проверки ключевых данных на «вшивость». Если наличие слабых ключей в ГОСТе – дискуссионный вопрос, то наличие слабых узлов замены не вызывает сомнения. Очевидно, что «тривиальная» таблица замен, по которой любое значение заменяется им же самим, является настолько слабой, что при ее использовании шифр взламывается элементарно, каков бы ни был ключ.

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

Ключ

Ключ должен являться массивом статистически независимых битов, принимающих с равной вероятностью значения 0 и 1. Нельзя полностью исключить при этом, что некоторые конкретные значения ключа могут оказаться «слабыми», то есть шифр может не обеспечивать заданный уровень стойкости в случае их использования. Однако, предположительно, доля таких значений в общей массе всех возможных ключей ничтожно мала. По крайней мере, интенсивные исследования шифра до сих пор не выявили ни одного такого ключа ни для одной из известных (т.е. предложенных ФАПСИ) таблиц замен. Поэтому ключи, выработанные с помощью некоторого датчика истинно случайных чисел, будут качественными с вероятностью, отличающейся от единицы на ничтожно малую величину. Если же ключи вырабатываются с помощью генератора псевдослучайных чисел, то используемый генератор должен обеспечивать указанные выше статистические характеристики, и, кроме того, обладать высокой криптостойкостью, – не меньшей, чем у самого ГОСТа. Иными словами, задача определения отсутствующих членов вырабатываемой генератором последовательности элементов не должна быть проще, чем задача вскрытия шифра. Кроме того, для отбраковки ключей с плохими статистическими характеристиками могут быть использованы различные статистические критерии. На практике обычно хватает двух критериев, – для проверки равновероятного распределения битов ключа между значениями 0 и 1 обычно используется критерий Пирсона («хи квадрат»), а для проверки независимости битов ключа – критерий серий. Об упомянутых критериях можно прочитать в учебниках или справочниках по математической статистике.

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

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

Таблица замен

Таблица замен является долговременным ключевым элементом, то есть действует в течение гораздо более длительного срока, чем отдельный ключ. Предполагается, что она является общей для всех узлов шифрования в рамках одной системы криптографической защиты. Даже при нарушении конфиденциальности таблицы замен стойкость шифра остается чрезвычайно высокой и не снижается ниже допустимого предела. Поэтому нет особой нужды держать таблицу в секрете, и в большинстве коммерческих применений ГОСТа так оно и делается. С другой стороны, таблица замен является критически важным элементом для обеспечения стойкости всего шифра. Выбор ненадлежащей таблицы может привести к тому, что шифр будет легко вскрываться известными методами криптоанализа. Критерии выработки узлов замен – тайна за семью печатями и ФАПСИ вряд ли ей поделится с общественностью в ближайшем обозримом будущем. В конечном итоге, для того, чтобы сказать, является ли данная конкретная таблица замен хорошей или плохой, необходимо провести огромный объем работ – многие тысячи человеко- и машино-часов. Единожды выбранная и используемая таблица подлежит замене в том и только в том случае, если шифр с ее использованием оказался уязвимым к тому или иному виду криптоанализа. Поэтому лучшим выбором для рядового пользователя шифра будет взять одну из нескольких таблиц, ставших достоянием гласности. Например, из стандарта на хеш-функцию , она же «центробанковская» ; сведения об этих таблицах можно найти в открытой печати и даже в интернете, если хорошо поискать.

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

1. С помощью той или иной методики вырабатываете комплект из восьми узлов замен с гарантированными характеристиками нелинейности. Таких методик существует несколько, одна из них – использование так называемых бент-функций.
2. Проверяете выполнение простейших «критериев качества» – например, тех, что опубликованы для узлов замены DES. Вот еще несколько общих соображений на этот счет: Каждый узел замен может быть описан четверкой логических функций от четырех логических аргументов. Если эти функции, записанные в минимальной форме (т.е. с минимально возможной длиной выражения) окажутся недостаточно сложными, такой узел замены отвергается. Кроме того, отдельные функции в пределах всей таблицы замен должны отличаться друг от друга в достаточной степени. На этом этапе отсеиваются многие заведомо некачественные таблицы.
3. Для шифра с выбранными вами таблицами строите различные модели раунда, соответствующие разным видам криптоанализа, и измеряете соответствующие «профильные» характеристики. Так, для линейного криптоанализа строите линейный статистический аналог раунда шифрования и вычисляете «профильную» характеристику – показатель нелинейности. Если она оказывается недостаточной, таблица замен отвергается.
4. Наконец, используя результаты предыдущего пункта, подвергаете шифр с выбранной вами таблицей интенсивным исследованиям – попытке криптоанализа всеми известными методами. Именно этот этап является наиболее сложным и трудоемким. Но если он сделан качественно, то с высокой степенью вероятности можно констатировать, что шифр с выбранными вами таблицами не будет вскрыт простыми смертными, и, – не исключено, – окажется не по зубам спецслужбам.

Можно, однако, поступить гораздо проще. Все дело в том, что чем больше в шифре раундов, тем меньшее влияние на стойкость всего шифра имеют характеристики стойкости одного раунда. В ГОСТе аж 32 раунда – больше, чем практически во всех шифрах с аналогичной архитектурой. Поэтому для большинства бытовых и коммерческих применений бывает достаточно получить узлы замен как независимые случайные перестановки чисел от 0 до 15. Это может быть практически реализовано, например, с помощью перемешивания колоды из шестнадцати карт, за каждой из которых закреплено одно из значений указанного диапазона.

Относительно таблицы замен необходимо отметить еще один интересный факт. Для обратимости циклов шифрования «32-З» и «32-Р» не требуется, чтобы узлы замен были перестановками чисел от 0 до 15. Все работает даже в том случае, если в узле замен есть повторяющиеся элементы, и замена, определяемая таким узлом, необратима, – однако в этом случае снижается стойкость шифра. Почему это именно так, не рассматривается в настоящей статье, однако в самом факте убедиться несложно. Для этого достаточно попытаться сначала зашифровать, а затем расшифровать блок данных, используя такую «неполноценную» таблицу замен, узлы которой содержат повторяющиеся значения.

Вариации на тему ГОСТа

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

Как поступить в этом и аналогичном ему случаях, чтобы увеличить быстродействие шифрования? Ответ лежит на поверхности – использовать модификацию шифра с меньшим количеством основных шагов (раундов) в базовых циклах. Во сколько раз мы уменьшаем число раундов шифрования, во столько же раз возрастает быстродействие. Указанного изменения можно достигнуть двумя путями, – уменьшением длины ключа и уменьшением числа «циклов просмотра» ключа. Вспомните, что число основных шагов в базовых циклах шифрования равно N =n·m , где n – число 32-битовых элементов в ключе, m – число циклов использования ключевых элементов, в стандарте n =8, m =4. Можно уменьшить любое из этих чисел, но простейший вариант – уменьшать длину ключа, не трогая схемы его использования.

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

Что касается устойчивости шифра к взлому «экстенсивными» методами, то есть к «переборной» атаке, тот тут все более или менее ясно: ключ размером 64 бита находится где-то на грани доступности этому виду атаки, шифр с ключом 96 бит и выше (помните, что ключ должен содержать целое число 32-битовых элементов) вполне устойчив против него. Действительно, несколько лет назад прежний стандарт шифрования США, DES, был неоднократно взломан переборным путем, – сначала его взломала вычислительная сеть, организованная на базе глобальной сети Интернет, а затем – специализированная, т.е. сконструированная специально для этого вычислительная машина. Примем, что стандартный вариант ГОСТа при программной реализации на современных процессорах работает вчетверо быстрее DES. Тогда 8-раундовый «редуцированный ГОСТ» будет работать в 16 раз быстрее DES. Примем также, что за прошедшее с момента взлома DES время производительность вычислительной техники согласно закону Мура возросла вчетверо. Получаем в итоге, что сейчас проверка одного 64-битового ключа для «редуцированного ГОСТа» с восемью циклами осуществляется в 64 раза быстрее, чем в свое время выполнялась проверка одного ключа DES. Таким образом, преимущество такого варианта ГОСТа перед DES по трудоемкости переборной атаки сокращается с 2 64–56 = 2 8 = 256 до 256/ 64 = 4 раз. Согласитесь, это весьма иллюзорное различие, почти что ничего.

Гораздо сложнее оценить устойчивость ослабленных модификаций ГОСТа к «интенсивным» способам криптоанализа. Однако общую закономерность можно проследить и здесь. Дело в том, что «профильные» характеристики многих наиболее сильных на сегодняшний момент видов криптоанализа зависят экспоненциально от числа раундов шифрования. Так, для линейного криптоанализа (ЛКА) это будет характеристика линейности L :

где C и – константы, R – число раундов. Аналогичная зависимость существует и для дифференциального криптоанализа. По своему «физическому смыслу» все характеристики такого рода – вероятности. Обычно объем необходимых для криптоанализа исходных данных и его трудоемкость обратно пропорциональны подобным характеристикам. Отсюда следует, что эти показатели трудоемкости растут экспоненциально с ростом числа основных шагов шифрования. Поэтому при снижении числа раундов в несколько раз трудоемкость наиболее известных видов анализа изменится как, – очень приблизительно и грубо, – корень этой степени из первоначального количества. Это очень большое падение стойкости.

С другой стороны, ГОСТ проектировался с большим запасом прочности и на сегодняшний день устойчив ко всем известным видам криптоанализа, включая дифференциальный и линейный. Применительно к ЛКА это означает, что для его успешного проведения требуется больше пар «открытый блок – зашифрованный блок», чем «существует в природе», то есть более 2 64 . С учетом сказанного выше это означает, что для успешного ЛКА 16-раундового ГОСТа потребуется не менее блоков или 2 35 байтов или 32 Гбайта данных, а для 8-раундового – не менее блоков или 2 19 байтов или 0.5 Мбайт.

Выводы из всего, сказанного выше, приведены в следующей таблице, обобщающей характеристики редуцированных вариантов ГОСТа.

Число раундов	Размер ключа, бит	Индекс быстро-действия	Вероятные характеристики шифра(очень грубая оценка)
24	192	1,33	Устойчив к большинству известных видов КА, или находиться на грани устойчивости. Практическая реализация КА невозможна из-за высоких требований к исходным данным и трудоемкости.
16	128	2	Теоретически неустойчив к некоторым видам криптоанализа, однако их практическая реализация в большинстве случаев затруднена из-за высоких требований к исходным данным и трудоемкости.
12	95	2,67	Неустойчив к некоторым известным видам криптоанализа, однако годится для обеспечения секретности небольших объемов данных (до десятков-сотен Кбайт) на короткий срок.
8	64	4	Неустойчив к некоторым известным видам криптоанализа, однако годится для обеспечения секретности небольших объемов данных (до десятков Кбайт) на короткий срок.

Два последних варианта, с 12 и 8 раундами, способны обеспечить весьма и весьма ограниченную во времени защиту. Их использование оправдано лишь в задачах, где требуется лишь краткосрочная секретность закрываемых данных, порядка нескольких часов. Возможная область применения этих слабых вариантов шифра – закрытие UDP-трафика электронных биржевых торговых систем. В этом случае каждый пакет данных (datagram, средняя «D» из аббревиатуры UDP) шифруется на отдельном 64-битовом ключе, а сам ключ шифруется на сеансовом ключе (ключе, область действия которого – один сеанс связи между двумя компьютерами) и передается вместе с данными.

Прежде чем закончить с редуцированными вариантами ГОСТа скажу, что все приведенные выше соображения носят в высшей степени спекулятивный характер. Стандарт обеспечивает стойкость только для одного, 32-раундового варианта. И никто не может дать вам гарантий, что устойчивость редуцированных вариантов шифра к взлому будет изменяться указанным выше образом. Если вы все же решились их использовать в своих разработках, помните, что вы ступили на весьма зыбкую почву, которая может в любой момент уйти из-под ваших ног. Коль скоро вопросы скорости шифрования являются для вас критическими, может, стоит подумать об использовании более быстрого шифра или более мощного компьютера? Еще одно соображение, по которому это стоит сделать, заключается в том, что ослабленные варианты ГОСТа будут максимально чувствительны к качеству используемых узлов замены.

У рассматриваемого вопроса есть и обратная сторона. Что если скорость шифрования некритична, а требования к стойкости весьма жестки? Повысить стойкость ГОСТа можно двумя путями – условно назовем их «экстенсивный» и «интенсивный». Первый из них – это ни что иное, как простое увеличение числа раундов шифрования. Мне не совсем понятно, зачем это может реально понадобиться, ведь отечественный стандарт и без этого обеспечивает необходимую стойкость. Впрочем, если вы страдаете паранойей больше необходимого уровня (а все «защитники информации» просто обязаны ею страдать, это условие профпригодности такое, вопрос только в степени тяжеcти случая:), это поможет вам несколько успокоиться. Если вы не уверены в этом КГБ-шном шифре или используемой вами таблице замен, просто удвойте, учетверите, и т.д. число раундов – кратность выберите исходя из тяжести вашего случая. Указанный подход позволяет реально увеличить стойкость шифра, – если раньше криптоанализ был просто невозможным, то теперь он невозможен в квадрате!

Более хитрым и интересным является вопрос, а можно ли увеличить стойкость шифра, не меняя количества и структуры основных шагов шифрования. Как ни удивительно, ответ на этот него положительный, хотя мы опять ступаем на зыбкую почву спекуляций. Дело в том, что в ГОСТе на основном шаге преобразования предполагается выполнение замены 4 на 4 бит, а на практике (речь об этом еще впереди) все программные реализации выполняют замену побайтно, т.е. 8 на 8 бит – так делается по соображениям эффективности. Если сразу спроектировать такую замену как 8-битовую, то мы существенно улучшим характеристики одного раунда. Во-первых, увеличится «диффузионная» характеристика или показатель «лавинности» – один бит исходных данных и/или ключа будет влиять на большее число бит результата. Во вторых, для больших по размеру узлов замены можно получить более низкие дифференциальную и линейную характеристики, уменьшив тем самым подверженность шифра одноименным видам криптоанализа. Особенно актуально это для редуцированных циклов ГОСТа, а для 8 и 12-раундовых вариантов такой шаг просто необходим. Это несколько скомпенсирует потерю стойкости в них от уменьшения числа раундов. Что затрудняет использование этого приема – так это то, что конструировать подобные «увеличенные» узлы замены вам придется самостоятельно. А также то, что более крупные узлы вообще конструировать заметно труднее, чем меньшие по размеру.

Нестандартное использование стандарта.

Безусловно, основное назначение криптоалгоритмов ГОСТ – это шифрование и имитозащита данных. Однако им можно найти и другие применения, связанные, естественно, с защитой информации. Коротко расскажем о них:

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

• Как уже отмечалось выше, гамму можно использовать как «сырье» для выработки ключей. Для этого нужно лишь получить отрезок гаммы нужной длины – 32 байта. Таким способом ключи можно изготавливать по мере необходимости и их не надо будет хранить, – если такой ключ понадобится повторно, будет достаточно легко его выработать снова. Надо только будет вспомнить, на каком ключе он был выработан исходно, какая использовалась синхропосылка и с какого байта выработанной гаммы начинался ключ. Вся информация, кроме использованного ключа, несекретна. Данный подход позволит легко контролировать достаточно сложную и разветвленную систему ключей, используя всего лишь один «мастер-ключ».
• Аналогично предыдущему, гамму можно использовать в качестве исходного «сырья» для выработки паролей. Тут может возникнуть вопрос, зачем вообще нужно их генерировать, не проще ли по мере надобности их просто выдумывать. Несостоятельность такого подхода была наглядно продемонстрирована серией инцидентов в компьютерных сетях, самым крупным из которых был суточный паралич интернета в ноябре 1988 года, вызванный «червем Морриса». Одним из способов проникновения злоумышленной программы на компьютер был подбор паролей: программа пыталась войти в систему, последовательно перебирая пароли из своего внутреннего списка в несколько сотен, причем в значительной доле случаев ей это удавалось сделать. Фантазия человека по выдумыванию паролей оказалась весьма бедной. Именно поэтому в тех организациях, где безопасности уделяется должное внимание, пароли генерирует и раздает пользователям системный администратор по безопасности. Выработка паролей чуть сложнее, чем выработка ключей, так как при этом «сырую» двоичную гамму необходимо преобразовать к символьному виду, а не просто «нарезать» на куски. Кроме того, отдельные значения, возможно, придется отбросить, чтобы обеспечить равную вероятность появления всех символов алфавита в пароле.
• Еще один способ использования криптографической гаммы – гарантированное затирание данных на магнитных носителях. Дело в том, что даже при перезаписи информации на магнитном носителе остаются следы предыдущих данных, которые может восстановить соответствующая экспертиза. Для уничтожения этих следов такую перезапись надо выполнить многократно. Оказалось, что потребуется перезаписывать информацию на носитель меньшее количество раз, если при такой процедуре использовать случайные или псевдослучайные данные, которые останутся неизвестными экспертам, пытающимся восстановить затертую информацию. Гамма шифра здесь будет как нельзя кстати.

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

• Мы знаем, что один из таких вариантов использования ГОСТа – выработка имитовставки для массивов данных. Однако на базе любого блочного шифра, и ГОСТа в том числе, достаточно легко построить схему вычисления односторонней хэш-функции, называемой также в литературе MDC, что в разных источниках расшифровывается как код обнаружения изменений / манипуляций (M odification/M anipulation D etection C ode) или дайджест сообщения (M essage D igest C ode). Первая расшифровка появилась в литературе гораздо раньше, вторую, более короткую, я думаю, придумали те, кому оказалось не под силу запомнить первую:), – это была шутка. MDC может непосредственно использоваться в системах имитозащиты в качестве аналога имитовставки, не зависящего, однако, от секретного ключа. Кроме того, MDC широко используется в схемах электронно-цифровой подписи (ЭЦП), ведь большинство таких схем сконструированы таким способом, что подписывать удобно блок данных фиксированного размера. Как известно, на базе обсуждаемого стандарта ГОСТ 28147-89 построен стандарт Российской Федерации на вычисление односторонней хэш-функции ГОСТ Р34.11-94 .
• Менее известно, что на базе любого блочного шифра, и ГОСТа в том числе, может быть построена вполне функциональная схема ЭЦП, с секретным ключом подписи и открытой проверочной комбинацией. По ряду причин эта схема не получила широкого практического распространения, однако в отдельных случаях до сих пор может рассматриваться как весьма привлекательная альтернатива доминирующим ныне в мире «математическим» схемам ЭЦП.

Литература

Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования ГОСТ 28147-89. Гос. Ком. СССР по стандартам, М., 1989. ftp://ftp.wtc-ural.ru/pub/ru.crypt/GOST-28147
Шеннон Клод. Математическая теория секретных систем. В сборнике «Работы по теории информации и кибернетике», М., ИЛ, 1963, с. 333-369. http://www.enlight.ru/crypto/articles/shannon/shann__i.htm
Announcing Approval of Federal Information Processing Standard (FIPS) 197, Advanced Encryption Standard (AES), Federal Register Vol. 66, No. 235 / Thursday, December 6, 2001 / Notices, pp 63369–63371. http://csrc.nist.gov/encryption/aes/
Файстель Хорст. Криптография и компьютерная безопасность. Перевод А.Винокурова по изданию Horst Feistel. Cryptography and Computer Privacy, Scientific American, May 1973, Vol. 228, No. 5, pp. 15-23. http://www.enlight.ru/crypto/articles/feistel/feist_i.htm
Шнайер Брюс. Прикладная криптография. 2-е изд. Протоколы, алгоритмы и исходные тексты на языке Си., М., «Триумф», 2002 http://www.ssl.stu.neva.ru/psw/crypto/appl_rus/appl_cryp.htm
Menezes Alfred, van Oorschot Paul, Vanstone Scott. Handbook of applied cryptography. ttp://www.cacr.math.uwaterloo.ca/hac/
Винокуров Андрей. Как устроен блочный шифр? Рукопись. http://www.enlight.ru/crypto/articles/vinokurov/blcyph_i.htm
Винокуров Андрей. Выпуски по криптографии для электронного журнала iNFUSED BYTES online. http://www.enlight.ru/crypto/articles/ib/ib.htm
Винокуров Андрей, Применко Эдуард. Текст доклада «О программной реализация стандартов шифрования РФ и США», конференция по информатизации, Москва, МИФИ, 28-29 января 2001г. Опубликован в материалах конференции.
Информационная технология. Криптографическая защита информации. Функция хэширования ГОСТ Р34.11-94, Госстандарт РФ, М., 1994.

В нашей стране установлен единый алгоритм криптографического представления данных для систем обработки информации в сетях ЭВМ, отдельных вычислительных комплексов и ЭВМ, который определяется ГОСТ 28147-89 .

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

При описании алгоритма используются следующие обозначения:

L и R - последовательности битов;
LR - конкатенация последовательностей L и R, в которой биты последовательности R следуют за битами последовательности L;
(+) - поразрядное сложение по модулю 2 (операция "исключающее ИЛИ");
[+] - сложение 32-разрядных чисел по модулю 2 32 ;
{+} - сложение 32-разрядных чисел по модулю 2 32 -1.

Числа суммируются по следующему правилу:

A [+] B = A + B, если A + B < 2 32 ,
A [+] B = A + B - 2 32 , если A + B >= 2 32 . A {+} B = A + B , если A + B < 2^32 - 1, A {+} B = A + B - (2^32 - 1), если A + B >= 2^32 - 1.

Алгоритм предусматривает четыре режима работы:

В любом случае для шифрования данных используется 256-битовый ключ K, который представляется в виде восьми 32-битовых подключей K i:

K = K 7 K 6 K 5 K 4 K 3 K 2 K 1 K 0 .

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

Режим простой замены

Первый и самый простой режим - замена . Данные, подлежащие шифрованию, разбивают на 64-битовые блоки. Процедура шифрования блока открытых данных T 0 включает 32 цикла (j=1...32).

Блок T 0 разделяется на две последовательности по 32 бита: В(0)A(0), где В(0) - левые или старшие биты, A(0) - правые или младшие биты.

Эти последовательности вводят в накопители N 1 и N 2 перед началом первого цикла шифрования.

Первый цикл (j=1) процедуры шифрования 64-битового блока данных описывается следующими формулами:

Здесь i обозначает номер итерации (i = 1, 2,..., 32).

Функция f называется функцией шифрования. Ее аргументом является сумма по модулю 2 32 числа A(i), полученного на предыдущем шаге итерации, и числа X(j) ключа (размерность каждого из этих чисел равна 32 знакам).

Функция шифрования включает две операции над полученной 32-разрядной суммой. Первая операция называется подстановкой К. Блок подстановки К состоит из 8 узлов замены К(1) ... К(8) с памятью 64 бит каждый. Поступающий на блок подстановки 32-разрядный вектор разбивается на 8 последовательно идущих 4-х разрядных векторов, каждый из которых преобразуется в 4-х разрядный вектор соответствующим узлом замены, представляющим собой таблицу из 16 целых чисел в диапазоне 0...15.

Входной вектор определяет адрес строки в таблице, число из которой является выходным вектором. Затем 4-х разрядные выходные векторы последовательно объединяются в 32-разрядный вектор. Таблицы блока подстановки К содержит ключевые элементы, общие для сети ЭВМ и редко изменяемые.

Вторая операция - циклический сдвиг влево 32-разрядного вектора, полученного в результате подстановки К. 64-разрядный блок зашифрованных данных Т ш представляется в виде Т ш =A(32)B(32).

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

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

Режим гаммирования

Открытые данные, разбитые на 64-разрядные блоки Т(i) (i=1, 2,..., m, где m определяется обьемом шифруемых данных), зашифровываются в режиме гаммирования путем поразрядного сложения по модулю 2 с гаммой шифра Г ш, которая вырабатывается блоками по 64 бит, то есть Г ш = (Г(1),Г(2),...,Г(i),...,Г(m)).

Уравнение зашифрования данных в режиме гаммирования может быть представлено в следующем виде:

Ш(i) = A (Y(i-1) [+] C2, Z(i-1) {+} C1) (+) T(i) = Г(i) (+) T(i) .
Здесь Ш(i) - 64-разрядный блок зашифрованного текста,
A - функция шифрования в режиме простой замены (аргументами этой функции являются два 32-разрядных числа),
С1 и С2 - константы, заданные в ГОСТ 28147-89,
Y(i) и Z(i) - величины, которые определяются итерационно по мере формирования гаммы следующим образом:
(Y(0), Z(0)) = A(S), где S - 64-разрядная двоичная последовательность (синхропосылка);
(Y(i), Z(i)) = (Y(i-1) [+] C2, Z(i-1) {+} C1) для i = 1, 2,...,m.

Расшифрование данных возможно только при наличии синхропосылки, которая не является секретным элементом шифра и может храниться в памяти ЭВМ или передаваться по каналам связи вместе с зашированными данными.

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

Режим гаммирования с обратной связью очень похож на режим гаммирования. Как в и режиме гаммирования открытые данные, разбитые на 64-разрядные блоки Т(i) (i=1, 2,..., m , где m определяется обьемом шифруемых данных), зашифровываются путем поразрядного сложения по модулю 2 с гаммой шифра Г ш, которая вырабатывается блоками по 64 бит:

Г ш = (Г(1),Г(2),...,Г(i),...,Г(m)).

Число двоичных разрядов в блоке Т(m) может быть меньше 64, при этом неиспользованная для шифрования часть гаммы шифра из блока Г(m) отбрасывается.

Уравнение зашифрования данных в режиме гаммирования с обратной связью может быть представлено в следующем виде:

Здесь Ш(i) - 64-разрядный блок зашифрованного текста,
A - функция шифрования в режиме простой замены. Аргументом функции на первом шаге итеративного алгоритма является 64-разрядная синхропосылка, а на всех последующих - предыдущий блок зашифрованных данных Ш(i-1).

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

Процесс выработки имитовстаки единообразен для любого из режимов шифрования данных.

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

Для получения имитовставки открытые данные представляются в виде 64-разрядных блоков Т(i) (i = 1, 2,..., m , где m определяется объемом шифруемых данных). Первый блок открытых данных Т(1) подвергается преобразованию, соответствующему первым 16 циклам алгоритма зашифрования в режиме простой замены. Причем в качестве ключа для выработки имитовставки используется ключ, по которому шифруются данные.

Полученное после 16 циклов работы 64-разрядное число суммируется по модулю 2 со вторым блоком открытых данных Т(2). Результат суммирования снова подвергается преобразованию, соответствующему первым 16 циклам алгоритма зашифрования в режиме простой замены. Полученное 64-разрядное число суммируется по модулю 2 с третьим блоком открытых данных Т(3) и т.д. Последний блок Т(m) при необходимости дополненный до полного 64-разрядного блока нулями, суммируется по модулю 2 с результатом работы на шаге m-1, после чего зашифровывается в режиме простой замены по первым 16 циклам работы алгоритма. Из полученного 64-разрядного числа выбирается отрезок Ир длиной р бит.

Имитовставка Ир передается по каналу связи или в память ЭВМ после зашифрованных данных. Поступившие зашифрованные данные расшифровываются, и из полученных блоков открытых данных T(i) вырабатывается имитовставка Ир", которая затем сравнивается с имитовставкой Ир, полученной из канала связи или из памяти ЭВМ. В случае несовпадения имитовставок все расшифрованные данные считают ложными.