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

Николя Куртуа - «великий и ужасный»

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

В октябре 2010 года был начат процесс рассмотрения вопроса о включении алгоритма ГОСТ 28147-89 в международный стандарт ISO/IEC 18033-3. Уже в мае 2011 года на электронном архиве ePrint появилась статья известного криптографа Николя Куртуа , отмеченного весьма неоднозначным отношением к нему мирового криптографического сообщества. Публикации Куртуа представляют собой печальный пример манипулирования понятиями, которое не открывает никаких новых свойств рассматриваемого объекта, но с претензией на сенсацию провоцирует распространение в некомпетентной среде ошибочных мнений о его действительных свойствах.

Алгебраический метод

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

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

Алгебраический метод, эксплуатируемый Куртуа, коротко можно описать так. На первом этапе используются такие свойства ГОСТ 28147-89, как существование неподвижной точки для части шифрующего преобразования, а также так называемой точки отражения (reflection point). Благодаря этим свойствам из достаточно большого количества пар открытых-шифрованных текстов выбирается несколько пар, которые позволяют рассматривать преобразования не на 32, а лишь на 8 раундах. Второй этап состоит в том, что по полученным на первом этапе результатам 8-ми раундовых преобразований строится система нелинейных уравнений, неизвестными в которой являются биты ключа. Далее эта система решается (это звучит просто, но в действительности является самой трудоемкой частью метода, т.к. система состоит из нелинейных уравнений).

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

Дифференциальный метод

Рассмотрим второй метод Куртуа, который основан на дифференциальном криптоанализе.

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

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

Куртуа использует несколько модифицированный вариант дифференциального метода. Сразу же отметим, что свой анализ Куртуа проводит для S-блоков, отличных от действующих и от предложенных в ISO. В работе приводятся дифференциальные характеристики (те самые номера, в которых должны отличаться блоки) для малого числа раундов. Обоснование продления характеристик на большее число раундов, как водится, основано на «фактах». Куртуа высказывает, опять же, ничем, кроме его авторитета, не подкрепленное предположение, что изменение S-блоков не повлияет на стойкость ГОСТ 28147-89 против его атаки (при этом по непонятным причинам S-блоки из 1-го рабочего проекта дополнения к стандарту ISO/IEC 18033-3 не рассматривались). Анализ, проведенный авторами статьи , показывает, что даже если принять на веру необоснованные «факты» Куртуа и провести анализ ГОСТ 28147-89 с другими S-блоками, то атака опять же оказывается не лучше полного перебора.

Детальный анализ работ Куртуа с подробным обоснованием беспочвенности всех утверждений о снижении стойкости российского стандарта был проведен в работах [ , ].

При этом абсолютное отсутствие аккуратности выкладок признает даже сам Куртуа! Следующий слайд взят из презентации Куртуа на секции коротких объявлений FSE 2012.

Необходимо отметить, что работы Куртуа неоднократно критиковались также и зарубежными исследователями. Например, его работы по построению атак на алгоритм блокового шифрования AES с помощью XSL-метода содержали те же принципиальные недоработки, что и работы по анализу российского стандарта: большинство оценок трудоемкости появляется в тексте совершенно безосновательно и бездоказательно - подробную критику можно найти, например, в работе . Кроме того, сам Куртуа признает повсеместные отказы в публикации его работ на крупных криптографических конференциях и в признанных рецензируемых журналах, оставлявшие ему зачастую лишь возможность выступить на секции коротких объявлений. Об этом, например, можно прочитать в разделе 3 работы . Вот некоторые цитаты, приводимые самим Куртуа и относящиеся к его работам:

• «I think that the audiences of Asiacrypt will not feel it is interesting». Рецензент Asiacrypt 2011.
• «… there is a big, big, big problem: this attack, which is the main contribution of the paper has already been published at FSE’11 (it was even the best paper), …». Рецензент Crypto 2011.

Таким образом, профессиональная часть международной криптографической общественности относится к качеству работ Куртуа с не меньшим сомнением, чем, скажем, к не подтвержденным никакими последовательными выкладками заявлениям некоторых российских специалистов об их умении взламывать AES за 2 100 или к очередным "доказательствам" на две страницы гипотезы о неравенстве сложностных классов P и NP.

Атаки Исобе и Динура-Данкельмана-Шамира

Общая идея атак Исобе () и Динура-Данкельмана-Шамира (далее: атака ДДШ) () заключается в построении для определенного (зависящего от ключа) узкого множества открытых текстов эквивалентного на этом множестве преобразования, имеющего более простую, чем само шифрующее преобразование, структуру. В случае метода Исобе это множество таких 64-битных блоков x, что F 8 -1 (Swap(F 8 (z))) = z, где z = F 16 (x), через F 8 (x) и F 16 (x) обозначены первые 8 и первые 16 раундов шифрования ГОСТ 28147-89 соответственно, через Swap - операция обмена местами половинок 64-байтового слова. При попадании открытого текста в это множество результат полного 32-раундового преобразования ГОСТ 28147-89 совпадает с результатом 16-раундового, что и эксплуатируется автором атаки. В случае метода ДДШ это множество таких x, что F 8 (x) = x (неподвижная точка преобразования F 8). Для всякого открытого текста из этого множества преобразование ГОСТ 28147-89 работает в точности так же, как последние его 8 раундов, что и упрощает анализ.

Трудоемкость атаки Исобе составляет 2 224 операций зашифрования, атаки ДДШ - 2 192 . Однако все вопросы о том, следует ли, что атаки Исобе и ДДШ вносят новые ограничения на условия применения нашего алгоритма, снимает оценка требований к объему материала, необходимого для проведения каждой из атак: для метода Исобе требуется 2 32 пар открытых и шифрованных текстов, а для метода ДДШ - 2 64 . Обработка таких объемов материала без смены ключа априорно неприемлема для любого блокового шифра с длиной блока 64: на материале объемом 2 32 , с учетом задачи о днях рождения (см., например, ), близка к 1/2 вероятность появления повторяющихся блоков, что предоставит нарушителю возможность делать по шифрованным текстам некоторые заключения об открытых текстах без определения ключа. Наличие же 2 64 пар открытых и шифрованных текстов, полученных на одном ключе, фактически позволяет противнику осуществлять операции зашифрования и расшифрования вообще без знания этого ключа. Это обусловлено чисто комбинаторным свойством: противник в этом случае обладает всей таблицей шифрующего преобразования. Такая ситуация абсолютно недопустима ни при каких разумных эксплуатационных требованиях. Например, в КриптоПро CSP присутствует техническое ограничение на объём шифруемого (без преобразования ключа) материала в 4 Мб (см. ). Таким образом, строгий запрет на использование ключа на материале такого объема присущ всякому блоковому шифру с длиной блока 64 бита, а следовательно, атаки Исобе и ДДШ никоим образом не сужают область использования алгоритма ГОСТ 28147-89 при сохранении максимально возможной стойкости 2 256 .

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

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

Отметим, что определенные небрежности в оценках средней трудоемкости присутствуют и в работе Динура, Данкельмана и Шамира. Так, при построении атаки не уделяется должного внимания следующему моменту: для существенной доли ключей множество открытых текстов x, таких, что F 8 (x) = x, является пустым: неподвижных точек у 8 раундов преобразования может просто не быть. Существование неподвижных точек зависит также и от выбора узлов замены. Таким образом, атака является применимой только при определенных узлах замены и ключах.

Стоит упомянуть также еще об одной работе с атакой на ГОСТ 28147-89. В феврале 2012 года на электронном архиве ePrint международной криптографической ассоциации появилась обновленная версия статьи (от ноября 2011 года), которая содержала новую атаку на ГОСТ 28147-89. Характеристики представленной атаки таковы: объем материала - 2 32 (как у Исобе), а трудоемкость - 2 192 (как у ДДШ). Таким образом, эта атака улучшала рекордную по времени атаку ДДШ по объему материала с 2 64 до 2 32 . Отметим отдельно, что авторы честно привели все выкладки с обоснованием трудоемкости и объема материала. Через 9 месяцев в приведенных выкладках была найдена принципиальная ошибка, и с ноября 2012 года обновленная версия статьи в электронном архиве уже не содержит каких-либо результатов касательно отечественного алгоритма.

Атаки в предположении, что нарушитель знает «кое-что» о ключах

Заметим напоследок, что в литературе также имеется некоторое количество работ (см., например, и ), посвященных атакам на ГОСТ 28147-89 в так называемой модели со связанными ключами. Данная модель в своей основе содержит предположение о возможности нарушителя получать доступ для анализа не просто к парам открытых и шифрованных с помощью искомого ключа текстов, но также к парам открытых и шифрованных текстов, полученных с помощью (также неизвестных) ключей, отличающихся от искомого известным регулярным образом (например, в фиксированных битовых позициях). В данной модели действительно удается получить интересные результаты о ГОСТ 28147-89, однако в этой модели не менее сильные результаты удается получать и о, например, получившем наиболее широкое распространение в современных сетях общего пользования стандарте AES (см, например, ). Заметим, что условия для проведения такого рода атак возникают при использовании шифра в некотором протоколе. Нельзя не отметить, что результаты такого рода, хоть и представляют несомненный академический интерес с точки зрения изучения свойств криптографических преобразований, но фактически не относятся к практике. Например, все сертифицированные ФСБ России средства криптографической защиты информации выполняют строжайшие требования по схемам выработки ключей шифрования (см., например, ). Как указано в результатах проведенного в анализа, при наличии 18 связанных ключей и 2 10 пар блоков открытого и шифрованного текста трудоемкость полного вскрытия закрытого ключа, при вероятности успеха 1-10 -4 , действительно составляет 2 26 . Однако при соблюдении упомянутых выше требований по выработке ключевого материала вероятность обнаружения таких ключей равна 2 -4352 , то есть в 2 4096 раз меньше, чем если просто попытаться угадать секретный ключ с первой попытки.

К работам, относящимся к модели со связанными ключами, относится также и работа , наделавшая в 2010 году много шума в российских электронных изданиях, не страдающих от привычки внимательно проверять материал в процессе гонки за сенсациями. Результаты, представленные в ней, не были подкреплены каким-либо сколь-нибудь строгим обоснованием, зато содержали громкие заявления о возможности взламывать государственный стандарт Российской Федерации на слабеньком ноутбуке за считанные секунды - в общем, статья была написана в лучших традициях Николя Куртуа. Но, несмотря на совершенно очевидную мало-мальски знакомому с основными принципами научности публикаций читателю безосновательность статьи, именно для успокоения российской общественности после работы Рудским был написан подробный и обстоятельный текст , содержащий всесторонний анализ данной недостатьи. В статье с говорящим названием "О нулевой практической значимости работы «Key recovery attack on full GOST block cipher with zero time and memory»" приводится обоснование того, что средняя трудоемкость приведенного в метода не меньше, чем трудоемкость полного перебора.

Сухой остаток: какова стойкость на практике?

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

Атака	Трудоемкость	Память	Требуемый материал
Исобе	2 224	2 64	2 32
Динур-Данкельман-Шамир, FP, 2DMitM	2 192	2 36	2 64
Динур-Данкельман-Шамир, FP, low-memory	2 204	2 19	2 64
	2 224	2 36	2 32
Динур-Данкельман-Шамир, Reflection, 2DMitM	2 236	2 19	2 32
Полный перебор	2 256	1	4
Количество наносекунд с возникновения Вселенной	2 89

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

Алгоритм, определяемый ГОСТ 28147-89, имеет длину ключа шифрования 256 бит. Он шифрует информацию блоками по 64 бит (такие алгоритмы называются блочными), которые затем разбиваются на два субблока по 32 бит (N1 и N2) (рисунок 1). Субблок N1 обрабатывается определенным образом, после чего его значение складывается со значением субблока N2 (сложение выполняется по модулю 2, т. е. применяется логическая операция XOR - «исключающее или»), а затем субблоки меняются местами. Данное преобразование выполняется определенное число раз («раундов»): 16 или 32 в зависимости от режима работы алгоритма. В каждом раунде выполняются две операции.

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

Первая - наложение ключа. Содержимое субблока N1 складывается по модулю 2 с 32-бит частью ключа Kx. Полный ключ шифрования представляется в виде конкатенации 32-бит подключей: K0, K1, K2, K3, K4, K5, K6, K7. В процессе шифрования используется один из этих подключей - в зависимости от номера раунда и режима работы алгоритма.

Вторая операция - табличная замена. После наложения ключа субблок N1 разбивается на 8 частей по 4 бит, значение каждой из которых заменяется в соответствии с таблицей замены для данной части субблока. Затем выполняется побитовый циклический сдвиг субблока влево на 11 бит.

Табличные замены (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 а 2 ...).

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

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

K0, K1, K2, K3, K4, K5, K6, K7, K0, K1 и т. д. - в раундах с 1-го по 24-й;

K7, K6, K5, K4, K3, K2, K1, K0 - в раундах с 25-го по 32-й.

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

K0, K1, K2, K3, K4, K5, K6, K7 - в раундах с 1-го по 8-й;

K7, K6, K5, K4, K3, K2, K1, K0, K7, K6 и т. д. - в раундах с 9-го по 32-й.

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

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

• 1. В регистры N1 и N2 записывается их начальное заполнение - 64-бит величина, называемая синхропосылкой.
• 2. Выполняется зашифрование содержимого регистров N1 и N2 (в данном случае - синхропосылки) в режиме простой замены.
• 3. Содержимое регистра N1 складывается по модулю (232 - 1) с константой C1 = 224 + 216 + 28 + 24, а результат сложения записывается в регистр N1.
• 4. Содержимое регистра N2 складывается по модулю 232 с константой C2 = 224 + 216 + 28 + 1, а результат сложения записывается в регистр N2.
• 5. Содержимое регистров N1 и N2 подается на выход в качестве 64-бит блока гаммы шифра (в данном случае N1 и N2 образуют первый блок гаммы).

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

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

Таблица 1. Зашифрование и расшифрование в режиме гаммирования

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

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

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

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

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

Цикл повторяется до последнего блока информации. Получившееся в результате этих преобразований 64-бит содержимое регистров N1 и N2 или его часть и называется имитоприставкой. Размер имитоприставки выбирается, исходя из требуемой достоверности сообщений: при длине имитоприставки r бит вероятность, что изменение сообщения останется незамеченным, равна 2-r.Чаще всего используется 32-бит имитоприставка, т. е. половина содержимого регистров. Этого достаточно, поскольку, как любая контрольная сумма, имитоприставка предназначена прежде всего для защиты от случайных искажений информации. Для защиты же от преднамеренной модификации данных применяются другие криптографические методы - в первую очередь электронная цифровая подпись.

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

Алгоритм ГОСТ 28147-89 считается очень сильным алгоритмом - в настоящее время для его раскрытия не предложено более эффективных методов, чем упомянутый выше метод «грубой силы». Его высокая стойкость достигается в первую очередь за счет большой длины ключа - 256 бит. При использовании секретной синхропосылки эффективная длина ключа увеличивается до 320 бит, а засекречивание таблицы замен прибавляет дополнительные биты. Кроме того, криптостойкость зависит от количества раундов преобразований, которых по ГОСТ 28147-89 должно быть 32 (полный эффект рассеивания входных данных достигается уже после 8 раундов).

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

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

Причина в том, что я его только недавно придумал и пока никому об этом не рассказывал. Однако производительность кода, так же как и производительность процессора, имеет объективные характеристики, которые поддаются измерениям. Эта статья - именно о производительности кода, выполняемого процессорным ядром.

В чем измеряется производительность кода? Поскольку я первый об этом заговорил, то по праву первооткрывателя буду его измерять в RTT-шках;).

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

Студент ответит - одну, его преподаватель подумает и скажет, что четыре, профессионал - что пока только двенадцать операций.

Так вот, программный код, который загружает все исполнительные устройства процессора одновременно на протяжении всего времени исполнения кода, будет иметь производительность 12 RTT-шек. Максимум! Честно признаюсь, такого кода я раньше не писал, но в этой статье попытаюсь сделать над собой усилие.

Я докажу, что код с одновременным выполнением двенадцати 32-битных операций - возможен

Программный код, который использует в процессорном ядре одно исполнительное устройство, естественно, будет иметь производительность в 1 RTT-шку. Такой производительностью кода могут «похвастаться» программы, генерируемые компиляторами языков высокого уровня, и интерпретаторы виртуальных машин. Не нужно считать, что показатель загрузки процессора, который можно увидеть в диспетчере задач ОС, может служить объективным критерием эффективности кода. Загрузка ядра процессора может быть 100%, но при этом программный код будет использовать одно исполнительное устройство в нем (производительность 1 RTT). В этом случае при 100%-й загрузке процессорное ядро будет работать в 1/12 своей максимальной производительности. Другими словами, когда в диспетчере задач ОС Windows показывается максимальная загрузка процессора, его реальная производительность может варьироваться от 1 до 12 RTT. Увидев в окне производительности 100%-ю загрузку на каком-либо процессорном ядре, неправильно считать, что в этом ядре работают все исполнительные устройства, отнюдь!

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

Традиционная реализация ГОСТ 28147-89

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

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

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

По п. 1.2 ГОСТа этот блок реализует тетрадные (по четыре бита) перестановки в 32-битном слове, но архитектура процессора х86/64 и его система команд не способна эффективно манипулировать тетрадами.

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

В более продвинутых реализациях эти таблицы имеют размер 1024 байта (256 слов по четыре байта). Это сделано для того, чтобы реализовать в таблицах дополнительно циклический сдвиг на 11 позиций полученного в результате подстановки 32-битного слова (следующая операция алгоритма преобразования по ГОСТу). Пример реализации ГОСТа по данному методу показан в приложении 1 (на диске).

Информация блока подстановок является секретным компонентом криптофункции (как это сформулировано в ГОСТе, см. на рис. 2).

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

Короче говоря, ФСБ пропускает такие программные реализации криптопроцедуры, несмотря на явное снижение стойкости такого решения и прямое нарушение собственных требований по ГОСТу (п. 1.7). И это несмотря на общеизвестные методы взлома шифров через съем дампа памяти…

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

Но хватит лирики, важно в рамках рассматриваемой темы то, что этот программный код имеет производительность в 1 RTT-шку. Теперь напишем код с производительностью 2 RTT-шки.

Многопоточная реализация ГОСТ 28147-89

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

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

Однако существует и иной вариант параллельной обработки данных на одном- единственном ядре процессора. Поясню эту неочевидную мысль.

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

Загрузкой работой всех АЛУ управляет специальный аппаратный блок внутри процессорного ядра - планировщик, который просматривает исполняемый код форвардно, на глубину до 32–64 байт. Если планировщик обнаруживает команды, которые можно запускать на АЛУ без конфликтов, то он их запускает одновременно на разных исполнительных устройствах. При этом счетчик выполненных команд указывает на ту исполняемую команду (их в такой схеме несколько), после которой все команды уже выполнены.

Большинство программных последовательностей, генерируемых автоматически (компиляторами), не могут загрузить все АЛУ и FPU, находящиеся в ядре процессора. В этом случае оборудование процессора простаивает, что значительно снижает его результирующую производительность. Разработчики процессоров это понимают и вводят режимы увеличения частоты ядра, когда оборудование используется не полностью. Также для этого предназначены системы гипертрейдинга, и эту систему я буду использовать для «прессования» кода по максимуму в дальнейшем.

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

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

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

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

Далее показан пример с чередованием команд из разных потоков обработки. В этом случае команды, относящиеся к разным блокам данных, чередуются. Планировщик выбирает независимые друг от друга команды и передает их на выполнение в АЛУ1 и АЛУ2. Группировка команд первого и второго потока на этих АЛУ осуществляется автоматически, поскольку в алгоритм работы планировщика заложена группировка команд с зацеплением по общим данным на одном и том же исполнительном устройстве.

Чтобы такой программный код работал без простоев АЛУ, необходимо, чтобы каждый программный поток работал со своим набором регистров. Кеш в этой схеме становится узким местом (у него только два порта выдачи данных), поэтому ключи храним в MMX-регистрах. Поскольку в данном случае узлы замены (и сдвига) в памяти только читаются, то они могут быть общими для обоих программных потоков.

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

Метод параллельного шифрования эффективно реализуется только для 64-битного режима работы процессора, поскольку в этом режиме имеется достаточное количество РОН (целых 16 штук!). Пример реализации ГОСТа по данному методу показан в приложении 2 (на диске).

Ясно, что данная реализация ГОСТа имеет производительность кода 2 RTT-шки. А теперь посмотрим, как это сказывается на времени выполнения.

Цикл шифрования для одного потока (приложение 1) составляет 352 такта, и за это время обсчитывается 8 байт данных, для двухпоточной реализации ГОСТа (приложение 2) требуется 416 тактов процессора, но при этом обсчитывается 16 байт. Таким образом, результирующая скорость преобразования повышается с 80 до 144 мегабайт для процессора частотой 3,6 ГГц.

Интересная получается картина: код содержит ровно в два раза больше команд, а выполняется всего на 15% дольше, но, думаю, читатели уже поняли причину этого феномена…

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

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

Использование SSE-регистров и AVX-команд современных процессоров для реализации ГОСТ 28147-89

Современные процессоры архитектуры х86/64 имеют в своем составе набор регистров SSE размером 16 байт и специализированные FPU (как минимум два) для выполнения различных операций над этими регистрами. Возможна реализация ГОСТа на этом оборудовании, причем в этом случае узлы замены можно размещать не в виде таблиц в оперативной памяти, а непосредственно на выделенных SSE-регистрах.

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

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

Схема одного из возможных размещений узлов замены на SSE-регистрах показана на рис. 4.

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

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

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

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

Имея узлы хранения подстановок на SSE-регистрах и многовходовый коммутатор в блоках FPU, можно организовать следующее преобразование в блоке подстановок (рис. 5).

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

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

Работой коммутаторов управляет специальная трехадресная команда AVX VPSHUFB. Ее первый операнд является приемником информации из коммутаторов, второй - источником, к которому подключены входы коммутаторов. Третий операнд является управляющим регистром для коммутаторов, каждый байт которого ассоциирован с соответствующим коммутатором; значение в нем задает номер направления, с которого коммутатор считывает информацию. Описание этой команды из официальной документации Intel см. на рис. 5. На рис. 6 приведена схема работы этой команды - изображена только половина SSE-регистров, для второй половины все аналогично.

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

Программа с выборкой тетрад через коммутаторы FPU была написана, но я даже не стал помещать ее в приложение - слишком убого. Иметь регистр размером 128 бит и использовать в нем только 32 бита - непрофессионально.

Как говорится, «Наш финиш - горизонт», поэтому выжимать так выжимать... будем прессовать и складывать в пакеты!

Это не игра слов, а суровая FPUшная реальность - регистры SSE можно разбивать на равные части и выполнять над этими частями одинаковые преобразования одной командой. Для того чтобы процессор это понял, имеется магическая буковка «Р» - пакет, которая ставится перед мнемоникой команды, и не менее магические буковки «Q», «D», «W», «B», которые ставятся в конце и объявляют, на какие части разбиты в этой команде регистры SSE.

Нас интересует пакетный режим с разбивкой SSE-регистра на четыре 32-битных блока; соответственно, все команды будут иметь префикс «P», а в конце - символ «D». Это дает возможность одной процессорной командой параллельно обрабатывать сразу четыре блока по 32 бита, то есть в параллель рассчитывать четыре блока данных.

Программа, реализующая этот метод, имеется в приложении 3, там же - все пояснения.

Впрочем, прессовать так прессовать! В современных процессорах имеется как минимум два блока FPU, и для их полной загрузки можно использовать два потока независимых команд. Если грамотно чередовать команды из независимых потоков, то можно загрузить работой оба блока FPU полностью и получить сразу восемь параллельно обрабатываемых потоков данных. Такая программка была написана, и ее можно посмотреть в приложении 4, только смотреть нужно осторожно - можно слететь с катушек. Это, что называется, «код не для всех...».

Цена вопроса

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

Для четырех потоков была получена скорость выполнения 472 процессорных такта. Таким образом, для процессора с частотой 3,6 ГГц один поток считается со скоростью 59 мегабайт в секунду, а четыре потока соответственно со скоростью 236 мегабайт в секунду.

Для восьми потоков была получена скорость выполнения 580 процессорных тактов. Таким образом, для процессора с частотой 3,6 ГГц один поток считается со скоростью 49 мегабайт в секунду, а восемь потоков со скоростью 392 мегабайта в секунду.

Как может заметить читатель, код в примере № 3 имеет производительность 4 RTT, а код в примере № 4 имеет производительность 8 RTT. В этих примерах на SSE-регистрах закономерности те же, что и при использовании РОН, только планировщик снизил свою эффективность. Сейчас он обеспечивает 20%-е увеличение длительности при двукратном увеличении длины кода.

Причем эти результаты были получены с использованием универсальных AVX-команд, имеющихся как в процессорах Intel, так и в процессорах AMD. Если выполнить оптимизацию под процессор AMD, результат будет значительно лучше. Звучит поперек тренда, но тем не менее это правда, и вот почему: процессоры AMD имеют дополнительный набор команд, так называемое XOP-расширение, и в этом дополнительном наборе команд есть такие, которые значительно упрощают реализацию алгоритма ГОСТа.

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

Если речь зашла о дальнейшей оптимизации, нелишне помнить о наличии 256-битных регистров (YMM-регистры), используя которые можно теоретически еще удвоить скорость вычислений. Но пока это только перспектива, на данный момент процессоры очень сильно замедляются, когда выполняют 256-битные инструкции (FPU имеют ширину тракта 128 бит). Эксперименты показали, что на современных процессорах счет в 16 потоков на YMM-регистрах выигрыша не дает. Но это только пока, на новых моделях процессоров, несомненно, будет увеличено быстродействие 256-битных команд, и тогда использование 16 параллельных потоков станет целесообразно и приведет к еще большему увеличению скорости работы криптопроцедуры.

Теоретически можно рассчитывать на скорость 600–700 мегабайт в секунду при наличии в процессоре двух FPU с шириной рабочего тракта 256 бит каждый. В этом случае можно говорить о написании кода с эффективностью 16 RTT, и это не фантастика, а ближайшая перспектива.

Смешанный режим

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

Рассчитывать на прибавку в 50% здесь не приходится, узким местом становится кеш-память, где хранятся технологические маски, но прибавку в 100 дополнительных мегабайт все же получить можно. Этот вариант не приведен в приложениях (макросы аналогичны используемым в коде на 8 RTT), но он имеется в программных файлах. Так что если кто не верит в возможность шифрования со скоростью 500 мегабайт в секунду на одном процессорном ядре, пусть запустит тестовые файлы. Там же есть и тексты с комментариями, чтобы никто не подумал, что я лукавлю.

Такой фокус возможен только на процессорах Intel, у AMD только два блока FPU на два процессорных модуля (аналог режима гипертрейдинг). Но зато имеется еще четыре АЛУ, которые грех не использовать.

Можно загнать процессорные модули «Бульдозера» в режим, аналогичный режиму гипертрейдинга, но запускать на разных модулях в одном потоке преобразование на РОН, а в другом потоке на SSE-регистрах и получить те же 12 RTT. Этот вариант я не проверял, но, думаю, на AMD код в 12 RTT будет работать более эффективно. Желающие могут попробовать, тестовые программы можно подкорректировать для работы на «Бульдозерах» достаточно легко.

Кому это нужно?

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

Причем, как это ни странно, встроенное в процессоры шифрование по AES-алгоритму оказывается значительно медленнее, тесты показывают скорость на уровне 100–150 мегабайт в секунду, и это при аппаратной реализации алгоритма! Проблема заключается в однопоточном счете и блоке замен, который оперирует байтами (таблица из 256 строк). Так что ГОСТ оказывается эффективнее в реализации на архитектуре х86/64, кто бы мог подумать…

Это если говорить о достигнутом уровне скорости шифрования. А если иметь в виду теоретические изыски в области повышения эффективности кода, то скорее всего это никому не нужно. Специалистов уровня 3–6 RTT практически нет, компиляторы вообще генерят код на уровне 1–2,5 RTT, а основная масса программистов не знает ассемблера, а если и знает его правописание, то не понимает устройства современного процессора. А без этих знаний что ассемблер, что какой-нибудь там СИ-шарп - без разницы.

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

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

ГОСТ 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-битным ключом).

Задачи по информационной безопасности

Задания на контрольную работу 2

Примеры выполнения заданий 3

Приложение А. Алгоритм шифрования ГОСТ 28147-89 10

Приложение Б. Символы кириллицы

(альтернативная кодовая таблица ASCII) 13

Приложение В. Блок подстановки в алгоритме шифрования

ГОСТ 28147-89 14

Приложение Г. Алгоритм шифрования RSA 15

Приложение Д. Таблица простых чисел 17

Приложение Е. Функция хеширования 18

Приложение Ж. Электронная цифровая подпись 19

Вопросы к зачету 21

Литература 22

Задача №1. Шифр Цезаря .

Используя шифр Цезаря, зашифруйте свои данные: Фамилию Имя Отчество.

Задача №2. Алгоритм шифрования гост 28147-89.

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

Задача №3. Алгоритм шифрования rsa.

Сгенерируйте открытый и закрытый ключи в алгоритме шифрования RSA, выбрав простые числа p и q из первой сотни. Зашифруйте сообщение, состоящее из ваших инициалов: ФИО.

Задача №4. Функция хеширования.

Найти хеш–образ своей Фамилии, используя хеш–функцию , гдеn = pq.

Задача №5. Электронная цифровая подпись.

Примеры выполнения заданий

Задача №1. Шифр Цезаря . Используя шифр Цезаря, зашифруйте свои данные: Фамилию Имя Отчество.

Исходный текст:

« КОЗИНА ГАЛИНА ЛЕОНИДОВНА»

Используем алфавит, содержащий 33 буквы и пробел, стоящий после буквы Я:

АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯпробел

Ключом в шифре Цезаря является число 3. Каждая буква в исходном тексте сдвигается по алфавиту на 3 позиции. Таким образом, получаем:

Исходный текст					ЛЕОНИДОВНА
Зашифрованный текст					ОЗСРЛЖСЕРГ

Задача №2. Алгоритм шифрования ГОСТ 28147-89. Выполните первый цикл алгоритма шифрования ГОСТ 28147-89 в режиме простой замены. Для получения 64 бит исходного текста используйте 8 первых букв из своих данных: Фамилии Имени Отчества. Для получения ключа (256 бит) используют текст, состоящий из 32 букв. Первый подключ содержит первые 4 буквы.

Исходные данные для зашифрования: КОЗИНА Г

Для ключа возьмем последовательность состоящую из 32 букв:

АЛИНа пошла в лес собирать грибы

Для первого подключа Х используем первые 4 буквы ключа: АЛИН.

Переводим исходный текст и первый подключ в двоичную последовательность (см. Приложение Б):

исходный текст

первый подключ X0

Таким образом, первые 64 бита определяют входную последовательность

L0: 11001010 11001110 11000111 11001000

R0: 11001101 11000000 00100000 11000011

следующие 32 бита определяют первый подключ

Х0: 11000000 11001011 11001000 11001101

I. Найдем значение функции преобразования f(R0,X0) (см. Приложение А)

1). Вычисление суммы R0 и X0 по mod 2 32

R0: 1100 1101 1100 0000 0010 0000 1100 0011

Х0: 1100 0000 1100 1011 1100 1000 1100 1101

1000 1110 1000 1011 1110 1001 1001 0000

2). Преобразование в блоке подстановки

Результат суммирования R0+X0 по mod 2 32

1000 1110 1000 1011 1110 1001 1001 0000

преобразуем в блоке подстановки (см. Приложение В). Для каждого 4-битного блока вычислим его адрес в таблице подстановки. Номер блока соответствует номеру столбца, десятичное значение блока соответствует номеру строки в таблице. Таким образом, 5-тый блок (1011) заменяется заполнением 11-ой строки и пятого столбца в таблице подстановки (1110).

номера блоков

1000 1110 1000 1011 1110 1001 1001 0000

соответствующие номера строк в таблице подстановки

8 14 8 11 14 9 9 0

заполнение

9 2 3 14 5 15 3 4

результат

1001 0010 0011 1110 0101 1111 0011 0100

3). Циклический сдвиг результата п.2 на 11 бит влево

Таким образом, нашли значение функции f (R0,X0):

1111 0010 1111 1001 1010 0100 1001 0001

II. Вычисляем R1= f(R0,X0) L0.

Результат преобразования функции f(R0,X0) складываем с L0 по mod2:

L0: 1100 1010 1100 1110 1100 0111 1100 1000

f(R0,X0): 1111 0010 1111 1001 1010 0100 1001 0001

R1: 0011 1000 0011 0111 0110 0011 0101 1001

Задача №3. Алгоритм шифрования RSA . Сгенерируйте откры-тый и закрытый ключи в алгоритме шифрования RSA, выбрав простые числа p и q из первой сотни. Зашифруйте сообщение, состоящее из ваших инициалов: ФИО.

I.Генерация ключей (см. Приложение Г).

Выберем два простых числа р = 13 и q = 19 (см. Приложение Д).

Тогда модуль

n = pq =13*19 = 247

и функция Эйлера

(n ) = (p -1)(q -1) = 12*18 = 216.

Закрытый ключ d выбираем из условий d <  (n ) и d взаимно просто с  (n ) , т.е. d и  (n ) не имеют общих делителей.

Пусть d = 25.

Открытый ключ e выбираем из условий e < (n ) и de =1(mod  (n )): e <216,

25e =1(mod 216).

Последнее условие означает, что число 25e -1 должно делиться на 216 без остатка.

Таким образом, для определения e нужно подобрать такое число k , что

25e -1 = 216 k .

При k =14 получаем 25e =3024+1 или

В нашем примере

(121, 247) – открытый ключ,

(25, 247) – секретный ключ.

II. Шифрование.

Представим шифруемое сообщение «КГЛ» как последова-тельность целых чисел. Пусть буква «К» соответствует числу 12, буква «Г» - числу 4 и буква «Л» - числу 13.

Зашифруем сообщение, используя открытый ключ (121, 247):

С 1 = (
) mod 247= 12

С 2 = (
) mod 247=199

С 3 = (
) mod 247= 91

Таким образом, исходному сообщению (12, 4, 13) соответствует криптограмма (12, 199, 91).

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

Расшифруем сообщение (12, 199, 91), пользуясь секретным ключом (25,247):

М 1 = (
) mod 247=12

М 2 = (
) mod 247= 4

М З = (
) mod 247=13

В результате расшифрования было получено исходное сообщение (12, 4, 13), то есть "КГЛ".

Замечания.

Например,

Для рассматриваемого примера получим

Задача №4. Функция хеширования. Найти хеш–образ своей Фамилии, используя хеш–функцию
, гдеn = pq, p, q взять из Задания №3.

Хешируемое сообщение «КОЗИНА». Возьмем два простых числа p =13, q =19 (см. Приложение Е). Определим n =pq =13*19=247. Вектор инициализации выберем равным 8 (выбираем случайным образом). Слово«КОЗИНА» можно представить последователь-ностью чисел (12, 16, 9, 10, 15, 1) по номерам букв в алфавите. Таким образом,

n=247, H 0 =8, M 1 =12, M 2 =16, M 3 =9, M 4 =10, M 5 =15, M 6 =1.

Используя формулу

,

получим хеш-образ сообщения «КОЗИНА»:

H 1 =(H 0 +M 1) 2 mod n = (8 + 12) 2 mod 247 = 400 mod 247=153

H 2 =(H 1 +M 2) 2 mod n = (153 + 16) 2 mod 247 = 28561 mod 247= 156

H 3 =(H 2 +M 3) 2 mod n = (156 + 9) 2 mod 247 = 27225 mod 247= 55

H 4 =(H 3 +M 4) 2 mod n = (55 + 10) 2 mod 247 = 4225 mod 247= 26

H 5 =(H 4 +M 5) 2 mod n = (26 + 15) 2 mod 247 = 1681 mod 247= 199

H 6 =(H 5 +M 6) 2 mod n = (199 + 1) 2 mod 247 = 40000 mod 247= 233

В итоге получаем хеш-образ сообщения «КОЗИНА», равный 233.

Задача №5. Электронная цифровая подпись. Используя хеш-образ своей Фамилии, вычислите электронную цифровую подпись по схеме RSA.

Пусть хеш-образ Фамилии равен 233, а закрытый ключ алгоритма RSA равен (25, 247). Тогда электронная цифровая подпись сообщения, состоящего из Фамилии, вычисляется по правилу (см. Приложение Ж)

s = 233 25 mod 247 = 168.

Для проверки ЭЦП, используя открытый ключ (121, 247), найдем

H = 168 121 mod 247 = 233.

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