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

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

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

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

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

Известны способы контроля целостности данных за счет применения криптографических хэш-функций (Патент на изобретение RUS №2730365, 21.08.2020; Патент на изобретение RUS №2758194, 26.10.2021; Патент на изобретение RUS №2759240, 11.11.2021; Патент на изобретение RUS №2771146, 27.04.2022; Патент на изобретение RUS №2771209, 28.04.2022; Патент на изобретение RUS №2771236, 28.04.2022; Патент на изобретение RUS №2771273, 29.04.2022; Патент на изобретение RUS №2774099, 15.06.2022; Шеннон, К. Работы по теории информации и кибернетике / К. Шеннон. - М.: Изд-во иностранной литературы, 1963. 829 с; Шнайер, Б. Секреты и ложь. Безопасность данных в цифровом мире / Б. Шнайер. - СПб: Питер, 2003. - 367 с.).

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

- отсутствие возможности восстановления целостности данных;

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

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

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

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

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

Известны способы контроля и восстановления целостности данных за счет применения криптографических методов и методов теории надежности (Патент на изобретение RUS №2680739, 26.02.2019; Патент на изобретение RUS №2696425, 02.08.2019; Патент на изобретение RUS №2707940, 02.12.2019).

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

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

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

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

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

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

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

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

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

Поставленная цель достигается тем, что в известном способе контроля и восстановления целостности многомерных массивов данных, заключающемся в том, что контроль и восстановление целостности данных осуществляется на основе крипто-кодовых конструкций, построенных для многомерных структурированных массивов данных размерности k, состоящих из блоков данных, к которым для возможности обнаружения признаков нарушения целостности применяется хэш-функция h, при этом вычисленные хэш-коды размещаются в свободных блоках массива и являются эталонными, значения которых при запросе на использование данных сравниваются со значениями хэш-кодов, вычисляемых уже от проверяемых блоков данных, при восстановлении целостности блоки данных, подлежащие защите, а также вычисленные от них эталонные хэш-коды являются наименьшими полиномиальными вычетами, при этом полученный массив данных рассматривается как единый суперблок модулярного полиномиального кода, над которым выполняется операция расширения путем введения n-k избыточных оснований, для которых вычисляются соответствующие им избыточные вычеты, дополнительно вводимые для коррекции ошибки, в случае возникновения которой восстановление блоков данных без ущерба для однозначности их представления осуществляется посредством реконфигурации системы путем исключения из вычислений блока данных с признаками нарушения целостности, в представленном же способе контроль и восстановление целостности многомерных массивов данных M[k₁, …, k_p] (k - размерность массива, р - мерность пространства данных) осуществляется на основе крипто-кодовых конструкций, полученных посредством применения ϕ-функции, которые в условиях деградации системы хранения с общим ресурсом V_общ., вызванной деструктивными воздействиями злоумышленника и возмущениями среды функционирования, при израсходывании свободного ресурса V_св. фрагментируются на массивы меньшей размерности Frag(M[k₁, …, k_p])→M[(k-γ)₁, …, (k-γ)_р], где Frag(M[k₁, …, k_p]) - операция фрагментации, γ - число, на которое сокращается размерность массива, от полученного массива данных для осуществления контроля и восстановления целостности данных посредством криптографических и кодовых преобразований в зависимости от требуемых корректирующих способностей вычисляются эталонные хэш-коды и избыточные блоки, при дальнейшей деградации системы хранения полученный массив фрагментируется на массивы, являющиеся объектами, принадлежащими его подпространствам Frag(M[k₁, …,k_p]={М_ψ1, …_{, ψp}})→М[k₁, …, k_p-γ]={М_ψ1,…_,ψ,_р-γ}, (γ - число, на которое сокращается мерность пространства данных), от полученного массива данных также вычисляются эталонные хэш-коды и избыточные блоки, позволяющие выполнить контроль и восстановление целостности данных, подлежащих защите.

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

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

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

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

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

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

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

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

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

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

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

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

фиг. 3 - схема, иллюстрирующая фрагментацию 3-мерного куба на 2-мерные объекты;

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

фиг. 5 схема, иллюстрирующая порядок снижения корректирующих способностей модулярного кода.

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

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

Криптографические преобразования, выполняемые при построении крипто-кодовых конструкций, основываются на применении криптографической хэш-функции (Кнут, Д.Э. Искусство программирования для ЭВМ. Том 3 сортировка и поиск / Д.Э. Кнут. - М.: Мир, 1978. - 824 с.). Применение хэш-функции к массивам данных обеспечивает возможность обнаружения с криптографической достоверностью блока данных или совокупности блоков данных с признаками нарушения целостности.

Под хэш-функцией h понимается функция, отображающая данные М∈{0, 1}* в хэш-коды Н∈{0, 1}^ξ:

h{M)→H,

где «(⋅)*» произвольный размер блока данных, «(⋅)^ξ» фиксированный размер блока с хэш-кодом (ξ∈N), и удовлетворяющая следующим свойствам:

- по вычисленному значению хэш-функции Н∈{0,1}^ξ сложно вычислить исходные данные М∈{0, 1}*, отображаемые в это значение;

- для заданных исходных данных М₁∈{0, 1}* сложно вычислить другие исходные данные М₂∈{0, 1}*, отображаемые в то же значение хэш-функции, то есть h(М₁)=h(M₂), где M₁≠М₂;

- сложно вычислить какую-нибудь пару исходных данных (M₁, M₂), где М₁ ≠М₂,

M_t∈{0, 1}*, t=1, 2, отображаемых в одно и то же значение хэш-функции, то есть h(M₁)=h(M₂).

Под хэш-кодом Н∈{0, 1}^ξ понимается строка бит, являющаяся выходным результатом хэш-функции h.

Строки бит, которые хэш-функция h отображает в хэш-код Н∈{0, 1}^ξ, будут называться блоком данных М∈{0, 1}*.

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

Код, корректирующий ошибки (корректирующий код, помехоустойчивый код) - это код, предназначенный для обнаружения и исправления ошибок. Основная техника - добавление при записи (передаче) в полезные данные специальным образом структурированной избыточной информации, а при чтении (приеме) использование такой избыточной информации для обнаружения и исправления ошибки. Число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода (Блейхут, Р. Теория и практика кодов, контролирующих ошибки / Р. Блейхут; перевод с англ. И.И. Грушко, В.М. Блиновский; под ред. К.Ш. Зигангирова. - М.: Мир, 1986. - 576 с.).

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

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

ƒ(M_к)→М_ρ,

где М_к - информационные блоки данных, содержащиеся в 1-мерном массиве данных M.[k]={М₀, M₁, …, M_k-1} (частный случай); М_ρ - контрольные (избыточные) блоки; к=0, 1, …, k-1; ρ=k, …, n-1.

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

- рабочий ресурс СХД (рабочий объем (V_α) хранящихся в СХД данных);

- свободный ресурс СХД (свободный объем (V_св.) СХД).

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

К тому же, свободный ресурс рассматриваемых СХД сокращается по причине непрерывного роста объема накапливаемых в СХД данных.

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

- целевой ресурс СХД (целевой объем (V_β) хранящихся в СХД данных, предназначенный для хранения целевой информации);

- контрольный ресурс СХД (объем (V_α-V_β) контрольных данных (хэш-коды, дополнительные контрольные (избыточные) блоки), предназначенный для обеспечения возможности контроля и восстановления целостности структурированных массивов данных).

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

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

В зависимости от степени деградации рассматриваемых СХД при сокращении рабочего ресурса СХД целесообразно выполнять ступенчатое («малыми шагами») сокращение сначала контрольного ресурса СХД (без сокращения целевого), постепенно снижая при этом корректирующие способности получаемых крипто-кодовых конструкций до величены, не менее требуемой (минимально допустимой).

Снижение корректирующих способностей получаемых крипто-кодовых конструкций объясняется сокращением объема (V_α-V_β) контрольных данных (числа хэш-кодов, дополнительных контрольных (избыточных) блоков), предназначенного для осуществления контроля и восстановления целостности структурированных массивов данных. Однако, это позволяет продолжать обеспечивать целостность данных (обнаружение и исправление части (в некоторых случаях - всех) возникающих ошибок).

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

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

Операция фрагментация, проводимая за счет разбиения исходного массива данных на:

- массивы меньшей размерности, описывается следующим выражением:

Frag(M[k₁, …, k_p])→М[(k-γ)₁, …, (k-γ)_р];

- массивы, являющиеся объектами, принадлежащими его подпространствам, описывается следующим выражением:

Frag(M[k₁, …,k_p]={М_ψ1,,…_{, ψр}})→М[k_1, …, k_p-γ]={М_ψ1,…_{, ψp-γ}},

где «Frag(M[k₁,…, k_p])» - операция фрагментации; «γ» обозначает число, на которое сокращается размерность массива, или число, на которое сокращается мерность пространства данных, соответственно.

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

Пример 1. Одним из возможных промежуточных результатов выполняемой фрагментации 3-мерного структурированного массива данных, который графически может быть представлен 3-мерным кубом, при вынужденном сокращении целевого ресурса СХД является его разбиение на объекты его подпространства, в частности, на 2-мерные объекты (фиг. 3).

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

Пример 2. Полученный при фрагментации (фиг. 3) массив будет являться 2-мерным структурированным массивом М[k, k] с размерностью к, содержащем блоки данных M_i,j (i, j=0, 1,…, k-1), и может быть представлен в следующем виде:

Вынужденное сокращение мерности пространства данных (целевого ресурса СХД), подлежащих защите, характеризуется определенной степенью деградации СХД, что, как следствие, предполагает изначальное сокращение мерности пространства контроля и восстановления целостности структурированных массивов данных.

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

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

Полученный при фрагментации 2-мерный структурированный массив данных (1) с размерностью k содержит блоки данных M_i,j (i, j=0, …, k-1), подлежащие защите.

Для обеспечения возможности контроля целостности данных полученные блоки данных M_i,j будут интерпретироваться как векторы:

где

Для обеспечения возможности контроля целостности полученного 2-мерного структурированного массива данных (1) в 1-мерном пространстве его элементы - блоки данных M_i,j будут рассматриваться как k элементов 1-мерных подмассивов данных (блоки данных i-х строк массива) и обозначаться:

M⁽ⁱ⁾[k]={M_i,0, M_i,1, …, M_i,k-1}.

С учетом требуемой обнаруживающей способности, а также возможного контрольного ресурса СХД применим к элементам 1-мерных подмассивов данных M⁽ⁱ⁾[k] хэш-функцию h и получим 1-мерные подмассивы с эталонными хэш-кодами:

H⁽ⁱ⁾[k]={H_i,0, H_i,1, …, H_i,k-1},

которые также будут интерпретироваться как векторы:

где

Массив (1) примет вид:

Количество вычисляемых хэш-кодов H_i,j для i-й строки 2-мерного структурированного массива данных (1) будет зависить также от количества вычисляемых дополнительных контрольных (избыточных) блоков для j-го столбца рассматриваемого массива данных, применяемых при восстановлении данных.

Для обеспечения возможности восстановления целостности данных посредством использования математического аппарата кодов, корректирующих ошибки, блоки данных 2-мерного структурированного массива данных (1) будут интерпретироваться:

- как целые неотрицательные числа, представленные в двоичной системе счисления (частный случай):

где g=0, 1, …, τ-1 (при использовании модулярного кода (МК));

- как элементы расширенного поля GF(2^τ):

где - фиктивная переменная; g=0, 1, …, τ-1 (при использовании модулярного полиномиального кода (МПК)).

Для обеспечения возможности восстановления целостности 2-мерного структурированного массива данных (1) в 1-мерном пространстве его элементы - блоки данных будут рассматриваться как k элементов 1-мерных подмассивов данных (блоки данных j-x столбцов массива) и обозначаться:

С учетом требуемой исправляющей способности, а также возможного контрольного ресурса СХД применим к элементам 1-мерных подмассивов данных M^(j)[k] функцию кодирования ƒ (используем выбранный код, корректирующий ошибки, в частности, МК (МПК)) и получим 1-мерные подмассивы с контрольными (избыточными) блоками.

При использовании МК элементы 1-мерных подмассивов данных M^(j)[k] представим как наименьшие неотрицательные вычеты по сгенерированным, упорядоченным по величине, взаимно простым модулям p_i,j, получим информационный суперблок МК, состоящий из информационных блоков данных:

M_0,j, M_1,j, …, M_k-1,j.

Выполним расширение МК путем введения n-k контрольных (избыточных) оснований:

p_k,j, p_k+1,j, …, p_n-1,j

и получим контрольные (избыточные) блоки:

M_k,j, M_k+1,j, …, M_n-1,j,

и, как следствие, соответствующие им 1-мерные подмассивы с контрольными (избыточными) блоками:

M^(j)[n-k]={M_k,j, M_k+1,j, …, M_n-1,j}.

Совокупность контрольных (избыточных) блоков вместе с блоками данных информационного суперблока МК, расположенных в j-м столбце 2-мерного структурированного массива данных (1) образуют кодовый вектор МК.

Получим структурированный массив с контрольными (избыточными) блоками кодового вектора МК:

где ρ=k, k+1…, n-1.

Таким образом, на основе ϕ-функцией следующего вида:

где i, j=0, 1, …, k-1; символ «1D» обозначает, что 1-мерные криптографические (применение хэш-функции h) и кодовые (использование кодов, корректирующих ошибки, в частности, МК (функция кодирования ƒ)) преобразования выполняются над элементами структурированного массива данных М[k, k], представленного в 2-мерном пространстве данных («2D»); получим крипто-кодовую конструкцию, которая при сопоставлении блоков данных M_ρ,j, интерпретируемых как целые неотрицательные числа, их векторам:

где символ «⇒» - операция сопоставления; может быть представлена 2-мерным массивом:

где G_i,j получены посредством:

где символ «⊕» обозначает суммирование в поле Галуа GF(2); n=2k.

При этом ϕ-функция (2) примет вид:

ϕ^(2D)(h^(1D)(M_i,j), ƒ^(1D)(M_i,j))→Ψ[k,2k].

Данные, подлежащие защите, представленные в виде (3), могут быть отправлены на хранение.

При использовании МПК элементы 1-мерных подмассивов данных [k] представим как наименьшие полиномиальные вычеты по основаниям таким, что

где i₁, i₂=0, 1, …, k-1; i₁≠i₂.

При этом

где - степень полинома

Представим блоки данных как единый суперблок МПК по системе оснований:

В соответствии с Китайской теоремой об остатках для многочленов для заданного множества многочленов при выполнении условия (4), и многочленов таких, что выполняется условие (5), система сравнений:

будет имеет единственное решение

Выполним операцию расширения МПК путем введения n-k контрольных (избыточных) оснований:

и в соответствии с:

получим контрольные (избыточные) вычеты:

При выполнении условия (4) для i₁, i₂=0, 1, …, n-1; i₁≠i₂, а также получим расширенный МПК в кольце многочленов:

и структурированный массив:

Сопоставим многочлены:

их векторам:

Выполним по аналогичным с использованием МК правилам операцию суммирование в поле Галуа GF(2) эталонных хэш-кодов и контрольных (избыточных) блоков, получим массив (3), отправляемый на хранение.

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

При запросе на использование данных, находящихся на хранении, представленных массивом (3), выполним контроль их целостности. При этом массив (3):

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

Выполним сопоставление блоков данных, интерпретируемых как векторы где i, j=0, 1, …, k-1, их блокам данных, представленным в виде:

- целых неотрицательных чисел (в двоичной системе счисления):

- элементов расширенного поля GF(2^τ):

Проведем операцию расширения информационного суперблока МК (при использовании МК) или МПК (при использовании МПК), в результате которой получим контрольные (избыточные) блоки: соответственно.

Получим расширенный МК (расширенный МПК в кольце многочленов):

и соответствующие им структурированные массивы:

- для расширенного МК:

- для расширенного МПК в кольце многочленов:

Выполним обратное сопоставление полученных контрольных (избыточных) блоков, представленных в виде:

- целых неотрицательных чисел (в двоичной системе счисления) блокам, представленным в виде векторов:

где ρ=k, k+1,…,n-1;

- элементов расширенного поля GF(2^τ) также блокам, представленным в виде векторов:

Проведем обратные преобразования:

и получим хэш-коды:

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

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

При обнаружении признаков нарушения целостности данных выполним локализацию i-й строки (строк) массива (3) - 1-мерного подмассива (1-мерных подмассивов) данных M⁽ⁱ⁾[k], содержащего (содержащих) блок (блоки) данных с признаками нарушения целостности.

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

Local (М[k, k])→[M⁽ⁱ⁾[k]],

где «Local (М[k, k])» - операция локализации; символ «[⋅]» обозначает локализованный 1-мерный подмассив данных M⁽ⁱ⁾[k] с признаками нарушения целостности; [M⁽ⁱ⁾[k]]≠М⁽ⁱ⁾[k].

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

Local(M_i,0, M_i,1, …, M_i,k-1)→[M_i,j],

где символ «[⋅]» в этом случае обозначает локализованный блок данных M_i,j с признаками нарушения целостности; [M_i,j]≠M_i,j.

Порядок восстановления целостности данных заключается в следующем.

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

Порядок локализации и восстановления целостности блока (блоков) данных поясняется при использовании МК (частный случай).

В соответствии с математическим аппаратом МК, основанным на фундаментальных положениях Китайской теоремы об остатках, для обеспечения возможности восстановления целостности полученного структурированного массива (3) его блоки данных M_i,j - элементы 1-мерного подмассива данных M^(j)[k] будут интерпретироваться как наименьшие неотрецательные вычеты α_0,j, α_1,j, …, α_k-1,j целого неотрицательного числа A_j по основаниям p_0,j, p_1,j, …, p_k-1,j.

При этом для числа A_j по основаниям p_k,j, …, p_n-1,j требуется вычислить контрольные (избыточные) вычеты α_k,j, …, α_n-1,j так, чтобы число A_j можно было однозначно представить набором попарно простых вычетов:

A_j=(α_0,j, α_1,j, …, α_k-1,j, α_k,j, …, α_n-1,j)MA

по основаниям модулярной арифметики (MA):

p_0,j<p_1,j<….<p_k-1,j<p_k,j<…<p_n-1,j,

где P_k-1,j=p_o,jp_1,j… p_k-1,j>A_j; - наименьший неотрицательный вычет числа A_j по модулю

Таким образом, вычеты MA α_0,j, α_1,j, …, α_k-1,j будут интерпретироваться как блоки данных M_0,j, M_1,j, …, M_k-1,j и считаться информационными (информационной группой k блоков данных), a α_k,j,…, α_n-1,j - как блоки M_k,j, …, M_n-1,j и считаться контрольными (избыточными) (контрольной (избыточной) группой (n-k) блоков).

При этом сама МА является расширенной, где P_n-1,j=P_k-1,jp_k,j…p_n-1,j, и охватывает полное множество состояний, представляемых n вычетами системы.

Эта область будет являться полным диапазоном МА [0, P_n-1,j) и состоять из рабочего диапазона [0, P_k-1,j), определяемого неизбыточными основаниями МА (блоками данных M_0,j, M_1,j, …, M_k-1,j), и диапазона [P_k-1j, P_n-1,j), определяемого контрольными (избыточными) основаниями МА (блоками M_k, …, M_n-1) и представляющего недопустимую область.

Это будет означать, что операции над числом A_j выполняются в диапазоне [0, P_n-1,j), и если результат операции МА выходит за пределы P_k-1,j, то следует вывод о нарушении целостности данных (возникновении ошибки).

Проверка этого правила позволяет локализовать блок (блоки) данных M_i,j с признаками нарушения целостности (возникшую ошибку).

Пример 3. Рассмотрим 2-мерный структурированный массив данных М[k, k], в котором требуется обнаружить и локализовать блок данных M_i,j (i=0, 1, …, 3) с признаками нарушения целостности в j-м столбце.

Выберем систему оснований p_0,j=2, p_1,j=3, p_2,j=5, p_3,j=7, для которой рабочий диапазон равен:

P_3,j=p_0,jp_1,jp_2,jp_3,j=2⋅3⋅5⋅7=210.

Введем контрольные (избыточные) основания p_4,j=11, P_5,j=13, удовлетворяющие условиям применения МК.

Тогда полный диапазон определяется как

P_5,j=P_3,jp_4,jp_5,j=210⋅11⋅13=30030.

В соответствии с Китайской теоремой об остатках вычислим ортогональные базисы системы:

Пусть блоки данных, подлежащие защите, 1-мерного подмассива данных M^(j)[k] вместе с контрольными (избыточными) блоками, интерпретируемые как наименьшие неотрицательные вычеты целого неотрицательного числа A_j вида:

A_j=(1, 2, 2, 3, 6, 4)=17,

отправлены на хранение (фиг. 4).

При запросе на использование данных получили следующее число (данные):

Для проверки на наличие (отсутствие) признаков нарушения целостности полученных данных (возникшей ошибки) вычислим величину числа

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

С учетом результатов предварительной локализации блока данных с признаками нарушения целостности по i-м строкам массива (к примеру, определено, что блок данных с признаками нарушения целостности расположен во второй строке массива (i=1)), а также в результате локализации по столбцам и определении j-го столбца массива, в котором расположен блок данных с признаками нарушения целостности сделаем вывод о том, что ошибочна цифра [α_1,j]=1 (блок данных [M_1,j]) по основанию p_1,j=3.

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

Локализация блоков данных с признаками нарушения целостности также может быть выполнена посредством вычисления проекций числа (Акушский, И.Я. Машинная арифметика в остаточных классах / И.Я. Акушский, Д.И. Юдицкий. - М.: Сов. радио, 1968. - 440 с.).

После локализации блока данных [M_i,j] с признаками нарушения целостности (возникшей ошибки) на основе использования математического аппарата избыточных МК выполняется операция реконфигурации.

Операция реконфигурации выполняется за счет вычисления A_j из системы:

по «правильным» основаниям МА (с учетом исключения «неправильного» основания МА):

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

В соответствии с (7) вычислим:

получим: A_j=17<210.

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

Пример 4. В соответствии с (8) вычислим:

α_1,j ≡A_j mod p_1,j≡17 mod 3,

получим: α_1,j=2.

Таким образом, при использования математического аппарата МК может быть выполнена локализация блока (блоков) данных [M_i,j] с признаками нарушения целостности, а также посредством последовательной реконфигурации системы восстановлена его (их) целостность.

При использовании МПК для локализации блока (блоков) данных с нарушением целостности критерием отсутствия признаков ее нарушения (обнаруживаемых ошибок) является выполнение неравенства:

где - решение системы сравнений для

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

После локализации блока (блоков) данных с признаками нарушения целостности по аналогичным правилам выполняется процедура ее восстановления.

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

где повторно вычислено с учетом исключения блока с признаками нарушения целостности; при этом количество вводимых n-k контрольных (избыточных) блоков определяется требуемыми корректирующими способностями применяемого МПК.

Подтверждение с криптографической достоверностью целостности данных после процедуры восстановления обеспечивается за счет выполнения операции суммирование в поле Галуа GF(2) при вычислении G_i,j, а также обратных преобразований при вычислении

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

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

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

При дальнейшей деградации СХД при израсходовании свободного ресурса СХД происходит сокращение рабочего ресурса СХД, которое может привести:

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

- либо к потере части целевой информации (при сокращении целевого ресурса СХД).

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

Сокращение контрольного ресурса СХД, в свою очередь, может выполняться либо за счет сокращения мерности контроля и восстановления целостности данных, либо размерности 1-мерных кодовых векторов, полученных при расширении МК - 1-мерных подмассивов данных M^(j)[k], элементы которых интерпретироваться как наименьшие неотрицательные вычеты.

В соответствии с представленными примерами сокращение размерности 1-мерного кодового вектора на один элемент будет характеризоваться введением не двух контрольных (избыточных) оснований p_4,j, p_5,j, а одного p_4,j. При этом корректирующая способность получаемого кода позволит гарантированно (с учетом возникновения ошибки определенной кратности) обеспечивать целостность данных при ее нарушении в единичном блоке данных, содержащемся в 1-мерном подмассиве данных М^(j)[k].

Для обнаружения и локализации q блоков данных с признаками нарушения целостности, в частности, 2-х блоков данных (2-кратной ошибки по двум основаниям системы) число A_j будет вычисляться следующим образом:

где - ортогональный базис; - целое положительное число (вес ортогонального базиса), подбираемое так, чтобы имело место следующее сравнение: σ⁽¹⁾, σ⁽²⁾=0, 1, …, k-1, …, n-1.

Вычисление числа возможных сочетаний блоков с признаками нарушения целостности (возникающих ошибок) производится следующим образом:

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

Пример 5. При нарушении целостности 2-х из оставшихся 5-ти блоков (возникновение 2-кратной ошибки) число возможных сочетаний блоков с признаками нарушения целостности равно:

С учетом того, что корректирующая способность полученного кода позволяет гарантированно (с учетом возникновения ошибки определенной кратности) обеспечивать целостность данных при ее нарушении в единичном блоке данных, содержащемся в 1-мерном подмассиве данных М^(j)[k], целостность второго блока данных будет восстановлена только при условии, что этим блоком будет любой блок, кроме блока данных M_3,j, так как основание р_3,j системы, по которому он был получен уже будет являться не информационным, а контрольным (избыточным) (фиг. 5).

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

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

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

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

Способ контроля и восстановления целостности многомерных массивов данных в условиях деградации систем хранения, заключающийся в том, что контроль и восстановление целостности данных осуществляется на основе крипто-кодовых конструкций, построенных для многомерных структурированных массивов данных размерности k, состоящих из блоков данных, к которым для возможности обнаружения признаков нарушения целостности применяется хэш-функция h, при этом вычисленные хэш-коды размещаются в свободных блоках массива и являются эталонными, значения которых при запросе на использование данных сравниваются со значениями хэш-кодов, вычисляемых уже от проверяемых блоков данных, при восстановлении целостности блоки данных, подлежащие защите, а также вычисленные от них эталонные хэш-коды являются наименьшими полиномиальными вычетами, при этом полученный массив данных рассматривается как единый суперблок модулярного полиномиального кода, над которым выполняется операция расширения путем введения n-k избыточных оснований, для которых вычисляются соответствующие им избыточные вычеты, дополнительно вводимые для коррекции ошибки, в случае возникновения которой восстановление блоков данных без ущерба для однозначности их представления осуществляется посредством реконфигурации системы путем исключения из вычислений блока данных с признаками нарушения целостности, отличающийся тем, что контроль и восстановление целостности многомерных массивов данных M[k₁, …, k_p] (k - размерность массива, р - мерность пространства данных) осуществляется на основе крипто-кодовых конструкций, полученных посредством применения ϕ-функции, которые в условиях деградации системы хранения с общим ресурсом V_oбщ., вызванной деструктивными воздействиями злоумышленника и возмущениями среды функционирования, при израсходовании свободного ресурса V_св. фрагментируются на массивы меньшей размерности Frag(M[k₁, …, k_p])→М[(k-γ)₁, …, (k-γ)_р], где Frag(M[k₁, …, k_p]) - операция фрагментации, γ - число, на которое сокращается размерность массива, от полученного массива данных для осуществления контроля и восстановления целостности данных посредством криптографических и кодовых преобразований в зависимости от требуемых корректирующих способностей вычисляются эталонные хэш-коды и избыточные блоки, при дальнейшей деградации системы хранения полученный массив фрагментируется на массивы, являющиеся объектами, принадлежащими его подпространствам Frag(M[k₁, …, k_p]={М_{ψ1, …, ψр}})→М[k_1, …, k_p-γ]={М_{ψ1, …, ψр-γ}}, (γ - число, на которое сокращается мерность пространства данных), от полученного массива данных также вычисляются эталонные хэш-коды и избыточные блоки, позволяющие выполнить контроль и восстановление целостности данных, подлежащих защите.