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

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

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

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

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

Известны способы контроля целостности данных за счет применения криптографических методов: ключевое хэширование, средства электронной подписи (Патент на изобретение RUS №2620730 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; Патент на изобретение RUS №2696425 22.05.2018; Патент на изобретение RUS №2707940 02.12.2019; Патент на изобретение RUS №2726930 16.07.2020; Патент на изобретение RUS №2758194 26.10.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 №2785862 14.12.2022; Патент на изобретение RUS №2786617 22.12.2022; Патент на изобретение RUS №2793782 06.04.2023; Кнут, Д.Э. Искусство программирования для ЭВМ. Том 3 сортировка и поиск [Текст] / Д.Э.Кнут.- М.: «Мир», 1978. - 824 с; Menezes, A.J. Handbook of Applied Cryptography [Текст] / A.J.Menezes, Paul C. van Oorschot, Scott A.Vanstone. - M.: CRC Press, Inc., 1996. - 816 c; Biham, E. A framework for iterative hash functions. - HAIFA [Текст] / E.Biham, O.Dunkelman. - M.: HAIFA, ePrint Archive, Report 2007/278. - 20 c.; To же [Электронный ресурс]. - Режим доступа: eprint.iacr.org/2007/278.pdf (July, 2007); Wang, X. How to break MD5 and Other Hash Function [Текст] / X. Wang, H. Yu. - M.: EUROCRYPT 2005, LNCS 3494, Springer-Verlag 2005. - C. 19-35; Bellare, M. New Proofs for NMAC and HMAC: Security without Collision-Resistance [Текст] / M. Bellare. - M.: CRYPTO 2006, ePrint Archive, Report 2006/043. - 31 с.; To же [Электронный ресурс]. - Режим доступа: eprint.iacr.org/2006/043.pdf (2006); 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. R 139-146; Samoylenko, D. Protection of information from imitation on the basis of crypt-code structures / D. Samoylenko, M. Eremeev, O. Finko, S. Dichenko // Advances in Intelligent Systems and Computing. 2019. №889. P. 317-331.; Диченко, C.A. Концептуальная модель обеспечения целостности информации в современных системах хранения данных. Информатика: проблемы, методология, технологии. Сборник материалов XIX международной научно-методической конференции. Под ред. Д.Н. Борисова. Воронеж. - 2019. - С. 697-701, для которых типичны две обобщенные схемы получения хэш-кодов: для каждого подблока в блоке данных и для целого блока данных.

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

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

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

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

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

Наиболее близким по технической сущности к заявленному изобретению (прототипом) является способ контроля целостности данных на основе правил построения криптографического фрактала (Способ контроля целостности данных на основе правил построения криптографического фрактала / К.Ю. Сопин, Д.М. Симоненко, С.А. Диченко, Д.В. Самойленко, О.А. Финько // Патент на изобретение RU 2808761, 2023 год. Заявка №2023120733 от 07.08.2023), где контроль целостности данных осуществляется путем сравнения значений хэш-кодов, вычисленных при запросе на использование защищаемых данных, расположенных на боковых ребрах треугольников, представленных в виде треугольников Паскаля, объединенных в общую схему по правилам построения треугольника Серпинского, со значениями эталонных хэш-кодов, вычисленных ранее (фиг. 1). При этом, благодаря механизму циклического вычисления хэш-кодов, находящихся на ребрах треугольников Паскаля, а также свойствам самоподобия треугольника Серпинского, осуществляется контроль целостности данных с возможностью обнаружения и локализации признаков ее нарушения в единичных блоках данных, накапливаемых в системах хранения, в том числе, распределенных системах хранения данных.

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

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

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

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

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

Поставленная цель достигается тем, что в известном способе контроля целостности данных, заключающемся в том, что блок данных М, представленный в виде вектора, для осуществления контроля целостности содержащихся в нем данных фрагментируют на блоки данных M⁽¹⁾, М⁽²⁾, М⁽³⁾ фиксированной длины, каждый из которых, в свою очередь, также фрагментируют на блоки данных где ϕ=1, 2, 3; i=1, 2, …, n; j=1, 2, к которым для контроля целостности применяют хэш-фуикцию h, при этом схема хэширования основана на правилах построения треугольника Паскаля и представлена в виде таблицы, имеющей треугольную форму, по боковым сторонам полученного треугольника последовательно размещают блоки данных подлежащие защите, внутри треугольника размещают промежуточные результаты преобразований, вычисляемые от блоков данных подлежащих защите, на нижней стороне треугольника размещают блоки со значениями хэш-функции h, которые вычисляются от блоков данных, подлежащих защите, и результатов промежуточных преобразований нижнего уровня, полученные для блоков данных M^(ϕ), схемы применения хэш-функции h, имеющие треугольные формы, объединяют в общую схему по правилам построения треугольника Серпинского, в представленном же способе общий эталонный хэш-код Н для контроля целостности данных, представленных в виде блока данных М, вычисляют от хэш-кодов расположенных на нижней стороне треугольника, содержащего фрагментированные блоки данных от хэш-кодов а также блоков данных расположенных на правой боковой стороне треугольника, содержащего фрагментированные блоки данных блока данных от хэш-кодов а также блоков данных расположенных на левой боковой стороне треугольника, содержащего фрагментированные блоки данных блока данных полученная система хэш-кодов для контроля целостности блока данных М является начальным промежуточным элементом криптографических фракталов - треугольников Серпинского I^(α) (α=1, 2, 3, …, β), совокупность которых объединяют в общую схему, представленную пирамидой с β угольным основанием таким образом, чтобы между двумя различными треугольниками Серпинского I^(α) было одно общее ребро с блоками данных или относящимися к отдельным хранилищам распределенных систем хранения данных.

Сопоставительный анализ заявленного решения с прототипом показывает, что предлагаемый способ отличается от известного тем, что поставленная цель достигается за счет вычисления общего эталонного хэш-кода Н для контроля целостности данных, представленных в виде блока данных М, от хэш-кодов расположенных на нижней стороне треугольника, содержащего фрагментированные блоки данных от хэш-кодов а также блоков данных расположенных на правой боковой стороне треугольника, содержащего фрагментированные блоки данных блока данных от хэш-кодов а также блоков данных расположенных на левой боковой стороне треугольника, содержащего фрагментированные блоки данных блока данных при этом полученная система хэш-кодов для контроля целостности блока данных М является начальным промежуточным элементом криптографических фракталов - треугольников Серпинского I^(α) (α=1, 2, 3, …, β), совокупность которых объединяют в общую схему, представленную пирамидой с β угольным основанием, что позволяет осуществлять контроль целостности данных при ее нарушении в отдельных хранилищах распределенных систем хранения данных.

Контроль целостности данных при ее нарушении в отдельных хранилищах распределенных систем хранения данных будет осуществляться путем сравнения значений хэш-функции h, вычисленных при запросе на использование защищаемых данных, и эталонных значений, что позволит в момент времени t в условиях воздействий дестабилизирующих факторов определить блоки данных с признаками нарушения целостности. Новым является то, что в предлагаемом способе полученные треугольники Паскаля с блоками данных, подлежащими защите, и вычисленными от них хэш-кодами объединяются в общую схему по правилам построения треугольника Серпинского таким образом, чтобы вычисление общего эталонного хэш-кода Н для контроля целостности данных, представленных в виде блока данных М, осуществлялся от хэш-кодов расположенных на нижней стороне треугольника, содержащего фрагментированные блоки данных от хэш-кодов а также блоков данных расположенных на правой боковой стороне треугольника, содержащего фрагментированные блоки данных блока данных от хэш-кодов а также блоков данных расположенных на левой боковой стороне треугольника, содержащего фрагментированные блоки данных блока данных Новым является то, что полученные треугольники Серпинского I^(α) (α=1, 2, 3, …, β) объединяют в общую схему, представленную пирамидой с β угольным основанием таким образом, чтобы блоки данных и блоки данных каждого I^(α)-го треугольника, относились к отдельным хранилищам распределенных систем хранения данных. Новым является то, что такое объединение треугольников Серпинского I^(α), содержащих блоки данных, подлежащие защите, позволяет осуществить контроль их целостности при ее нарушении в отдельных хранилищах распределенных систем хранения данных.

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

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

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

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

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

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

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

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

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

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

фиг. 2 - схема применения хэш-функции h к блокам данных М^(ϕ), подлежащих защите;

фиг. 3 - общая схема применения хэш-функции h к блокам данных М⁽¹⁾, М⁽²⁾, М⁽³⁾, подлежащих защите;

фиг. 4 - схема, иллюстрирующая порядок получения блоков со значениями H^(ϕ) на первом шаге применения хэш-функции h;

фиг. 5 - схема, иллюстрирующая порядок получения блоков со значениями H^(ϕ) на втором шаге применения хэш-функции h;

фиг. 6 - схема, иллюстрирующая порядок получения блоков со значениями H^(ϕ) на третьем шаге применения хэш-функции h;

фиг. 7 - схема, иллюстрирующая порядок получения блоков со значениями H^(ϕ) на четвертом шаге применения хэш-функции h;

фиг. 8 - схема, иллюстрирующая порядок получения блоков со значениями H^(ϕ) на пятом шаге применения хэш-функции h;

фиг. 9 - схема применения хэш-функции h для контроля целостности блока данных М;

фиг. 10 - схема, иллюстрирующая два шага построения треугольника Серпинского;

фиг. 11 - общая схема построения пирамиды Серпинского (β=4);

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

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

По аналогии со стандартом (ГОСТ Р 53111-2008. Устойчивость функционирования сети связи общего пользования. Требования и методы проверки. - М.: Стандартинформ, 2009. -15 с. ) под дестабилизирующими факторами понимаются воздействия на распределенную систему хранения данных (СХД), источником которых является физический или технологический процесс внутреннего или внешнего по отношению к СХД характера, приводящие к выходу из строя ее элементов. При этом реализация угроз безопасности информации может быть осуществлена в результате как деструктивных воздействий злоумышленника, так и возмущений среды функционирования рассматриваемых СХД. Объектами воздействий могут быть как информация (данные), программно-аппаратные средства обработки и хранения информации (автоматизированные рабочие места, серверы и т.д.), программные средства (системное и прикладное программное обеспечение, системы виртуализации и т.д.), машинные носители информации, содержащие как защищаемую информацию, так и аутентификационную информацию, средства защиты информации и т.д.

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

Блок данных М, подлежащий защите, представленный в виде вектора:

где μ_g ∈ {0,1} (g=1, 2, …, τ), для осуществления контроля целостности содержащихся в нем данных фрагментируется на блоки данных фиксированной длины:

где обозначает операцию конкатенации (объединения).

Каждый из полученных блоков данных M^(ϕ) (ϕ=1, 2, 3) в свою очередь также фрагментируется на блоки данных (i=1, 2, …, n; j=1, 2), к которым для контроля целостности данных применяется хэш-функция h. Схема применения хэш-функции h к полученным блокам данных основана на правилах построения треугольника Паскаля (Успенский, В.А. Треугольник Паскаля / В.А. Успенский. - М.: Наука, 1979. - 48 с.) и представлена в виде таблицы, имеющей треугольную форму (фиг. 2).

По боковым сторонам полученного треугольника последовательно размещены блоки данных (i=1, 2, …, n; j=1, 2), подлежащие защите, внутри треугольника - промежуточные результаты преобразований (блоки со значениями (i=1, 2, …, n-1; j=1, 2, …, n-1) хэш-функции h), вычисляемые от:

- блоков данных (r=1; j=1, 2), подлежащих защите, к примеру:

- блоков данных (r=2, …, n-1; j=1, 2), подлежащих защите, и блоков со значениями (i=1, 2, …, n-2; j=1, 2, …, n-2) хэш-функции h, вычисляемых на предыдущем уровне треугольника, к примеру:

- блоков со значениями (i=1, 2, …, n-2; j=1, 2, …, n-2) хэш-функции h, вычисляемых на предыдущем уровне треугольника, к примеру:

На нижней стороне треугольника - блоки со значениями (i=n; j=1, 2, …, n+2) хэш-функции h, которые вычисляются от блоков данных (i=n; j=1, 2), подлежащих защите, и результатов промежуточных преобразований нижнего уровня:

Блоки со значениями (i=n; j=1, 2, …, n, n+1, n+2) в последующем будут использоваться для контроля целостности блоков данных (i=1, 2, …, n; j=1, 2).

Далее полученные для блоков данных M^(ϕ) (ϕ=1, 2, 3) схемы применения хэш-функции h, имеющие треугольные формы, объединяются в общую схему, как представлено на фиг. 3, с вычислением общего эталонного хэш-кода Н для контроля целостности массива данных М:

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

- хэш-кодов расположенных на нижней стороне треугольника, содержащего фрагментированные блоки данных (i=1, …, n; j=1, …, n+2) блока данных М⁽¹⁾;

- хэш-кодов Н⁽²⁾, а также блоков данных расположенных на правой боковой стороне треугольника, содержащего фрагментированные блоки данных блока данных M⁽²⁾;

- хэш-кодов Н⁽³⁾, а также блоков данных расположенных на левой боковой стороне треугольника, содержащего фрагментированные блоки данных блока данных М⁽³⁾.

Пример 1

На первом шаге получим блоки с промежуточными значениями:

и разместим их, как показано на фиг. 4.

На втором шаге получим блоки с промежуточными значениями:

и разместим их, как показано на фиг. 5.

На третьем шаге получим блоки с промежуточными значениями:

и разместим их, как показано на фиг. 6.

На четвертом шаге получим блоки с промежуточными значениями:

и разместим их, как показано на фиг. 7.

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

и разместим его, как показано на фиг. 8.

Таким образом, получим блок с вычисленным значением общего эталонного хэш-кода Н хэш-функции h, которая применяется ко всем элементам из каждого блока данных М^(ϕ) (ϕ=1, 2, 3), подлежащего защите.

Верхний индекс «ϕ» вычисляемых блоков со значениями G^(ϕ) хэш-функции h определяется верхними индексами блоков со значениями, к которым применяется хэш-функции h.

Пример 2

Блок с промежуточным значением хэш-функции h имеет верхний индекс, равный «1, 2», так как для его вычисления применяются блоки с индексами «1» и «2», в частности и H⁽²⁾.

Блок с промежуточным значением хэш-функции h имеет верхний индекс, равный «2, 3», так как для его вычисления применяются блоки с индексами «2» и «3», в частности

Таким образом, верхние индексы блоков со значениями G^(ϕ) хэш-функции h показывают, к элементам каких блоков данных М^(ϕ), подлежащих защите, применяется хэш-функция для их вычисления.

Общая схема применения хэш-функции h для контроля целостности блока данных М представлена на фиг. 9.

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

Для обеспечения возможности контроля целостности данных при ее нарушении в отдельных хранилищах распределенных СХД совокупность полученных треугольников Серпинского I^(α) (α=1, 2, 3, …, β) требуется объединить в общую схему, представленную пирамидой с β угольным основанием (фиг. 11). В полученной схеме между двумя различными треугольниками Серпинского I^(α) должно быть одно общее ребро с блоками данных или относящимися к отдельным хранилищам распределенных систем хранения данных.

В качестве частного случая на фиг. 12 представлена развертка пирамиды Серпинского с треугольным основанием.

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

Изобретение относится к способу контроля целостности данных на основе криптографической пирамиды Серпинского. Технический результат заключается в возможности контроля целостности данных при ее нарушении в отдельных хранилищах распределенных систем хранения данных. В способе блок данных М, представленный в виде вектора, для осуществления контроля целостности содержащихся в нем данных фрагментируют на блоки данных М⁽¹⁾, M⁽²⁾, M⁽³⁾ фиксированной длины, каждый из которых, в свою очередь, также фрагментируют на блоки данных где ϕ=1, 2, 3; i=1, 2, …, n; j=1, 2, к которым для контроля целостности применяют хэш-функцию h, при этом схема хэширования основана на правилах построения треугольника Паскаля и представлена в виде таблицы, имеющей треугольную форму, по боковым сторонам полученного треугольника последовательно размещают блоки данных подлежащие защите, внутри треугольника размещают промежуточные результаты преобразований, вычисляемые от блоков данных подлежащих защите, на нижней стороне треугольника размещают блоки со значениями хэш-функции h, которые вычисляются от блоков данных, подлежащих защите, и результатов промежуточных преобразований нижнего уровня, полученные для блоков данных М^(ϕ), схемы применения хэш-функции h, имеющие треугольные формы, объединяют в общую схему по правилам построения треугольника Серпинского, при этом общий эталонный хэш-код Н для контроля целостности данных, представленных в виде блока данных М, вычисляют от хэш-кодов расположенных на нижней стороне треугольника, содержащего фрагментированные блоки данных от хэш-кодов а также блоков данных расположенных на правой боковой стороне треугольника, содержащего фрагментированные блоки данных блока данных от хэш-кодов а также блоков данных расположенных на левой боковой стороне треугольника, содержащего фрагментированные блоки данных блока данных полученная система хэш-кодов для контроля целостности блока данных М является начальным промежуточным элементом криптографических фракталов - треугольников Серпинского I^(α) (α=1, 2, 3, …, β), совокупность которых объединяют в общую схему, представленную пирамидой с β угольным основанием таким образом, чтобы между двумя различными треугольниками Серпинского I^(α) было одно общее ребро с блоками данных или относящимися к отдельным хранилищам распределенных систем хранения данных. 12 ил.

Способ контроля целостности данных на основе криптографической пирамиды Серпинского, заключающийся в том, что блок данных М, представленный в виде вектора, для осуществления контроля целостности содержащихся в нем данных фрагментируют на блоки данных М⁽¹⁾, M⁽²⁾, M⁽³⁾ фиксированной длины, каждый из которых, в свою очередь, также фрагментируют на блоки данных где ϕ=1, 2, 3; i=1, 2, …, n; j=1, 2, к которым для контроля целостности применяют хэш-функцию h, при этом схема хэширования основана на правилах построения треугольника Паскаля и представлена в виде таблицы, имеющей треугольную форму, по боковым сторонам полученного треугольника последовательно размещают блоки данных подлежащие защите, внутри треугольника размещают промежуточные результаты преобразований, вычисляемые от блоков данных подлежащих защите, на нижней стороне треугольника размещают блоки со значениями хэш-функции h, которые вычисляются от блоков данных, подлежащих защите, и результатов промежуточных преобразований нижнего уровня, полученные для блоков данных М^(ϕ), схемы применения хэш-функции h, имеющие треугольные формы, объединяют в общую схему по правилам построения треугольника Серпинского, отличающийся тем, что общий эталонный хэш-код Н для контроля целостности данных, представленных в виде блока данных М, вычисляют от хэш-кодов расположенных на нижней стороне треугольника, содержащего фрагментированные блоки данных от хэш-кодов а также блоков данных расположенных на правой боковой стороне треугольника, содержащего фрагментированные блоки данных блока данных от хэш-кодов а также блоков данных расположенных на левой боковой стороне треугольника, содержащего фрагментированные блоки данных блока данных полученная система хэш-кодов для контроля целостности блока данных М является начальным промежуточным элементом криптографических фракталов - треугольников Серпинского I^(α) (α=1, 2, 3, …, β), совокупность которых объединяют в общую схему, представленную пирамидой с β угольным основанием таким образом, чтобы между двумя различными треугольниками Серпинского I^(α) было одно общее ребро с блоками данных или относящимися к отдельным хранилищам распределенных систем хранения данных.