Проект нового стандарта шифровании данных ГОСТ — алгоритм «Кузнечик»

В настоящее время идет активное обсуждение разработки и принятия нового отечественного стандарта шифрования данных. Проект стандарта с подробным описанием представлен на сайте http://www.tc26.ru/.

Проект стандарта включает описание двух разных блочных шифров. Первый — это блочный шифр, описанный в ГОСТ 28 147–89 с зафиксированными блоками нелинейной подстановки. Второй — новый блочный шифр типа «подстановочноперестановочная сеть» с размером блока 128 бит, для генерации раундовых ключей которого используется есть Фсйстсля. Данный тип шифров является хорошо изученным и относительно простым с точки зрения криптографического анализа и обоснования требуемых свойств. Новый блочный шифр в проекте стандарта описан под именем «Кузнечик» («Kuznyechik»).

Работа алгоритма «Кузнечик» происходит следующим образом. На вход шифрования поступает 128-битовый блок открытого текста. Первоначально данный текст складывается по модулю 2 с первым раундовым подключом. После этого выполняется девять раундов преобразования. Каждый раунд состоит из трех операций: преобразования S, преобразования L, сложения с очередным раундовым подключом. Выход девятого раунда образует блок шифр-текста длиной 128 бит. Алгоритм расшифрования использует инверсные операции. Кроме того, меняется порядок использования раундовых подключей. На вход алгоритма расшифрования «Кузнечик» поступает 128- битовый блок шифрованного текста. Первоначально данный текст складывается по модулю 2 с последним раундовым подключом К К). После этого выполняется девять раундов преобразования. Каждый раунд состоит из трех операций: инверсного преобразования S, инверсного преобразования L, сложения с очередным раундовым подключом. Выход девятого раунда образует блок восстановленного открытого текста длиной 128 бит. Общий вид алгоритма шифрования «Кузнечик» можно представить так, как это сделано на рис. 29.

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

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

Преобразование S является аналогом S-блока замены. На вход преобразования S поступает 128-битное значение, которое разбивается на шестнадцать элементов по 8 бит а|5, …, ао. Каждый элемент заменяется с помощью нелинейного биективного преобразования л. Второе базовое преобразование нового шифра — операция R. На выходе преобразования R первый элемент получается с помощью линейного преобразования С, а остальные элементы переписываются в неизменном виде с ai₅ по &. Смысл операции L заключается в том, что операция R примсняется 16 раз подряд. Таким образом, после шестнадпатикратпого применения преобразования R, все байты преобразуемой последовательности изменят свои значения в результате преобразования L.

Рис. 29. Схема зашифрования/расшифрования данных с помощью шифра «Кузнечик».

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

Обработка выполняется в течение 8 раундов. Функция F заключается в сложении с константой С и выполнении прсобразований S и L. Всего для работы алгоритма шифрования требуется 10 раундовых подключей, поэтому схема, приведенная на рис. 30, применяется 4 раза, вырабатывая каждый раз по 2 раундовых подключа.

Рис.^; 30. Схема выработки раундовых подключей Рассмотрим, как работают основные операции, входящие в состав шифра «Кузнечик». При этом двоичные строки из V*, длина которых кратна 4, будем записывать в шестнадцатеричном виде, а символ конкатенации («||») опускать. То есть, строка a G V_4n будет представлена в виде a_n. ia_n. г-? .ао, где aiG {0, 1, …, 9, a, b, с, d, е, f}, i = 0, 1, …, n — 1. Соответствие между двоичными строками длиной 4 и шестнадцатеричными строками длиной 1 задастся естественным образом. Преобразование, ставящее в соответствие двоичной строке длиной 4п шестнадцатеричную строку длиной п, и соответствующее обратное преобразование для простоты записи опускаются.

В алгоритме используется операция S: V 12s —? V|₂g, работа которой описывается следующим образом:

гдеа = а1₅||…||а₀е V,28, а^ V₈, i = 0, 1,…, 15.

По сути дела, данное преобразование является аналогом S-блока замены. На вход преобразования поступает 128-битное значение, которое разбивается на шестнадцать элементов по 8 бит а₍5. …, ао. Каждое значение а< определяет индекс массива л:

л = (252, 238, 221, 17, 207, ПО, 49, 22, 251, 196, 250, 218, 35, 197, 4, 77, 233, 119, 240, 219, 147, 46, 153, 186, 23, 54, 241. 187, 20, 205, 95, 193, 249, 24, 101, 90, 226, 92, 239, 33, 129, 28, 60, 66, 139, 1, 142, 79, 5, 132, 2, 174, 227, 106, 143, 160, 6, 11, 237, 152, 127,212,211,31,235,52, 44,81,234, 200, 72, 171,242, 42, 104, 162, 253, 58, 206, 204, 181, 112, 14, 86, 8, 12, 118, 18, 191, 114, 19, 71, 156, 183, 93, 135, 21, 161, 150, 41, 16, 123, 154, 199, 243, 145, 120, 111, 157, 158, 178, 177, 50, 117, 25, 61, 255, 53, 138, 126, 109, 84, 198, 128, 195, 189, 13, 87, 223, 245, 36, 169,.

• 62, 168, 67, 201, 215, 121, 214, 246, 124, 34, 185, 3, 224, 15, 236,
• 222, 122, 148, 176, 188, 220, 232, 40, 80, 78, 51, 10, 74, 167, 151,
• 96, 115, 30, 0, 98, 68, 26, 184, 56, 130, 100, 159, 38, 65, 173, 69, 70, 146, 39, 94, 85, 47, 140, 163, 165, 125, 105, 213, 149, 59, 7, 88, 179, 64, 134, 172, 29, 247, 48, 55, 107, 228, 136, 217, 231, 137, 225, 27, 131, 73, 76, 63, 248, 254, 141, 83, 170, 144, 202, 216, 133,
• 97, 32, 113, 103, 164, 45, 43, 9, 91, 203, 155, 37, 208, 190, 229,
• 108, 82, 89, 166, 116, 210, 230, 244, 180, 192, 209, 102, 175, 194,
• 57, 75, 99, 182).

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

Так, например, в результате применения преобразования S, значение ffeeddccbbaa99881122334455667700 будет преобразовано в значение b66cd8887d38c8d77765aeca0c9a7cfc. Разберем подробнее, как выполнено данное преобразование. Легко можно видеть, что первые два символа ff (что в 10-ричном виде соответствует значению 255) будут указывать на последний элемент массива л. л (255) = 182, что в 16-ричном виде соответствует значению Ь6, которое и составляет первые символы выходного преобразования. Аналогичным образом видно, что последние два символа 00 будут указывать на первый элемент массива л. л (0) = 252, что в 16-ричном виде соответствует значению fc, которое и составляет последние символы выходного преобразования.

Рис. 31. Преобразование S.

Операция R работает следующим образом:

где, а = a|₅||…||a₍, e V,₂₈, a, G V₈, i = 0, 1, 15.

Таким образом, на выходе преобразования R первый элемент будет получен с помощью преобразования С, а остальные элементы перепишутся в неизменном виде с ai₅ по ai Схематично процесс преобразования данных с помощью преобразования R можно сделать так, как это показано на рис. 31. При этом сама операция С работает следующим образом:

для любых aj? V_s, i = 0, 1, …, 15, где операции сложения и умножения осуществляются в поле F, константы являются элементами поля, а, А обозначает биективное отображение.

Рис. 32. Преобразование R.

Прежде чем перейти к рассмотрению примера, заметим, что все операции для алгоритма «Кузнечик» выполняются в конечном поле GF (2)[x]4>(x), где р (х) = х⁸ + х⁷ + х⁶ + х + 1, р (х)? GF (2)[x]; элементы ноля F представляются целыми числами, причем элементу zo + Z| • 0 + … + z₇ • 0⁷?F, где Zi? {0, 1}, i = 0, 1, …, 7, и 0 обозначает класс вычетов по модулю р (х), содержащий х, соответствует число z₀ + 2 • Zi + … + 2⁷ • z₇. Это значит, что если в результате применения операций умножения, результат выйдет за пределы степени поля, то для его нормализации необходимо будет вычислить его значение модуля, применив многочлен р (х) = х⁸ + х⁷ + х⁶ + х + 1.

В преобразовании? (а|₅, …, а (x), где р (х) = х⁸ + х⁷ + х⁶ + х + 1? GF (2)[x], то для корректного выполнения умножения необходимо использовать полиномы, соответствующие биективному отображению, сопоставляющие двоичной строке из V₈ элемент поля F. Поэтому, для удобства дальнейшей работы, составим табл. 21, в которой сопоставим десятичные значения констант, их шестнадцатеричный и двоичный вид, а также соответствующие им полиномы.

Таблица 21.

Соответствие констант и полиномов для.

Рассмотрим, как будет работать преобразование R, если значение 100 поступит на его вход. Значение, поступающее, на вход преобразования R можно представить в виде следующих 16 значений: а|₅ = 0, а_!4 = 0,.

ав = 0, а,₂ = 0, а_п = 0, а₁₀ = 0, а₉ = 0, а₈ = 0, а₇ = 0, а₆ = 0, а₅ = 0, а₄ = 0, а₃ = 0, а₂ = 0, ai = 1, а₀ = 0. Тогда:

Как упоминалось ранее, А обозначает биективное отображение, сопоставляющее двоичной строке из V₈ элемент поля F.

следующим образом: строке z₇||___||zi||z₀, z;G {(), 1}, i = 0, 1, …, 7,.

соответствует элемент Zo + Z| • 0 + … + z-j • 0 GF. To есть значению 1 будет соответствовать 1 (см. табл. 21). В таком случае имеем:

Значение 148 в десятичном виде соответствует 16-ричному значению 94, которое и является первым элементом выходной последовательности в рассматриваемом примере. Остальные выходные элементы преобразования R просто записаны в виде последовательности значений Э|5, …, а^.

В данном случае умножение выполнялось на 1 и в результате умножения было образовано всего одно слагаемое. Рассмотрим пример посложнее. Применим к полученному результату еще раз преобразование R.

В этом случае значение, поступающее на вход преобразования R, можно представить в виде следующих 16 значений: а15 = 94, Э]4 = 0, Эи = 0, а2 = 0, ац ⁼ 0, аю ⁼ 0, а = 0, as = О, а₇ = 0, а₆ = 0, а₅ = 0, а₄ = 0, а₃ = 0, = 0, а, = 0, ао = 1. Тогда запишем:

Значение 148 в десятичном виде соответствует 16-ричному значению 94, поэтому полиномы для двух этих значений будут одинаковые. И для получения результата их надо перемножить между собой. При этом необходимо отметить, что при образовании полиномов операция сложения понимается как операция сложения по модулю 2. Таким образом, члены полинома, полученного в результате умножения, имеющие одинаковую степень, будут взаимоисключаться:

Степень полученного полинома превышает допустимую степень полинома в поле GF (2)[XH)(x). Поэтому полученное произведение необходимо разделить на значение полинома р (х) и в качестве результата взять остаток от деления так, как показано на рис. 33.

Тогда получаем, что

Следовательно:

Таким образом получается, что.

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

Операция L опирается на преобразование R и выглядит следующим образом:

Рис. 33. Нормализация полинома.

По сути дела смысл операции L заключается в том, что операция R применяется 16) раз подряд. Если изобразить операцию L схематично так, как показано на рис. 33, то станет ясно, что после шестнадцатикратного применения преобразования R все байты преобразуемой последовательности изменят свои значения в результате преобразования С. На рис. 34 упрошены связи между состояниями R¹ и нс отражены связи так, как это показано на рис. 32 (однако они подразумеваются). На рис. 34 черными квадратиками выделены байты, которые изменяют свои значения в результате очередного применения преобразования С.

Так, чтобы выполнить преобразование.

необходимо выполнить 16 промежуточных итераций следующим образом:

Рис. 34. Преобразование L.

Ниже приведено несколько примеров выполнения преобразования L:

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

• — режим простой замены (ElcctronicCodcbook, ЕСВ);
• — режим гаммирования (Counter, CTR);

режим гаммирования с обратной связью по выходу (OutputFccdback, OFB);

• — режим простой замены с зацеплением (CipherBlockChaining, СВС);
• — режим гаммирования с обратной связью по шифртексту (CipherFeedback, CFB);
• — режим выработки имитовставки (Message Authentication Code algorithm).

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

Режимы блочного шифра выведены в отдельный проект национального стандарта «Информационная технология. Криптографическая защита информации. Режимы работы блочных шифров», что соответствует международной практике. Ожидается, что описанный блочный шифр с длиной блока 128 бит будет устойчив ко всем известным на сегодняшний день атакам на блочные шифры. Фиксация блоков нелинейной подстановки сделает алгоритм, описанный в стандарте ГОСТ 28 147–89, более унифицированным и поможет исключить использование «слабых» блоков нелинейной подстановки [12].