CRC-алгоритмы обнаружения ошибок

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

Контрольные суммы применяются в случаях, когда требуется уверенность в неизмененности передаваемых данных. Они активно используются при передаче данных по сети, при хранении данных на различных носителях и т.д.

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

Здесь мы немного расскажем об одном из наиболее часто используемых способов создания контрольных сумм – CRC. Данный класс алгоритмов достаточно хорошо выявляет ошибки в поток входных данных. Однако, алгоритм не лишен недостатков. Так, например, существуют алгоритмы, позволяющие добавлять к данным дополнительные байты таким образом, чтобы значение CRC не изменялось бы. Это ограничивает, например, возможности использования данных алгоритмов при подсчете контрольных сумм выполняемых файлов (действительно, из сказанного следует, что злоумышленник может изменить содержимое выполняемого файла, а затем, добавив в него необходимые байты, подогнать значение контрольной суммы к исходной).

Алгоритмы CRC основаны на понятии полиномиальная арифметика. В ней коэффициенты в позиционном представлении числа a={a₀,a₁,…,a_N} рассматриваются, как коэффициенты многочлена P_a= a₀ +a₁ x +… +a_N x^N. Арифметические действия, при этом, переопределяются как действия над многочленами (более подробно – см. прилагающуюся статью). Нам интересен случай, когда рассматривается двоичное представление числа, а сами коэффициента многочлена рассматриваются как элементы кольца вычетов по модулю 2. Для данного модуля кольцо является еще и полем, т.е. в нем корректно определены операции сложения, вычитания, умножения и деления.

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

1+1=0

1-1=0

101+011=110

Деление целых чисел в этих терминах производится как обычно – столбиком. Далее под делением мы будем иметь в виду деление именно в указанном смысле. Отметим, что операция сложения и вычитания здесь не отличаются.

Исходные данные представляются как одно большое двоичное число X. Вычисление контрольных сумм сводится к вычислению остатка от деления числа X на некоторое заранее заданное число m. Приведем примеры стандартных значений m для различных алгоритмов (в скобках номера единичных битов):

16 бит: (16,12,5,0) [стандарт X25] (16,15,2,0) ["CRC-16"] 32 бит: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) [Ethernet]

Отметим, что для получения n -битного остатка от деления требуется n+1 -битный делитель.

Деление столбиком сводится к следующему. Заводится переменная x длиной n+1 бит, которую мы будем называть аккумулятором. В нее записываются первые n+1 бит данных. Далее циклически выполняется следующий шаг

Если старший бит x равен 1, то x=x^m. Далее x сдвигается влево на 1 бит и в младший бит записывается следующий бит данных.

В конце в переменной x будет лежать остаток от деления на m.

При использовании n+1 -битного делителя m, реальные данные дополняются с конца n нулями, от полученных данных считается остаток от деления на m. Полученное значение записывается на место n последних нулей данных. Последнее эквивалентно вычитанию (=сложению) из данных m, поэтому остаток от деления полученного большого числа на m станет равным 0. Именно это свойство и можно использовать при проверке сохранности данных.

Обычно, алгоритм немного модифицируется. Проблема заключается в том, что остаток от деления не зависит от добавления некоторого количества нулей в начало данных. Для избежания этой проблемы в начало данных можно записывать некоторые стандартные биты. Данную операцию можно осуществить иначе – в аккумулятор, можно изначально не просто помещать первые n+1 бит данных, а выполнять еще x=x^x₀, где x₀ – некоторое начальное значение. Используется, также, конечное значение x₁, для которого выполняется аналогичная операция с конечным результатом.

Стандартный алгоритм CRC16 не использует начальные и конечные значения. Модификация CRC16/CITT использует стартовое значение FFFFh. Алгоритм CRC32 использует FFFFFFFFh в качестве начального и конечного значений.

Лекция 14

Поиск строк

Пусть имеется последовательность символов S={ s_i } из алфавита S : s_i Î S, i=1,…,N и последовательность W={ w_i } из алфавита S : w_i Î S, i=1,…,M, M£N.

Ставится задача поиска всех таких целых 0£k£N-M, что для всех i=1,…,M: s_k+i=w_i.

Стандартной интерпретацией данной задачи является задача поиска заданного слова в строке или задача поиска слова в файле.

У данной задачи существует прямое решение, при котором происходит последовательная проверка совпадения подстроки W со всеми подряд идущими подстроками строки S длины M. Легко увидеть, что данный алгоритм требует времени порядка Q(MN) (реализация данного алгоритма приведена в следующем параграфе). На самом деле задачу можно решить существенно быстрее, о чем и пойдет речь далее.

---

Дата добавления: 2015-10-30