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

Классы МПК:H04L9/00 Устройство для секретной или скрытой связи
Автор(ы):, ,
Патентообладатель(и):Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Национальный исследовательский ядерный университет МИФИ" (НИЯУ МИФИ) (RU)
Приоритеты:
подача заявки:
2012-07-17
публикация патента:

Изобретение относится к вычислительной технике и электросвязи,

предназначено для решения задач защиты компьютерной информации.

Техническим результатом изобретения является повышение быстродействия за счет увеличения степени параллелизма. Способ выполнения трех раундов преобразования осуществляется вдоль осей х, у, z. В первом раунде выполняют N двухмерных преобразований замены слоев Lx0 , Lx1, ..., Lx(N-1); во втором раунде выполняют N двухмерных преобразований замены слоев Ly0, Ly1, ..., Ly(N-1); в третьем раунде выполняют N двухмерных преобразований замены слоев Lz0 , Lz1, ..., Lz(N-1) . 5 ил., 1 табл.

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

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

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

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

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

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

Известен способ преобразования замены, описанный в Российском стандарте криптографической защиты информации [Стандарт СССР ГОСТ 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 слоя Lx0, Lx1, Lx2, Lx3 вдоль оси x; деление результата работы первого раунда перед выполнением преобразований второго раунда на 4 слоя Ly , Ly1, Ly2, Ly3 вдоль оси y; деление результата работы второго раунда перед выполнением преобразований третьего раунда на 4 слоя Lz0, Lz1, L z2, Lz3 вдоль оси z.

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

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

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

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

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

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

деление блока данных М перед выполнением преобразований первого раунда на N слоев Lx0, Lx1, способ трехмерного нелинейного преобразования замены, патент № 2519004 , Lx(N-1) вдоль оси х;

деление результата работы первого раунда перед выполнением преобразований второго раунда на N слоев Ly0, Ly1, способ трехмерного нелинейного преобразования замены, патент № 2519004 , Ly(N-1) вдоль оси y;

деление результата работы второго раунда перед выполнением преобразований третьего раунда на N слоев Lz0, Lz1, способ трехмерного нелинейного преобразования замены, патент № 2519004 , Lz(N-1) вдоль оси z;

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

формируют k таблиц замен Si размерностью N×2N каждая, i=0, 1, способ трехмерного нелинейного преобразования замены, патент № 2519004 , (k-1), kспособ трехмерного нелинейного преобразования замены, патент № 2519004 1;

в первом раунде выполняют N двухмерных преобразований замены слоев Lx0, Lx1, способ трехмерного нелинейного преобразования замены, патент № 2519004 , Lx(N-1);

во втором раунде выполняют N двухмерных преобразований замены слоев Ly0, L y1, способ трехмерного нелинейного преобразования замены, патент № 2519004 , Ly(N-1);

в третьем раунде выполняют N двухмерных преобразований замены слоев Lz0, L z1, способ трехмерного нелинейного преобразования замены, патент № 2519004 , Lz(N-1).

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

в первом раунде слой L делят на NN-разрядных векторов-строк R0, R1, способ трехмерного нелинейного преобразования замены, патент № 2519004 , R(N-1), каждый i-й N-разрядный вектор R i, i=0, 1, способ трехмерного нелинейного преобразования замены, патент № 2519004 , (N-1), заменяют N-разрядным вектором из таблицы замен S0 в соответствии с выражением Ri=S 0(Ri), выбранные из таблицы замен N N-разрядных векторов Ri объединяют в преобразованный слой L;

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

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

в первом раунде слой L делят на N N-разрядных векторов-строк R0 , R1, способ трехмерного нелинейного преобразования замены, патент № 2519004 , R(N-1), каждый i-й N-разрядный вектор R i, i=0, 1, способ трехмерного нелинейного преобразования замены, патент № 2519004 , (N-1), заменяют N-разрядным вектором из таблицы замен S в соответствии с выражением Ri=S(Ri), выбранные из таблицы замен N N-разрядных векторов Ri объединяют в преобразованный слой L;

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

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

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

могут использоваться три различные таблицы замен S0, S1 и S2 размерностью N×2n каждая, при этом слои Lxi, расположенные вдоль оси х, заменяют с использованием таблицы замен S0 ; слои Lyi, расположенные вдоль оси y, заменяют с использованием таблицы замен S1, а слои Lzi , расположенные вдоль оси z, заменяют с использованием таблицы замен S2.

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

могут использоваться шесть различных таблиц замен S0, S1, способ трехмерного нелинейного преобразования замены, патент № 2519004 , S5 размерностью N×2n каждая, при этом строки слоев Lxi, расположенных вдоль оси x, заменяют с использованием таблицы замен S0; столбцы слоев Lxi, расположенных вдоль оси x, заменяют с использованием таблицы замен S1; строки слоев Lyi, расположенных вдоль оси y, заменяют с использованием таблицы замен S2 ; столбцы слоев Lyi, расположенных вдоль оси y, заменяют с использованием таблицы замен S3, строки слоев L zi, расположенных вдоль оси z, заменяют с использованием таблицы замен S4; столбцы слоев Lzi, расположенных вдоль оси z, заменяют с использованием таблицы замен S5 .

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

Суть предлагаемого способа иллюстрируют фиг.1-5. На фиг.1, 2 показан принцип двухмерного преобразования слоя, иначе говоря, принцип работы 2D S-блока при N=4. На фиг.1 показан блок 1 данных (слой) 4×4; строки 20, 21, 22, 23 слоя; столбцы 30, 31, 32, 33 слоя. На фиг.2 показаны преобразования замены 40, 41, 42, 43 строк, которые могут выполняться параллельно, и преобразования замены 50 , 51, 52, 53 столбцов, которые также могут выполняться параллельно, входной 6 (исходный) и выходной 7 (преобразованный) блок данных (слой). На фиг.3-5 показан принцип трехмерного преобразования слоя, иначе говоря, принцип работы 3D S-блока при N=4. На фиг.3 показан блок 8 данных 4×4×4 и отдельный бит 9 блока 8 данных. На фиг.4 показано разделение на слои 10xk, 10yk, 10zk, k=0, 1, 2, 3, вдоль осей x, y, z и отдельные слои 10xk, 10yk, 10zk (Lxk, Lyk , Lzk). Ha фиг.5 показаны операции преобразования 11x0, 11x1, 11x2, 11x3 слоев 10x0, 10x2, 10x3 вдоль оси x, которые могут выполняться параллельно; операции преобразования 11y0, 11y1, 11y2, 11y3 слоев 10y0, 10y1, 10y2, 10 y3 вдоль оси y, которые могут выполняться параллельно и операции преобразования 11z0, 11z1, 11 z2, 11z3 слоев 10z0, 10z1 , 10z2, 10z3 вдоль оси z, которые могут выполняться параллельно.

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

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

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

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

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

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

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

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

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

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

- Преобразование 4 SubRows. Преобразование каждого i-го N-разрядного двоичного набора 2iRi:Ri=S[Ri ], i=0, 1, способ трехмерного нелинейного преобразования замены, патент № 2519004 , (N-1);

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

- Преобразование 5 SubColumns. Преобразование каждого /-го N-разрядного двоичного набора 3iC ii=S[Ci], i=0, 1, способ трехмерного нелинейного преобразования замены, патент № 2519004 , (N-1);

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

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

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

- Разбиение входного массива 12 A на N слоев 10xi, Lxi размерностью N×N вдоль оси x, i=0, 1, способ трехмерного нелинейного преобразования замены, патент № 2519004 , (N-1), (фиг.4);

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

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

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

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

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

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

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

Предложены способы выполнения операции замены в двух и трех измерениях с использованием соответственно 2D и 3D 3-блоков. Описаны операции преобразования строк, столбцов и слоев блоков данных. Наиболее очевидное назначение предлагаемых алгоритмов - преобразование N2- и N3-разрядных блоков данных с использованием таблицы замен размерности 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. Таким образом, можно сделать вывод, что достоинством изобретения помимо расширения функциональных возможностей за счет увеличение разрядности блока данных, обрабатываемого одним блоком замены, является более высокая степень параллелизма, что обеспечивает получение заявляемого технического результата - увеличение быстродействия при реализации с использованием гибридных суперкомпьютерных технологий.

ФОРМУЛА ИЗОБРЕТЕНИЯ

Способ трехмерного нелинейного преобразования замены, включающий представление входного блока М и всех промежуточных результатов преобразования разрядностью N3 (N > 1) бит в виде кубического массива битов NхNх N; введение понятие слоя (Layer) - квадратного массива битов NхN; выполнение трех раундов преобразования соответственно вдоль осей х, у, z; деление блока данных М перед выполнением преобразований первого раунда на N слоев L x0, Lx1, ..., Lx(N-1) вдоль оси х; деление результата работы первого раунда перед выполнением преобразований второго раунда на N слоев Ly0, Ly1, ..., L y(N-1) вдоль оси у; деление результата работы второго раунда перед выполнением преобразований третьего раунда на N слоев Lz0, Lz1 , ..., Lz(N-1) вдоль оси z; отличающийся тем, что формируют k таблиц замен Si размерностью Nх2N каждая, i = 0, 1, ..., (k - 1), 1способ трехмерного нелинейного преобразования замены, патент № 2519004 k; в первом раунде выполняют N двухмерных преобразований замены слоев Lx0, Lx1, ..., Lx(N-1); во втором раунде выполняют N двухмерных преобразований замены слоев Ly0 , Ly1, ..., Ly(N-1) ; в третьем раунде выполняют N двухмерных преобразований замены слоев Lz0, Lz1, ..., Lz(N-1), при этом двумерное преобразование замены слоя L выполняется за два шага, на первом шаге слой L делят на NN -разрядных векторов-строк R0, R1 ..., R(N-1) , каждый j-й N-разрядный вектор Rj , j= 0, 1, ..., (N - 1), заменяют N-разрядным вектором из соответствующей таблицы замен Si согласно выражению Rj = Sj (Rj), выбранные из таблицы замен NN- разрядных векторов Rj объединяют в преобразованный слой L; на втором шаге слой L делят на NN -разрядных векторов-столбцов С0 , С1 ..., С (N-1), каждый j N-разрядный вектор Cj, j = 0, 1, (N - 1), заменяют N-разрядным вектором из соответствующей таблицы замен Sj согласно выражению Cj = Sj (Cj), выбранные из таблицы замен N N -разрядных векторов Cj объединяют в преобразованный слой L, который выдают в качестве результата двумерного преобразования замены слоя L.


Скачать патент РФ Официальная публикация
патента РФ № 2519004

patent-2519004.pdf
Патентный поиск по классам МПК-8:

Класс H04L9/00 Устройство для секретной или скрытой связи

Патенты РФ в классе H04L9/00:
способ защищенной связи в сети, устройство связи, сеть и компьютерная программа для этого -  патент 2528078 (10.09.2014)
способ защиты информации -  патент 2527734 (10.09.2014)
способ формирования электронного документа -  патент 2527731 (10.09.2014)
способ многоканального приема и передачи информации по безопасности мореплавания -  патент 2527189 (27.08.2014)
система и способ защиты беспроводной передачи -  патент 2524565 (27.07.2014)
способ и устройство для получения ключа безопасности в ретрансляционной системе -  патент 2523954 (27.07.2014)
способ защиты данных безопасности, передаваемых устройством передатчика в устройство приемника -  патент 2523952 (27.07.2014)
криптография на эллиптической кривой -  патент 2520379 (27.06.2014)
способ управления доступом к набору каналов для приемного или декодирующего устройства (варианты) -  патент 2519395 (10.06.2014)
способ шлифования n-битового блока данных м -  патент 2518950 (10.06.2014)


Наверх