Циклический избыточный код (англ. Cyclic redundancy code, CRC) - алгоритм вычисления контрольной суммы, предназначенный для проверки целостности передаваемых данных. Алгоритм CRC обнаруживает все одиночные ошибки, двойные ошибки и ошибки в нечетном числе битов.
Понятие циклические коды достаточно широкое, тем не менее на практике его обычно используют для обозначения только одной разновидности, использующей циклический контроль (проверку) избыточности.
Алгоритм CRC базируется на свойствах деления с остатком двоичных многочленов, то есть многочленов над конечным полем GF(2). Значение CRC является по сути остатком от деления многочлена, соответствующего входным данным, на некий фиксированный порождающий многочлен.
Каждой конечной последовательности битов взаимооднозначно сопоставляется двоичный многочлен , последовательность коэффициентов которого представляет собой исходную последовательность. Например, последовательность битов 1011010 соответствует многочлену:
Количество различных многочленов степени меньшей N равно 2N, что совпадает с числом всех двоичных последовательностей длины N.
Значение CRC с порождающим многочленом G(x) степени N определяется как битовая последовательность длины N, представляющая многочлен R(x), получившийся в остатке при делении многочлена P(x), представляющего входной поток бит, на многочлен G(x):
где:
- многочлен, представляющий значение CRC;
- многочлен, коэффициенты которого представляют входные данные;
- порождающий многочлен;
- степень порождающего многочлена.
Умножение осуществляется приписыванием нулевых битов к входной последовательности, что улучшает качество хэширования для коротких входных последовательностей.
При делении с остатком степень многочлена-остатка строго меньше степени многочлена-делителя, то есть при делении на многочлен G(x) степени N можно получить 2N различных остатков от деления. При «правильном» выборе порождающего многочлена G(x), остатки от деления на него будут обладать нужными свойствами хеширования - хорошей перемешиваемостью и быстрым алгоритмом вычисления. Высокая скорость вычисления обеспечивается тем фактом, что степень порождающего многочлена обычно пропорциональна длине байта или машинного слова (например 8, 16, 32 или 64).
Операция деления на примитивный полином также эквивалентна следующей схеме: пусть выбран примитивный полином, задающий цикл де Брейна 0010111001011100… и блок данных 0111110, построена таблица, верхняя строка заполнена блоком данных, а нижние строки - смещения на 0,1,2 бит цикла де Брейна:
Тогда контрольная сумма будет равна операции XOR тех столбцов, над которыми в верхней строке расположена 1. В этом случае, 010 xor 101 xor 011 xor 111 xor 110 = 101 (CRC).
В то время, как циклические избыточные коды являются частью стандартов, сами они не стандартизированы в плане адаптации одного алгоритма для конкретной степени полинома. Например, существуют три описания полинома для CRC-12, десять противоречивых определений CRC-16 и четыре - CRC-32.
Существует много полиномов, которые используются в различных протоколах, причём в конкретных реализациях вычисление CRC может включать пре- и пост-инверсию, а также обратный порядок обработки битов. В проприетарных реализациях CRC для усложнения анализа кода иногда применяется запутанное вычисление начальных значений, однако криптостойкости алгоритму это не добавляет. В предлагаемой реализации используется полином CRC-64-ECMA-182 (0xC96C5795D7870F42).
