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

Формула изобретения

Способ трехмерного нелинейного преобразования замены, включающий представление входного блока М и всех промежуточных результатов преобразования разрядностью N³ (N > 1) бит в виде кубического массива битов NхNх N; введение понятие слоя (Layer) - квадратного массива битов NхN; выполнение трех раундов преобразования соответственно вдоль осей х, у, z; деление блока данных М перед выполнением преобразований первого раунда на N слоев L _x0, L_x1, ..., L_x(N-1) вдоль оси х; деление результата работы первого раунда перед выполнением преобразований второго раунда на N слоев L_y0, L_y1, ..., L _y(N-1) вдоль оси у; деление результата работы второго раунда перед выполнением преобразований третьего раунда на N слоев L_z0, L_z1 , ..., L_z(N-1) вдоль оси z; отличающийся тем, что формируют k таблиц замен S_i размерностью Nх2^N каждая, i = 0, 1, ..., (k - 1), 1 k; в первом раунде выполняют N двухмерных преобразований замены слоев L_x0, L_x1, ..., L_x(N-1); во втором раунде выполняют N двухмерных преобразований замены слоев L_y0 , L_y1, ..., L_y(N-1) ; в третьем раунде выполняют N двухмерных преобразований замены слоев L_z0, L_z1, ..., L_z(N-1), при этом двумерное преобразование замены слоя L выполняется за два шага, на первом шаге слой L делят на NN -разрядных векторов-строк R₀, R₁ ..., R_(N-1) , каждый j-й N-разрядный вектор R_j , j= 0, 1, ..., (N - 1), заменяют N-разрядным вектором из соответствующей таблицы замен S_i согласно выражению R_j = S_j (R_j), выбранные из таблицы замен NN- разрядных векторов R_j объединяют в преобразованный слой L; на втором шаге слой L делят на NN -разрядных векторов-столбцов С₀ , С₁ ..., С _(N-1), каждый j-й N-разрядный вектор Cj, j = 0, 1, (N - 1), заменяют N-разрядным вектором из соответствующей таблицы замен Sj согласно выражению Cj = Sj (Cj), выбранные из таблицы замен N N -разрядных векторов Cj объединяют в преобразованный слой L, который выдают в качестве результата двумерного преобразования замены слоя L.

Описание изобретения к патенту

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

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

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

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

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

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

Известен способ преобразования замены, описанный в Российском стандарте криптографической защиты информации [Стандарт СССР ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования]. Способ-аналог включает в себя формирование 32-разрядного вектора, после чего над двоичным вектором F выполняют операцию замены F:=S(F), при этом операция замены выполняется следующим образом. Двоичный вектор F разбивается на 8 двоичных векторов длиной по 4 бит каждый. Каждый 4-разрядный двоичный вектор заменяется двоичным вектором из соответствующей таблицы замен размерности 4×16. Выбранные из таблиц замен восемь 4-разрядных векторов объединяются в преобразованный двоичный вектор F.

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

Наиболее близким по своей технической сущности к заявленному способу является принятый за прототип способ трехмерного преобразования [Иванов М.А., Ковалев А.В., Чугунков И.В. и др. Стохастические методы защиты информации в компьютерных системах и сетях. М.: Кудиц-Пресс, 2009, с.243-246], включающий представление входного блока M и всех промежуточных результатов преобразования разрядностью 512 бит в виде кубического массива; введение понятие слоя (Layer) - квадратного массива разрядностью 128 бит; выполнение трех раундов преобразования соответственно вдоль осей x, y, z; деление блока данных M перед выполнением преобразований первого раунда на 4 слоя L_x0, L_x1, L_x2, L_x3 вдоль оси x; деление результата работы первого раунда перед выполнением преобразований второго раунда на 4 слоя L_y , L_y1, L_y2, L_y3 вдоль оси y; деление результата работы второго раунда перед выполнением преобразований третьего раунда на 4 слоя L_z0, L_z1, L _z2, L_z3 вдоль оси z.

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

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

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

представление входного блока M и всех промежуточных результатов преобразования разрядностью N³ (N>1) бит в виде кубического массива битов N×N×N;

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

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

деление блока данных М перед выполнением преобразований первого раунда на N слоев L_x0, L_x1, , L_x(N-1) вдоль оси х;

деление результата работы первого раунда перед выполнением преобразований второго раунда на N слоев L_y0, L_y1, , L_y(N-1) вдоль оси y;

деление результата работы второго раунда перед выполнением преобразований третьего раунда на N слоев L_z0, L_z1, , L_z(N-1) вдоль оси z;

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

формируют k таблиц замен S_i размерностью N×2^N каждая, i=0, 1, , (k-1), k 1;

в первом раунде выполняют N двухмерных преобразований замены слоев L_x0, L_x1, , L_x(N-1);

во втором раунде выполняют N двухмерных преобразований замены слоев L_y0, L _y1, , L_y(N-1);

в третьем раунде выполняют N двухмерных преобразований замены слоев L_z0, L _z1, , L_z(N-1).

Новым также является то, что двумерное преобразование замены слоя L может выполняться за два раунда, при этом формируют две различные таблицы замен S₀ и S₁ размерностью N×2^N каждая;

в первом раунде слой L делят на NN-разрядных векторов-строк R₀, R₁, , R_(N-1), каждый i-й N-разрядный вектор R _i, i=0, 1, , (N-1), заменяют N-разрядным вектором из таблицы замен S₀ в соответствии с выражением R_i=S ₀(R_i), выбранные из таблицы замен N N-разрядных векторов R_i объединяют в преобразованный слой L;

во втором раунде слой L делят на NN-разрядных векторов-столбцов С₀, С₁, , C(N-1), каждый i-й N-разрядный вектор C_i, i=0, 1, , (N-1), заменяют N-разрядным вектором из таблицы замен S₁ в соответствии с выражением С,=Si (С,), выбранные из таблицы замен N N-разрядных векторов C_i объединяют в преобразованный слой L, который выдают в качестве результата двумерного преобразования замены слоя L.

Новым также является то, что двумерное преобразование замены слоя L может выполняться за два раунда, при этом формируют таблицу замен S размерностью N×2^N;

в первом раунде слой L делят на N N-разрядных векторов-строк R₀ , R₁, , R_(N-1), каждый i-й N-разрядный вектор R _i, i=0, 1, , (N-1), заменяют N-разрядным вектором из таблицы замен S в соответствии с выражением R_i=S(R_i), выбранные из таблицы замен N N-разрядных векторов R_i объединяют в преобразованный слой L;

во втором раунде слой L делят на NN-разрядных векторов-столбцов C₀ , С₁, , C_(N-1), каждый i-й N-разрядный вектор C _i, i=0, 1, (N-1), заменяют N-разрядным вектором из таблицы замен S в соответствии с выражением С_i=S(C_i ), выбранные из таблицы замен N N-разрядных векторов C_i объединяют в преобразованный слой L, который выдают в качестве результата двумерного преобразования замены слоя L.

Новым также является то, что при выполнении трехмерного нелинейного преобразования замены могут использоваться две различные таблицы замен S₀ и S₁ размерностью N×2 каждая, при этом строки всех слоев заменяют с использованием таблицы замен S₀, а столбцы всех слоев заменяют с использованием таблицы замен S₁.

Новым также является то, что при выполнении трехмерного нелинейного преобразования замены

могут использоваться три различные таблицы замен S₀, S₁ и S₂ размерностью N×2ⁿ каждая, при этом слои L_xi, расположенные вдоль оси х, заменяют с использованием таблицы замен S₀ ; слои L_yi, расположенные вдоль оси y, заменяют с использованием таблицы замен S₁, а слои L_zi , расположенные вдоль оси z, заменяют с использованием таблицы замен S₂.

Новым также является то, что при выполнении трехмерного нелинейного преобразования замены

могут использоваться шесть различных таблиц замен S₀, S₁, , S₅ размерностью N×2ⁿ каждая, при этом строки слоев L_xi, расположенных вдоль оси x, заменяют с использованием таблицы замен S₀; столбцы слоев L_xi, расположенных вдоль оси x, заменяют с использованием таблицы замен S₁; строки слоев L_yi, расположенных вдоль оси y, заменяют с использованием таблицы замен S₂ ; столбцы слоев L_yi, расположенных вдоль оси y, заменяют с использованием таблицы замен S₃, строки слоев L _zi, расположенных вдоль оси z, заменяют с использованием таблицы замен S₄; столбцы слоев L_zi, расположенных вдоль оси z, заменяют с использованием таблицы замен S₅ .

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

Суть предлагаемого способа иллюстрируют фиг.1-5. На фиг.1, 2 показан принцип двухмерного преобразования слоя, иначе говоря, принцип работы 2D S-блока при N=4. На фиг.1 показан блок 1 данных (слой) 4×4; строки 2₀, 2₁, 2₂, 2₃ слоя; столбцы 3₀, 3₁, 3₂, 3₃ слоя. На фиг.2 показаны преобразования замены 4₀, 4₁, 4₂, 4₃ строк, которые могут выполняться параллельно, и преобразования замены 5₀ , 5₁, 5₂, 5₃ столбцов, которые также могут выполняться параллельно, входной 6 (исходный) и выходной 7 (преобразованный) блок данных (слой). На фиг.3-5 показан принцип трехмерного преобразования слоя, иначе говоря, принцип работы 3D S-блока при N=4. На фиг.3 показан блок 8 данных 4×4×4 и отдельный бит 9 блока 8 данных. На фиг.4 показано разделение на слои 10_xk, 10_yk, 10_zk, k=0, 1, 2, 3, вдоль осей x, y, z и отдельные слои 10_xk, 10_yk, 10_zk (L_xk, L_yk , L_zk). Ha фиг.5 показаны операции преобразования 11_x0, 11_x1, 11_x2, 11_x3 слоев 10_x0, 10_x2, 10_x3 вдоль оси x, которые могут выполняться параллельно; операции преобразования 11_y0, 11_y1, 11_y2, 11_y3 слоев 10_y0, 10_y1, 10_y2, 10 _y3 вдоль оси y, которые могут выполняться параллельно и операции преобразования 11_z0, 11_z1, 11 _z2, 11_z3 слоев 10_z0, 10_z1 , 10_z2, 10_z3 вдоль оси z, которые могут выполняться параллельно.

Рассмотрим последовательность выполнения двухмерного преобразования замены слоя, т.е. алгоритм функционирования 2D S-блока.

Представим входные 6 и выходные 7 блоки данных, а также все промежуточные результаты преобразований в виде квадратного массива битов 1 размерностью N×N, где N - разрядность используемых узлов замены. Таким образом, объем ключевой информации, однозначно определяющей логику работы каждого узла замены, равен N×2^N. На фиг.1 показан пример массива размерностью 4×4.

Последовательность выполнения операции А=SubSquare[A] 11 (или кратко, А=S_sq[A]), замены квадратного массива 10 битов A размерностью N×N, имеет следующий вид:

- Разбиение входного 6 массива A на N строк 2_iR _i длины N, i=0, 1, , (N-1), (фиг.1);

- Преобразование 4 SubRows. Преобразование 4, каждого i-го N-разрядного двоичного набора 2_iR_i с использованием соответствующего узла замены S_i:R_i=S_i[R_i ], i=0, 1, , (N-1);

- Разбиение получившегося массива А=SnbRows[A] на N столбцов 3_iC_i длины N,i=0, 1, , (N-1), (фиг.1);

- Преобразование 5 SubColumns. Преобразование 5, каждого i-го N-разрядного двоичного набора 3_iC_i с использованием соответствующего узла замены S_i+N:C_i=S_i+N[C _i], i=0, 1, , (N-1);

- Результатом замены является 7 А=SnbColunms[A].

В частном случае, когда используется только одна таблица замен, т.е.=S, получаем следующий алгоритм:

- Разбиение входного 6 массива A на N строк 2 _iR_i, длины N;

- Преобразование 4 SubRows. Преобразование каждого i-го N-разрядного двоичного набора 2_iR_i:R_i=S[R_i ], i=0, 1, , (N-1);

- Разбиение получившегося массива А=SubRows[A] на N столбцов 3_iC_i, длины N;

- Преобразование 5 SubColumns. Преобразование каждого /-го N-разрядного двоичного набора 3_iC _i:С_i=S[C_i], i=0, 1, , (N-1);

- Результатом замены является блок 7 А=SubCoIumns[A]. Рассмотрим последовательность выполнения трехмерного преобразования замены, т.е. алгоритм функционирования 3D S-блока.

Представим входные 12 и выходные 13 блоки данных, а также все промежуточные результаты преобразований в виде кубического массива битов 8 размерностью N×N×N, где N - разрядность используемых узлов замены. Таким образом, объем ключевой информации, однозначно определяющей логику работы каждого узла замены, равен N×2ⁿ. На фиг.3 показан пример массива 8 размерностью 4×4×4.

Последовательность выполнения операции замены кубического массива битов 12 А=SubCube[A] (или кратко, А=S_cu[A]) размерностью N×N×N имеет следующий вид:

- Разбиение входного массива 12 A на N слоев 10_xi, L_xi размерностью N×N вдоль оси x, i=0, 1, , (N-1), (фиг.4);

- Преобразование SubLayersX. Выполнение преобразования 11_xi, L_xi=SubSquare[L _xi] каждого i-го слоя 10_xi L_xi с использованием соответствующих узлов замены, j=0, 1, , (N-1); все преобразования 1 при этом могут выполняться параллельно;

- Разбиение получившегося массива А=SubLayersX[A] на N слоев 10_yi L_yi размерностью N×N вдоль оси у, i=0, 1, , (N-1), (фиг.4);

- Преобразование SubLayersY. Выполнение преобразования 11_yi L_yi=SubSquare[L _yi] каждого i-го слоя 10_yi L_yi с использованием соответствующих узлов замены, i=0, 1, , (N-1); все преобразования 11_yi при этом могут выполняться параллельно;

- Разбиение получившегося массива A=SubLayersY[A] на N слоев 10_zi L_zi - размерностью N×N вдоль оси z, i=0, 1, , (N-1), (фиг.4);

- Преобразование SubLayersZ. Выполнение преобразования 11_Zi L_zi=SiibSqnare[L _Zi] каждого i-го слоя 10_zi L_zi с использованием соответствующих узлов замены, i=0, 1, , (N-1); все преобразования 11_zi при этом могут выполняться параллельно;

- Результатом замены является 13 А=SubLayersZ[A].

На фиг.5 показана последовательность преобразования массива 8 размером 4×4×4.

Предложены способы выполнения операции замены в двух и трех измерениях с использованием соответственно 2D и 3D 3-блоков. Описаны операции преобразования строк, столбцов и слоев блоков данных. Наиболее очевидное назначение предлагаемых алгоритмов - преобразование N²- и N³-разрядных блоков данных с использованием таблицы замен размерности N×2 при построении нелинейных функций выхода или обратной связи ГПСЧ, примитивов хеширования, блочного и поточного шифрования.

В последние годы все большую популярность завоевывают гибридные вычислительные системы, сочетающие удобство классических вычислений на центральных процессорах (CPU) с массово-параллельными вычислениями на графических процессорах (GPU) [Боресков А.В., Харламов А.А. Основы работы с технологией CUDA. М.: ДМК Пресс, 2011], [CUDA Zone. URL http://developer.nvidia.com/category/zone/cuda-zone]. Особенностью 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.

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

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

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