Результат интеллектуальной деятельности: СПОСОБ НЕЛИНЕЙНОГО ТРЕХМЕРНОГО МНОГОРАУНДОВОГО ПРЕОБРАЗОВАНИЯ ДАННЫХ RDOZEN

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

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

Стохастическое преобразование - непредсказуемое преобразование данных; примером стохастического преобразования может являться криптографическое преобразование;

Генератор псевдослучайных чисел - генератор последовательности чисел, статистически неотличимой от последовательности случайных чисел с равномерным законом распределения; наиболее жесткие требования предъявляются к ГПСЧ, ориентированным на решение задач криптографической защиты информации;

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

Подключ - часть ключа;

Раунд - последовательность шагов, образующих одну итерацию итеративного (многораундового) преобразования;

Раундовый ключ (RoundKey) - ключевая информация, использующаяся при выполнении одного раунда преобразования, существует два способа формирования раундовых ключей: раундовый ключ может являться частью секретного ключа (пример - Российский стандарт криптозащиты ГОСТ 28147-89), последовательность раундовых ключей может получаться в результате работы процедуры разворачивания исходного ключа (пример - американский стандарт криптозащиты AES);

Раундовый подключ - часть раундового ключа;

Двоичный вектор - некоторая последовательность нулевых и единичных бит, например (01101010), двоичный вектор разрядности n может быть интерпретирован как элемент конечного поля GF(2ⁿ);

Замена (Substitution) - операция, выполняемая над двоичным вектором i ∈ GF(2ⁿ), при этом результат операции равен содержимому ячейки с индексом i таблицы замен размерности n×2ⁿ;

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

Важнейшим элементом любой системы защиты информации (СЗИ) являются ГПСЧ. Функциями ГПСЧ СЗИ являются:

- генерация ключевой информации и паролей пользователей;

- формирование гаммы при поточном шифровании данных;

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

- внесение неопределенности в работу средств и объектов защиты и др.

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

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

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

Известен способ нелинейного многораундового 3D-преобразования данных [Иванов М.А., Ковалев А.В., Чугунков И.В. и др. Стохастические методы защиты информации в компьютерных системах и сетях. М.: Кудиц-Пресс, 2009, с. 243-246], который включает:

формирование ключа, в качестве которого выступает содержимое таблицы стохастического преобразования H размерностью 8×256;

представление входного, выходного блоков данных, всех промежуточных результатов преобразования в виде кубического массива байтов 4×4×4;

выполнение над входным блоком М разрядностью 512 бит трех раундов трехмерного преобразования соответственно вдоль осей x, у, z;

введение понятие слоя (Layer) - квадратного массива байтов 4×4.

При выполнении преобразований первого раунда блок данных S делится на 4 слоя L_x0, L_x1, L_x2, L_x3 вдоль оси x, каждый слой L_xk, k=0, 1, 2, 3, представляется в виде квадратного массива байтов 4×4, после чего подвергается двумерному преобразованию T_Layer, зависящему от содержимого секретной таблицы Н; преобразованные слои объединяются в преобразованный блок S.

При выполнении преобразований второго раунда блок данных S делится на 4 слоя L_y0, L_y1, L_y2, L_y3 вдоль оси x, каждый слой L_yk, k=0, 1, 2, 3, представляется в виде квадратного массива байтов 4×4, после чего подвергается двумерному преобразованию T_Layer, зависящему от содержимого секретной таблицы Н; преобразованные слои объединяются в преобразованный блок S.

При выполнении преобразований третьего раунда блок данных S делится на 4 слоя L_z0, L_z1, L_z2, L_z3 вдоль оси x, каждый слой L_zk, k=0, 1, 2, 3, представляется в виде квадратного массива байтов 4×4, после чего подвергается двумерному преобразованию T_Layer, зависящему от содержимого секретной таблицы Н; преобразованные слои объединяются в преобразованный блок S.

В состав операции двумерного преобразования T_Layer слоя L включаются два шага: перемешивание строк (MixRows) и перемешивание столбцов (MixColumns).

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

- слой L разбивается на 4 строки;

- каждая k-ая строка (k=0, 1, 2, 3) перешивается с использованием стохастического сумматора, логика работы которого определяется содержимым ключевой таблицы H;

- перемешанные строки объединяются в преобразованный слой L.

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

- слой L разбивается на 4 столбца;

- каждый k-й столбец (k=0, 1, 2, 3) перешивается с использованием стохастического сумматора, логика работы которого определяется содержимым ключевой таблицы Н;

- перемешанные столбцы объединяются в преобразованный слой L.

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

Наиболее близким по своей технической сущности к заявленному способу нелинейного многораундового преобразования данных является принятый за прототип способ трехмерного преобразования данных DOZEN (Патент РФ на изобретение №2503994). Это преобразование включает:

представление входного, выходного блоков данных, всех промежуточных результатов преобразования в виде кубического массива байтов 4×4×4;

введение понятие слоя (Layer) - квадратного массива байтов 4×4;

формирование из исходного ключа последовательности раундовых ключей K₀, K₁, K₂, K₃ разрядностью 512 бит каждый и секретной таблицы замен размерностью 8×256;

формирование по входному блоку М разрядностью 512 бит блока данных S той же разрядности в соответствии с выражением S:=М, после чего выполняется начальное поразрядное сложение по модулю двух (XOR) блоков S и раундового ключа (AddRoundKey) K₀ в соответствии с выражением S:=S⊕K₀, после чего выполняются 3 раунда преобразования вдоль осей x, y, z;

каждый i-й раундовый ключ K_i (i=1, 2, 3) делится на четыре раундовых подключа K_i0, K_i1, K_i2, K_i3 разрядностью 128 бит каждый;

раундовые подключи K_i0, K_i1, K_i2, K_i3 представляются в виде квадратного массива байтов 4×4;

при выполнении преобразований первого раунда блок данных S делится на 4 слоя L_x0, L_x1, L_x2, L_x3 вдоль оси x; каждый слой L_xk, k=0, 1, 2, 3, представляется в виде квадратного массива байтов 4×4, после чего подвергается двумерному преобразованию T_Layer, после чего преобразованные слои объединяются в преобразованный блок S;

при выполнении преобразований второго раунда блок данных S делится на 4 слоя L_y0, L_y1, L_y2, L_y3 вдоль оси x; каждый слой L_yk, k=0, 1, 2, 3, представляется в виде квадратного массива байтов 4×4, после чего подвергается двумерному преобразованию T_Layer, после чего преобразованные слои объединяются в преобразованный блок S;

при выполнении преобразований третьего раунда блок данных S делится на 4 слоя L_z0, L_z1, L_z2, L_z3 вдоль оси x, каждый слой L_zk, k=0, 1, 2, 3, представляется в виде квадратного массива байтов 4×4, после чего подвергается двумерному преобразованию T_Layer, после чего преобразованные слои объединяются в преобразованный блок S.

В состав операции двумерного преобразования T_Layer слоя L включаются четыре последовательно выполняемых шага - замены байтов (SubBytes), перемешивания строк (MixRows), перемешивания столбцов (MixColumns) и сложения (XOR) с соответствующим раундовым подключом (AddRoundSubKey) K_ik.

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

- слой L разбивается на 16 байтов, каждый байт заменяется байтом из фиксированной таблицы замен размерностью 8×256;

- выбранные из таблицы замен 16 байтов объединяются в преобразованный слой L.

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

- слой L разбивается на 4 строки;

- байты каждой k-й строки (k=0, 1, 2, 3) при выполнении преобразования рассматриваются как коэффициенты многочлена А(х) степени 3 над полем GF(2⁸), суть операции перемешивания строки - умножение по модулю х⁴+1 многочлена А(х) на многочлен 03х³+х²+х+02;

- перемешанные строки объединяются в преобразованный слой L.

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

- слой L разбивается на 4 столбца;

- байты каждого k-го столбца (k=0, 1, 2, 3) при выполнении преобразования рассматриваются как коэффициенты многочлена А(х) степени 3 над полем GF(2⁸), суть операции перемешивания столбца - умножение по модулю х⁴+1 многочлена А(х) на многочлен 03х³+х²+х+02;

- перемешанные столбцы объединяются в преобразованный слой L.

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

К причинам, препятствующим достижению указанного ниже результата, относится сложность перехода при программной реализации от преобразований T_Layers, выполняемых вдоль оси x, к преобразованиям T_Layers, выполняемых вдоль оси y, а затем к преобразованиям T_Layers, выполняемых вдоль оси z. При аппаратной реализации преобразования DOZEN эти переходы осуществляются обычными перемычками, т.е. не требуют дополнительных затрат времени на их реализацию. При программной же реализации преобразования DOZEN ситуация прямо противоположная - требуются недопустимо большие временные затраты на реализацию таких переходов.

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

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

представление входного, выходного блоков данных, всех промежуточных результатов преобразования в виде кубического массива байтов 4×4×4;

формирование последовательности раундовых ключей K₀, K₁, K₂, K₃ разрядностью 512 бит каждый;

введение понятие слоя (Layer) - квадратного массива байтов 4×4;

формирование по входному блоку М разрядностью 512 бит блока данных S той же разрядности в соответствии с выражением S:=М, после чего выполнение начального поразрядного сложения по модулю двух (XOR) блоков S и раундового ключа (AddRoundKey) K₀ в соответствии с выражением S:=S⊕K₀, после чего выполняются 3 раунда преобразования;

деление каждого i-го раундового ключа K_i (i=1, 2, 3) на четыре раундовых подключа K_i0, K_i1, K_i2, K_i3 разрядностью 128 бит каждый;

представление раундовых подключей K_i0, K_i1, K_i2, K_i3 в виде квадратного массива байтов 4×4;

при выполнении преобразований первого раунда деление блока данных S на 4 слоя L_x0, L_x1, L_x2, L_x3 вдоль оси x; представление каждого слоя L_xk, k=0, 1, 2, 3, в виде квадратного массива байтов 4×4, двумерное стохастическое преобразование T_Layer каждого слоя L_xk, объединение слоев L_xk в преобразованный блок S;

включение в состав операции преобразования слоя (T_Layer) операций замены байтов (SubBytes) и сложения (XOR) с соответствующим раундовым подключом (AddRoundSubKey) K_xk;

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

- слой L разбивается на 16 байтов, каждый байт заменяется байтом из таблицы замен размерностью 8×256;

- выбранные из таблицы замен 16 байтов объединяются в преобразованный слой L;

дополнительно

второй и третий раунды выполняются аналогично первому: при выполнении преобразований второго и третьего раунда осуществляется деление блока данных S на 4 слоя L_x0, L_x1, L_x2, L_x3 вдоль оси x; каждый слой L_xk, k=0, 1, 2, 3, представляется в виде квадратного массива байтов 4×4, после чего происходит двумерное стохастическое преобразование T_Layer каждого слоя L_xk, объединение слоев L_xk в преобразованный блок S;

между первым и вторым раундами, а также между вторым и третьим раундами выполняется преобразование перестановки байтов PermBytes;

при выполнении преобразования T_Layer последовательно выполняются операции замены байтов SubBytes, перемешивания байтов состояния MixState и сложения с раундовым подключом AddRoundSubKey;

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

- слой L разбивается на 16 байтов;

- суть операции перемешивания байтов состояния - умножение строки байтов состояния на квадратную матрицу 16×16, при этом все операции умножения и сложения элементов строки и матрицы осуществляются в поле GF(2⁸);

- перемешанные байты объединяются в преобразованный слой L.

Суть предлагаемого способа иллюстрируют фиг. 1-5. На фиг. 1 показаны блок данных (по сути, формат состояния) и отдельный байт блока данных. На фиг. 2 показан принцип разделения блока данных на слои вдоль оси x и отдельные слои L_xk. На фиг. 3 показана последовательность выполнения преобразования RDOZEN. На фиг. 4 показан пример реализации операции PermState. На фиг. 5 показана схема алгоритма возможного варианта реализации операции PermBytes.

На фиг. 1-3 показаны входной 1 и выходной 2 блоки данных; раундовые ключи K₀, K₁, K₂, K₃ (соответственно 3₀, 3₁, 3₂, 3₃); раундовые подключи K_i0, K_i1, K_i2, K_i3 (соответственно 3_i0, 3_i1, 3_i2, 3_i3), i=1, 2, 3; слои L_x0, L_x1, L_x2, L_x3 (соответственно 4_x0, 4_x1, 4_x2, 4_х3) вдоль оси x, операции 5_x0, 5_x1, 5_x2, 5_x3 преобразования слоев (T_Layers) вдоль оси x; операции 6₁ и 6₂ перемешивания байтов состояния (PermBytes), зависящие соответственно от ключей 7₁ и 7₂ перемешивания. В состав операции преобразования слоя (T_Layer) входят последовательно выполняемые операции замены 9 байтов слоя (SubBytes), перемешивания 10 состояния (MixState) слоя, сложения 11 (XOR) с раундовым подключом (AddRoundSubKey). На фиг. 4 показаны 8-разрядный счетчик 11, сумматор 12 по модулю 256, 8-разрядный регистр 13, байты 14₀, 14₁, …, 14₆₃ состояния слоя. Показаны также байты 7₀, 7₁, …, 7₆₃ ключа 7₁ или 7₂.

Рассмотрим предлагаемое трехмерное многораундовое преобразование с архитектурой Куб, получившее название RDOZEN, которое может использоваться в качестве нелинейной функции ГПСЧ (функции выхода в случае использования режима CTR или функции обратной связи в случае использования режима OFB).

Основные идеи, лежащие в основе проекта:

- представление входных 1 и выходных 2 блоков данных, всех промежуточных результатов S преобразований и раундовых ключей (RoundKeys) K₀, K₁, K₂, K₃ (3₀, 3₁, 3₂, 3₃) в виде кубического массива байтов 4×4×4 (фиг. 1);

- определение понятия слоя 4 (Layer) - квадратного массива байтов 4×4 (фиг. 2);

- представление i-го раундового ключа в виде четырех подключей (RoundSubKeys) K_i0, K_i1, K_i2, K_i3 (3_i0, 3_i1, 3_i2, 3_i3), i=1, 2, 3, каждый из которых суть квадратный массив байтов 4×4;

- представление каждого из ключей 7₁ и 7₂ перемешивания в виде последовательности байтов, соответственно 7_1.0, 7_1.1, …, 7_1.63 и 7_2.0, 7_2.1, …, 7_2.63 (фиг. 4);

- трехкратное преобразование блока данных по слоям вдоль оси x, между которыми выполняется операция перемешивания байтов 6 состояния (PermBytes) (фиг. 3);

- включение в состав операции двухмерного преобразования слоя (T_Layer) 5 трех шагов - замены 9 байтов (SubBytes), перемешивания 10 состояния слоя (MixState), сложения (XOR) 11 с раундовым подключом (AddRoundSubKey) (фиг. 3).

Операция перестановки 6 байт состояния (PermBytes) может быть фиксированной, а может зависеть от ключевой информации. Именно второй вариант изображен на рис. 3 и 4.

Операция перемешивания 10 состояния слоя (MixState) может быть полностью аналогичной, например, линейному преобразованию L блочного шифра Кузнечик, специфицированному в ГОСТ Р 34.12-2015 «Информационная технология. Криптографическая защита информации. Блочные шифры» (далее просто новый ГОСТ), который утвержден в 2015 году и вступает в действие с 1 января 2016 года. Суть преобразования - 16 тактов работы последовательного ГПСЧ, функционирующего в конечном поле GF(2⁸), примитивный элемент а которого является корнем многочлена . Пусть a - 128-разрядное состояние слоя, а ₁₅, …, а ₀ - байты слоя, тогда линейное преобразование L определяется следующими выражениями:

,

где - базовое линейное преобразование:

Если реализовать параллельный ГПСЧ (при индексе децимации, равном 16), то в результате преобразование L выполняется за один такт. В этом случае суть операции перемешивания байтов состояния заключается в умножении строки байтов состояния на квадратную матрицу 16×16, элементы которой определяются коэффициентами базового линейного преобразования , при этом все операции умножения и сложения элементов строки и матрицы осуществляются в поле GF(2⁸).

Последовательность преобразования (фиг. 3) блока 1 данных М размером 512 бит (4×4×4×8), имеющего структуру, показанную на фиг. 1, где a _x,y,z, x=0, 1, 2, 3, y=0, 1, 2, 3, z=0, 1, 2, 3, - байты:

1) сложение 8 (XOR) блока 1 данных с раундовым 3₀ ключом K₀;

2) первый раунд: разбиение получившегося блока данных на слои (Layers) L_x0, L_x1, L_x2, L_x3 (соответственно 4_x0, 4_x1, 4_x2, 4_х3) вдоль оси x (фиг. 2); двухмерное стохастическое преобразование слоев (T_Layer) L_x0, L_x1, L_x2, L_x3 (соответственно операции 5_x0, 5_x1, 5_x2, 5_x3) путем выполнения для каждого слоя L_xk 4_хк шестнадцати (по числу байтов) операций 9 SubByte, операции 10 MixState и операции 11 AddRoundSubKey;

3) подготовка к выполнению второго раунда - формирование нового «псевдокуба», т.е. нового блока данных размером 512 бит (4×4×4×8), имеющего структуру, показанную на фиг. 1, с иным разбиением на столбцы, строки и слои;

4) второй раунд (полностью аналогичный первому): разбиение получившегося блока данных вновь на слои (Layers) L_x0, L_x1, L_x2, L_x3 (соответственно 4_x0, 4_x1, 4_x2, 4_x3) вдоль оси x (фиг. 2); двухмерное стохастическое преобразование слоев (T_Layer) L_x0, L_x1, L_x2, L_x3 (соответственно операции 5_x0, 5_х1, 5_х2, 5_х3) (фиг. 3);

5) подготовка к выполнению третьего раунда - формирование нового «псевдокуба», т.е. нового блока данных размером 512 бит (4×4×4×8), имеющего структуру, показанную на фиг. 1, с иным разбиением на столбцы, строки и слои;

6) третий раунд (полностью аналогичный первому и второму): разбиение получившегося блока данных вновь на слои (Layers) L_x0, L_x1, L_x2, L_x3 (соответственно 4_x0, 4_x1, 4_x2, 4_x3) вдоль оси x (фиг. 2); двухмерное стохастическое преобразование слоев (T_Layer) L_x0, L_x1, L_x2, L_x3 (соответственно операции 5_x0, 5_x1, 5_x2, 5_x3) (фиг. 3).

Раундовые ключи 3₀, 3₁, 3₂, 3₃ и ключи 7₁ и 7₂ перемешивания являются либо элементами исходного ключа, как это происходит в преобразовании, задаваемом шифром Магма, специфицированному в ГОСТ Р 34.12-2015, либо формируются с помощью процедуры разворачивания исходного ключа, подобно тому, как это происходит в преобразовании, задаваемом шифром Кузнечик, специфицированному там же.

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

- Сложение 8 с раундовым ключом 3₀ (AddRoundKey K₀);

- Преобразование 5_х0 слоя 4_х0 (T_Layer L_x0);

- Преобразование 5_x1 слоя 4_x1 (T_Layer L_x1);

- Преобразование 5_х2 слоя 4_х2 (T_Layer L_x2);

- Преобразование 5_x3 слоя 4_x3 (T_Layer L_x3);

- Перестановка байт состояния (PermBytes);

- Преобразование 5_x0 слоя 4_x0 (T_Layer L_x0);

- Преобразование 5_x1 слоя 4_x1 (T_Layer L_x1);

- Преобразование 5_х2 слоя 4_x2 (T_Layer L_x2);

- Преобразование 5_x3 слоя 4_x3 (T_Layer L_x3);

- Перестановка байт состояния (PermBytes);

- Преобразование 5_x0 слоя 4_х0 (T_Layer L_x0);

- Преобразование 5_x1 слоя 4_x1 (T_Layer L_x1);

- Преобразование 5_x2 слоя 4_x2 (T_Layer L_x2);

- Преобразование 5_х3 слоя 4_х3 (T_Layer L_x3).

Особенностью предлагаемого решения является высокая степень параллелизма на уровне элементарных преобразований за счет возможности параллельного выполнения операций T_Layer. При этом операция преобразования слоя T_Layer по сравнению с прототипом является более криптостойкой и допускает более эффективную программную реализацию. За счет исключения переходов от преобразований T_Layers, выполняемых вдоль оси x, к преобразованиям T_Layers, выполняемых вдоль оси y, а затем к преобразованиям T_Layers, выполняемых вдоль оси z, также повышается быстродействие алгоритма при его программной реализации, так как вместо преобразований перешивания слоев последовательно вдоль осей x, y, z трижды выполняется однотипное преобразование слоев вдоль оси x, между которыми осуществляется операция формирования нового состояния путем перестановки его байтов.

На фиг. 4 показан пример быстродействующей реализации операции перестановки байт, аналогичной применяемой в поточном шифре RC4. Пусть PKey[i] - i-й байт 7_i ключа 7 перестановки, S[i] - i-й байт 14 г состояния 14 (промежуточному результату вычислений перед выполнением операции PermBytes), тогда последовательность перемешивания может быть описана следующим образом:

Инициализация переменной j:j=0;

Для ∀i=0, 1, …, 63

вычисление: j=(j+S[i]+PKey[i]) mod 64;

перестановка байт состояния: S[i]↔S[j].

На фиг. 5 показана схема алгоритма выполнения операции PermBytes.

Очевидно, что в пределах каждого раунда работы RDOZEN все слои могут быть обработаны параллельно, а применение технологии CUDA позволит существенно упростить процесс разработки ПО на основе алгоритма RDOZEN. Алгоритм допускает эффективную программную реализацию за счет (1) исключения обработки слоев последовательно вдоль трех осей x, y, z и (2) использования быстродействующих операций MixState и PermBytes.