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

Изобретение относится к вычислительной технике и электросвязи, предназначено для решения задач защиты компьютерной информации, может использоваться при построении генераторов псевдослучайных чисел, а также криптографических примитивов хеширования, блочного и поточного шифрования. Достигаемый технический результат - повышение криптостойкости и быстродействия нелинейного преобразования. Способ включает представление входных 1 и выходных 2 блоков данных, всех промежуточных результатов S преобразований и раундовых ключей (RoundKeys) 30, 31, 32, 33 в виде кубического массива байтов 4×4×4, определение понятия слоя 4 (Layer) - квадратного массива байтов 4×4, представление i-го раундового ключа в виде четырех подключей (RoundSubKeys) 3i0, 3i1, 3i2, 3i3, i=1, 2, 3, каждый из которых суть квадратный массив байтов 4×4, сложение 10 (XOR) блока 1 данных с раундовым ключом 30, трехмерное преобразование блока данных по слоям 4x0, 4x1, 4х2, 4x3, 4у0, 4у1, 4у2, 4у3, 4z0, 4z1, 4z2, 4z3 соответственно вдоль осей x, у, z, включение в состав операции двухмерного преобразования слоя (T-Layer) 5 четырех шагов: замену 6 байтов (SubBytes), перемешивание 7 строк (MixRows), перемешивание 8 столбцов (MixColumns), сложение (XOR) 9 с раундовым подключом (AddRoundSubKey). 4 ил., 1 табл.

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Известен ГПСЧ, функционирующий в конечных полях GF(2n) [Иванов М.А. Генератор псевдослучайных последовательностей. Авторское свидетельство СССР №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, Ki), где Ki - подключ, используемый на i-м раунде. Полученное значение F:=E(F, Ki) поразрядно суммируется по модулю два ⊕ с подблоком R в соответствии с выражением R:=R⊕F. Вычисление раундовой функции E(F, Кi) осуществляется в соответствии со следующими шагами преобразования. Первоначально сформированный двоичный вектор F:=L преобразуется путем наложения на него текущего подключа Кi, являющегося фиксированным для данного раунда, с помощью операции сложения по модулю 232 в соответствии с формулой F:=(F+К,) mod 232, после чего над двоичным вектором 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 битам. Преобразование выполняется путем формирования из секретного ключа с помощью процедуры разворачивания ключа последовательности раундовых ключей K0, K1…, KR, где R - число раундов преобразования. По входному блоку М формируется блок 5 в соответствии с выражением S:=М. Затем выполняется операция начального поразрядного сложения по модулю два (XOR) блока S и раундового ключа (AddRoundKey) K0 в соответствии с выражением S:=S⊕K0, после чего выполняются R раундов преобразования. В состав каждого i-го раунда кроме последнего входят последовательно выполняемые преобразования замены байтов (SubBytes) S:=SubBytes(S), циклического сдвига строк (ShiftRows) S:=ShiftRows(S), перемешивания столбцов (MixColumns) S:=MixColunms(S) и сложения по модулю два (XOR) с раундовым ключом (AddRoundKey) К, в соответствии с выражением S:=S⊕Ki. В состав последнего раунда входят последовательно выполняемые преобразования замены байтов (SubBytes), циклического сдвига строк (ShiftRows) и сложения (XOR) с раундовым ключом (AddRoundKey) KR. Операция замены байтов SubBytes выполняется следующим образом. Блок S разбивается на 16 байтов. Каждый байт заменяется байтом из фиксированной таблицы замен размерностью 8×256. Выбранные из таблицы замен 16 байтов объединяются в преобразованный блок S. Операция сдвига строк (ShiftRows) выполняется следующим образом. Блок S разбивается на 4 строки. Каждая i-я строка (i=0, 1, 2, 3) циклически сдвигается на i байтов. Сдвинутые строки объединяются в преобразованный блок S. Операция перемешивания столбцов (MixColumns) выполняется следующим образом. Блок S разбивается на 4 столбца. При выполнении преобразования MixColumns байты столбца рассматриваются как коэффициенты многочлена А(х) степени 3 над полем GF(28). Суть операции перемешивания столбца - умножение по модулю х4+1 многочлена А(х) на многочлен 03x32+х+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 слоя Lx0, Lx1, Lx2, Lx3 вдоль оси х, каждый слой Lxk,k=0, 1, 2, 3, представляется в виде квадратного массива байтов 4×4, после чего подвергается двумерному преобразованию T_Layer, зависящему от содержимого секретной таблицы H; преобразованные слои объединяются в преобразованный блок S.

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

При выполнении преобразований третьего раунда блок данных S делится на 4 слоя Lz0, Lz1, Lz2, Lz3 вдоль оси х, каждый слой Lzk,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 слоя Lx0, Lx1, Lx2, Lx3 вдоль оси х; каждый слой Lxk, k=0, 1, 2, 3, представляют в виде квадратного массива байтов 4×4, после чего подвергают двумерному преобразованию T_Layer, после чего преобразованные слои объединяют в преобразованный блок S;

при выполнении преобразований второго раунда блок данных S делится на 4 слоя Ly0, Ly1, Ly2, Lу3 вдоль оси х; каждый слой Lyk,k=0, 1, 2, 3, представляется в виде квадратного массива байтов 4×4, после чего подвергается двумерному преобразованию T_Layer, после чего преобразованные слои объединяются в преобразованный блок S;

при выполнении преобразований третьего раунда блок данных S делят на 4 слоя Lz0, Lz1, Lz2, Lz3 вдоль оси х, каждый слой Lzk, k=0, 1, 2, 3, представляют в виде квадратного массива байтов 4×4, после чего подвергают двумерному преобразованию T_Layer, после чего преобразованные слои объединяют в преобразованный блок S;

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

формируют последовательность раундовых ключей K0, K1, K2, K3 разрядностью 512 бит каждый и секретную таблицу замен размерностью 8×256;

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

каждый i-й раундовый ключ Ki(i=1, 2, 3) делят на четыре раундовых подключа Ki0, Ki1, Ki2, Ki3 разрядностью 128 бит каждый;

раундовые подключи Кi0, Ki1, Ki2, Кi3 представляют в виде квадратного массива байтов 4×4;

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

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

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

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

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

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

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

- умножение по модулю х4+1 многочлена А(х) на многочлен 03х32+х+02;

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

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

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

- умножение по модулю х4+1 многочлена А(х) на многочлен 03х32+х+02;

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

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

На фиг.1-3 показаны входной 1 и выходной 2 блоки данных; раундовые ключи K0, К1, К2, К3 (соответственно 30, 31, 32, 33); раундовые подключи Ki0, Ki1, Ki2, Ki3 (соответственно 3i0, 3i1, 3i2, 3i3), i=1, 2, 3; слои Lx0, Lx1, Lx2, Lх3 (соответственно 4x0, 4x1, 4x2, 4x3) вдоль оси x, операции 5x1, 5x2, 5x2, 5x3 преобразования слоев (T_Layer) вдоль оси x; слои Lz0, Lz1, Lx2, Lx3 (соответственно 4z0, 4z1, 4z2, 4z3) вдоль оси у, операции 5z0, 5z1, 5z2, 5z3 преобразования слоев (T_Layer) вдоль оси у; слои Lz0, Lz1, Lz2, Lz3 (соответственно 4z0, 4z1, 4z2, 4z3) вдоль оси z, операции 5z0, 5z1, 5z2, 5z3 преобразования слоев (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) K0, K1, K2, K3 (30, 31, 32, 33) в виде кубического массива байтов 4×4×4 (фиг.1);

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

- представление i-го раундового ключа в виде четырех подключей (RoundSubKeys) Ki0, Ki1, Ki2, Ki3 (3i0, 3i1, 3i2, 3i3), 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(28), ak и ak' - соответственно входное и преобразованное значение 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 данных с раундовым 30 ключом K0;

2) первый раунд: разбиение получившегося блока данных на слои (Layers) Lx0, Lx1, Lx2, Lх3 (соответственно 4x0, 4x1, 4x2, 4x3) вдоль оси x (фиг.2);

3) двухмерное стохастическое преобразование слоев (T_Layer) Lx0, Lx1, Lx2, Lx3 (соответственно операции 5x0, 5xl, 5x2, 5x3) путем выполнения для каждого слоя Lxk 4хk шестнадцати (по числу байтов) операций 6 SubByte, четырех (по числу строк) операций 7 MixRow, четырех (по числу столбцов) операций 8 MixColumn и операции 9 AddRoundSubKey;

4) второй раунд: разбиение получившегося блока данных на слои Ly0, Ly1, Ly2, Ly3 (соответственно 4y0, 4y1, 4y2, 4y3) вдоль оси у (фиг.2);

5) двухмерное стохастическое преобразование слоев (T_Layer) Ly0, Ly1, Ly2, Ly3 (соответственно операции 5y0, 5y1, 5y2, 5y3) путем выполнения для каждого слоя Lуk 4yk шестнадцати (по числу байтов) операций 6 SubByte, четырех (по числу строк) операций 7 MixRow, четырех (по числу столбцов) операций 8 MixColumn и операции 9 AddRoundSubKey;

6) третий раунд: разбиение получившегося блока данных на слои Lz0, Lz1, Lz2, Lz3 (соответственно 4z0, 4z1, 4z2, 4z3) вдоль оси z (фиг.2);

7) двухмерное стохастическое преобразование слоев (T_Layer) Lz0, Lz1, Lz2, Lz3 (соответственно операции 5z0, 5zl, 5z2, 5z3) путем выполнения для каждого слоя Lzk 4zk шестнадцати (по числу байтов) операций 6 SubByte, четырех (по числу строк) операций 7 MixRow, четырех (по числу столбцов) операций 8 MixColumn и операции 9 AddRoundSubKey.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Данные анализа степени параллелизма в предлагаемом преобразовании позволяют сделать вывод, что достоинством предлагаемого решения является высокая степень параллелизма, что обеспечивает получение заявляемого технического результата -увеличение быстродействия при реализации с использованием гибридных суперкомпьютерных технологий. При этом операция преобразования слоя 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 слоя LX0, LX1, LX2, LX3 вдоль оси x; представление каждого слоя Lxk, k=0, 1, 2, 3, в виде квадратного массива байтов 4×4, двумерное стохастическое преобразование T_Layer каждого слоя Lxk , объединение слоев Lxk в преобразованный блок S; при выполнении преобразований второго раунда деление блока данных S на 4 слоя Ly0, Ly1, Ly2, Ly3 вдоль оси у; представление каждого слоя Lyk , k=0, 1, 2, 3, в виде квадратного массива байтов 4×4, двумерное стохастическое преобразование T_Layer каждого слоя Lyk , объединение слоев Lyk в преобразованный блок S; при выполнении преобразований третьего раунда деление блока данных S на 4 слоя Lz0, Lz1, Lz2, Lz3 вдоль оси z; представление каждого слоя Lzk, k=0, 1, 2, 3, в виде квадратного массива байтов 4×4, двумерное стохастическое преобразование T_Layer каждого слоя Lzk, объединение слоев Lzk в преобразованный блок S; отличающийся тем, что формируют последовательность раундовых ключей K0, K1, K2, K3 разрядностью 512 бит каждый и секретную таблицу замен размерностью 8×256; формируют по входному блоку М разрядностью 512 бит блок данных S той же разрядности в соответствии с выражением S:=М, после чего выполняют начальное поразрядное сложение по модулю два (XOR) блока S и раундового ключа (AddRoundKey) K0 в соответствии с выражением S:=S⊕K0, после чего выполняют 3 раунда преобразования вдоль осей х, у, z; каждый i-й раундовый ключ Ki (i=1, 2, 3) делят на четыре раундовых подключа Ki0, Ki1, Ki2, Ki3 разрядностью 128 бит каждый; раундовые подключи Ki0, Ki1, Ki2, Ki3 представляют в виде квадратного массива байтов 4×4; в состав операции двумерного стохастического преобразования T_Layer слоя L включают четыре последовательно выполняемых шага - замены байтов (SubBytes), перемешивания строк (MixRows), перемешивания столбцов (MixColumns) и сложения (XOR) с соответствующим раундовым подключом (AddRoundSubKey) Kik; операция замены байтов SubBytes выполняют следующим образом: слой L разбивают на 16 байтов, каждый байт заменяют байтом из таблицы замен размерностью 8×256; выбранные из таблицы замен 16 байтов объединяют в преобразованный слой L; операцию перемешивания строк MixRows выполняют следующим образом: слой L разбивают на 4 строки; байты каждой k-й строки (k=0, 1, 2, 3) при выполнении преобразования рассматривают как коэффициенты многочлена А(х) степени 3 над полем GF(28), суть операции перемешивания строки - умножение по модулю х4+1 многочлена А(х) на многочлен 03x32+x+02; перемешанные строки объединяют в преобразованный слой L; операцию перемешивания столбцов MixColumns выполняют следующим образом: слой L разбивают на 4 столбца; байты каждого k-го столбца (k=0, 1, 2, 3) при выполнении преобразования рассматривают как коэффициенты многочлена А(х) степени 3 над полем GF(28), суть операции перемешивания столбца - умножение по модулю х4+1 многочлена А(х) на многочлен 03х32+х+02; перемешанные столбцы объединяют в преобразованный слой L.



 

Похожие патенты:

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

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

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

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

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

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

Изобретение относится к связи, более конкретно к технологиям для формирования последовательностей скремблирования и дескремблирования в системе связи. .

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

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

Изобретение относится к вычислительной технике и предназначено для генерации случайной последовательности значений из заданного множества значений с требуемыми характеристиками генерируемой последовательности. Техническим результатом является создание генератора, обеспечивающего генерацию последовательности значений из заданного множества значений с учетом наличия вероятностной связи каждого очередного значения с предыдущим. Устройство содержит первый селектор-мультиплексор, второй селектор-мультиплексор, первый регистр, источник случайных чисел, оперативное запоминающее устройство, K≥2 блоков хранения границ интервалов, K блоков сравнения, шифратор приоритетов, N≥1 инверторов, второй регистр. 2 ил.

Изобретение относится к способам создания широкополосных случайных процессов с заданными собственными и взаимными спектральными плотностями мощности и может быть использовано в приборостроении, машиностроении, вычислительной технике для создания, в частности, многоканальных автоматических систем, в испытаниях на вибростойкость к воздействиям случайной вибрации. Техническим результатом является генерирование двух случайных сигналов с заданной функцией когерентности. Способ включает формирование во временной области по заданным спектральным плотностям Sx(f) и Sy(f) стационарных случайных сигналов x(f), y(t) в форме разложения Райса-Пирсона со случайными на каждой гармонике fi фазами Θi и Ωi, определяемыми методом случайной выборки случайной величины, одна из которых - Θi для сигнала x(t) равномерно распределена в диапазоне [-π, π], а другая - Ωi для второго сигнала y(t) определяется как сумма Ωi=Θi+Δφi случайной величины Θi и случайной величины Δφi, равномерно распределенной в диапазоне [-φi, φi], границы которого определяются через взаимную спектральную плотность Sxy(f) случайных сигналов x(t) и y(t). 1 ил.

Изобретение относится к области вычислительной техники и может быть использовано для генерирования широкополосных случайных стационарных сигналов с заданными собственными и взаимными спектральными плотностями мощности. Техническим результатом является генерирование двух случайных сигналов с заданной функцией когерентности. Устройство содержит однопроцессорный компьютер, программное обеспечения для формирования по заданным спектральным плотностям Sx(f) и Sy(f) случайных сигналов в форме разложения Райса-Пирсона со случайными на каждой гармонике fi фазами Θi и Ωi, определяемыми методом случайной выборки случайной величины, одна из которых - Θi для сигнала x(f) равномерно распределена в диапазоне [-π, π], а другая - Ωi для второго сигнала y(t), определяется как сумма Ωi=Θi+Δφi случайной величины Θi и случайной величины Δφi, равномерно распределенной в диапазоне [-φi, φi], границы которого определяются через взаимную спектральную плотность Sxy(f) случайных сигналов x(t) и y(t) с последующим выполнением процедуры ОБПФ, модуля цифро-аналогового преобразователя для перевода сформированных цифровых сигналов в аналоговые сигналы генератора. 1 ил.

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах для формирования кодовых последовательностей. Технический результат заключается в расширении функциональных возможностей за счет расширения класса формируемых последовательностей путем добавления на h-разрядный выход устройства-прототипа модуля, содержащего h/3 нелинейных преобразователей, каждый из которых имеет три двоичных входа и двухбитовый вход, а также блока из h мультиплексоров с двумя входами данных каждый и с общим управляющим входом. Технический результат достигается за счет того, что в генератор нелинейных псевдослучайных последовательностей введены h/3 однотипных нелинейных преобразователя с тремя входами данных и двумя выходами, hmod3=0, и блок из h мультиплексоров с двумя входами данных каждый и с общим управляющим входом, каждый из нелинейных преобразователей содержит инвертор, четыре функциональных преобразователя и четыре конъюнктора на два входа и два дизъюнктора на два входа. 3 ил., 1 табл.

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

Изобретение относится к вычислительной технике и может быть использовано для генерации потоков псевдослучайных чисел (ПСЧ). Техническим результатом является возможность генерации N начальных значений и отсутствие корреляций при их использовании между не менее N потоками ПСЧ. Устройство содержит генератор получения начального значения и генератор ПСЧ, который содержит устройство вычисления потока ПСЧ, средство вычисления битов ПСЧ из координат единичного квадрата, средство формирования прообраза n-битного ПСЧ из n битов ПСЧ, средство записи в промежуточные регистры, средство сдвига битов регистра, элемент памяти, средство записи ПСЧ в элемент памяти, средство формирования потока ПСЧ из записанных в память ПСЧ, средство передачи потока ПСЧ в вычислительное устройство. 3 н.п. ф-лы, 3 ил.

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

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

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