СПОСОБ НЕЛИНЕЙНОГО ТРЕХМЕРНОГО МНОГОРАУНДОВОГО ПРЕОБРАЗОВАНИЯ ДАННЫХ

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

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

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

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

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

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

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

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

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

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

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

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

Базовое стохастическое преобразование - n раундов произвольного блочного шифра, работающего с 64-разрядными блоками данных (примеры таких шифров - DES, ГОСТ 26147-89, Blowfish, Магма (ГОСТ Р 34.12-2015)). Величина n выбирается таким образом, чтобы соответствующее число раундов шифрования обеспечивали полное рассеивание и перемешивание информации (например, для ГОСТ 26147-89 n≥6).

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

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

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

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

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

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

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

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

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

разбиение 256-разрядного ключа на восемь 32-разрядных подключей;

выполнение 32-раундового преобразования;

при этом каждый i-й раунд, i=1, 2, …, 31, выполняется следующим образом:

происходит разбиение 64-разрядного входного блока на старшую L (Left) и младшую R (Right) половины; новые значения L и R вычисляются следующим образом: L=R, R=L XOR F(RK_i R), где RK_i - подключ i-го раунда, a F - раундовая функция;

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

происходит разбиение 64-разрядного входного блока на старшую L и младшую R половины; новые значения L и R вычисляются следующим образом: L=L XOR F(RK₃₂, R), R=R, где RK₃₂ - подключ 32-го раунда;

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

сложение 32-разрядного входного блока с раундовым подключом по модулю 2³²; замену с использованием восьми 4-разрядных элементов замены, циклический сдвиг на 11 разрядов влево.

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

Наиболее близким по своей технической сущности к заявленному способу нелинейного многораундового преобразования данных является принятый за прототип способ трехмерного преобразования данных 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, у, 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, каждый слой, 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) при выполнении преобразования рассматриваются как коэффициенты многочлена А(x) степени 3 над полем GF(2⁸), суть операции перемешивания строки - умножение по модулю х⁴+1 многочлена А(x) на многочлен 03х³+х²+х+02;

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

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

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

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

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

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

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

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

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

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

введение понятие слоя (Layer);

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

деление каждого i-го раундового ключа K_i (i=1, 2, 3) на раундовые подключи;

стохастическое преобразование (MixLayer) каждого слоя вдоль оси х, объединение преобразованных слоев в преобразованный блок S в первом раунде;

стохастическое преобразование (MixLayer) каждого слоя вдоль оси у, объединение преобразованных слоев в преобразованный блок S во втором раунде;

стохастическое преобразование (MixLayer) каждого слоя вдоль оси z, объединение преобразованных слоев в преобразованный блок S в третьем раунде;

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

все блоки данных представляются в виде кубического массива бит 8×8×8;

операции преобразования (перемешивания) слоя (MixLayer) реализуются в виде n итераций, при этом число итераций n должно обеспечивать полное рассеивание и перемешивание информации;

при выполнении преобразований первого раунда блок данных S делится на восемь слоев S_x0, S_x1, …, S_x7 вдоль оси x; каждый слой S_xk, k=0, 1, …, 7, условно представляется в виде квадратного массива битов 8×8, после чего подвергается преобразованию MixLayer, затем преобразованные слои объединяются в преобразованный блок S;

при выполнении преобразований второго раунда блок данных S делится на восемь слоев S_y0, S_y1, …, S_y7 вдоль оси у; каждый слой S_yk, k=0, 1, …, 7, условно представляется в виде квадратного массива битов 8×8, после чего подвергается преобразованию MixLayer, затем преобразованные слои объединяются в преобразованный блок S;

при выполнении преобразований третьего раунда блок данных S делится на восемь слоев S_z0, S_z1, …, S_z7 вдоль оси z, каждый слой S_zk, k=0, 1, …, 7, условно представляется в виде квадратного массива битов 8×8, после чего подвергается преобразованию MixLayer, затем преобразованные слои объединяются в преобразованный блок S;

выбирается секретная таблица замен размерностью 4×8×256 (в случае использования четырех 8-разрядных S-блоков) или 8×4×16 (в случае использования восьми 4-разрядных S-блоков);

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

каждый k-й подключ K_ik используется для преобразования соответствующего k-го слоя в i-м раунде (слоя S_ik);

каждый j-й подключ K_ikj - используется при выполнении j-й итерации (j=0, 1, …, (n-1)) преобразования соответствующего k-го слоя в i-м раунде.

L_RK - разрядность раундового ключа исходного 64-разрядного блочного шифра (разрядность раундового ключа исходного базового преобразования). Например, при использовании ГОСТ 28147-89, L_RK=32.

Каждая из n итераций преобразования MixLayer может являться раундом ГОСТ 28147-89, предполагающим деление входного 64-разрядного блока данных на левую L (Left) и правую R (Right) половины, последовательное выполнение операций Т=(R+SK)mod 2³², Т=S(T), Т=ROL¹¹ (T), Т=Т XOR L, L=R, R=Т, объединение новых значений L и R в преобразованный 64-разрядный блок данных, где Т (Temporary) - временная переменная, SK (SubKey) - 32-разрядный подключ, S() - операция замены (Substitution), ROL^m() - операция циклического сдвига влево (Rotate Left) на m разрядов, XOR - операция поразрядного сложения по модулю два.

Суть предлагаемого способа иллюстрируют фиг. 1-3.

На фиг. 1 показаны блок 1 данных (иначе говоря, формат состояния) и принцип разделения блока 1 данных на слои вдоль оси x, у, z и отдельные слои 2 S_xk, 3 S_yk, 4 S_zk блока данных, где S_1k=S_xk, S_2k=S_yk, S_3k=S_zk.

На фиг. 2 показан пример реализации преобразования перемешивания слоя MixLayer (базового стохастического преобразования) на основе преобразований ГОСТ 28147-89. На фиг. 2 показаны входной 5 слой блока данных, выходной (преобразованный) 6 слой блока данных; раундовые подключи K_ik0, K_ik1, …, K_ik(n-1) (соответственно 7_ik0, 7_ik1, …, 7_ik(n-1)); i=1, 2, 3, k=0, 1, …, 7; раунды (итерации) 8₁ 8₂, …, 8_n базового стохастического преобразования слоя; n (по числу итераций базового преобразования) блоков 9 выполнения операции XOR, n блоков 10 циклического сдвига на 11 разрядов влево, n блоков 11 замены, n блоков 12 сложения по модулю 2³², а, также условные графические обозначения блоков 9-12.

На фиг. 3 показана последовательность трехмерного преобразования на основе ГОСТ 28147-89 (далее 3DGOST). Для ГОСТ 28147-89 четное значение n должно удовлетворять условию n≥6. На фиг. 3 показаны исходный 512-разрядный блок 13 данных М; преобразованный 512-разрядный блок 14 данных С=3DGOST(M); ключ 15; раундовые ключи 7₁, 7₂, 7₃ (K₁ K₂, K₃), раундовые подключи 7₁₀, 7₁₁, …, 7₁₇ первого раунда (соответственно K₁₀, K₁₁, …, K₁₇), раундовые подключи 7₂₀, 7₂₁, …, 7₂₇ второго раунда (соответственно K₂₀, K₂₁, …, K₂₇), раундовые подключи 7₃₀, 7₃₁, …, 7₃₇ третьего раунда (соответственно K₃₀, K₃₁, …, K₃₇); операции 16 перешивания слоев Mixlayer (базовые стохастическое преобразования) - операции 16_х0, 16_х1, …, 16_x7 перемешивания слоев первого раунда (Mixlay-ersX), операции 16_y0, 16_y1, …, 16_у7 перемешивания слоев второго раунда (MixlayersY), операции 16_z0, 16_z1, …, 16_z7 перемешивания слоев третьего раунда (MixLayersZ); раундовые подключи 7_ik0, 7_ik1, …, 7_ik(n-1) (соответственно K_ik0, K_ik1, …, K_ik(n-1)), используемые при выполнении отдельных итераций 18 операции 16 MixLayer; операция 17 разворачивания ключа (Key Expansion); раунды (итерации) 18₁ 18₂, …, 18_n базового стохастического преобразования.

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

Основные идеи, лежащие в основе предлагаемого способа:

- представление входных и выходных блоков данных, всех промежуточных результатов преобразований и раундовых ключей в виде кубического массива бит 8×8×8 (фиг. 1);

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

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

- реализация каждой операции перемешивания слоя (MixLayer) на основе базового стохастического преобразования, в качестве которого используется n раундов 64-разрядного блочного шифра (фиг. 3). Последовательность преобразования блока 13 входных данных М размером 512 бит (8×8×8), имеющего структуру, показанную на фиг. 1:

1) первый раунд: разбиение получившегося блока данных на слои (Layers) 2 (S_x0, S_x1, …, S_x7) вдоль оси x (фиг. 1); преобразование перемешивания слоев (MixLayersX) S_x0, S_x1, …, S_x7 (соответственно операции 16_x0, 16_х1, …, 16_х7) путем выполнения для каждого слоя 2 базового стохастического преобразования (фиг. 2, 3);

2) второй раунд: разбиение получившегося блока данных на слои (Layers) 3 (S_y0, S_y1, …, S_y7) вдоль оси у (фиг. 1); преобразование перемешивания слоев (MixLayersX) S_y0, S_y1, …, S_y7 (соответственно операции 16_y0, 16_у1, …, 16_y7) путем выполнения для каждого слоя 3 базового стохастического преобразования (фиг. 2, 3);

3) третий раунд: разбиение получившегося блока данных на слои (Layers) 4 (S_z0, S_zl, …, S_z7) вдоль оси z (фиг. 1); преобразование перемешивания слоев (MixLayersX) S_z0, S_z1, …, S_z7 (соответственно операции 16_z0, 16_z1, …, 16_z7) путем выполнения для каждого слоя 4 базового стохастического преобразования (фиг. 2, 3).

Раундовые ключи 7₁ 7₂, 7₃ формируются с помощью процедуры 17 разворачивания исходного ключа (Key Expansion). Раундовые подключи 7₁₀ … 7₃₇ первого уровня (на фиг. 3) являются частью соответствующих раундовых ключей. Раундовые подключи 7₁₀ … 7₂₇ являются частью ключа 7₁ раундовые подключи 7₂₀ … 7₂₇ являются частью ключа 7₂, раундовые подключи 7₃₀ … 7₃₇ являются частью ключа 7₃.

>

где - операция конкатенации.

Раундовые подключи 7₁₀₀ … 7_10(n-1) являются частью ключа 7₁₀, раундовые подключи 7₁₁₀ … 7_11(n-1) являются частью ключа 7₁₁, … раундовые подключи 7₃₇₀ … 7_37(n-1) являются частью ключа 7₃₇ (фиг. 3).

Таким образом, последовательность трехмерного нелинейного много-раундового преобразования состоит из 24-х последовательно выполняемых операций MixLayer (фиг. 3):

- Преобразование 16_x0 слоя 2_x0 (MixLayer S_x0);

- Преобразование 16_x1 слоя 2_x1 (MixLayer S_x1);

- …

- Преобразование 16_x7 слоя 2_x7 (MixLayer S_x7);

- Преобразование 16_y0 слоя 3_у0 (MixLayer S_y0);

- Преобразование 16_y1 слоя 3_y1 (MixLayer S_y1);

- …

- Преобразование 16_y7 слоя 3_y7 (MixLayer S_y7);

- Преобразование 16_z0 слоя 4_z0 (MixLayer S_z0);

- Преобразование 16_z1 слоя 4_z1 (MixLayer S_z1);

- …

- Преобразование 16_z7 слоя 4_z7 (MixLayer S_z7).

В зависимости от шифра, на основе которого строится базовое стохастическое преобразование (БСП), возможны три ситуации:

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

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

3) Если в начале и в конце БСП присутствуют операции, зависящие от ключа, дополнительная операция сложения не требуется.

Учитывая, что в прототипе слоев в каждом раунде четыре, а в предлагаемом - восемь, а разрядности слоев соответственно находятся в соотношении 128/64, а значит операция MixLayer в прототипе сложнее, повышается быстродействие. Кроме того, особенностью предлагаемого решения является более высокая степень параллелизма на уровне элементарных преобразований за счет возможности параллельного выполнения операций MixLayer вдоль каждой из осей. Очевидно, что в пределах каждого раунда преобразования все восемь слоев могут быть обработаны параллельно, поэтому применение технологии CUDA позволит существенно упростить процесс разработки ПО.

Учитывая, что базовое стохастическое преобразование имеет разрядность 64, а результирующее - разрядность 64×8=512, повышается криптойкость результирующего преобразования, так как достигается 512-битовый уровень безопасности. Иначе говоря, предлагаемое решение позволит продлить жизнь многим качественным 64-разрядным криптоалгоритмам, не "дотягивающим" до требуемого сейчас 256-битного уровня безопасности для блочных шифров и 512-битного уровня безопасности для криптографических хеш-функций.