СПОСОБ КОНТРОЛЯ И ВОССТАНОВЛЕНИЯ ЦЕЛОСТНОСТИ ОДНОМЕРНЫХ МАССИВОВ ДАННЫХ НА ОСНОВЕ КОМПЛЕКСИРОВАНИЯ КРИПТОГРАФИЧЕСКИХ МЕТОДОВ И МЕТОДОВ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ
METHOD FOR INTEGRITY CONTROL AND RESTORE OF ONE-DIMENSIONAL DATA ARRAYS BASED ON COMPLEXING CRYPTOGRAPHIC METHODS AND METHODS FOR NOISE-RESISTANT CODING

Область техники, к которой относится изобретение
Предлагаемое изобретение относится к информационным технологиям и может быть использовано для контроля и восстановления целостности представленной в 1-мерном пространстве данных информации, непрерывно накапливаемой в системах хранения данных в условиях деструктивных воздействий злоумышленника и возмущений среды функционирования.
Уровень техники
а) Описание аналогов
Известны способы контроля целостности данных за счет применения криптографических методов: ключевое хэширование, средства электронной подписи (Заявка на патент РФ №2012107193/08 публ. 10.10.2013; Заявка на патент РФ №2006116797/09 публ. 27.01.2008; Заявка на патент РФ №2007141753/09 публ. 10.09.2010; Заявка на патент РФ №2013149120/08 публ. 10.05.2015; Заявка на патент РФ №2004110622/09 публ. 10.10.2007; Заявка на патент РФ №2005113932/09 публ. 20.01.2007; Кнут, Д.Э. Искусство программирования для ЭВМ. Том 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 с.; 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 c.; To же [Электронный ресурс]. - Режим доступа: eprint.iacr.org/2006/043.pdf (2006)), для которых типичны две обобщенные схемы получения хэш-кодов: для целого массива данных и для каждого блока данных, содержащегося в рассматриваемом массиве.
Недостатками данных способов являются:
- высокая избыточность контрольной информации при хэшировании каждого блока данных, содержащегося в рассматриваемом массиве, при небольшой их размерности;
- отсутствие возможности обнаружения и локализации отдельных блоков данных с признаками нарушения целостности при хэшировании целого массива данных.
Известны способы восстановления целостности данных за счет применения различных видов резервирования (с использованием программно-аппаратной или программной реализации технологии RAID (Redundant Array of Independent Disks) (RAID-массивы), методы дублирования, методы избыточного кодирования) (Патент США №7392458 публ. 24.06.2008; Патент США №7437658 публ. 14.10.2008; Патент США №7600176 публ. 06.10.2009; Заявка на патент США №20090132851 публ. 21.05.2009; Заявка на патент США №20100229033 публ. 09.09.2010; Заявка на патент США №201101145677 публ. 16.06.2011; Заявка на патент США №20110167294 публ. 07.07.2011; Заявка на патент США №20110264949 публ. 27.10.2011; Уоррен, Г. Подсчет битов: алгоритмические трюки для программистов (Hacker's Delight) [Текст] / Г. Уоррен, мл. - М.: «Вильямс», 2007. - 512 с; Морелос-Сарагоса, Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение [Текст] / Р.Морелос-Сарагоса; перевод с англ. В.Б. Афанасьев. - М.: Техносфера, 2006. - 320 с.; Хемминг, Р.В. Теория кодирования и теория информации [Текст] / Р.В. Хемминг; перевод с англ. - М.: «Радио и связь», 1983. - 176 с.).
Недостатком данных способов является:
- высокая избыточность.
б) Описание ближайшего аналога (прототипа)
Наиболее близким по технической сущности к заявленному изобретению (прототипом) является способ многоуровневого контроля и обеспечения целостности данных (Патент РФ №2707940 публ. 02.12.2019), в котором контроль целостности представленной в 1-мерном пространстве данных информации осуществляется на верхнем уровне за счет множества хэш-кодов, полученных с помощью стандартной процедуры реализации хэш-функции от совокупности данных в порядке, определенном специальной процедурой выбора блоков данных, основанной на математическом аппарате линейной алгебры (линейной системы хэш-кодов), а восстановление целостности при этом обнаруженного и локализованного блока данных осуществляется на нижнем уровне посредством применения кодов, корректирующих ошибки (фиг. 1). Применение линейной системы хэш-кодов к предварительно закодированным данным позволяет обнаружить, локализовать и восстановить целостность блока данных с признаками ее нарушения без необходимости введения высокой избыточности.
Недостатком известного способа является отсутствие возможности обнаружения, локализации и восстановления целостности информации, представленной в 1-мерном пространстве данных, при нарушении целостности х блоков данных в условиях деструктивных воздействий злоумышленника и возмущений среды функционирования.
Раскрытие изобретения
а) Технический результат, на достижение которого направлено изобретение
Целью настоящего изобретения является разработка способа контроля и восстановления целостности 1-мерных массивов данных на основе комплексирования криптографических методов и методов помехоустойчивого кодирования с возможностью обнаружения, локализации и восстановления целостности х блоков данных с признаками ее нарушения без необходимости введения высокой избыточности в условиях деструктивных воздействий злоумышленника и возмущений среды функционирования.
б) Совокупность существенных признаков
1
2
n
n+1
n+2
Поставленная цель достигается тем, что в известном способе контроля и обеспечения целостности данных, заключающемся в том, что для обнаружения, локализации и восстановления целостности 1-мерного массива данных, содержащиеся в нем данные представляются в виде блоков данных фиксированной длины m, m, …, m, которые являются информационной группой n блоков, к которой по правилам построения избыточных кодов добавляется дополнительная контрольная группа r блоков m, …, m, вводимая для коррекции ошибки, при возникновении которой восстановление целостности массива данных осуществляется посредством применения математического аппарата избыточных кодов, а обнаружение ошибки выполняется на основе вычисленной от них эталонной системы хэш-кодов, правила построения которой определяются математическим аппаратом линейной алгебры, в представленном же способе 1-мерный массив данных M[k] разбивается на отдельные 1-мерные структурированные массивы данных  при условии, что i=1, 2, …, х,  содержащиеся в них элементы  для обеспечения возможности применения криптографических и кодовых преобразований при контроле и восстановлении их целостности в условиях деструктивных воздействий злоумышленника и возмущений среды функционирования представляются по правилам построения кодового слова, при этом блоки данных  будут интерпретироваться как целые неотрицательные числа и считаться k информационными блоками данных, для которых в количестве, достаточном для обеспечения возможности восстановления целостности отдельного 1-мерного структурированного массива данных  по правилам построения кодов, корректирующих ошибки, вычисляются r дополнительных контрольных блоков данных  полученная совокупность информационных и дополнительных контрольных блоков данных будет считаться кодовым словом (n, k)-кода, после выполнения кодовых преобразований получим массив с элементами  которые для обеспечения возможности контроля их целостности будут интерпретироваться как двоичные векторы  от которых посредством применения криптографической хэш-функции h вычисляются хэш-коды  где j=0, 1, …, η-1, при этом выбор совокупности блоков данных для хэширования будет определяться на основе математического аппарата теории систем векторов и линейных векторных пространств, после выполнения криптографических преобразований над элементами массива получим на основе комплексирования криптографических методов и методов помехоустойчивого кодирования крипто-кодовую конструкцию, правила построения которой определяются и могут быть описаны посредством ϕ-функции, при этом обеспечивающую обнаружение, локализацию и восстановление целостности х блоков данных с признаками ее нарушения без необходимости введения высокой избыточности.
Сопоставительный анализ заявленного решения с прототипом показывает, что предлагаемый способ отличается от известного тем, что поставленная цель достигается за счет разбиения 1-мерного массива данных M[k] на отдельные 1-мерные структурированные массивы данных  при условии, что i=1, 2, …, х,  при этом содержащиеся в них элементы  в зависимости от выполняемых над ними операций интерпретируются как целые неотрицательные числа при кодовых преобразованиях или как двоичные векторы при криптографических преобразованиях, в результате которых образуется крипто-кодовая конструкция, правила построения которой определяются и могут быть описаны посредством ϕ-функции, полученная крипто-кодовая конструкция обеспечивает при этом обнаружение, локализацию и восстановление целостности х блоков данных с признаками ее нарушения без необходимости введения высокой избыточности. Контроль целостности блоков данных, интерпретируемых как двоичные векторы  будет осуществляться путем сравнения значений хэш-функции, вычисленных при запросе на использование защищаемых данных, и эталонных значений, что позволит в момент времени t в условиях деструктивных воздействий злоумышленника и возмущений среды функционирования определить блоки данных с признаками нарушения целостности. Новым является то, что в предлагаемом способе 1-мерный массив данных М[л] разбивается на отдельные 1-мерные структурированные массивы данных  при условии, что i=1, 2, …, х,  в результате выполнения криптографических и кодовых преобразований над элементами которых обеспечивается возможность обнаружения, локализации и восстановления целостности х блоков данных с признаками ее нарушения. Новым является то, что на основе комплексирования криптографических методов и методов помехоустойчивого кодирования образуется крипто-кодовая конструкция, правила построения которой определяются и могут быть описаны посредством ϕ-функции, которая обеспечивает обнаружение, локализацию и восстановление целостности блоков данных с признаками ее нарушения в количестве, определяемом еще при разбиении 1-мерного массива данных M[k] без необходимости введения высокой избыточности. Новым является то, что в предлагаемом способе ошибки с кратностью больше «1» подлежат обнаружению и локализации, в том числе, посредством используемого кода, корректирующего ошибки.
в) Причинно-следственная связь между признаками и техническим результатом Благодаря новой совокупности существенных признаков в способе реализованы возможности:
- контроля и восстановления целостности 1-мерных массивов данных с возможностью обнаружения, локализации и восстановления целостности х блоков данных с признаками ее нарушения;
- построения крипто-кодовой конструкции, правила построения которой определяются и могут быть описаны посредством ϕ-функции, обеспечивающей обнаружение, локализацию и восстановление целостности блоков данных с признаками ее нарушения в количестве, определяемом еще при разбиении 1-мерного массива данных M[k] без необходимости введения высокой избыточности.
- обнаружения и локализации ошибки с кратностью больше «1» посредством используемого кода, корректирующего ошибки.
Доказательства соответствия заявленного изобретения условиям патентоспособности «новизна» и «изобретательский уровень»
Проведенный анализ уровня техники позволил установить, что аналоги, характеризующиеся совокупностью признаков, тождественных всем признакам заявленного технического решения, отсутствуют, что указывает на соответствие заявленного способа условию патентоспособности «новизна».
Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность отличительных существенных признаков, обуславливающих тот же технический результат, который достигнут в заявленном способе. Следовательно, заявленное изобретение соответствует условию патентоспособности «изобретательский уровень».
Краткое описание чертежей
Заявленный способ поясняется чертежами, на которых показано:
фиг. 1 - общая схема, поясняющая способ многоуровневого контроля и обеспечения целостности данных;
фиг. 2 - схема 1-мерного пространства данных;
фиг. 3 - схема, иллюстрирующая порядок расположения информационных и контрольных символов в кодовом слове (n, k)-кода;
фиг. 4 - схема, иллюстрирующая порядок построения кодового слова (n, k)-кода;
фиг. 5 - схема, иллюстрирующая порядок расположения вычисленных хэш-кодов в 1-мерном пространстве;
фиг. 6 - схема, иллюстрирующая порядок хэширования элементов кодового слова (n, k)-кода;
фиг. 7 - схема, иллюстрирующая выполнение операций кодирования и хэширования в 1-мерном пространстве;
фиг. 8 - схема, иллюстрирующая выполнение 1-мерных криптографических и кодовых преобразований над элементами отдельных структурированных массивов данных, представленных в 1-мерном пространстве данных;
фиг. 9 - схема, иллюстрирующая разработанный способ контроля и восстановления целостности одномерных массивов данных на основе комплексирования криптографических методов и методов помехоустойчивого кодирования.
Осуществление изобретения
к
Расположение блоков данных М (к=0, 1, …, k-1), подлежащих защите, в 1-мерном пространстве данных может быть охарактеризовано с помощью одной оси координат (фиг. 2).
При этом для обеспечения возможности применения криптографических и кодовых преобразований при контроле и восстановлении целостности структурированных массивов данных интерпретация содержащихся в них блоков данных будет различной.
Блоки данных произвольного структурированного массива данных будут интерпретироваться как целые неотрицательные числа, представленные, к примеру, в двоичной системе счисления:
g
τ
где μ ∈ {0, 1}; g=0, 1, …, τ-1; или как элементы расширенного поля GF(2):
g
где  - фиктивная переменная; μ ∈ {0, 1}; g=0, 1, …, τ-1, для обеспечения возможности выполнения с ними преобразований, идентичных преобразованиям, используемым при построении кодов, корректирующих ошибки. К примеру, при выполнении операции расширения для построения кодов системы остаточных классов: модулярных кодов, модулярных полиномиальных кодов.
Интерпретация блоков данных как векторов:
g
где μ ∈ {0, 1}; g=1, 2, …, τ, позволяет обеспечить возможность выполнения с ними преобразований, идентичных преобразованиям, используемым в различных криптоалгоритмах, к примеру, при примененении функции хэширования.
Поэтому в зависимости от вида выполняемых для контроля и восстановления целостности структурированных массивов данных преобразований используются различные формы представления содержащихся в них блоков данных.
Для обеспечения возможности восстановления целостности структурированного массива данных М[k], представленного в 1-мерном пространстве данных:
к
где k - размерность массива данных, содержащиеся в нем блоки данных М представляются по правилам построения кодового слова.
к
При этом блоки данных М (элементы структурированного массива данных M[k]) будут интерпретироваться как целые неотрицательные числа и считаться к информационными символами (блоками данных):
для которых в количестве, достаточном для обеспечения возможности восстановления целостности структурированного массива данных, вычисляются r дополнительных контрольных символов (блоков данных):
к
ρ
Полученная совокупность информационных (блоки данных М) и дополнительных контрольных (блоки данных М, где ρ=k, k+1, …, k+r-1) символов:
будет считаться кодовым словом (n, k) - кода (фиг. 3).
ρ
Вычисление дополнительных контрольных символов (блоков данных М) выполняется по правилам построения кодов, корректирующих ошибки, с учетом требуемых для обеспечения возможности восстановления целостности структурированного массива данных корректирующих способностей (фиг. 4).
min
Правила построения (n, k)-кодов с описанием их параметров, в частности, минимального кодового расстояния d, представлены во множестве известных работ (Морелос-Сарагоса, Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение [Текст] / Р. Морелос-Сарагоса; перевод с англ. В.Б.Афанасьев. - М.: Техносфера, 2006. - 320 с.; Хемминг, Р.В. Теория кодирования и теория информации [Текст] / Р.В. Хемминг; перевод с англ. - М.: «Радио и связь», 1983. - 176 с.).
После выполнения кодовых преобразований массив (1) примет вид:
р
к
где элементы М (ρ=k, …, n-1) подмассива М[r] получены в результате кодовых преобразований над элементами М (к=0, 1, …, k-1) подмассива M[k].
Для обеспечения возможности контроля целостности полученного при построении кодового слова (n, k)-кода массива (2) его элементы:
i
j
будут интерпретироваться как двоичные векторы M (i=0, 1, …, n-1), от которых посредством применения криптографической хэш-функции h вычисляются хэш-коды H (j=0, 1, …, η-1).
i
Выбор совокупности блоков данных M для хэширования будет определяться на основе математического аппарата теории систем векторов и линейных векторных пространств.
0
1
n-1
Для этого вектор блоков данных M, M, …, M рассматривается как система линейно независимых векторов:
только при ненулевом наборе коэффициентов:
q
где x ∈ {0, 1}; q=0, 1, …, n-1.
Данная система образует базис:
Вектор блоков данных с хэш-кодами  в свою очередь, также можно рассматривать как систему линейно независимых векторов, образующих базис:
Схема хэширования совокупности блоков данных  представляется в виде двоичной матрицы, составленной из коэффициентов базиса:
где η<п.
При этом строки матрицы обладают свойствами:
- являются различными и линейно-независимыми векторами;
min
- расстояние между векторами (по Хэммингу) d≥2;
min
- каждый вектор имеет вес (в смысле Хэмминга) ω≥d;
- нулевой вектор не входит в матрицу.
Аналогичными свойствами обладает порождающая матрица в теории линейных кодов, что обеспечивает возможность использования правил построения линейных кодов для хэширования данных.
j
При хэшировании данных получим вектор блоков данных с вычисленными хэш-кодами H (j=n, …, w-1):
где символ «→», означающий отображение, в данном случае используется как специальная многомерная некоммутативная операция хэширования.
На фигуре 5 представлен порядок расположения вычисленных хэш-кодов по отношению к информационным и дополнительным контрольным символам кодового слова (n, k)-кода в 1-мерном пространстве.
Порядок получения вектора блоков данных с вычисленными хэш-кодами поясняется следующим выражением:
i
n-1,w-n-1
i
i
i
i
i
где символ  означает специальную многомерную некоммутативную операцию хэширования блоков данных, представленных двоичными векторами M, отмеченных единичным символом a=1 (если a=∅, то aM=∅, где «∅» - пустое множество); M - информационный вектор (массив );  a ∈ {0,1}.
i
Порядок хэширования элементов кодового слова (n, k)-кода, интерпретируемых как двоичные векторы M (i=0, 1, …, n-1), представлен на фигуре 6.
Операции, выполняемые при хэшировании данных, определены государственным стандартом (ГОСТ 34.11-2012. Информационная технология. Криптографическая защита информации. Функция хэширования. - М.: Стандартинформ, 2012. - 34 с.).
После выполнения криптографических преобразований над элементами массива (2) получим крипто-кодовую конструкцию, представленную массивом:
правила построения которой определяются и могут быть описаны посредством ϕ-функции следующего вида:
где символ «1D» обозначает, что 1-мерные криптографические (хэш-функция h) и кодовые (функция кодирования f) преобразования выполняются над элементами структурированного массива данных M[k], представленного в 1-мерном пространстве данных; к=0, 1, …, k-1; ρ=k, …, n-1; j=n, …, w-1.
l
При контроле целостности данных для обнаружения ошибки в теории линейных кодов требуется вычислить синдром ошибки S - матрица-строка  элементами s ∈ {0,1}, по одному для каждого проверочного символа (блока данных).
Нарушение целостности (возникновение ошибки) рассматриваемых блоков данных с вычисленными хэш-кодами  будет характеризоваться несоответствием сравниваемых двоичных векторов при проверке синдрома.
j
Для этого сравниваются значения вычисленных при запросе на использование данных хэш-кодов  со значениями ранее вычисленных эталонных хэш-кодов H. По результатам сравнения делается вывод:
- об отсутствии признаков нарушения целостности блоков данных, при
- о нарушении целостности блоков данных, при
После обнаружения и локализации блока данных (совокупности блоков данных) с признаками нарушения целостности выполняется восстановление целостности структурированных массивов данных посредством применения математического аппарата используемых кодов, корректирующих ошибки.
В полученной крипто-кодовой конструкции, описываемой посредством ϕ-функции (3), для контроля и восстановления целостности структурированного массива данных, представленного в 1-мерном пространстве данных, выполняются 1-мерные криптографические и кодовые преобразования (фиг. 7), то есть в пространстве с мерностью, соответствующей мерности пространства данных.
При этом используемому при кодировании коду, корректирующему ошибки, для восстановления целостности уже обнаруженных и локализованных за счет использования функции хэширования блоков данных с признаками нарушения целостности достаточно обладать исправляющей способностью, равной его обнаруживающей.
j
Для обеспечения криптографической достоверности при контроле и восстановлении целостности структурированных массивов данных вычисляемые эталонные хэш-коды H должны храниться в надежной среде.
В случае построения крипто-кодовой конструкции по правилам, определяемым посредством ϕ-функции следующего вида:
к
где изначально от элементов структурированного массива данных М[k] вычисляются хэш-коды, а затем дополнительные контрольные символы, то требуется обеспечить среду хранения, исключающую деструктивные воздействия, еще и для них, так как хэш-функция будет применяться только к блокам данных М.
к
Совокупность блоков данных М и вычисленных от них хэш-кодов будет интерпретироваться как целые неотрицательные числа и считаться информационными символами, для которых в количестве, достаточном для обеспечения возможности восстановления целостности структурированного массива данных М[k] будут вычисляться дополнительные контрольные символы по правилам построения кодов, корректирующих ошибки.
Ошибки с кратностью больше «1» подлежат обнаружению и локализации посредством используемого кода, корректирующего ошибки. При этом в таких крипто-кодовых конструкциях для подтверждения с криптографической достоверностью целостности исходного структурированного массива данных после выполнения процедуры восстановления требуется введение дополнительных механизмов контроля.
Для обеспечения возможности обнаружения и локализации х блоков данных с признаками нарушения целостности (х-кратной ошибки) посредством применения хэш-функции требуется разбиение рассматриваемого 1-мерного структурированного массива данных М[k] на отдельные 1-мерные структурированные массивы данных с мéньшей размерностью.
Так при таком разбиении рассматриваемого 1-мерного структурированного массива данных M[k] и получении совокупности отдельных 1-мерных структурированных массивов данных:
где  с элементами:
контроль и восстановление их целостности будет выполняться посредством применения 1-мерных криптографических и кодовых преобразований (фиг. 8), осуществляемых по аналогичным правилам, как и для отдельного структурированного массива данных, представленного в 1-мерном пространстве данных.
Такой контроль их целостности будет характеризоваться возможностью обнаружения и локализации x блоков данных с признаками нарушения целостности (x-кратной ошибки).
Схема, иллюстрирующая разработанный способ контроля и восстановления целостности одномерных массивов данных на основе комплексирования криптографических методов и методов помехоустойчивого кодирования, представлена на фигуре 9.