Способ нелинейного трехмерного многораундового преобразования данных dozen

Способ нелинейного трехмерного многораундового преобразования данных dozen

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Известен ГПСЧ, функционирующий в конечных полях GF(2ⁿ) [Иванов М.А. Генератор псевдослучайных последовательностей. Авторское свидетельство СССР №1465885. - БИ, 1989, №10]. Генератор может использоваться в задачах криптографической защиты информации только в качестве элементарного строительного блока при построении более сложных нелинейных устройств.

На практике используются две разновидности ГПСЧ - схема OFB (Output Feedback - обратная связь по выходу), когда качество генератора определяется нелинейной функцией обратной связи, и двухступенчатая схема CTR, когда первая ступень (счетчик) обеспечивает максимальный период формируемой последовательности, а качество генератора определяется нелинейной функцией выхода второй ступени [Иванов М.А., Ковалев А.В., Чугунков И.В. и др. Стохастические методы защиты информации в компьютерных системах и сетях. - М.: Кудиц-Пресс, 2009].

Известен способ нелинейного многораундового преобразования данных, описанный в Российском стандарте криптографической защиты информации [Стандарт СССР ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования]. Способ аналог включает в себя формирование ключа в виде последовательности из 8 подключей длиной 32 бита. Перед преобразованием 64-разрядный блок данных разбивается на два 32-разрядного подблока L и R, которые поочередно преобразуются путем выполнения 32 раундов преобразования. Один раунд преобразования заключается в следующем. По подблоку L формируется двоичный вектор F в соответствии с выражением F:=L, который преобразуется в зависимости от одного из подключей в соответствии с раундовой функцией преобразования Е. Преобразование двоичного вектора на i-м раунде записывается в виде F:=E(F, K_i), где K_i - подключ, используемый на i-м раунде. Полученное значение F:=E(F, K_i) поразрядно суммируется по модулю два ⊕ с подблоком R в соответствии с выражением R:=R⊕F. Вычисление раундовой функции E(F, К_i) осуществляется в соответствии со следующими шагами преобразования. Первоначально сформированный двоичный вектор F:=L преобразуется путем наложения на него текущего подключа К_i, являющегося фиксированным для данного раунда, с помощью операции сложения по модулю 2³² в соответствии с формулой F:=(F+К,) mod 2³², после чего над двоичным вектором F выполняют операцию замены F:=S(F), затем операцию циклического сдвига влево (в сторону старших разрядов) на 11 разрядов F:=F <<<11. После каждого раунда шифрования, за исключением последнего, подблоки переставляются. Операция замены выполняется следующим образом. Двоичный вектор F разбивается на 8 двоичных векторов длиной по 4 бит каждый. Каждый 4-разрядный двоичный вектор заменяется двоичным вектором из соответствующей таблицы замен. Выбранные из таблиц замен восемь 4-разрядных векторов объединяются в преобразованный двоичный вектор F.

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

Одним из путей решения проблемы построения качественного генератора является использование гибридных вычислительных технологий при программной реализации ГПСЧ. Наиболее подходящей для реализации на GPU является архитектура Квадрат, предложенная авторами криптоалгоритмов Square и Rijndael, при этом последний в 2001 г. победил в конкурсе на принятие нового Американского стандарта криптозащиты AES (Advanced Encryption Standard).

Известен способ нелинейного многораундового 2D-преобразования, описанный в версии стандарта AES-128 [Daemen J., Rijmen V. AES Proposal: Rijndael. URL: ammended.pdf или Иванов M.A., Ковалев А.В., Чугунков И.В. и др. Стохастические методы защиты информации в компьютерных системах и сетях. М.: Кудиц-Пресс, 2009, с.241]. В данном способе все входные и выходные блоки данных, все промежуточные результаты преобразований, все раундовые ключи представляются в виде квадратного массива S байтов 4×4, таким образом, разрядность всех блоков данных равна 128 битам. Преобразование выполняется путем формирования из секретного ключа с помощью процедуры разворачивания ключа последовательности раундовых ключей K₀, K₁…, K_R, где R - число раундов преобразования. По входному блоку М формируется блок 5 в соответствии с выражением S:=М. Затем выполняется операция начального поразрядного сложения по модулю два (XOR) блока S и раундового ключа (AddRoundKey) K₀ в соответствии с выражением S:=S⊕K₀, после чего выполняются R раундов преобразования. В состав каждого i-го раунда кроме последнего входят последовательно выполняемые преобразования замены байтов (SubBytes) S:=SubBytes(S), циклического сдвига строк (ShiftRows) S:=ShiftRows(S), перемешивания столбцов (MixColumns) S:=MixColunms(S) и сложения по модулю два (XOR) с раундовым ключом (AddRoundKey) К, в соответствии с выражением S:=S⊕K_i. В состав последнего раунда входят последовательно выполняемые преобразования замены байтов (SubBytes), циклического сдвига строк (ShiftRows) и сложения (XOR) с раундовым ключом (AddRoundKey) K_R. Операция замены байтов SubBytes выполняется следующим образом. Блок S разбивается на 16 байтов. Каждый байт заменяется байтом из фиксированной таблицы замен размерностью 8×256. Выбранные из таблицы замен 16 байтов объединяются в преобразованный блок S. Операция сдвига строк (ShiftRows) выполняется следующим образом. Блок S разбивается на 4 строки. Каждая i-я строка (i=0, 1, 2, 3) циклически сдвигается на i байтов. Сдвинутые строки объединяются в преобразованный блок S. Операция перемешивания столбцов (MixColumns) выполняется следующим образом. Блок S разбивается на 4 столбца. При выполнении преобразования MixColumns байты столбца рассматриваются как коэффициенты многочлена А(х) степени 3 над полем GF(2⁸). Суть операции перемешивания столбца - умножение по модулю х⁴+1 многочлена А(х) на многочлен 03x³+х²+х+02. Перемешанные столбцы объединяются в преобразованный блок S.

Таким образом, последовательность 10-раундового преобразования AES-128 имеет следующий вид: начальный шаг сложения с раундовым ключом, 9 раундов, каждый из которых состоит из четырех шагов (замены байтов, циклического сдвига строк, перемешивания столбцов и сложения с раундовым ключом), последний 10-й раунд, состоит из трех шагов (замены байтов, циклического сдвига строк и сложения с раундовым ключом).

Основными достоинствами стохастических алгоритмов с архитектурой Квадрат являются:

- простая и понятная логика работы, удобная для анализа и обоснования стойкости;

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

- байт-ориентированная структура, удобная для реализации на 8-рарядных микроконтроллерах.

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

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

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

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

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

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

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

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

При выполнении преобразований третьего раунда блок данных S делится на 4 слоя L_z0, L_z1, L_z2, L_z3 вдоль оси х, каждый слой L_zk,k=0, 1, 2, 3, представляется в виде квадратного массива байтов 4×4, после чего подвергается двумерному преобразованию T_Layer, зависящему от содержимого секретной таблицы H; преобразованные слои объединяются в преобразованный блок 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) перешивается с использованием стохастического сумматора, логика работы которого определяется содержимым ключевой таблицы H;

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

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

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

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

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

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

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

введение в состав операции преобразования слоя (T_Layer) последовательно выполняемых операций перемешивания строк (MixRows) и перемешивания столбцов (MixColumns);

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

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

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

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

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

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

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

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

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

в состав операции двумерного преобразования 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. Таким образом, техническим результатом заявленного изобретения является повышение криптостойкости и увеличение быстродействия.

Суть предлагаемого способа иллюстрируют фиг.1-4. На фиг.1 показаны блок данных и отдельный байт блока данных. На фиг.2 показан принцип разделения блока данных на слои вдоль осей х, у, z и отдельные слои L_xk, L_yk, L_zk. На фиг.3 показана последовательность выполнения преобразования. На фиг.4 показан пример построения ГПСЧ по схеме CTR, т.е. пример использования преобразования DOZEN в качестве функции выхода ГПСЧ.

На фиг.1-3 показаны входной 1 и выходной 2 блоки данных; раундовые ключи 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_х3 (соответственно 4_x0, 4_x1, 4_x2, 4_x3) вдоль оси x, операции 5_x1, 5_x2, 5_x2, 5_x3 преобразования слоев (T_Layer) вдоль оси x; слои L_z0, L_z1, L_x2, L_x3 (соответственно 4_z0, 4_z1, 4_z2, 4_z3) вдоль оси у, операции 5_z0, 5_z1, 5_z2, 5_z3 преобразования слоев (T_Layer) вдоль оси у; слои L_z0, L_z1, L_z2, L_z3 (соответственно 4_z0, 4_z1, 4_z2, 4_z3) вдоль оси z, операции 5_z0, 5_z1, 5_z2, 5_z3 преобразования слоев (T_Layer) вдоль оси z; замена 6 байтов (SubBytes), перемешивание 7 строк (MixRows), перемешивание 8 столбцов (MixColumns), сложение 9 (XOR) с раундовым подключом (AddRoundSubKey), сложение 10 (XOR) с раундовым ключом (AddRoundKey). На фиг.4 показаны счетчик 11, вход 12 параллельной загрузки начального состояния счетчика, выход 13 счетчика, выход 14 ГПСЧ.

Рассмотрим трехмерное многораундовое преобразование с архитектурой Куб, получившее название DOZEN (дюжина, по числу операций T_Layer), которое может использоваться в качестве нелинейной функции ГПСЧ (функции выхода в случае использования режима CTR (фиг.4) или функции обратной связи в случае использования режима 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;

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

- включение в состав операции двухмерного преобразования слоя (T_Layer) 5 четырех шагов - замены 6 байтов (SubBytes), перемешивания 7 строк (MixRows), перемешивания 8 столбцов (MixColumns), сложения (XOR) 9 с раундовым подключом (AddRoundSubKey);

- использование при выполнении преобразований MixRow 7 и MixColumn 8 операции, использующейся в криптоалгоритме Rijndael при реализации преобразования MixColumn.

Уравнение операции перемешивания, записанное в матричной форме, имеет следующий вид:

,

где 001, 02, 03 - элементы GF(2⁸), a_k и a_k' - соответственно входное и преобразованное значение k-го байта строки или столбца, k=0, 1, 2, 3.

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

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

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

3) двухмерное стохастическое преобразование слоев (T_Layer) L_x0, L_x1, L_x2, L_x3 (соответственно операции 5_x0, 5_xl, 5_x2, 5_x3) путем выполнения для каждого слоя L_xk 4_хk шестнадцати (по числу байтов) операций 6 SubByte, четырех (по числу строк) операций 7 MixRow, четырех (по числу столбцов) операций 8 MixColumn и операции 9 AddRoundSubKey;

4) второй раунд: разбиение получившегося блока данных на слои L_y0, L_y1, L_y2, L_y3 (соответственно 4_y0, 4_y1, 4_y2, 4_y3) вдоль оси у (фиг.2);

5) двухмерное стохастическое преобразование слоев (T_Layer) L_y0, L_y1, L_y2, L_y3 (соответственно операции 5_y0, 5_y1, 5_y2, 5_y3) путем выполнения для каждого слоя L_уk 4_yk шестнадцати (по числу байтов) операций 6 SubByte, четырех (по числу строк) операций 7 MixRow, четырех (по числу столбцов) операций 8 MixColumn и операции 9 AddRoundSubKey;

6) третий раунд: разбиение получившегося блока данных на слои L_z0, L_z1, L_z2, L_z3 (соответственно 4_z0, 4_z1, 4_z2, 4_z3) вдоль оси z (фиг.2);

7) двухмерное стохастическое преобразование слоев (T_Layer) L_z0, L_z1, L_z2, L_z3 (соответственно операции 5_z0, 5_zl, 5_z2, 5_z3) путем выполнения для каждого слоя L_zk 4_zk шестнадцати (по числу байтов) операций 6 SubByte, четырех (по числу строк) операций 7 MixRow, четырех (по числу столбцов) операций 8 MixColumn и операции 9 AddRoundSubKey.

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

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

Шаг 0. Сложение 10 с раундовым ключом 3₀ (AddRoundKey K₀)

Первый раунд:

Шаг 1. Преобразование 5_x0 слоя 4_x0 (T_Layer L_x0).

Шаг 2. Преобразование 5_x1 слоя 4_х1 (T_Layer L_x1).

Шаг 3. Преобразование 5_х2 слоя 4_x2 (T_Layer L_x2).

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

Второй раунд:

Шаг 5. Преобразование 5_y0 слоя 4_y0 (T_Layer L_y0).

Шаг 6. Преобразование 5_y1 слоя 4_y1 (T_Layer L_y1).

Шаг 7. Преобразование 5_y2 слоя 4_y2 (T_Layer L_y2).

Шаг 8. Преобразование 5_y3 слоя 4_y3 (T_Layer L_y3).

Третий раунд:

Шаг 9. Преобразование 5_z0 слоя 4_z0 (T_Layer L_z0).

Шаг 10. Преобразование 5_z1 слоя 4_z1 (T_Layer L_z1).

Шаг 11. Преобразование 5_z2 слоя 4_z2 (T_Layer L_z2).

Шаг 12. Преобразование 5_z3 слоя 4_z3 (T_Layer L_z3).

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

В последние годы все большую популярность завоевывают гибридные вычислительные системы, сочетающие удобство классических вычислений на центральных процессорах (CPU) с массово-параллельными вычислениями на графических процессорах (GPU) [Боресков А.В., Харламов А.А. Основы работы с технологией CUDA. М:. ДМК Пресс, 2011], [CUDA Zone. URL ]. Особенностью GPU является наличие большого числа (десятки и сотни) вычислительных ядер, работающих параллельно. В задачах, допускающих распараллеливание обработки потока исходных данных, выигрыш в производительности для системы CPU/GPU составляет до нескольких десятков раз по сравнению с классической CPU-системой. Многие из наиболее производительных современных суперкомпьютеров также имеют гибридную архитектуру CPU/GPU.

В гибридных системах CPU решает задачи управления выполнением программы в целом и проведения не очень "тяжелых" вычислений; наиболее критичные по производительности участки программы оформляются в виде специальных функций-ядер (kernel), которые запускаются на GPU. Современные производители графических процессоров, в частности, компания NVIDIA, предоставляют разработчикам программ для систем CPU/GPU мощные инструментальные средства. Полезной и приятной особенностью таких средств является то, что они являются бесплатными. В качестве примеров можно указать CUDA Toolkit [CUDA Toolkit. URL ] и Parallel NSight [NVIDIA Parallel Nsight. URL nvidia-parallel-nsight], которые интегрируются с современными популярными системами разработки ПО, такими как Microsoft Visual Studio и NetBeans.

Для программной реализации предложенного алгоритма DOZEN наиболее целесообразной представляется технология CUDA (Compute Unified Device Architecture - вычислительная унифицированная архитектура устройств) от компании NVIDIA [Боресков А.В., Харламов А.А. Основы работы с технологией CUDA. М.: ДМК Пресс, 2011], [CUDA Zone. URL ].

Минимальной вычислительной единицей в CUDA является нить (thread). По сути, нить есть набор конкретных действий над элементом данных, нити группируются в пучки (warp); все нити одного пучка физически параллельно выполняются на потоковом мультипроцессоре; из потоковых мультипроцессоров состоит графический процессор. Очень важной особенностью CUDA является то, что при программировании нити образуют трехмерные структуры, именуемые блоками (block). Блоки, в свою очередь, группируются в еще более крупную многомерную структуру, именуемую сеткой (grid). Другими словами, сетка есть совокупность всех нитей, выполняющих параллельную обработку данных, и вместе с тем представляющая собой гибкую многомерную иерархическую структуру. Таким образом, CUDA-программист может оперировать с одно-, двух- или трехмерными структурами для параллельной обработки исходных данных, в том числе, комбинируя размерности этих структур. В таблице 1 представлена степень параллелизма для предлагаемого трехмерного нелинейного преобразования

Очевидно, что в пределах каждого раунда работы DOZEN все слои могут быть обработаны параллельно, а применение CUDA позволит существенно упростить процесс разработки ПО на основе алгоритма DOZEN.

Способ нелинейного трехмерного многораундового преобразования данных DOZEN, включающий представление входного, выходного блоков данных, всех промежуточных результатов преобразования в виде кубического массива байтов 4×4×4; введение понятие слоя (Layer) - квадратного массива байтов 4×4; включение в состав операции преобразования слоя (T_Layer) последовательно выполняемых операций перемешивания строк (MixRows) и перемешивания столбцов (MixColumns); выполнение 3 раундов трехмерного преобразования соответственно вдоль осей х, у, z; при выполнении преобразований первого раунда деление блока данных 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; при выполнении преобразований второго раунда деление блока данных S на 4 слоя L_y0, L_y1, L_y2, L_y3 вдоль оси у; представление каждого слоя L_yk , k=0, 1, 2, 3, в виде квадратного массива байтов 4×4, двумерное стохастическое преобразование T_Layer каждого слоя L_yk , объединение слоев L_yk в преобразованный блок S; при выполнении преобразований третьего раунда деление блока данных S на 4 слоя L_z0, L_z1, L_z2, L_z3 вдоль оси z; представление каждого слоя L_zk, k=0, 1, 2, 3, в виде квадратного массива байтов 4×4, двумерное стохастическое преобразование T_Layer каждого слоя L_zk, объединение слоев L_zk в преобразованный блок S; отличающийся тем, что формируют последовательность раундовых ключей K₀, K₁, K₂, K₃ разрядностью 512 бит каждый и секретную таблицу замен размерностью 8×256; формируют по входному блоку М разрядностью 512 бит блок данных S той же разрядности в соответствии с выражением S:=М, после чего выполняют начальное поразрядное сложение по модулю два (XOR) блока S и раундового ключа (AddRoundKey) K₀ в соответствии с выражением S:=S⊕K₀, после чего выполняют 3 раунда преобразования вдоль осей х, у, 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; в состав операции двумерного стохастического преобразования 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 многочлена А(х) на многочлен 03x³+х²+x+02; перемешанные строки объединяют в преобразованный слой L; операцию перемешивания столбцов MixColumns выполняют следующим образом: слой L разбивают на 4 столбца; байты каждого k-го столбца (k=0, 1, 2, 3) при выполнении преобразования рассматривают как коэффициенты многочлена А(х) степени 3 над полем GF(2⁸), суть операции перемешивания столбца - умножение по модулю х⁴+1 многочлена А(х) на многочлен 03х³+х²+х+02; перемешанные столбцы объединяют в преобразованный слой L.