СПОСОБ ОБЕСПЕЧЕНИЯ ЦЕЛОСТНОСТИ ДАННЫХ
METHOD OF ENSURING THE INTEGRITY OF DATA

Область техники, к которой относится изобретение
Предлагаемое изобретение относится к информационным технологиям и может быть использовано для обеспечения целостности данных в информационных системах посредством контроля, а также восстановления целостности данных при их возможном изменении в условиях преднамеренных воздействий злоумышленника.
Уровень техники
а) Описание аналогов
Известны способы обеспечения целостности данных за счет применения различных видов резервирования (с использованием программно-аппаратной или программной реализации технологии 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) [Текст] / Г. Уоррен, мл. - М.: «Вильямc», 2007. - 512 с.; Морелос-Сарагоса, Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение [Текст] / Р. Морелос-Сарагоса; перевод с англ. В.Б. Афанасьев. - М.: Техносфера, 2006. - 320 с.; Хемминг, Р.В. Теория кодирования и теория информации [Текст] / Р.В. Хемминг; перевод с англ. - М.: «Радио и связь», 1983. - 176 с.).
Недостатками данных способов являются:
- высокая избыточность;
- большое количество криптографических преобразований.
Известны способы обеспечения целостности данных за счет применения криптографических методов: ключевое и бесключевое хеширование, средства электронной подписи (Заявка на патент РФ №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 С. 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 с.; To же [Электронный ресурс]. - Режим доступа: eprint.iacr.org/2006/043.pdf (2006)), для которых типичны две обобщенные схемы получения хэш-кодов: для каждой записи в блоке данных (фиг. 1) и для целого блока данных (фиг. 2).
Недостатками данных способов являются:
для схемы (фиг. 1):
- высокая избыточность при контроле целостности последовательностей записей небольшой размерности;
для схемы (фиг. 2):
- отсутствие возможности локализации искаженных записей в каждом блоке данных.
б) Описание ближайшего аналога (прототипа)
Наиболее близким по технической сущности к заявленному изобретению (прототипом) является способ обеспечения необходимого уровня защищенности (целостности) данных на основе множества хэш-кодов (фиг. 3), полученных с помощью стандартной процедуры реализации хэш-функции от совокупности данных (записей) в порядке, определенном специальной процедурой выбора записи, основанной на математическом аппарате линейной алгебры (линейных систем хэш-кодов (ЛСХК)) (Финько, О.А. Обеспечение целостности данных в автоматизированных системах на основе линейных систем хэш-кодов / О.А. Финько, С.В. Савин // Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета. - 2015. - №114. - С. 796-811), где контроль целостности данных (обнаружение ошибки) по аналогии с линейными кодами осуществляется за счет вычисления синдрома, при проверке которого можно сделать вывод о наличии или отсутствии ошибки.
Недостатком известного способа является отсутствие возможности исправления возникающей в записях ошибки (восстановления данных при их изменении) в условиях преднамеренных воздействий злоумышленника.
Раскрытие изобретения
а) Технический результат, на достижение которого направлено изобретение
Целью настоящего изобретения является разработка способа обеспечения целостности данных посредством контроля, а также восстановления целостности данных при их возможном изменении в условиях преднамеренных воздействий злоумышленника.
б) Совокупность существенных признаков
1
2
n
1
2
n
n+1
k
Поставленная цель достигается тем, что в известном способе обеспечения целостности данных, заключающемся в том, что обнаружение и локализация возникающей ошибки в записях m, m, …, m блока данных М обеспечиваются посредством системы хэш-кодов за счет вычисления сигнатур хэш-функции, в представленном же способе система хэш-кодов, строящаяся по правилам, аналогичным правилам построения модулярных кодов, обеспечивает для записей m, m, …, m, которые являются информационной группой n записей, предназначенной для однозначного восстановления целостности блока данных М, вычисление контрольной группы k-n записей m, …, m, дополнительно вводимой для коррекции ошибки, возникающей в условиях преднамеренных воздействий злоумышленника, в случае возникновения которой восстановление целостности блока данных М без ущерба для однозначности его представления осуществляется посредством реконфигурации системы путем исключения одной или нескольких записей , где i=1, 2, …, k, с возникшей ошибкой, в свою очередь, обнаружение ошибки, а также проверка достоверности восстановления целостности данных производится посредством сравнения вычисленной сигнатуры S хэш-функции h(M) от проверяемого блока данных М с ранее вычисленной сигнатурой S* хэш-функции h(M*) от первоначального блока данных М*.
Сопоставительный анализ заявленного решения с прототипом показывает, что предлагаемый способ отличается от известного тем, что поставленная цель достигается за счет обнаружения ошибки путем сравнения вычисленной сигнатуры хэш-функции от проверяемого блока данных с ранее вычисленной сигнатурой хэш-функции от первоначального блока данных, для которого по правилам, аналогичным правилам построения модулярных кодов, строится система хэш-кодов, позволяющая обеспечить исправление возникающей ошибки в условиях преднамеренных воздействий злоумышленника, а также проверить достоверность восстановления целостности данных за счет повторного сравнения сигнатур хэш-функции от проверяемого и первоначального блоков данных.
Определение 1. Системой хэш-кодов называется множество хэш-кодов, полученных с помощью стандартной процедуры реализации хэш-функции от блока данных в порядке, соответствующем получению наименьших неотрицательных вычетов числа по основаниям системы в модулярной арифметике (МА).
1
2
n
n+1
k
min
k
Целостность блока данных М, подлежащего защите, будет обеспечиваться за счет обнаружения возникающей ошибки, а также проверки достоверности восстановления целостности данных путем сравнения вычисленной сигнатуры хэш-функции от проверяемого блока данных с ранее вычисленной сигнатурой хэш-функции от первоначального блока данных, что позволяет в момент времени t в условиях преднамеренных воздействий злоумышленника восстановить целостность первоначального блока данных М*. Исправление возникающей ошибки будет осуществляться по известным правилам, применяемым при использовании кодов в МА (Акушский, И.Я. Машинная арифметика в остаточных классах [Текст] / И.Я. Акушский, Д.И. Юдицкий. - М.: Советское радио, 1968. - 440 с.). Новым является то, что в предлагаемом способе получение совокупностей записей m, m, …, m, m, …, m интерпретируется как построение модулярного кода, что позволяет восстановить целостность блока данных М с возможностью исправления возникающей ошибки на любой стадии его обработки (при условии, что минимальное кодовое расстояние d и кратность t гарантированно исправляемой ошибки удовлетворяют неравенству:). Новым является то, что восстановить целостность блока данных М возможно путем исключения из процесса восстановления любых r записей без ущерба для однозначности представления первоначального блока данных М* (где r=k-n - количество дополнительных записей), вследствие чего система записей блока данных будет интерпретироваться как несистематический или неразделимый код. Новым является то, что сигнатура S хэш-функции h(M) вычисляется от проверяемого блока данных М, что в отличие от способа-прототипа позволяет обеспечить контроль целостности данных посредством обнаружения ошибки, а также проверить достоверность восстановления целостности данных путем сравнения значения вычисленной сигнатуры хэш-функции с ранее вычисленной сигнатурой хэш-функции от первоначального блока данных.
В несистематических кодах каждая разрядная цифра несет часть информации о числе, включая и избыточные символы. В несистематическом коде любые из r разрядных цифр можно считать избыточными символами.
в) Причинно-следственная связь между признаками и техническим результатом
Благодаря новой совокупности существенных признаков в способе реализована возможность:
- обнаружения возникающей ошибки в условиях преднамеренных воздействий злоумышленника;
- локализации и исправления обнаруженной ошибки;
- восстановления целостности первоначального блока данных посредством осуществления реконфигурации системы путем исключения записи с возникшей ошибкой;
- проверки достоверности восстановления целостности данных.
Доказательства соответствия заявленного изобретения условиям патентоспособности «новизна» и «изобретательский уровень»
Проведенный анализ уровня техники позволил установить, что аналоги, характеризующиеся совокупностью признаков, тождественных всем признакам заявленного технического решения, отсутствуют, что указывает на соответствие заявленного способа условию патентоспособности «новизна».
Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность отличительных существенных признаков, обуславливающих тот же технический результат, который достигнут в заявленном способе. Следовательно, заявленное изобретение соответствует условию патентоспособности «изобретательский уровень».
Краткое описание чертежей
Заявленный способ поясняется чертежами, на которых показано:
фиг. 1 - схема формирования хэш-кода для каждой записи в блоке данных;
фиг. 2 - схема формирования хэш-кода для блока данных;
фиг. 3 - общая схема формирования ЛСХК;
фиг. 4 - схема, поясняющая процедуру формирования системы модулярных хэш-кодов с возможностью обнаружения изменений в блоке данных;
фиг. 5 - схема, поясняющая процедуру восстановления целостности блока данных при обнаружении его изменения в отдельной записи.
Осуществление изобретения
Возможность реализации заявленного способа объясняется следующим. Обнаружение возникающей ошибки в условиях преднамеренных воздействий злоумышленника производится посредством сравнения вычисленной сигнатуры S хэш-функции h(M), где М - проверяемый блок данных, с ранее вычисленной сигнатурой S* хэш-функции h(M*), где М* - первоначальный блок данных (фиг. 4).
1
2
n
n+1
k
В случае обнаружения ошибки (нарушения целостности блока данных М) производится ее локализация и исправление (восстановление целостности первоначального блока данных М*) (фиг. 5) на основе математического аппарата МА, в соответствии с которым блок данных М будет интерпретироваться как целое неотрицательное число А, однозначно представленное набором остатков по основаниям МА р, р, …, p<p<…<p:
1
2
n
n+1,
k
MA
A=(α, α, …, α, α …, α),
n
1
2
n
j
pj
р
1
2
n
n+1
k
где P=pp…p>A; α=|A|; |⋅| - наименьший неотрицательный вычет числа «⋅» по модулю р; p, p, …, p<p<…<p - попарно простые; j=1, 2, …, n, n+1, …, k (Акушский, И.Я. Машинная арифметика в остаточных классах [Текст] / И.Я. Акушский, Д.И. Юдицкий. - М.: Советское радио, 1968. - 440 с.; Торгашев, В.А. Система остаточных классов и надежность ЦВМ [Текст] / В.А. Торгашев. М.: Советское радио, 1973. 120 с.).
j
j
1
2
n
1
2
n
n+1
k
n+1
k
k
n
n+1
k
k
n
n
1
2
n
1
2
n
n
k
n+1
k
k
n
Полученные остатки α будут интерпретироваться как записи m блока данных М, то есть остатки МА α, α, …, α будут интерпретироваться как записи m, m, …, m и считаться информационной группой n записей, а α, …, α - интерпретироваться как контрольная группа k-n записей m, …, m. Сама МА является в этом случае расширенной, где P=Pp…p, и охватывает полное множество состояний, представляемых всеми к вычетами. Эта область будет являться полным диапазоном МА [0, P) и состоять из рабочего диапазона [0, P), где P=pp…p, определяемого неизбыточными основаниями МА (записями m, m, …, m), и диапазона [P, P), определяемого избыточными основаниями МА (записями m, …, m) и представляющего недопустимую область. Это означает, что операции над числом А выполняются в диапазоне [0, P). Поэтому правильность исправления обнаруженной ошибки будет подтверждаться результатом операции МА, входящим в пределы P.
Математический аппарат модулярных кодов основывается на фундаментальных положениях Китайской теоремы об остатках, поэтому исправление возникающей ошибки будет осуществляться на основании следующих теорем:
1
2
n
n+1
i
n+1
1
2
i
n
n+1
i
i
Теорема 1. Пусть основания p, p, …, p, p МА удовлетворяют условию p<p (i=1, 2, …, n) и пусть А=(α, α, …, α, …, α, α) - правильное число. Тогда величина числа А не изменится, если представлять его в системе оснований, из которой изъято основание p (то есть если в представлении А зачеркнуть цифру α).
1
2
i-1
i+1
n+1
Доказательство. Неравенство  тождественно следующему неравенству А<pp, …, pp, p, и, следовательно, число А может быть единственным образом представлено своими остатками по этим основаниям.
i
Определение 2. Число , полученное из А зачеркиванием цифры , называется проекцией числа А по основанию p.
1
2
n
n+1
1
2
n
n+1
Определение 3. Система оснований p, p, …, p, p, удовлетворяющая условию p<p<…<p<p, называется упорядоченной системой оснований.
1
2
i
n
n+1
Теорема 2. Если в упорядоченной системе оснований задано правильное число A=(α, α, …, α, …, α, α), то проекции этого числа по всем основаниям совпадают, то есть .
Доказательство. Для правильного числа при условии теоремы имеют место неравенства  и в соответствии с предыдущей теоремой величину А сохранит его проекция по каждому основанию (Акушский, И.Я. Машинная арифметика в остаточных классах [Текст] / И.Я. Акушский, Д.И. Юдицкий. - М.: Советское радио, 1968. - 440 с.).
Таким образом, после локализации записи  с возникшей ошибкой операция реконфигурации выполняется вычислением А* из системы
по «правильным» основаниям МА:
i,j
i,j
где  - ошибочный остаток; B - ортогональные базисы; i, j=1, …, n, …, k; i≠j;  μ подбирается так, чтобы имело место следующее сравнение:
Составляется таблица 1, содержащая значения ортогональных базисов и модулей системы при условии возникновения однократной ошибки по каждому основанию МА.
Пример
1
2
3
4
4
1
2
3
4
5
6
6
4
5
6
Выберем систему оснований p=2, р=3, р=5, р=7, для которой рабочий диапазон равен Р=pppp=2⋅3⋅5⋅7=210. Введем контрольные основания р=11, p=13, тогда полный диапазон определяется как Р=Ppp=210⋅11⋅13=30030.
Вычислим ортогональные базисы системы:
Дано число . Вместо него при обработке данных получили  Для локализации ошибки вычисляем величину числа :
Полученное число является неправильным , что свидетельствует об ошибке при обработке данных.
Вычислим проекции числа  по каждому из оснований.
1
По основанию р=2:
2
3
4
5
6
для оснований МА р=3, р=5, р=7, р=11, р=13 вычислим ортогональные базисы Тогда
2
По основанию р=3:
1
3
4
5
6
для оснований МА р=2, р=5, р=7, р=11, р=13 вычислим ортогональные базисы Тогда
3
По основанию р=5:
1
2
4
5
6
для оснований МА р=2, р=3, р=7, р=11, р=13 вычислим ортогональные базисы  Тогда
4
По основанию р=7:
1
2
3
5
6
для оснований МА р=2, р=3, р=5, р=11, р=13 вычислим ортогональные базисы  Тогда
5
По основанию р=11:
1
2
3
4
6
для оснований МА p=2, р=3, р=5, р=7, р=13 вычислим ортогональные базисы  Тогда
6
По основанию р=13:
1
2
3
4
5
для оснований МА: p=2, р=3, р=5, р=7, р=11 вычислим ортогональные базисы  Тогда
5
Итак, все проекции числа , кроме , неправильные. Следовательно, ошибочна цифра  по основанию р=11.
После локализации ошибки производим реконфигурацию системы за счет исключения записи  с возникшей ошибкой, что позволит восстановить целостность первоначального блока данных.
В соответствии с (1) вычислим А*, используя таблицу 1. Получим
Восстановление целостности первоначального блока данных М* обеспечивается посредством осуществления реконфигурации системы путем исключения записи  с возникшей ошибкой. Проверка достоверности восстановления целостности данных обеспечивается сравнением повторно вычисленной сигнатуры S хэш-функции h(M), где М - проверяемый блок данных, с ранее вычисленной сигнатурой S* хэш-функции h(M*) от первоначального блока данных М*.