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

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

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

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

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

- количеством запросов пользователей системы;

- актуальностью (датой создания);

- категорией субъекта, отправляемого данные на хранение, и т.д. (От хранения данных к управлению информацией. 2-е изд. - СПб.: Питер, 2016. - 544 с.).

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

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

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

Известны способы контроля целостности данных за счет применения криптографических методов: ключевое хэширование, средства электронной подписи (Патент на изобретение RUS №2680033, 14.02.2019; Патент на изобретение RUS №2680350, 19.02.2019; Патент на изобретение RUS №2680739, 26.02.2019; Патент на изобретение RUS №2696425, 02.08.2019; Патент на изобретение RUS №2707940, 02.12.2019; Патент на изобретение RUS №2726930, 16.07.2020; Патент на изобретение RUS №2730365, 21.08.2020; Патент на изобретение RUS №2758194, 26.10.2021; Патент на изобретение RUS №2758943, 03.11.2021; Патент на изобретение RUS №2759240, 11.11.2021; Патент на изобретение RUS №2771146, 27.04.2022; Патент на изобретение RUS №2771208, 28.04.2022; Патент на изобретение RUS №2771209, 28.04.2022; Патент на изобретение RUS №2771236, 28.04.2022; Патент на изобретение RUS №2771238, 28.04.2022; Патент на изобретение RUS №2771273, 29.04.2022; Патент на изобретение RUS №2774099, 15.06.2022; Патент на изобретение RUS №2785484, 08.12.2022; Патент на изобретение RUS №2785800, 13.12.2022; Патент на изобретение RUS №2786617, 22.12.2022; Патент на изобретение RUS №2793782, 06.04.2023; Шеннон, К. Работы по теории информации и кибернетике / К. Шеннон. - М.: Изд-во иностранной литературы, 1963. - 829 с.; Шнайер, Б. Секреты и ложь. Безопасность данных в цифровом мире / Б. Шнайер. - СПб.: Питер, 2003. - 367 с.), для которых типичны две обобщенные схемы вычисления значений хэш-функции: для каждого подблока в блоке данных и для целого блока данных.

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

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

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

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

Известны способы контроля целостности данных за счет применения некриптографических методов: кодов, корректирующих ошибки (Морелос-Сарагоса, Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / Р. Морелос-Сарагоса; перевод с англ. В.Б. Афанасьев. - М.: Техносфера, 2006. - 320 с.; Хемминг, Р.В. Теория кодирования и теория информации / Р.В. Хемминг; перевод с англ. - М.: «Радио и связь», 1983. - 176 с.).

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

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

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

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

Наиболее близким по технической сущности к заявленному изобретению (прототипом) является способ контроля целостности многомерных массивов данных на основе правил построения кода Рида-Соломона (Патент на изобретение RUS №2785862, 14.12.2022), в котором обеспечивается возможность обнаружения и локализации двух и более блоков данных с признаками нарушения целостности без вычисления и введения для этого высокой избыточности контрольных данных (фиг. 1).

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

Раскрытие изобретения (его сущность)

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

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

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

Поставленная цель достигается тем, что в известном способе контроля целостности данных, заключающемся в том, что для обеспечения возможности обнаружения и локализации данных с признаками нарушения целостности первоначальный массив разбивается на блоки данных фиксированной длины, с которыми в последующем выполняются преобразования, в представленном же способе массив данных М фрагментируют на блоки с более ценными данными и остальные блоки каждый из которых для осуществления контроля целостности данных, обеспечивающего возможность обнаружения и локализации блоков данных с признаками нарушения целостности, представляют как число из расширения поля Галуа и объединяют в один массив где который подлежит кодированию линейным (n'',k'')-кодом V'' с минимальным расстоянием d'', где - информационные блоки, - кодовое слово, при этом через G'' обозначают порождающую матрицу кода, которая является максимальным соединением порождающих матриц G₁ и G₂ линейных (n₁,k₁)- и (n₂,k₂)-кодов V₁ и V₂ с минимальными расстояниями d₁ и d₂ соответственно, что обеспечивает для блоков M_l с более ценными данными большую степень защиты, равную , а для остальных блоков M_j - меньшую, но достаточную степень защиты, равную , в зависимости от требуемой корректирующей способности, что позволяет при контроле целостности данных обеспечивать различный уровень их защищенности в зависимости от степени их ценности, обнаружение и локализацию блоков данных с признаками нарушения целостности выполняют путем разделения кодового слова b на два слова и длиной n₁ и n₂ соответственно, и вычисления остатка от деления полученного кодового слова на порождающий многочлен g₁(x) кода V₁, по результатам чего принимают решение об отсутствии признаков нарушения целостности в случае получение остатка, равного 0, или об обратном.

Сопоставительный анализ заявленного решения с прототипом показывает, что предлагаемый способ отличается от известного тем, что поставленная цель достигается за счет преобразования данных, подлежащих защите от изменений в условиях деструктивных воздействий злоумышленника и возмущений среды функционирования, в блоки M_l с более ценными данными и остальные блоки M_j, каждый из которых представляют как число из расширения поля Галуа и объединяют в один массив, который подлежит кодированию линейным (n'',k'')-кодом V'' с минимальным расстоянием d'', что обеспечивает различный уровень их защищенности в зависимости от степени их ценности.

Контроль целостности блоков данных с разной степенью ценности выполняется посредством использования линейного кода, полученного путем объединения кодов V₁ и V₂ с минимальными расстояниями d₁ и d₂ соответственно, что позволит в момент времени t в условиях деструктивных воздействий злоумышленника и возмущений среды функционирования обеспечить контроль целостности данных, характеризуемый различным уровнем их защищенности в зависимости от степени их ценности. Новым является то, что в предлагаемом способе массив данных М фрагментируют на блоки M_l с более ценными данными и остальные блоки M_j, каждый из которых представляют как число из расширения поля Галуа и объединяют в один массив так, чтобы вначале следовали блоки с более ценными данными. Новым является то, что массив подлежит кодированию линейным (n'',k'')-кодом V'' с минимальным расстоянием d'', полученным путем объединения кодов V₁ и V₂ с минимальными расстояниями d₁ и d₂ соответственно. Новым является то, что обеспечивается для блоков M_l с более ценными данными большая степень защиты, равная а для остальных блоков M_j - меньшая, но достаточная степень защиты, равная в зависимости от требуемой корректирующей способности, что позволяет при контроле целостности данных обеспечивать различный уровень их защищенности в зависимости от степени их ценности. Новым является то, что обнаружение и локализацию блоков данных с признаками нарушения целостности выполняют путем разделения кодового слова b на два слова и длиной n₁ и n₂ соответственно, и вычисления остатка от деления полученного кодового слова на порождающий многочлен кода V₁, по результатам чего принимают решение об отсутствии признаков нарушения целостности в случае получение остатка, равного 0, или об обратном.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Каждый блок данных M_l и M_j представляется как число из расширения поля Галуа . Далее блоки данных объединяются в один массив: где ), причем вначале идут блоки с наиболее важными данными (фиг. 2).

Пусть V - линейный (n,k) - код с минимальным расстоянием d, - информационные символы, - кодовое слово. Через G обозначается порождающая матрица кода V, а через Т - переходная матрица, тогда b=aG и a=bT.

Рассмотрим частный вид соединения первого типа матриц А и В:

где С'' - максимальное соединение матриц А и В.

Для кодирования массива p необходимо получить код V'' с порождающей матрицей G''. Для этого нужно объединить порождающие матрицы G₁ и G₂ кодов V₁ и V₂, которые являются линейными (n₁,k₁)- и (n₂,k₂)-кодами над GF(q^m) с минимальными расстояниями d₁ и d₂ соответственно. В результате получается линейный (n₁+n₂,k₁)-код V'' над GF(q^m) с минимальным расстоянием d'', k₂ информационных символов которого имеют степень защиты . Первые k₁ символов кодового слова кода V'' - это информационные символы, а последние символов - проверочные. Среди k₁ информационных символов k₂ имеют степень защиты t'', а остальные информационные символы, а также проверочные имеют степень защиты

Порождающая матрица G'' строится путем соединения порождающих матриц G₁ и G₂. Она примет вид:

Порождающие матрицы G₁ и G₂ строятся путем деления и на порождающие многочлены g₁(х) и g₂(х). Порождающие многочлены g₁(х) и g₂(х) находятся в соответствии со следующим выражением:

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

Отправляемое на хранение кодовое слово вычисляется путем перемножения строки информационных блоков а на матрицу G'':

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

При обращении пользователя к хранимому слову b' оно разбивается на два слова: и . Производится деление слова на порождающий многочлен g₁(x) кода V₁.

В случае, если остаток от деления равен 0, считается, что целостность блоков данных не нарушена. В противном случае считается, что целостность блоков данных, находящихся на хранении, была нарушена. В таком случае производится их локализация.

С этой целью определяются локаторы ошибок. Для этого вычисляется остаток е(х) от деления на g₁(x), называемый полиномом ошибки. Далее определяется синдром ошибки, степень которого совпадает со степенью полинома ошибки. Коэффициенты полинома синдрома ошибки определяются по формуле , где а - примитивный элемент используемого расширения поля Галуа, i - степень элементов полинома ошибки, где z - степень полинома ошибки.

Многочлен локаторов L(x) определяется как , где Р^-1 представляет собой матрицу, обратную матрице Р.

Матрица Р определяется как

а столбец V находится как

при этом S_t - соответствующий коэффициент полинома синдрома ошибок.

В результате расчета по формуле получается столбец:

После этого L представляется в полиномиальном виде.

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

В результате процесса локализации (фиг. 3) определяются позиции блоков данных с признаками нарушения целостности. В частности, в k₂ информационных блоках, если произошло не более t'' ошибок, а также признаки нарушения целостности в остальных блоках при условии, если произошло не более t₁ ошибок.

Пример. На хранение подлежит отправке следующий массив данных:

Пусть первые 12 символов являются наиболее важными (для них требуется обеспечить высокую степень защиты).

Перед отправкой на хранение массива данных М, в котором некоторые данные имеют наибольшую ценность, выполним кодирование с помощью правил построения кодов с неравной защитой символов. Для этого массив данных М фрагментируем на блоки данных M_l и M_j фиксированной длины m=4.

Получим 3 блока данных которые нужно обеспечить высокой степенью защиты и 6 блоков данных для которых не требуется высокая степень защиты:

- для M_l: М₁=[0111], М₂=[0101], М₃=[1010];

- для M_j: М₁=[0000], M₂=[1001], M₃=[0001], M₄=[0001], М₅=[0001], М₆=[1001].

Далее блоки данных представим в виде наборов символов некоторого алфавита, в качестве которого используется поле Галуа расширения двоичного поля Галуа . Затем блоки данных объединим в массив данных р[9].

Данные после их представления в виде числа из поля Галуа расширения будут выглядеть следующим образом:

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

Для построения кода с неравной защитой символов выберем следующие коды: (15,9)-код V₁ и (7,3)-код V₂ (коды Рида-Соломона).

Код V₁ имеет степень защиты , код V₂ имеет степень защиты

Построим порождающие многочлены кодов V₁ и V₂ (все операции выполняются по правилам арифметики в полях Галуа):

Образующие матрицы для кодов V₁ и V₂ строятся способом, описанным выше.

Для построения кода с неравной защитой символов построим максимальное соединение матриц G₁ и G₂:

Для возможности осуществления контроля целостности данных выполним кодирование данных р, для этого умножим исходные данные на порождающую матрицу кода с неравной защитой символов С=pG''.

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

Допустим, что в данных при хранении возникли ошибки (нарушение целостности данных). При их запросе на использование были получены следующие данные:

Принятое слово b' разобьем на два слова и получим:

Декодируем слово . Запишем слово в полиномиальном виде:

Для обнаружения и исправления ошибки разделим на и получаем полином ошибки:

Полином синдрома ошибки примет вид:

Составим матрицу Р и вектор V:

Найдем обратную матрицу:

Найдем полином локаторов ошибок:

Найдем корни многочлена L(х) и получим:

Локаторы ошибок в таком случае имеют вид:

В соответствии с полученными локаторами блоки с признаками нарушения целостности имеют следующие позиции: х¹⁴, х¹³, х¹².

Таким образом, представлен способ контроля целостности данных, обеспечивающий различный уровень защищенности данных в зависимости от степени их ценности. В частности, приведен пример неравномерного кодирования и локализации блоков данных, имеющих признаки нарушения целостности, при использовании кода с неравной защитой символов (коды Рида-Соломона: (15,9)-код V₁ и (7,3)-код V₂).

Настоящее техническое решение относится к области вычислительной техники. Технический результат заключается в обеспечении контроля целостности данных с различным уровнем защищенности данных в зависимости от степени их ценности. Технический результат достигается за счёт преобразования данных, подлежащих защите от изменений в условиях деструктивных воздействий злоумышленника и возмущений среды функционирования, в блоки M_l с более ценными данными и остальные блоки M_j, каждый из которых представляют как число из расширения поля Галуа и объединяют в один массив, который подлежит кодированию линейным (n'',k'')-кодом V'' с минимальным расстоянием d'', что обеспечивает различный уровень их защищенности в зависимости от степени их ценности. 3 ил.

Способ контроля целостности данных на основе неравномерного кодирования, заключающийся в том, что для обеспечения возможности обнаружения и локализации данных с признаками нарушения целостности первоначальный массив разбивается на блоки данных фиксированной длины, с которыми в последующем выполняются преобразования, отличающийся тем, что массив данных М фрагментируют на блоки с более ценными данными и остальные блоки каждый из которых для осуществления контроля целостности данных, обеспечивающего возможность обнаружения и локализации блоков данных с признаками нарушения целостности, представляют как число из расширения поля Галуа и объединяют в один массив , где который подлежит кодированию линейным (n'',k'')-кодом V'' с минимальным расстоянием d'', где - информационные блоки, - кодовое слово, при этом через G'' обозначают порождающую матрицу кода, которая является максимальным соединением порождающих матриц G₁ и G₂ линейных (n₁,k₁)- и (n₂,k₂)-кодов V₁ и V₂ с минимальными расстояниями d₁ и d₂ соответственно, что обеспечивает для блоков M_l с более ценными данными большую степень защиты, равную а для остальных блоков M_j - меньшую, но достаточную степень защиты, равную , в зависимости от требуемой корректирующей способности, что позволяет при контроле целостности данных обеспечивать различный уровень их защищенности в зависимости от степени их ценности, обнаружение и локализацию блоков данных с признаками нарушения целостности выполняют путем разделения кодового слова b на два слова и длиной n₁ и n₂ соответственно, и вычисления остатка от деления полученного кодового слова на порождающий многочлен g₁(x) кода V₁, по результатам чего принимают решение об отсутствии признаков нарушения целостности в случае получение остатка, равного 0, или об обратном.