Математическое обоснование разработки линейной системы хэш-кодов для обеспечения целостности данных в АС

Введем параметры:

• 1) объемго фрагмента данных: ;
• 2) коэффициент избыточности:

.

где — общее количество фрагментов данных, — объем данных, занимаемый одной сигнатурой хэш-функции, — общее количество сигнатур хэш-функций;

• 3) уровень защищенностиго фрагмента данных: ;
• 4) средний уровень защищенности данных: .

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

Введем допущения:

• 1), если записи меньше записи ;
• 2) для контроля целостности любых данных всегда используется однотипная хэш-функция;
• 3) объемы данных, заключенных в одной записи (рис. 1) и в произвольном блоке данных (рис. 2) равны, следовательно, и уровни защищенности одной записи данных и блока данных _ одинаковы.

Таким образом, при данных допущениях и различных сочетаниях способов получения хэш-кодов (рис. 1, 2) уровень защищенности и коэффициент избыточности не меняется:, (рис. 3).

Рис. 3 — Обобщенная схема применения хэш-функций

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

Для решения данной задачи предлагается использовать математический аппарат теории систем векторов и линейных векторных пространств.

Множество двоичных векторов можно рассматривать как систему линейно независимых векторов, т.к.:

.

только при нулевом наборе коэффициентов:, где .

Данная система образует базис:

.

Тогда множество записей и хэш-кодов: — также можно рассматривать как систему линейно независимых векторов, где базисом для них будет:

.

Множество всех возможных схем хеширования записей можно представить в виде двоичной матрицы, составленной из коэффициентов базиса:

.

где каждая строка соответствует схеме хеширования и .

Строки матрицы обладают свойствами:

являются различными и линейно-независимыми векторами;

расстояние между векторами (по Хэммингу) ;

каждый вектор имеет вес (в смысле Хэмминга) ;

нулевой вектор не входит в матрицу.

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

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

Такие системы хэш-кодов в рамках настоящей работы будем назвать линейными (ЛСХК).