Известия РАН. Теория и системы управления, 2021, № 1, стр. 73-78

Введение. В работе рассматриваются вопросы передачи конфиденциальных данных с помощью одного из обобщений минимакса при транспортных ограничениях [1]. Сам минимакс имеет ряд обобщений [2, 3]. Здесь мы воспользуемся одним из них – гиперграфом [4]. Частным случаем гиперграфа является граф. Возможность использования графов для передачи конфиденциальных данных предполагал Клод Шеннон [5]. В современных исследованиях некоторые методы передачи защищенных данных применяют графы в качестве вспомогательных структур, например для работы с ключами или при анализе данных перед обработкой [6]. Также существуют методы, где граф является основным актором преобразования данных. В [7] основой для изменения данных выступает изоморфизм графов. Авторы [8] описывают два симметричных алгоритма для создания многомерных преобразований на базе трех семейств двудольных графов с множествами разбиений, изоморфных ${{\mathbb{K}}^{n}}$, где $\mathbb{K}$ – конечное коммутативное кольцо.

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

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

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

Далее опишем метод конфиденциальной передачи данных посредством экстремальных однородных гиперграфов.

1. Экстремальные однородные гиперграфы. Сначала необходимо дать некоторые определения.

Определение 1. Гиперграф $H = H(V,E) = H({{V}_{n}},E)$ – совокупность множества из т вершин V_n и множества непустых подмножеств множества вершин $E$ [9], ${{e}_{i}}$ – элементы множества E, где $i = \overline {{\text{1,|}}E{\text{|}}} $ называются гиперребрами [4].

Определение 2. Гиперграф ${{H}^{k}} = {{H}^{k}}({{V}_{n}},E)$ называют k-однородным гиперграфом (uniform hypergraph (UH)), если ${\text{|}}{{e}_{i}}{\text{|}} = k$, $\forall {{e}_{i}} \in E$.

Ненаправленные графы без петель – частный случай k-однородных гиперграфов при k = 2. Если рассмотреть 3-однородные гиперграфы, то они известны под названием 2-комплексов [10]. Этот термин пришел из топологии [11].

В отличие от произвольных гиперграфов k-однородные гиперграфы можно представить в виде k-индексной матрицы смежности ${{X}^{k}}({{H}^{k}}) = ({{x}_{{{{i}_{1}} \ldots {{i}_{k}}}}})$, где индексы ${{i}_{j}} = \overline {1,n} $ при $j = \overline {1,k} $.

Среди всех k-однородных гиперграфов нас интересует определенное подмножество – экстремальные однородные гиперграфы. Пусть ${{\mathbb{Z}}_{ + }}$ – множество неотрицательных целых чисел и $n$ – количество координат вектора A. Введем следующие обозначения: $\mathbb{Z}_{ + }^{n} = \{ {\mathbf{A}} = ({{a}_{1}},...,{{a}_{n}})$ : ${{a}_{i}} \in {{\mathbb{Z}}_{ + }}\;\forall i\} $ – множество неотрицательных n-координатных векторов и $\bar {\mathbb{Z}}_{ + }^{n} = \{ {\mathbf{A}} \in \mathbb{Z}_{ + }^{n}:{{a}_{i}} \geqslant {{a}_{{i + 1}}}$, $\forall i,i = \overline {1,n - 1} \} $ – множество неотрицательных n-координатных векторов с упорядоченными по невозрастанию координатами.

Определение 3. Реализацией вектора ${\mathbf{A}} \in \mathbb{Z}_{ + }^{n}$ в k-однородный гиперграф $H = H({\mathbf{A}})$ = H(V, E) называется такой гиперграф, что вектор степеней его вершин есть вектор A.

Пусть вектор A из $\mathbb{Z}_{ + }^{n}$ есть реализуемый в k-однородный гиперграф вектор и ${{\Gamma }^{k}} = \{ H({\mathbf{A}})\} $ – множество всех реализаций (с множеством вершин V_n).

Определение 4. Вектор A из $\mathbb{Z}_{ + }^{n}$, где $n \geqslant 2$, называется k-совершенным, если ${\text{|}}{{\Gamma }^{k}}{\text{|}} = 1$. При этом единственная реализация $H({\mathbf{A}})$ обозначается k-совершенным однородным гиперграфом.

Для определения экстремальности вектора (и гиперграфа) удобно перейти к вектору, координаты которого упорядочены по невозрастанию.

Определение 5. Вектор A из , где $n \geqslant 2$, называется k-экстремальным, если A – k-совершенный вектор. Единственная реализация $H({\mathbf{A}})$ будет экстремальным k-однородным гиперграфом.

Основное преимущество использования экстремальных гиперграфов состоит в том, что между множеством k-экстремальных векторов и множеством экстремальных k-однородных гиперграфов установлено взаимно-однозначное соответствие. Кроме того, существуют быстрые редукционные алгоритмы восстановления k-экстремальных векторов в k-однородный гиперграф при k = 2 [12] и k = 3 [13].

Для создания экстремальных гиперграфов понадобится еще одно понятие – база [14] экстремального k-однородного гиперграфа.

Пусть $n$, $k \in \mathbb{Z}$, $k \geqslant 2$. Для множества индексов ${{I}_{n}} = \{ i \in \mathbb{Z}:i = \bar {n}\} $ (номеров) введем обозначение k-индексных упорядоченных подмножеств множества I_n: $I_{n}^{k} = \{ ({{i}_{1}}, \ldots {{i}_{k}}):{{i}_{j}} = \bar {n}$, ${{i}_{j}} < {{i}_{{j + 1}}}\;\forall j\} $. Определим на $I_{n}^{k}$ частичный порядок: положим $({{i}_{j}}:j = \bar {k}) \geqslant ({{m}_{j}}:j = \bar {k})$, если ${{i}_{j}} \geqslant {{m}_{j}}$ $\forall j$, и $({{i}_{j}}:j = \bar {k}) > ({{m}_{j}}:j = \bar {k})$ при $({{i}_{j}}:j = \bar {k}) \geqslant ({{m}_{j}}:j = \bar {k})$ и $({{i}_{j}}:j = \bar {k})$ ≠ $({{m}_{j}}:j = \bar {k})$.

Построим конструкцию, позволяющую алгебраическим способом описать экстремальный k‑комплекс. Для ${{H}^{k}} = {{H}^{k}}({{V}_{n}},E)$ и ${{X}^{k}}({{H}^{k}}) = ({{x}_{{{{i}_{1}} \ldots {{i}_{k}}}}})$ зададим $I_{n}^{k}({{H}^{k}}) = \{ ({{i}_{1}}, \ldots ,{{i}_{k}}) \in I_{n}^{k}:{{x}_{{{{i}_{1}} \ldots {{i}_{k}}}}} = 1\} $ = = $\{ ({{i}_{1}}, \ldots ,{{i}_{k}}) \in I_{n}^{k}:\{ {{{v}}_{{{{i}_{j}}}}}:j = \bar {k}\} \in E\} $.

Определение 6. Пусть ${{H}^{k}}({{V}_{n}},E)$ – непустой экстремальный k-однородный гиперграф $(E \ne \emptyset )$, а ${{X}^{k}}({{H}^{k}}) = ({{x}_{{{{i}_{1}} \ldots {{i}_{k}}}}})$ – его матрица смежности. Подмножество индексов $\bar {I}_{n}^{k}({{H}^{k}})$ = = $\{ ({{i}_{1}}, \ldots ,{{i}_{k}})\} $ из $\hat {I}_{n}^{k}$ называется базой для комплекса H^k, если выполняются следующие условия:

– для разных элементов $({{i}_{1}}, \ldots ,{{i}_{k}})$ и $({{m}_{1}}, \ldots ,{{m}_{k}})$ из $\bar {I}_{n}^{k}({{H}^{k}})$ отношение порядка в $\hat {I}_{n}^{k}({{H}^{k}})$ не определено;

– для $\forall ({{i}_{1}}, \ldots ,{{i}_{k}}) \in \hat {I}_{n}^{k}({{H}^{k}}){\backslash }\bar {I}_{n}^{k}({{H}^{k}})$ существует такой $({{m}_{1}}, \ldots ,{{m}_{k}}) \in \bar {I}_{n}^{k}({{H}^{k}})$, что существует отношение частичного порядка: $({{i}_{1}}, \ldots ,{{i}_{k}}) < ({{m}_{1}}, \ldots ,{{m}_{k}})$.

Пример 1. Возьмем 4-экстремальный вектор ${\mathbf{A}} = (4,4,4,1,1,1,1)$. Построим его единственную реализацию ${{H}^{4}} = {{H}^{4}}({{V}_{7}},E) = {{H}^{4}}({\mathbf{A}})$, где множество гиперребер $E = \{ \{ {{{v}}_{1}},{{{v}}_{2}},{{{v}}_{3}},{{{v}}_{4}}\} ,\{ {{{v}}_{1}},{{{v}}_{2}},{{{v}}_{3}},{{{v}}_{5}}\} $, $\{ {{{v}}_{1}},{{{v}}_{2}},{{{v}}_{3}},{{{v}}_{6}}\} ,\{ {{{v}}_{1}},{{{v}}_{2}},{{{v}}_{3}},{{{v}}_{7}}\} \} $. Следовательно, $\bar {I}_{7}^{4}({{H}^{4}}) = \{ (1,2,3,7)\} $.

Определение 7. Подмножество индексов $({{m}_{1}}, \ldots ,{{m}_{k}})$ из $\hat {I}_{n}^{k}({{H}^{k}})$ (т. е. ${{x}_{{{{m}_{1}} \ldots {{m}_{k}}}}} = 1$) называется максимальным, если ${{x}_{{{{i}_{1}} \ldots {{i}_{k}}}}} = 0$, $\forall ({{i}_{1}}, \ldots ,{{i}_{k}}) > ({{m}_{1}}, \ldots ,{{m}_{k}})$.

Теорема 1. База состоит из всех максимальных подмножеств индексов.

Теорема 2. Любой экстремальный k-однородный гиперграф ${{H}^{k}} = {{H}^{k}}({{V}_{n}},E)$ имеет единственную базу.

Теорема 3. Пусть $\tilde {I}_{n}^{k} = \{ ({{i}_{1}}, \ldots ,{{i}_{k}}) \in I_{n}^{k}\} $ и между элементами $\tilde {I}_{n}^{k}$ отсутствует отношение частичного порядка. Тогда $\tilde {I}_{n}^{k}$ – база некоторого экстремального k-однородного гиперграфа.

Из теорем 2 и 3 вытекает следующая теорема.

Теорема 4: k-однородный гиперграф H^k является экстремальным тогда и только тогда, когда H^k имеет базу.

Доказательство последних теорем не вызывает затруднений. Приведенные здесь алгоритмы будут расширением и уточнением работы [15], доложенной на конференции “Авиация и космонавтика-2019”.

2. Конфиденциальная передача данных с помощью экстремальных однородных гиперграфов. Для передачи данных нам потребуется ввести несколько переменных:

– $EUH_{n}^{k} = EUH_{n}^{k}({\mathbf{A}}) = EUH_{n}^{k}({{V}_{n}},E)$ – экстремальный k-однородный гиперграф с множеством вершин V_n, и множеством гиперребер E;

– $n$ – количество вершин гиперграфа EUH;

– $N$ – общее количество данных для передачи (в байтах);

– $k$ – размерность гиперграфа EUH;

– $b$ – размер малого блока (в байтах);

– $B$ – размер большого блока (в байтах).

Опишем непосредственно алгоритм действий.

Алгоритм 1. Преобразование данных перед их передачей. На вход подается N байт данных.

Шаг 1. Выбираем размер малого блока b, размерность гиперграфа k и количество вершин в нем $n$. Подсчитываем размер большого блока: $B = bn$.

Шаг 2. Разбиваем на $p = \left\lceil {N{\text{/}}B} \right\rceil $ больших блоков входной поток данных. Дописываем в последний блок с номером $t = pB - N$ следующие значения по одному в каждый малый блок: t, $t + 1$, $t + 2$, $t + 3$, $ \ldots $, $2t - 1$ (если заполнить одинаковыми значениями, то последний блок может быть менее устойчив к линейному перебору).

Шаг 3. Выбирается k-экстремальный вектор A требуемой размерности и соответствующий ему экстремальный k-однородный гиперграф $EUH_{n}^{k}({\mathbf{A}})$ (алгоритм 2 далее).

Шаг 4. Формируем ключевой элемент в виде целочисленного массива из следующих переменных: b, t, p, k, n, вектор A. Преобразуем ключевой элемент по одному из известных алгоритмов, например ГОСТ или AES.

Шаг 5. Передаем преобразованный ключ контрагенту.

Шаг 6. Устанавливаем i = 1.

Шаг 7. Выбираем большой блок ${{B}_{i}}$ и изменяем его (алгоритм 3 далее).

Шаг 8. Передаем преобразованный большой блок контрагенту.

Шаг 9. Если рассматриваемый большой блок не последний ($i < p$), то переходим к следующему большому блоку ($i = i + 1$) и к шагу 7, иначе завершаем алгоритм.

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

Для построения гиперграфа и соответствующего ему вектора воспользуемся тем, что множество баз однозначно соответствует множеству экстремальных k-однородных гиперграфов (см. теорему 4).

Алгоритм 2. Выбор вектора и $EUH_{n}^{k}({\mathbf{A}})$. На вход подается $n$ и k.

Шаг 1. Формируем множество $I_{n}^{k}$, соответствующее множеству всех возможных одноэлементных баз, в этом множестве есть $C_{n}^{k}$ элементов.

Шаг 2. Устанавливаем результирующий n-координатный вектор A = 0.

Шаг 3. Выбираем случайным образом от n до n² количество итераций выбора вектора: n_c.

Шаг 4. Выбираем случайным образом базу из множества $I_{n}^{k}$ и уменьшаем n_c на единицу.

Шаг 5. Получаем вектор ${{{\mathbf{A}}}_{{{{n}_{c}}}}}$ из выбранной базы.

Шаг 6. Выполняем операцию объединения векторов A и ${{{\mathbf{A}}}_{{{{n}_{c}}}}}$ по правилу, описанному в работе [16].

Шаг 7. Если ${{n}_{c}} > 0$, то переходим к шагу 4.

Шаг 8. Результирующий вектор устанавливаем как вектор A.

Шаг 9. По редукционному алгоритму восстанавливаем искомый гиперграф [10, 12, 18, 17 ].

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

Алгоритм 3. Преобразование большого блока. На вход передается b, n, k и выбранный $EUH_{n}^{k}({\mathbf{A}})$.

Шаг 1. Разбиваем большой блок на n малых блоков (обозначим их s) с нумерацией от 1 до n. Устанавливаем взаимно-однозначное соответствие между вершинами выбранного гиперграфа и малыми блоками.

Шаг 2. Устанавливаем j = 1.

Шаг 3. Выделяем в гиперграфе подмножество вершин, имеющих общее гиперребро с j-той вершиной гиперграфа, и чей номер больше j: ${{M}_{j}} = \{ {{{v}}_{{tj}}}\} $, где ${{{v}}_{{tj}}}$ – вершина ${{{v}}_{t}}$ инцидентная вершине j и $t > j$.

Шаг 4. Находим $Y = \mathop \oplus \limits_i {{s}_{i}}$, где i такой, что ${{{v}}_{{ij}}} \in {{M}_{j}}$.

Шаг 5. Изменяем  j блок: ${{s}_{j}} = {{s}_{j}} \oplus Y$.

Шаг 6. Изменяем другие блоки: ${{s}_{i}} = {{s}_{i}} \oplus Y$, где i такой, что ${{{v}}_{{ij}}} \in {{M}_{j}}$.

Шаг 7. Если $j < n - k$, то увеличиваем j на 1 и переходим к шагу 3.

Полученный блок в результате работы алгоритма 3 легко восстановить в первоначальный вариант, если знать структуру использованного гиперграфа.

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

Алгоритм 4. Обратное преобразование блока данных. Входными данными являются ключевой элемент, восстановленный по методу, использованному в шаге 4 алгоритма 1, и данные, измененные по алгоритму 1. Ключевой элемент состоит из переменных b, t, p, k, $n$ и вектора A. Данные могут поступать по одному большому блоку или потоком, что несущественно для алгоритма. Поэтому в рамках алгоритма предполагаем, что каждый раз разбирается очередной большой блок данных.

Шаг 1. Восстанавливаем k-однородный гиперграф по одному из известных редукционных алгоритмов [10, 12, 18, 17 ].

Шаг 2. Устанавливаем $j = n - k$.

Шаг 3. Выделяем в гиперграфе подмножество вершин, инцидентных  j-той вершине гиперграфа, объединяем множество вершин, связанных с первой вершиной ${{M}_{j}} = \{ {{v}_{{tj}}}\} $, где ${{{v}}_{{tj}}}$ – вершина ${{{v}}_{t}}$, инцидентная вершине j и $t > j$.

Шаг 4. Изменяем блоки: ${{s}_{i}} = {{s}_{j}} \oplus {{s}_{i}}$, где i такой, что ${{v}_{{ij}}} \in {{M}_{j}}$.

Шаг 5. Находим $Y = \mathop \oplus \limits_i {{s}_{i}}$, где $i$ такой, что ${{{v}}_{{ij}}} \in {{M}_{j}}$.

Шаг 6. Изменяем  j блок: ${{s}_{j}} = {{s}_{j}} \oplus Y$.

Шаг 7. Если $j > 1$, то уменьшаем j на 1 и переходим к шагу 3.

Если $t \ne 0$, то необходимо последние t байтов убрать из последнего большого блока.

4. Устойчивость алгоритма к атакам. Защита от атак на этот метод преобразования данных базируется на двух вещах. Во-первых, защита ключевого элемента проводится с помощью известного стойкого алгоритма, т.е. гиперграф злоумышленнику. Во-вторых, защита обуславливается мощностью множества экстремальных k-однородных гиперграфов. Рассмотрим экстремальные 2-однородные гиперграфы: ${\text{|}}EUH_{n}^{2}{\text{|}} = {{2}^{{n - 1}}}$. Легко видеть, что стойкость алгоритма, сравнимая с AES128, достигается только на 129 вершинах (${\text{|}}EUH_{2}^{{129}}{\text{|}} = {{2}^{{128}}}$). Это приводит к тому, что ключ становится больше, как и время работы редукционного алгоритма, что не позволяет в реальных приложениях базироваться на преобразовании с помощью $EUH_{n}^{2}$.

Обратимся к случаю k = 3. Рост количества таких гиперграфов на $n$ вершинах быстрее экспоненциального. Этого легко видеть на основе следующего ряда (таблица), полученного экспериментальным способом. В третьем столбце мы видим функцию, демонстрирующую рост ${\text{|}}EUH_{n}^{3}{\text{|}}$ выше экспоненциального. При этом если данную функцию экстраполировать, то можем получить ${\text{|}}EUH_{{28}}^{3}{\text{|}} \approx {{10}^{{44}}}$, что существенно больше ${{2}^{{128}}} \approx 3.4 \times {{10}^{{38}}}$. Таким образом каждый вектор на 28 вершинах содержит больше информации, чем 128-битное число.

Можно задаться вопросом о длине записи вектора A, состоящего из 28 степеней вершин. Максимальная степень вершины при $k = 3$, $n = 28$ равна $C_{{n - 1}}^{{k - 1}} = C_{{27}}^{2} = 351$. Так как ${{2}^{8}} < 351 < {{2}^{9}}$, то для записи одной степени вершины достаточно 9 бит, для всех 28 вершин необходимо $28 \cdot 9 = 252$ бита. Более точная оценка: $28lo{{g}_{2}}351 = 237$ бит.

В работе [17] рассматривается общая формула мощности, которая полностью не определена, но имеет следующий общий вид:

где q, ${{l}_{q}}$, ${{a}_{q}}$ – целочисленные коэффициенты, нелинейно зависящие от n. Это позволяет при сравнительно небольшом количестве вершин получить надежный, устойчивый к линейному перебору ключ, т.е. подобрать его за разумное время не представляется возможным. Также отметим, что при использовании гиперграфов большего порядка стойкость возрастает аналогично формуле (1), только верхняя граница первой суммы будет больше (предположительно сравнимо с n^k), также в числе сочетаний 3 заменяется на k.

Заключение. Сформулируем главный вопрос, возникающий при работе с данным алгоритмом: чем данный метод лучше, чем известные методы, например AES или ГОСТ?

Главное преимущество рассматриваемого алгоритма состоит в том, что он исполняется быстрее. Например, для преобразования большого блока потребуется выполнить не более чем $(n - 1)$(n – k) операций побитового XOR. Таким образом, при условии использования параметров $b = 1$, k = 3 и $n = 32$ потребуется не более 900 операций. В AES128, к примеру, требуется выполнить более 1600 операций для блока длиной 32 байта. Кроме того, редукционный алгоритм восстановления k-однородного гиперграфа является полиномиальным и имеет сложность $O({{n}^{{k - 1}}})$, что также не сильно усложняет процесс получения изначальных данных, так как выполняется единственный раз при начале процесса преобразования или восстановления данных. Стоит отметить, что для рассмотренного алгоритма существует большое пространство для модификаций и улучшений и их изучение – дело дальнейших исследований.