СПОСОБ КОНТРОЛЯ ЦЕЛОСТНОСТИ МНОГОМЕРНЫХ МАССИВОВ ДАННЫХ Российский патент 2022 года по МПК G06F11/08 

Область техники, к которой относится изобретение

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

Уровень техники

а) Описание аналогов

Известны способы контроля целостности данных за счет применения криптографических методов: ключевое и бесключевое хэширование, средства электронной подписи (Патент на изобретение RUS №26207030, 07.12.2015; Патент на изобретение RUS №2669144, 28.11.2017; Патент на изобретение RUS №2680033, 22.05.2017; Патент на изобретение RUS №2680350, 02.05.2017; Патент на изобретение RUS №2680739, 28.11.2017; Патент на изобретение RUS №2686024, 25.04.2018; Кнут, Д.Э. Искусство программирования для ЭВМ. Том 3. Сортировка и поиск / Д.Э.Кнут.- М.: «Мир», 1978. - 824 с; Dichenko, S. Two-dimensional control and assurance of data integrity in information systems based on residue number system codes and cryptographic hash functions / S. Dichenko, O. Finko // Integrating Research Agendas and Devising Joint Challenges International Multidisciplinary Symposium ICT Research in Russian Federation and Europe. 2018. P. 139-146; Диченко, С.А. Гибридный криптокодовый метод контроля и восстановления целостности данных для защищенных информационно-аналитических систем / С. Диченко, О. Финько // Вопросы кибербезопасности. - 2019. - №6(34). - С. 17-36), для которых характерны три обобщенные схемы применения хэш-функции:

- с вычислением одного общего хэш-кода от к блоков данных (фиг. 1);

- с вычислением по одному хэш-коду от каждого из блоков данных (фиг. 2);

- с построением полносвязной сети хэширования (фиг. 3).

Недостатками данных способов являются:

- для схемы применения хэш-функции с вычислением одного общего хэш-кода от к блоков данных:

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

- отсутствие возможности повышения обнаруживающей способности средств контроля в условиях ограничений на допустимые затраты ресурса;

- для схемы применения хэш-функции с вычислением по одному хэш-коду от каждого из блоков данных:

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

- отсутствие возможности повышения обнаруживающей способности средств контроля в условиях ограничений на допустимые затраты ресурса;

- для схемы применения хэш-функции с построением полносвязной сети хэширования:

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

- в общем виде данная модель не позволяет после контроля целостности данных выполнить локализацию блока данных с нарушением целостности;

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

б) Описание ближайшего аналога (прототипа)

Наиболее близким по технической сущности к заявленному изобретению (прототипом) является способ двумерного контроля и обеспечения целостности данных (фиг.4), основанный на осуществлении контроля целостности данных, представленных в виде двумерного массива блоков данных фиксированной длины, от которых предварительно посредством применения хэш-функции к элементам строк массива вычисляются эталонные хэш-коды, значения которых в последующем сравниваются со значениями хэш-кодов, вычисляемых уже от проверяемых блоков данных, при запросе на их использование (Диченко С.А., Самойленко Д.В., Финько О.А. Способ двумерного контроля и обеспечения целостности данных // Патент на изобретение RUS №2696425, 02.08.2019).

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

Раскрытие изобретения

а) Технический результат, на достижение которого направлено изобретение

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

б) Совокупность существенных признаков

Поставленная цель достигается тем, что в известном способе двумерного контроля и обеспечения целостности данных, заключающемся в том, что для осуществления контроля целостности блоки данных M_i (i = 1, 2, …, n) представляются в виде подблоков фиксированной длины M_i,1, M_1,2, …, M_i,n, от которых предварительно вычисляются эталонные хэш-коды H_i хэш-функции h(M_i), значения которых в последующем сравниваются со значениями хэш-кодов хэш-функции вычисляемых уже от проверяемых блоков данных в представленном же способе многомерный массив данных размерности к представляется в виде 3-мерного массива данных М[k, k, k], состоящего из k³ блоков данных M_i,j,r (i = j = r = 0, 1, …, k-1), которые для контроля целостности будут размещаться в массиве размерности k+1, заполняя при этом от 0 до k-1 его блоков, к которым для обнаружения признаков нарушения целостности применяется хэш-функция h, при этом вычисленные хэш-коды H_i,j,r (i, j, r = 0, …, k) будут размещаться в 3k² свободных блоках массива и являться эталонными, значения которых при запросе на использование данных сравниваются со значениями хэш-кодов хэш-функции вычисляемых уже от проверяемых блоков данных

Сопоставительный анализ заявленного решения и прототипа показывает, что предлагаемый способ отличается от известного тем, что поставленная цель достигается за счет представления многомерного массива данных размерности k в виде 3-мерного массива данных М[k, k, k], состоящего из k³ блоков данных M_i,j,r, для обнаружения признаков нарушения целостности которых применяется хэш-функция и вычисляются 3k² хэш-кодов H_i,j,r, что позволяет повысить обнаруживающую способность средств контроля в условиях ограничений на допустимые затраты ресурса.

Контроль целостности k³ блоков данных M_i,j,r будет осуществляться за счет вычисления от них 3k² хэш-кодов H_i,j,r, что позволит в момент времени t в условиях ограничений на допустимые затраты ресурса сравнить их значения со значениями хэш-кодов вычисляемых при запросе на использование данных, подлежащих защите. Новым является то, что многомерный массив данных размерности к представляется в виде 3-мерного массива данных М[k, k, k], состоящего из k³ блоков данных M_i,j,r, которые для контроля целостности будут размещаться в массиве размерности k+1, заполняя при этом от 0 до k-1 его блоков, при этом свободные блоки массива будут предназначаться для эталонных хэш-кодов H_i,j,r. Новым является то, что применение хэш-функции к блокам данных M_i,j,r, расположенным в 3-мерном массиве данных М[k, k, k], позволяет повысить вероятность обнаружения и локализации q-блоков данных с признаками нарушения целостности за счет вычисления и расположения в свободных блоках массива 3k² эталонных хэш-кодов H_i,j,r хэш-функции h(M_i,j,r), значения которых при запросе на использование данных сравниваются со значениями хэш-кодов хэш-функции вычисляемых уже от проверяемых блоков данных

в) Причинно-следственная связь между признаками и техническим результатом

Благодаря новой совокупности существенных признаков в способе реализована возможность:

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

- локализации блоков данных с признаками нарушения целостности;

- повышения обнаруживающей способности средств контроля в условиях ограничений

на допустимые затраты ресурса.

Доказательства соответствия заявленного изобретения условиям патентоспособности «новизна» и «изобретательский уровень»

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

Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность отличительных существенных признаков, обуславливающих тот же технический результат, который достигнут в заявленном способе. Следовательно, заявленное изобретение соответствует условию патентоспособности «изобретательский уровень».

Краткое описание чертежей

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

фиг. 1 - схема применения хэш-функции с вычислением одного общего хэш-кода от к блоков данных;

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

фиг. 3 - схема применения хэш-функции с построением полносвязной сети хэширования;

фиг. 4 - схема, поясняющая порядок контроля целостности данных, представленных в виде двумерного массива блоков данных;

фиг. 5 - схема 3-мерного куба, содержащего блоки данных M_i,j,r;

фиг. 6 - порядок расположения k блоков данных на ребре куба;

фиг. 7 - порядок расположения в кубе размерности k = 3 блоков данных, подлежащих защите, и хэш-кодов;

фиг. 8 - сеть хэширования для обнаружения и локализации 1-кратной ошибки;

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

фиг. 11 - зависимость вероятности Р_обн.1 от размерности k.

Осуществление изобретения

Многомерный массив данных представляется в виде р-мерного массива, состоящего из элементов где индексы ψ₁, …, ψ_р принимают значения от 1 до k_a (а = 1, …, р) соответственно. При этом р-мерный массив данных будет содержать k₁ ×k₂ × … × k_p элементов и обозначаться как

Многомерный массив данных M[k₁, k₂, …, k_p] является математическим множеством, имеющим определенную структуру и аксиоматические правила, что позволяет рассматривать его аналогично пространству, а содержащиеся в нем элементы (блоки данных ) - как точки пространства. Такое пространство будем называть пространством данных.

Пространство данных будет считаться дискретным метрическим пространством, так как содержит в своей структуре точки, представленные элементами массива, изолированными друг от друга в некотором смысле. Внутри многомерного массива данных M[k₁, k₂, …, k_p] все элементы (блоки данных ) располагаются вдоль абстрактных прямых, параллельных осям координат, на одинаковых расстояниях друг от друга.

Пример 1. 3-мерный массив данных M[k₁, k₂, k₃] может быть представлен в виде 3-мерного куба (фиг. 5), содержащего систему координат с осями: x,y,z, по которым откладываются блоки данных M_i,j,r (i = 0, 1, …, k₁-1; j = 0, 1, …, k₂-1; r = 0, 1, …, k₃-1).

Представим 3-мерный массив данных M[k₁, k₂, k₃] в следующем виде:

где стрелка «» с индексом (z) показывает порядок представления массива посредством сечений, ориентированных по оси z; стрелки «→» и «↓» с индексами (х) и (у) указывают направления, в которых возрастают соответствующие индексы у элементов массива по осям х и у.

Если все измерения гиперкуба, содержащего блоки данных, будут иметь одинаковые значения (k₁ = k₂ = … = k_p), то он будет являться правильной фигурой, а его размер может быть описан одним числом k, равным количеству блоков данных, расположенных на его ребре (фиг. 6). Такой гиперкуб будем называть гиперкубом размерности k.

При этом 3-мерный массив данных М[k, k, k]={M_i,j,r} размерности к с помощью сечений ориентации (z) может быть представлен в следующем виде:

где i,j,r = 0, …, k-1.

Разместим 3-мерный массив данных (1) размерности k в массиве размерности k+1, представленном 3-х мерным кубом, заполнив при этом от 0 до k-1 его блоков.

При таком расположении из (k+1)³ блоков 3-мерного куба k³ блоков предназначены для хранения блоков данных, подлежащих защите.

3-мерный массив данных (1) примет вид:

где «0» обозначает свободный для записи блок куба.

Для обнаружения признаков нарушения целостности многомерных массивов данных (блоков данных M_i,j,r (i, j, r = 0, …,k-1)) применим хэш-функцию h.

Разместим полученные эталонные хэш-коды H_i,j,r = 0, …, k) в свободные для записи блоки куба.

Полученный 3-мерный массив, содержащий блоки данных и хэш-коды, с помощью сечений ориентации (z) может быть представлен в следующем виде:

Таким образом, полученный 3-мерный массив (3) может быть представлен в виде 3-мерного куба, содержащего (k+1)³ блоков, в том числе: k³ блоков данных M_{i,j,r (i, j, r = 0, …, k-1), подлежащих защите; 3k² блоков с хэш-кодами Hi,j,r(i, j, r = 0, …, k); 3k+1 свободных для записи блоков.}

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

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

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

Под синдромом ошибки будем понимать двоичное число, полученное при написании символа «0» для каждой выполненной проверки на соответствие значений вычисленного и эталонного хэш-кода и символа «1» при несоответствии сравниваемых значений.

Пример 2. Для контроля целостности многомерных массивов данных разместим в 3-мерном кубе (фиг. 7) блоки данных, подлежащие защите, и соответствующие им хэш-коды.

При этом блоки данных M_i,j,r, подлежащие защите, и вычисленные от них эталонные хэш-коды H_i,j,r интерпретируются как двоичные векторы:

где

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

Полученный 3-мерный массив с помощью сечений ориентации (х) может быть представлен в следующем виде:

Построим сеть хэширования (фиг. 8) для обеспечения возможности обнаружения и локализации 1-кратной ошибки. При этом каждому блоку данных M_i,j,r будет соответствовать неповторяющаяся совокупность трех хэш-кодов H_i,j,r.

Пример 3. В соответствии с построенной сетью хэширования (фиг. 8) блокам данных М₁₀₀, М₀₁₁ соответствуют следующие хэш-коды:

- для М₁₀₀: Н₁₂₀, Н₁₀₂, Н₂₀₀;

- для М₀₁₁: Н₀₂₁, Н₀₁₂, Н₂₁₁,

причем полученные совокупности хэш-кодов для всех блоков данных будут неповторяющимися.

Построим таблицу синдромов ошибок, приводящих к нарушению целостности блока данных M_i,j,r, в которой место ошибки определяется наличием символа «1» в соответствующих столбцах и строках.

Пример 4. Синдромы 1-кратных ошибок, приводящих к нарушению целостности блоков данных [М₁₀₀] и [М₀₁₁], представлены в таблице 1.

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

Сеть хэширования для возможности обнаружения и локализации 2-кратных ошибок представлена на фиг. 9.

Пример 5. Синдромы 2-кратных ошибок, приводящих к нарушению целостности блоков данных [М₁₀₀] и [М₁₁₀], а также [M₀₀₁] и [М₀₁₁], представлены в таблице 2.

Разработанный способ в сравнении с прототипом при ограничениях, наложенных на средства контроля, позволяет повысить вероятность обнаружения и локализации q-кратных ошибок (позволяет обнаруживать и локализовывать 1-, 2-, 3-кратные ошибки, а также до ≈ 98,6% всех 4-кратных ошибок (без учета коллизий)) без увеличения для этого количества вычисляемых хэш-кодов.

В частности, при k = 2 в 3-мерном массиве из всех 70 возможных различных сочетаний четырех блоков данных обнаруживаются и локализуются (без учета коллизий) до и 98,6% всех 4-кратных ошибок, за исключением одной (≈ 1,4%), возникающей в одном из следующих сочетаний блоков данных:

- первое сочетание: М₀₀₁, М₀₁₀, М₁₀₀, М₁₁₁;

- второе сочетание: М₀₀₀, М₀₁₁, M₁₀₁, М₁₁₀.

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

При k = 3 в 3-мерном массиве существует 17550 различных сочетаний по четыре блока данных. В этом случае обнаруживаются и локализуются (без учета коллизий) до ≈ 99,85% всех 4-кратных ошибок, за исключением 27 (≈ 0,15%), которые не обнаруживаются в результате совпадения синдромов ошибок у 27 различных пар сочетаний блоков данных.

Зависимость вероятности Р_обн.1 обнаружения и локализации 4-кратных ошибок (без учета коллизий) от размерности к при ее возрастании представлена на фиг. 11.

Изобретение относится к способу контроля целостности многомерных массивов данных. Технический результат заключается в обеспечении контроля целостности данных. В способе для осуществления контроля целостности блоки данных Mi (i = 1, 2, …, n) представляются в виде подблоков фиксированной длины Mi,1, Mi,2, …, Mi,n, от которых предварительно вычисляются эталонные хэш-коды Hi хэш-функции h(Mi), значения которых в последующем сравниваются со значениями хэш-кодов хэш-функции вычисляемых уже от проверяемых блоков данных при этом многомерный массив данных размерности k представляется в виде 3-мерного массива данных M[k, k, k], состоящего из k3 блоков данных Mi,j,r (r = j = r = 0, 1, …, k-1), которые для контроля целостности будут размещаться в массиве размерности k+1, заполняя при этом от 0 до k-1 его блоков, к которым для обнаружения признаков нарушения целостности применяется хэш-функция h, при этом вычисленные хэш-коды Hi,j,r (i, j, r = 0, …, k) будут размещаться в 3k2 свободных блоках массива и являться эталонными, значения которых при запросе на использование данных сравниваются со значениями хэш-кодов хэш-функции вычисляемых уже от проверяемых блоков данных 11 ил., 3 табл.

Способ контроля целостности многомерных массивов данных, заключающийся в том, что для осуществления контроля целостности блоки данных M_i (i = 1, 2, …, n) представляются в виде подблоков фиксированной длины M_i,1, M_i,2, …, M_i,n, от которых предварительно вычисляются эталонные хэш-коды H_i хэш-функции h(M_i), значения которых в последующем сравниваются со значениями хэш-кодов хэш-функции вычисляемых уже от проверяемых блоков данных отличающийся тем, что многомерный массив данных размерности k представляется в виде 3-мерного массива данных M[k, k, k], состоящего из k³ блоков данных M_i,j,r (r = j = r = 0, 1, …, k-1), которые для контроля целостности будут размещаться в массиве размерности k+1, заполняя при этом от 0 до k-1 его блоков, к которым для обнаружения признаков нарушения целостности применяется хэш-функция h, при этом вычисленные хэш-коды H_i,j,r (i, j, r = 0, …, k) будут размещаться в 3k² свободных блоках массива и являться эталонными, значения которых при запросе на использование данных сравниваются со значениями хэш-кодов хэш-функции вычисляемых уже от проверяемых блоков данных