Шифр «Кузнечик» (ГОСТ Р 34. 12-2015) и режимы работы блочных шифров (ГОСТ Р 34. 13-2015)

Структура алгоритма «Кузнечик». Стандарт ГОСТ 34.12—2015 наряду с 64-битным шифром («Магма») определяет 128-битный алгоритм, получивший название «Кузнечик» («Kuznyechik»).

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

За счет преобразования всего блока данных на каждом шаге обеспечивается гораздо более быстрое перемешивание входных данных по сравнению со схемой Фейстеля. Кроме того, слой линейного преобразования конструируется таким образом, чтобы обеспечить максимально возможное рассеивание. Для этих целей используется так называемая MDS матрица (maximum distance separable) — применяемая в качестве линейного преобразования f (x): Fⁿ —? F^m матрица над конечным полем F, такая, что любые два вектора вида (x, f (x)) е F^n+m имеют как минимум т + 1 различа;

Рис. 2.51. Раунд шифрования алгоритма «Кузнечик».

ющихся компонент. Иными словами, набор векторов вида (x, f (x)) обладает свойством максимальной разнесенности. Поэтому адекватная стойкость таких алгоритмов достигается за меньшее, по сравнению со схемой Фейстеля, число раундов.

Как и в алгоритме AES, линейное преобразование алгоритма «Кузнечик» использует операции над полем Галуа GF (2⁸). SP-сети с линейным преобразованием, состоящим из двух частей, первая из которых похожа на операцию MixColumns, а вторая — на операцию ShiftRows алгоритма AES, называют AES-подобными (like AES). К этому типу алгоритмов относятся шифр «Кузнечик», а также основное преобразование хэш-функции ГОСТ Р 34.11—2012 «Стрибог».

Шифр «Кузнечик» имеет размер входного блока данных 128 бит, длину ключа 256 бит и выполняет 10 раундов шифрования, структура которых представлена на рис. 2.51. В последнем раунде выполняется только одна операция — наложение раундового ключа.

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

Затем входной 128-битовый блок а алгоритма шифрования представляется в виде последовательности 16 байтов, которые нумеруются справа налево, начиная с 0:

где значком || обозначена операция конкатенации строк.

К каждому байту применяется нелинейная подстановка, задаваемая массивом 5= (252, 238, 221, 17, 207, 110, 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).

Поскольку каждый байт a_t может принимать значение от 0 до 255, массив 5 имеет 256 элементов. Это значит, что при a_t = 0 значение а_} будет заменено на 5(0) = 252, при а_{= 1 — на 5(1) = 238 и т. д. (все числа записаны в десятеричном виде). Для входного блока в целом нелинейная подстановка может быть определена как.

Линейное перемешивание L шифра «Кузнечик» может быть описано с помощью линейного регистра сдвига R:

• 1) байты а- представляются в виде полиномов поля Галуа GF (2⁸). Для простоты обозначим их также а
• 2) вычисляется

где + и • — операции сложения и умножения над полем Галуа GT (2⁸) с неприводимым многочленом т (х) = х⁸ + х¹ + х⁶ + х + 1 (вычисления проводятся по модулю т (х)). a_t е GF (2⁸), числовые коэффициенты (записаны в десятеричном виде) могут быть представлены восьмиразрядными двоичными числами, которым соответствуют полиномы 7-й степени над GF (2⁸). Результат операции — полином 7-й степени, который может быть переведен обратно в восемь двоичных разрядов (байт);

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

4) шаги 1—3 повторяются 16 раз, при этом входом каждого следующего шага является выход предыдущего:

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

где К, — раундовые ключи; LSX[k] — последовательное применение операций побитового XOR с ключом k, нелинейной замены 5 и линейного перемешивания L.

Процедура расширения ключа алгоритма «Кузнечик». Раундовые ключи алгоритма «Кузнечик» имеют длину 128 бит. Первые два раундовых ключа (Kj и К₂) получаются разбиением исходного ключа К на две части. Далее для выработки каждой пары раундовых ключей используется 8-раундовый алгоритм со структурой Фейстеля (рис. 2.52), в котором функция раундового преобразования Fопределяется как последовательность преобразований LSX, а в качестве раундовых ключей используются итерацион;

Рис. 252. Получение пары ключей из предыдущей пары ные константы C_jy полученные как последовательность счетчиков, прошедшая линейное преобразование L:

где значение i представлено в виде 128-битовой строки; где

k, A_v А₀ являются 128-битовыми строками.

Структура процедуры расширения ключа в целом представлена на рис. 2.53.

Рис. 253. Процедура расширения ключа алгоритма «Кузнечик».

Процедура расшифрования алгоритма «Кузнечик». К сожалению, для SP-сети процедура расшифрования отличается от процедуры шифрования. Для алгоритма «Кузнечик» процедура расшифрования может быть записана как.

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

Операция побитового XOR обратна сама себе, операция 5 ¹ может быть представлена как нелинейная подстановка с помощью массива, задающего преобразование, обратное S. Иными словами, операция 5 ¹ совпадает с 5 с точностью до массива замен.

Операция L ¹ может быть задана как L '(a) = (R ')^|6(й). В свою очередь,.

R '(а) = R '(«jsll…||<2₀) ^{= а}Л^й1з11−11^йо11 ^f(^ai4> ^й1з> ???> ^йо> ^я1з)> ^т-^е- совпадает с R с точностью до направления сдвига (порядка следования байтов в результирующей строке) и операндов преобразования /.

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

Режимы работы блочных шифров (ГОСТ Р 34.13—2015). Стандарт ГОСТ Р 34.13—2015 «Информационная технология. Криптографическая защита информации. Режимы работы блочных шифров» является адаптированной под нужды отечественной криптографии версией международных стандартов 1SO/IEC 10 116:2006 Information technology — Security techniques — Modes of operation for an n-bit block cipher (Информационные технологии. Методы обеспечения безопасности. Режимы работы для га-битовых блочных шифров) и ISO/IEC 9797−1:2011 Information technology — Security techniques — Message Authentication Codes (MACs) — Part 1: Mechanisms using a block cipher (Информационные технологии. Методы защиты. Коды аутентификации сообщений (MAC). Часть 1. Механизмы, использующие блочный шифр). ГОСТ Р 34.13—2015 определяет шесть режимов работы алгоритмов блочного шифрования с произвольной длиной входного блока п:

• • режим простой замены (Electronic Codebook, ЕСВ);
• • режим гаммирования (Counter, CTR);
• • режим гаммирования с обратной связью по выходу (Output Feedback, OFB);
• • режим простой замены с зацеплением (Cipher Block Chaining, СВС);
• • режим гаммирования с обратной связью по шифротексту (Cipher Feedback, CFB);
• • режим выработки имитовставки (Message Authentication Code algorithm).

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

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

Стандарт ГОСТ Р 34.13—2015 описывает три варианта процедуры дополнения, один из которых рекомендован исключительно для использования в режиме выработки имитовставки.

Первый вариант предполагает дополнение неполного блока справа нулями. Пусть |X|mod/? = г, X — открытый текст в двоичном представлении, тогда.

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

Второй вариант предполагает, что справа к открытому тексту X (в двоичном представлении) всегда приписывается едница, а затем нули так, чтобы последний блок имел полный размер п:

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

Режим простой замены полностью аналогичен одноименному режиму ГОСТ 28 147–89 и рассмотренному ранее режиму ЕСВ. Все блоки шифруются и расшифровываются независимо друг от друга.

В режиме простой замены с зацеплением используется двоичный регистр сдвига R длины т, т — nz, z > 1 — целое число. Начальным заполнением регистра является значение синхропосылки IV. Очередной блок шифротекста получается путем зашифрования результата побитового XOR значения очередного блока открытого текста М- со значением п старших разрядов регистра сдвига. Затем регистр R сдвигается влево на один блок (п бит). В младшие разряды записывается значение блока шифротекста (рис. 2.54).

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

Рис. 2.54. Шифрование в режиме простой замены с зацеплением.

Рис. 2.55. Расшифрование в режиме простой замены с зацеплением.

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

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

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

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

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

Начальное значение счетчика получается как значение IV, дополненное справа нулями до полной длины блока п CTR,= IV|| 0^Я/2. Последующие значения счетчика получаются сложением целочисленного значения счетчика по модулю 2^я с единицей: CTR, = (CTR._j + 1) mod2^я.

Режим гаммирования с обратной связью по выходу несколько отличается от ранее описанного режима OFB западных блочных шифров (рис. 2.56). В этом режиме используется двоичный регистр сдвига R длины т, т = nz, 2 > 1 — целое число. Начальным заполнением регистра г является значение синхропосылки IV длиной т. Значение сиихропосылки должно быть непредсказуемым (случайным или псевдослучайным) либо уникальным.

Старшие п бит регистра сдвига шифруются, затем s старших битов результата шифрования Y. используются в качестве гаммы шифра О_г На следующем шаге регистр R сдвигается влево на п бит, а в область младших битов записывается /2-битовое значение Y-.

Режим гаммирования с обратной связью, но шифротексту похож на режим CFB западных блочных шифров (рис. 2.57). Режим использует двоичный регистр сдвига R длины т, т>п. Начальным заполнением регистра является значение сиихропосылки IV.

Рис. 2.56. Режим гаммирования с обратной связью по выходу (ГОСТ Р 3/1.13−2015).

Рис. 2.57. Режим гаммирования с обратной связью по шифротексту (ГОСТ Р 34.13−2015).

При вычислении очередного блока гаммы О, выполняется шифрование п старших разрядов регистра сдвига R с последующим выбором s старших битов результата шифрования К Затем регистр R сдвигается влево на s разрядов, а в область младших битов записывается полученный блок шифротекста.

Режим выработки имитовставки реализует конструкцию ОМАС1, которая приведена в международном стандарте ISO/IEC 9797−1:2011 под названием СМАС. Режим позволяет вырабатывать имитовставку произвольной длины 5, 0 < s < п.

Шифрование в режиме выработки имитовставки выполняется блоками полной длины п. Поэтому в случае неполного последнего блока (|X|modw = г, г < п) он дополняется до полной длины с помощью второй из процедур дополнения (справа приписывается единица и затем нули). Если длина последнего блока открытого текста совпадает с п, дополнение не выполняется.

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

Поскольку стандартом ГОСТ Р 34.12—2015 определены два блочных шифра с длиной блока 64 и 128 бит, приведена процедура формирования вспомогательных ключей для этих значений п:

• 1) сначала вычисляется значение R, являющееся результатом шифрования нулевой строки длины п базовым алгоритмом шифрования на основном ключе К — R = Е_к(0″);
• 2) значение К_г вычисляется как R 1, если старший бит R равен нулю, и как (R 1) © В_Г1 — в противном случае. Здесь операция 1 обозначает логический сдвиг битовой строки влево на одну позицию — строка сдвигается влево на один бит и дополняется справа нулем;
• 3) значение К₂ вычисляется как К_{ 1, если старший бит К_{ равен нулю,

и как (К_х 1) ® В_п — в противном случае. Константы B_6i = О⁵⁹1| 11 011, В₁₂₈ =

= О¹²⁰1| 10 000 111. Стандарт также описывает процедуру получения констант В_Г1 для других значений п.

Необходимо обеспечивать конфиденциальность вспомогательных ключей K_v К._} и значения R, которые наряду с основным ключом К являются секретными параметрами криптосистемы.

Режим выработки имитовставки в целом совпадает с одноименным режимом ГОСТ 28 147–89, за исключения процедуры формирования последнего блока, в которой используется дополнительный ключ.

Имитовставка формируется следующим образом (рис. 2.58):

где q — число блоков открытого текста; X* — последний блок открытого текста после процедуры дополнения (если она требуется), в качестве дополнительного ключа К* используется K_v если последний блок имеет полную длину X_q = п и не требует дополнения, или К₂ — в противном случае (| Х_ч-г<�п).

Рис. 2.58. Выработка имитовставки (MAC)

Значением имитовставки (MAC) являются 5 старших битов последнего сформированного блока Y_q.

Процедура выработки имитовставки похожа на шифрование в режиме простой замены с зацеплением при размере сдвигового регистра т = п и его начальном значении 0″ .