Расчет контрольной суммы crc16

• Как просто посчитать контрольную сумму CRC (CRC32 — CRC16 — CRC8)
• Как запустить 16-ти разрядную программу
• Как проверить загрузочный сектор

Для начала давайте немного разберёмся в теории. Итак, что же такое CRC? Если кратко, это одна из разновидностей подсчёта контрольной суммы. Контрольная сумма — это метод проверки целостности принятой информации на стороне приёмника при передаче по каналам связи. Например, одна из простейших проверок — использование бита чётности. Это когда суммируются все биты передаваемого сообщения, и если сумма оказывается чётной, то в конец сообщения добавляется 0, если нечётной — то 1. При приёме также подсчитывается сумма битов сообщения, и сравнивается с принятым битом чётности. Если они отличаются, значит при передаче возникли ошибки, и передаваемая информация была искажена.

Но такой способ определения наличия ошибок — очень неинформативный и срабатывает не всегда, т.к. при искажении нескольких битов сообщения, чётность суммы может не измениться. Поэтому существует множество более "продвинутых" проверок, в том числе CRC.

По сути, CRC — это не сумма, а результат деления некого объёма информации (информационного сообщения) на константу, а точнее — остаток от деления сообщения на константу. Тем не менее, CRC исторически также называют "контрольная сумма". В значение CRC вносит вклад каждый бит сообщения. То есть, если хотя бы один бит исходного сообщения изменится при передаче, контрольная сумма тоже изменится, причём существенно. Это большой плюс такой проверки, так как он позволяет однозначно определить, исказилось исходное сообщение при передаче или нет.

Прежде чем приступать к вычислению CRC, понадобится ещё немного теории.
Что такое исходное сообщение должно быть понятно. Это непрерывная последовательность битов произвольной длины.

Что за константа, на которую мы должны делить исходное сообщение? Это некоторое число также любой длины, но обычно используются числа, кратные 1 байту — 8, 16 и 32 бита. Просто так легче считать, ведь компьютеры работают именно с байтами, а не с битами.

Константу-делитель обычно записывают в виде полинома (многочлена) вот таким образом: x^8 + x^2 + x^1 + x^0. Здесь степень числа "x" означает позицию бита-единицы в числе, начиная с нулевой, а старший разряд указывает на степень полинома и отбрасывается при интерпретации числа. То есть записанное ранее число — это не что иное как (1)00000111 в двоичной системе счисления, или 7 в десятичной. В скобках я указал подразумеваемый старший разряд числа.
Вот ещё пример: x^16 + x^15 + x^2 + x^0 = (1)1000000000000101" = 0x8005 = 32773.
Обычно используются некие стандартные многочлены для разных типов CRC.

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

В общем виде, деление числа на многочлен выполняется по такому алгоритму:
1) создаётся массив (регистр), заполненный нулями, равный по длине разрядности полинома;
2) исходное сообщение дополняется нулями в младших разрядах, в количестве, равном числу разрядов полинома;
3) в младший разряд регистра заносится один старший бит сообщения, а из старшего разряда регистра выдвигается один бит;
4) если выдвинутый бит равен "1", то производится инверсия битов (операция XOR, исключающее ИЛИ) в тех разрядах регистра, которые соответствуют единицам в полиноме;
5) если в сообщении ещё есть биты, переходим к шагу 3);
6) когда все биты сообщения поступили в регистр и были обработаны этим алгоритмом, в регистре остаётся остаток от деления, который и является контрольной суммой CRC.

Рисунок иллюстрирует деление исходной последовательности битов на число (1)00000111, или многочлен x^8 + x^2 + x^1 + x^0.

Осталась ещё пара дополнительных штрихов. Как вы могли заметить, сообщение можно разделить на любое число. Как его выбрать? Существует ряд стандартных полиномов, которые используются при вычислении CRC. Например, для CRC32 это может быть число 0x04C11DB7, а для CRC16 это может быть 0x8005.
Кроме того, в регистр в начале вычислений можно записать не нули, а какое-то другое число.

Также при расчётах непосредственно перед выдачей финальную контрольную сумму CRC могут делить на какое-то другое число.

И последнее. Байты сообщения при записи в регистр могут помещаться как старшим битом "вперёд", так и наоборот, младшим.

На основании всего вышеизложенного, давайте напишем функцию на языке Basic .NET, которая будет рассчитывать контрольную сумму CRC, принимая ряд параметров, которые я описал выше, и возвращая значение CRC в виде 32-разрядного беззнакового числа.

Public Shared Function GetCrc(ByVal bytes As Byte(), ByVal poly As UInteger, Optional ByVal w >
Dim w >
‘Дополняем сообщение width нулями (расчёт в байтах):
ReDim Preserve bytes(bytes.Length — 1 + widthInBytes)

‘Создаём очередь битов из сообщения:
Dim msgFifo As New Queue(Of Boolean)(bytes.Count * 8 — 1)
For Each b As Byte In bytes
Dim ba As New BitArray()
If reverseBytes Then
For i As Integer = 0 To 7
msgFifo.Enqueue(ba(i))
Next
Else
For i As Integer = 7 To 0 Step -1
msgFifo.Enqueue(ba(i))
Next
End If
Next

‘Создаём очередь из битов начального заполнения регистра:
Dim initBytes As Byte() = BitConverter.GetBytes(initReg)
Dim initBytesReversed As IEnumerable(Of Byte) = (From b As Byte In initBytes Take widthInBytes).Reverse
Dim initFifo As New Queue(Of Boolean)(width — 1)
For Each b As Byte In initBytesReversed
Dim ba As New BitArray()
If Not reverseBytes Then
For i As Integer = 0 To 7
initFifo.Enqueue(ba(i))
Next
Else
For i As Integer = 7 To 0 Step -1
initFifo.Enqueue(ba(i))
Next
End If
Next

‘Сдвиг и XOR:
Dim register As UInteger = 0 ‘заполняем width-разрядный регистр нулями.
Do While msgFifo.Count > 0

Dim poppedBit As Integer = CInt(register >> (width — 1)) And 1 ‘определить перед сдвигом регистра.

Dim shiftedBit As Byte = Convert.ToByte(msgFifo.Dequeue)
If initFifo.Count > 0 Then
Dim b As Byte = Convert.ToByte(initFifo.Dequeue)
shiftedBit = shiftedBit Xor b
End If

register = register > (32 — width)) ‘маскируем младшие разряды.

В интернете существует большое количество вариантов расчёта контрольной суммы CRC. Но что же собственно такое контрольная сумма и почему она рассчитывается именно так? Давайте разберёмся. А заодно напишем программу, которая будет рассчитывать CRC с заданными параметрами.

1 Теория, лежащая в основе расчёта CRC

Но такой способ определения наличия ошибок – очень неинформативный и срабатывает не всегда, т.к. при искажении нескольких битов сообщения, чётность суммы может не измениться. Поэтому существует множество более «продвинутых» проверок, в том числе CRC.

По сути, CRC – это не сумма, а результат деления некого объёма информации (информационного сообщения) на константу, а точнее – остаток от деления сообщения на константу. Тем не менее, CRC исторически также называют «контрольная сумма». В значение CRC вносит вклад каждый бит сообщения. То есть, если хотя бы один бит исходного сообщения изменится при передаче, контрольная сумма тоже изменится, причём существенно. Это большой плюс такой проверки, так как он позволяет однозначно определить, исказилось исходное сообщение при передаче или нет.

Что такое исходное сообщение – понятно. Это непрерывная последовательность битов произвольной длины.

Что за константа, на которую мы должны делить исходное сообщение? Это некоторое число также любой длины, но обычно используются числа, кратные 1 байту – 8, 16 или 32 бита. Просто так легче считать, ведь компьютеры работают именно с байтами, а не с битами.

Константу-делитель обычно записывают в виде полинома (многочлена) вот таким образом: x 8 + x 2 + x 1 + x 0 . Здесь степень числа "x" означает позицию бита-единицы в числе, начиная с нулевой, а старший разряд указывает на степень полинома и отбрасывается при интерпретации числа. То есть записанное ранее число – это не что иное как (1)00000111 в двоичной системе счисления, или 7 в десятичной. В скобках я указал подразумеваемый старший разряд числа, его не принято писать.

Вот ещё пример: x 16 + x 15 + x 2 + x 0 = (1)1000000000000101 = 0x8005 = 32773.

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

Алгоритм CRC	Образующий многочлен
CRC-16	0x8005
CRC-16-CCITT	0x1021
CRC-16-DNP	0x3D65
CRC-32-IEEE 802.3	0x04C11DB7
CRC-32C	0x1EDC6F41
CRC-32K	0x741B8CD7

В статье Википедии, посвящённой расчёту CRC, есть большая таблица образующих полиномов.

Так как же считать контрольную сумму? Существует базовый метод – деление сообщения на полином «в лоб» – и его модификации в целях уменьшения количества вычислений и, соответственно, ускорения расчёта CRC. Для начала мы рассмотрим именно базовый метод.

В общем виде деление числа на многочлен выполняется по такому алгоритму. Алгоритм вычисления контрольной суммы CRC:

1. Создаётся массив (регистр), заполненный нулями, равный по длине разрядности (степени) полинома.
2. Исходное сообщение дополняется нулями в младших разрядах, в количестве, равном числу разрядов полинома.
3. В младший разряд регистра заносится один старший бит сообщения, а из старшего разряда регистра выдвигается один бит.
4. Если выдвинутый бит равен "1", то производится инверсия битов (операция XOR, исключающее ИЛИ) в тех разрядах регистра, которые соответствуют единицам в полиноме.
5. Если в сообщении ещё есть биты, переходим к шагу 3).
6. Когда все биты сообщения поступили в регистр и были обработаны этим алгоритмом, в регистре остаётся остаток от деления, который и является контрольной суммой CRC.

Назовём этот метод расчёта CRC метод побитового сдвига или простой метод.

Рисунок иллюстрирует деление исходной последовательности битов на число (1)00000111, или многочлен x 8 + x 2 + x 1 + x 0 .

Схематичное представление вычисления CRC на примере деления на многочлен x 8 + x 2 + x 1 + x 0

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

Осталась ещё пара моментов, о которых стоит сказать. Как вы могли заметить, сообщение можно разделить на любое число. Как его выбрать? Существует ряд стандартных полиномов, которые используются при вычислении CRC. Например, для CRC32 это может быть число 0x04C11DB7, а для CRC16 это может быть 0x8005.

Кроме того, в регистр в начале вычислений можно записать не нули, а какое-то другое число. (И это рекомендуется делать: так повышается надёжность определения начала передачи сообщения, если, например, сообщение имеет в начале нулевые биты).

Также при расчётах непосредственно перед выдачей финальную контрольную сумму CRC можно поделить на какое-то другое число.

И последнее. Байты сообщения при записи в регистр могут помещаться как старшим битом «вперёд», так и наоборот, младшим. И результирующая CRC также может выдаваться, начиная со старшего бита или с младшего.

Изменение порядка битов в байте на обратный назовём «обращение», «реверс» или «отзеркаливание» байта.

Итого имеются 6 параметров, которые влияют на значение контрольной суммы:

• порядок CRC;
• образующий многочлен (его иногда называют «генераторный полином», переводя с английского буквально);
• начальное содержимое регистра;
• значение, с которым производится финальное XOR;
• реверс байтов информационного сообщения;
• реверс байтов CRC перед финальным XOR.

2 Расчёт контрольной суммы CRC методом побитового сдвига

На основании всего вышеизложенного, давайте напишем функцию на языке Visual Basic .NET, которая будет рассчитывать контрольную сумму CRC, принимая ряд параметров, которые я описал выше, и возвращая значение CRC в виде 32-разрядного беззнакового числа.

Код расчёта CRC методом побитового сдвига на языке VB.NET

Как вы могли заметить, в данной реализации расчёта CRC используется LINQ , так что соответствующая ссылка должна быть добавлена в проект.

Предлагаемая программа плохо масштабируема. То есть она работает хорошо при вычислении контрольной суммы CRC для коротких сообщений, длиной до нескольких десятков килобайтов. Я писал её с целью только продемонстрировать работу простого алгоритма, и не занимался оптимизацией. При расчёте CRC для длинного сообщения, размером десятки или сотни мегабайтов, программа будет сильно загружать процессор и память, т.к. всё сообщение целиком загружается в очередь. Этому способствует метод преобразования числа в битовую последовательность, используя Queue(Of Boolean). Для работы с такими большими сообщениями желательно реализовать промежуточный буфер, который будет передавать сообщение в программу небольшими порциями.

Зато у этой программы есть одно преимущество: она может быть использована для расчёта CRC любого порядка, не обязательно 8, 16 или 32. Это может быть CRC5 или CRC49. Только для чисел больше 32-х разрядов нужно изменить соответствующим образом входные параметры – допустим, poly передавать не как UInteger, а как ULong, или передавать его в виде битового массива (тогда теоретически порядок CRC вообще будет неограничен).

3 Расчёт контрольной суммы CRC табличным методом

Для сокращения числа вычислений из предыдущего метода – метода побитового сдвига – придуманы некоторые оптимизации.

В частности, сдвигают не по одному биту за раз, а сразу по несколько. Наибольшую популярность снискали варианты, в которых сообщение сдвигается на число битов, кратное числу битов в байте: 8, 16 или 32, т.к. с байтами легче работать (не нужны дополнительные преобразования). При этом идея алгоритма осталась та же: сдвиг и исключающее ИЛИ с содержимым регистра.

Кроме того, оказывается, что часть расчётов можно провести заранее и записать в массив – таблицу, из которой по мере необходимости будет браться нужное число. Такой метод расчёта назвали табличный метод расчёта CRC.

Я не буду здесь вдаваться в теорию, она довольно сложна и много раз описана в других статьях. В частности, очень хорошее и подробное описание бинарной арифметики, лежащей в основе расчёта CRC, и описание табличного метода, даётся в статье Ross N. Williams: "A Painless Guide to CRC Error Detection Algorithms". Рекомендую к прочтению обязательно! Оригинальный текст – в приложении к статье, а русский перевод легко найти в интернете.

Ну что же, пришло время для самой программы. Она будет несколько длиннее предыдущей. По сути, это реализация алгоритма из указанной статьи в стиле объектно-ориентированного программирования. Опять же будем писать программу на моём любимом языке программирования VB.NET. Я назвал этот класс RocksoftCrcModel, по названию компании, в которой работал автор указанной статьи.

Код расчёта CRC табличным методом на языке VB.NET

Этот код полностью готов к использованию, можно брать и применять. Пользоваться данной программой так:

• создать экземпляр класса RocksoftCrcModel(), передав в конструктор параметры модели CRC;
• для расчёта контрольной суммы, вызвать метод данного объекта ComputeCrc() или ComputeCrcAsBytes(), передав в качестве параметра информационное сообщение, для которого необходимо посчитать контрольную сумму;
• если меняются параметры модели CRC, таблица автоматически пересчитывается, и новый экземпляр класса можно не создавать.

Приведу пример использования данного класса для алгоритма CRC16. В качестве сообщения message будем использовать массив байтов, который представляет собой строку "123456789" в коде ASCII, которая используется во многих онлайн-калькуляторах CRC:

Данная реализация расчёта CRC была проверена мною путём сличения со многими онлайн-калькуляторами CRC (назовём это «слабой» проверкой, именно такое определение дано в вышеуказанной статье, когда проверка осуществляется на основании сравнения рассчитанной контрольной суммы с эталонной, при одинаковых исходных параметрах и сообщении).

Для любителей C# перепишем данный класс таким образом:

Код расчёта CRC табличным методом на языке C# (разворачивается)

Данная программа на C# не тестировалась мной, в отличие от предыдущей, написанной на VB.NET. Этот код получен через декомпиляцию предыдущего. Если в нём обнаружатся какие-то ошибки, то пишите в комментариях или мне на почту, исправлю.

Прикладываю к статье полностью рабочий и готовый к использованию файл RocksoftCrcModel.vb с реализацией расчёта контрольной суммы CRC, который мы тут рассмотрели, а также RocksoftCrcModel.cs на C#.

4 «Взлом» контрольной суммы CRC32 и CRC16

Кратко затронем вопрос «взлома» CRC32. И прежде всего давайте определимся с понятием «взлом» применительно к данному вопросу.

Если задача определения контрольной суммы некоторого массива данных – прямая задача, то «взлом» – это обратная задача, а именно: подгонка контрольной суммы под определённый массив данных.

Допустим, вы имеете файл и рассчитали его контрольную сумму. Вам нужно изменить в нём произвольное число байтов, сохранив при этом контрольную сумму. Сделать это совсем не сложно.

Для начала нужно посчитать обычным образом контрольную сумму CRC32, CRC16 или любую другую, какая вам нужна, для этого изменённого файла. Пусть это будет C1. Теперь нужно добавить такое же число нулевых байтов в конец файла, которое содержится в контрольной сумме (для CRC32 – 4 байта, для CRC16 – 2 байта, и т.д.). Можно простым перебором подобрать такое число C2, которое мы и запишем в эти нулевые байты. Ведь понятно, что полный диапазон всех допустимых значений CRC32 укладывается в 2 32

4,295 млрд. То есть за 4 с небольшим миллиарда итераций расчёта контрольной суммы с начальным содержимым регистра, равным С1, мы брутфорсом («в лоб», методом грубой силы) подберём нужное значение. При современных вычислительных мощностях это не составит проблемы. А уж «взломать» с помощью перебора CRC16 вообще дело нескольких секунд.

Можно ли разместить нулевые байты в середине или начале файла? Можно. К операции XOR применим сочетательный закон: a XOR (b XOR c) = (a XOR b) XOR c, поэтому можно с успехом разбить файл на 3 части: до вставки, после вставки, и сама вставка. Посчитать CRC для первых двух частей (C1 и C2 на иллюстрации), объединить их операцией XOR, заполнить этим числом начальное содержимое регистра, а затем «сбрутфорсить» CRC оставшейся третьей части X.

Есть более интеллектуальный и изящный способ подогнать CRC под нужное значение. Суть его в том, что вместо последовательного перебора всех подряд значений мы «прокручиваем назад» несколько раз (по числу байтов или битов контрольной суммы) наш табличный алгоритм или алгоритм побитового сдвига до тех пор, пока CRC не будет желаемой. На эту тему есть подробные и качественные материалы в сети.

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

5 Программа для расчёта контрольной суммы по алгоритмам CRC32, CRC16 и CRC8

На основе приведённого алгоритма была написана программа – калькулятор для расчёта контрольных сумм по алгоритмам CRC32, CRC16 и CRC8 . Внешний вид окна приведён на рисунке. Программа работает под ОС Windows и требует .NET версии 3.5 .

Интерфейс программы для расчёта контрольной суммы по алгоритмам CRC32, CRC16 и CRC8

Программа позволяет рассчитывать CRC массива байтов (введённого в поле «Сообщение») или указанного файла. Все рассмотренные выше параметры контрольной суммы настраиваются через интерфейс программы.

Ну и напоследок выкладываю ссылки на архив, в архиве лежат: программа «Калькулятор CRC», оригинальная статья "A Painless Guide to CRC Error Detection Algorithms", класс RocksoftCrcModel() на Visual Basic.NET и на C#.

Содержимое архива "CRC calculator"

Итак, подведём итоги. В этой статье мы:
– узнали, что такое контрольная сумма CRC и какие бывают её виды;
– научились считать CRC методом побитового сдвига и табличным методом; – узнали алгоритмы «взлома» CRC и сделали вывод о границах применимости контрольной суммы типа CRC.

Циклический избыточный код (англ. Cyclic redundancy check, CRC [1] ) — алгоритм нахождения контрольной суммы, предназначенный для проверки целостности данных [2] . CRC является практическим приложением помехоустойчивого кодирования, основанным на определённых математических свойствах циклического кода.

Содержание

Введение [ править | править код ]

Понятие циклические коды достаточно широкое [3] . В англоязычной литературе CRC понимается двояко в зависимости от контекста: Cyclic Redundancy Code или Cyclic Redundancy Check [4] . Под первым понятием подразумевают математический феномен циклических кодов, под вторым — конкретное применение этого феномена как хеш-функции.

Помехоустойчивое кодирование [ править | править код ]

Первые попытки создания кодов с избыточной информацией начались задолго до появления современных компьютеров. К примеру, ещё в 1960-х годах Ридом и Соломоном была разработана эффективная методика кодирования — Код Рида-Соломона. Использование её в те времена не представлялось возможным, так как произвести операцию декодирования за разумное время первыми алгоритмами не удавалось. Точку в этом вопросе поставила фундаментальная работа Берлекэмпа, опубликованная в 1968 году. Эта методика, на практическое применение которой указал через год Мэсси, и по сей день используется в цифровых устройствах, обеспечивающих приём RS-кодированных данных. Более того: данная система позволяет не только определять позиции, но и исправлять неверные кодовые символы (чаще всего октеты).

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

Хотя код CRC используют обычно только для обнаружения ошибок, его математические свойства дают возможность найти и исправить одиночную ошибку в блоке бит, если каждому биту защищаемого блока (включая проверочные биты) соответствует свой уникальный остаток от деления на порождающий многочлен. Например, если порождающий многочлен неприводим, и длина блока не превышает порядок порождённой циклической группы.

Контрольная сумма [ править | править код ]

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

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

Математическое описание [ править | править код ]

Алгоритм CRC базируется на свойствах деления с остатком двоичных многочленов, то есть многочленов над конечным полем G F ( 2 ) <displaystyle GF(2)> . Значение CRC является по сути остатком от деления многочлена, соответствующего входным данным, на некий фиксированный порождающий многочлен.

Каждой конечной последовательности битов a 0 , a 1 , … , a N − 1 <displaystyle a_<0>,a_<1>,dots ,a_> взаимно однозначно сопоставляется двоичный полином ∑ n = 0 N − 1 a n x n <displaystyle extstyle sum _^a_x^> , последовательность коэффициентов которого представляет собой исходную последовательность. Например, последовательность битов 1011010 соответствует многочлену:

P ( x ) = 1 ⋅ x 6 + 0 ⋅ x 5 + 1 ⋅ x 4 + 1 ⋅ x 3 + 0 ⋅ x 2 + 1 ⋅ x 1 + 0 ⋅ x 0 = x 6 + x 4 + x 3 + x 1 . <displaystyle P(x)=1cdot x^<6>+0cdot x^<5>+1cdot x^<4>+1cdot x^<3>+0cdot x^<2>+1cdot x^<1>+0cdot x^<0>=x^<6>+x^<4>+x^<3>+x^<1>.>

Количество различных многочленов степени, меньшей N <displaystyle N> , равно 2 N <displaystyle 2^> , что совпадает с числом всех двоичных последовательностей длины N <displaystyle N> .

Значение контрольной суммы в алгоритме с порождающим многочленом G ( x ) <displaystyle G(x)> степени N <displaystyle N> определяется как битовая последовательность длины N <displaystyle N> , представляющая многочлен R ( x ) <displaystyle R(x)> , получившийся в остатке при делении многочлена P ( x ) <displaystyle P(x)> , представляющего входной поток бит, на многочлен G ( x ) <displaystyle G(x)> :

R ( x ) = P ( x ) ⋅ x N mod G ( x ) <displaystyle R(x)=P(x)cdot x^,<mod <,>>G(x)>

Умножение x N <displaystyle x^> осуществляется приписыванием N <displaystyle N> нулевых битов к входной последовательности, что улучшает качество хеширования для коротких входных последовательностей.

При делении с остатком различных исходных многочленов на порождающий полином G ( x ) <displaystyle G(x)> степени N <displaystyle N> можно получить 2 N <displaystyle 2^> различных остатков от деления. G ( x ) <displaystyle G(x)> зачастую является неприводимым многочленом. Обычно его подбирают в соответствии с требованиями к хеш-функции в контексте каждого конкретного применения.

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

Вычисление CRC [ править | править код ]

	Имеется викиучебник по теме «Реализации алгоритмов/Циклический избыточный код»

Параметры алгоритма [ править | править код ]

Одним из основных параметров CRC является порождающий полином.

С порождающим полиномом связан другой параметр — его степень, которая определяет количество битов, используемых для вычисления значения CRC. На практике наиболее распространены 8-, 16- и 32-битовые слова, что является следствием особенностей архитектуры современной вычислительной техники.

Ещё одним параметром является начальное (стартовое) значение слова. Указанные параметры полностью определяют «традиционный» алгоритм вычисления CRC. Существуют также модификации алгоритма, например, использующие обратный порядок обработки битов.

Описание процедуры [ править | править код ]

Из файла берётся первое слово — это может быть битовый (CRC-1), байтовый (CRC-8) или любой другой элемент. Если старший бит в слове «1», то слово сдвигается влево на один разряд с последующим выполнением операции XOR c порождающим полиномом. Соответственно, если старший бит в слове «0», то после сдвига операция XOR не выполняется. После сдвига теряется старший бит, а младший бит освобождается — его значение устанавливается равным нулю. На место младшего бита загружается очередной бит из файла, и операция повторяется до тех пор, пока не загрузится последний бит файла. После прохождения всего файла, в слове остается остаток, который и является контрольной суммой.

Популярные и стандартизованные полиномы [ править | править код ]

В то время, как циклические избыточные коды являются частью стандартов, у этого термина не существует общепринятого определения — трактовки различных авторов нередко противоречат друг другу. [1] [5]

Этот парадокс касается и выбора многочлена-генератора: зачастую стандартизованные полиномы не являются самыми эффективными в плане статистических свойств соответствующего им check redundancy code.

При этом многие широко используемые полиномы не являются наиболее эффективными из всех возможных. В 1993—2004 годах группа учёных занималась исследованием порождающих многочленов разрядности до 16, [1] 24 и 32 бит [6] [7] и нашла полиномы, дающие лучшую, нежели стандартизированные многочлены, производительность в смысле кодового расстояния. [7] Один из результатов этого исследования уже нашёл своё применение в протоколе iSCSI.

Самый популярный и рекомендуемый IEEE полином для CRC-32 используется в Ethernet, FDDI; также этот многочлен является генератором кода Хемминга [8] . Использование другого полинома — CRC-32C — позволяет достичь такой же производительности при длине исходного сообщения от 58 бит до 131 кбит, а в некоторых диапазонах длины входного сообщения может быть даже выше — поэтому в наши дни он тоже пользуется популярностью. [7] К примеру, стандарт ITU-T G.hn использует CRC-32C с целью обнаружения ошибок в полезной нагрузке.

Ниже в таблице перечислены наиболее распространённые многочлены — генераторы CRC. На практике вычисление CRC может включать пре- и постинверсию, а также обратный порядок обработки битов. В проприетарных реализациях CRC для усложнения анализа кода применяют ненулевые начальные значения регистров.

Название	Полином	Представления: [9] нормальное / реверсированное / реверсированное от обратного
CRC-1	x + 1 <displaystyle x+1> (используется в аппаратном контроле ошибок; также известен как бит чётности)	0x1 / 0x1 / 0x1
CRC-4-ITU	x 4 + x + 1 <displaystyle x^<4>+x+1> (ITU G.704 [10] )	0x3 / 0xC / 0x9
CRC-5-EPC	x 5 + x 3 + 1 <displaystyle x^<5>+x^<3>+1> (Gen 2 RF >[11] )	0x09 / 0x12 / 0x14
CRC-5-ITU	x 5 + x 4 + x 2 + 1 <displaystyle x^<5>+x^<4>+x^<2>+1> (ITU G.704 [12] )	0x15 / 0x15 / 0x1A
CRC-5-USB	x 5 + x 2 + 1 <displaystyle x^<5>+x^<2>+1> (USB token packets)	0x05 / 0x14 / 0x12
CRC-6-ITU	x 6 + x + 1 <displaystyle x^<6>+x+1> (ITU G.704 [13] )	0x03 / 0x30 / 0x21
CRC-7	x 7 + x 3 + 1 <displaystyle x^<7>+x^<3>+1> (системы телекоммуникации, ITU-T G.707 [14] , ITU-T G.832 [15] , MMC, SD)	0x09 / 0x48 / 0x44
CRC-8-CCITT	x 8 + x 2 + x + 1 <displaystyle x^<8>+x^<2>+x+1> (ATM HEC), ISDN Header Error Control and Cell Delineation ITU-T I.432.1 (02/99)	0x07 / 0xE0 / 0x83
CRC-8-Dallas/Maxim	x 8 + x 5 + x 4 + 1 <displaystyle x^<8>+x^<5>+x^<4>+1> (1-Wire bus)	0x31 / 0x8C / 0x98
CRC-8	x 8 + x 7 + x 6 + x 4 + x 2 + 1 <displaystyle x^<8>+x^<7>+x^<6>+x^<4>+x^<2>+1> (ETSI EN 302 307 [16] , 5.1.4)	0xD5 / 0xAB / 0xEA [1]
CRC-8-SAE J1850	x 8 + x 4 + x 3 + x 2 + 1 <displaystyle x^<8>+x^<4>+x^<3>+x^<2>+1>	0x1D / 0xB8 / 0x8E
CRC-10	x 10 + x 9 + x 5 + x 4 + x + 1 <displaystyle x^<10>+x^<9>+x^<5>+x^<4>+x+1>	0x233 / 0x331 / 0x319
CRC-11	x 11 + x 9 + x 8 + x 7 + x 2 + 1 <displaystyle x^<11>+x^<9>+x^<8>+x^<7>+x^<2>+1> (FlexRay [17] )	0x385 / 0x50E / 0x5C2
CRC-12	x 12 + x 11 + x 3 + x 2 + x + 1 <displaystyle x^<12>+x^<11>+x^<3>+x^<2>+x+1> (системы телекоммуникации [18] [19] )	0x80F / 0xF01 / 0xC07
CRC-15-CAN	x 15 + x 14 + x 10 + x 8 + x 7 + x 4 + x 3 + 1 <displaystyle x^<15>+x^<14>+x^<10>+x^<8>+x^<7>+x^<4>+x^<3>+1>	0x4599 / 0x4CD1 / 0x62CC
CRC-16-IBM	x 16 + x 15 + x 2 + 1 <displaystyle x^<16>+x^<15>+x^<2>+1> (Bisync, Modbus, USB, ANSI X3.28 [20] , многие другие; также известен как CRC-16 и CRC-16-ANSI)	0x8005 / 0xA001 / 0xC002
CRC-16-CCITT	x 16 + x 12 + x 5 + 1 <displaystyle x^<16>+x^<12>+x^<5>+1> (X.25, HDLC, XMODEM, Bluetooth, SD и др.)	0x1021 / 0x8408 / 0x8810 [1]
CRC-16-T10-DIF	x 16 + x 15 + x 11 + x 9 + x 8 + x 7 + x 5 + x 4 + x 2 + x + 1 <displaystyle x^<16>+x^<15>+x^<11>+x^<9>+x^<8>+x^<7>+x^<5>+x^<4>+x^<2>+x+1> (SCSI DIF)	0x8BB7 [21] / 0xEDD1 / 0xC5DB
CRC-16-DNP	x 16 + x 13 + x 12 + x 11 + x 10 + x 8 + x 6 + x 5 + x 2 + 1 <displaystyle x^<16>+x^<13>+x^<12>+x^<11>+x^<10>+x^<8>+x^<6>+x^<5>+x^<2>+1> (DNP, IEC 870, M-Bus)	0x3D65 / 0xA6BC / 0x9EB2
CRC-16-Fletcher	Не CRC; см. Fletcher’s checksum	Используется в Adler-32 A & B CRC
CRC-24	x 24 + x 22 + x 20 + x 19 + x 18 + x 16 + x 14 + x 13 + x 11 + x 10 + x 8 + x 7 + x 6 + x 3 + x + 1 <displaystyle x^<24>+x^<22>+x^<20>+x^<19>+x^<18>+x^<16>+x^<14>+x^<13>+x^<11>+x^<10>+x^<8>+x^<7>+x^<6>+x^<3>+x+1> (FlexRay [17] )	0x5D6DCB / 0xD3B6BA / 0xAEB6E5
CRC-24-Radix-64	x 24 + x 23 + x 18 + x 17 + x 14 + x 11 + x 10 + x 7 + x 6 + x 5 + x 4 + x 3 + x + 1 <displaystyle x^<24>+x^<23>+x^<18>+x^<17>+x^<14>+x^<11>+x^<10>+x^<7>+x^<6>+x^<5>+x^<4>+x^<3>+x+1> (OpenPGP)	0x864CFB / 0xDF3261 / 0xC3267D
CRC-30	x 30 + x 29 + x 21 + x 20 + x 15 + x 13 + x 12 + x 11 + x 8 + x 7 + x 6 + x 2 + x + 1 <displaystyle x^<30>+x^<29>+x^<21>+x^<20>+x^<15>+x^<13>+x^<12>+x^<11>+x^<8>+x^<7>+x^<6>+x^<2>+x+1> (CDMA)	0x2030B9C7 / 0x38E74301 / 0x30185CE3
CRC-32-Adler	Не CRC; см. Adler-32	См. Adler-32
CRC-32-IEEE 802.3	x 32 + x 26 + x 23 + x 22 + x 16 + x 12 + x 11 + x 10 + x 8 + x 7 + x 5 + x 4 + x 2 + x + 1 <displaystyle x^<32>+x^<26>+x^<23>+x^<22>+x^<16>+x^<12>+x^<11>+x^<10>+x^<8>+x^<7>+x^<5>+x^<4>+x^<2>+x+1> (V.42, MPEG-2, PNG [22] , POSIX cksum)	0x04C11DB7 / 0xEDB88320 / 0x82608EDB [7]
CRC-32C (Castagnoli)	x 32 + x 28 + x 27 + x 26 + x 25 + x 23 + x 22 + x 20 + x 19 + x 18 + x 14 + x 13 + x 11 + x 10 + x 9 + x 8 + x 6 + 1 <displaystyle x^<32>+x^<28>+x^<27>+x^<26>+x^<25>+x^<23>+x^<22>+x^<20>+x^<19>+x^<18>+x^<14>+x^<13>+x^<11>+x^<10>+x^<9>+x^<8>+x^<6>+1> (iSCSI, G.hn payload)	0x1EDC6F41 / 0x82F63B78 / 0x8F6E37A0 [7]
CRC-32K (Koopman)	x 32 + x 30 + x 29 + x 28 + x 26 + x 20 + x 19 + x 17 + x 16 + x 15 + x 11 + x 10 + x 7 + x 6 + x 4 + x 2 + x + 1 <displaystyle x^<32>+x^<30>+x^<29>+x^<28>+x^<26>+x^<20>+x^<19>+x^<17>+x^<16>+x^<15>+x^<11>+x^<10>+x^<7>+x^<6>+x^<4>+x^<2>+x+1>	0x741B8CD7 / 0xEB31D82E / 0xBA0DC66B [7]
CRC-32Q	x 32 + x 31 + x 24 + x 22 + x 16 + x 14 + x 8 + x 7 + x 5 + x 3 + x + 1 <displaystyle x^<32>+x^<31>+x^<24>+x^<22>+x^<16>+x^<14>+x^<8>+x^<7>+x^<5>+x^<3>+x+1> (aviation; AIXM [23] )	0x814141AB / 0xD5828281 / 0xC0A0A0D5
CRC-64-ISO	x 64 + x 4 + x 3 + x + 1 <displaystyle x^<64>+x^<4>+x^<3>+x+1> (HDLC — ISO 3309)	0x000000000000001B / 0xD800000000000000 / 0x800000000000000D
CRC-64-ECMA	x 64 + x 62 + x 57 + x 55 + x 54 + x 53 + x 52 + x 47 + x 46 + x 45 + x 40 + x 39 + x 38 + x 37 + x 35 + x 33 + <displaystyle x^<64>+x^<62>+x^<57>+x^<55>+x^<54>+x^<53>+x^<52>+x^<47>+x^<46>+x^<45>+x^<40>+x^<39>+x^<38>+x^<37>+x^<35>+x^<33>+> x 32 + x 31 + x 29 + x 27 + x 24 + x 23 + x 22 + x 21 + x 19 + x 17 + x 13 + x 12 + x 10 + x 9 + x 7 + x 4 + x + 1 <displaystyle x^<32>+x^<31>+x^<29>+x^<27>+x^<24>+x^<23>+x^<22>+x^<21>+x^<19>+x^<17>+x^<13>+x^<12>+x^<10>+x^<9>+x^<7>+x^<4>+x+1> [24]	0x42F0E1EBA9EA3693 / 0xC96C5795D7870F42 / 0xA17870F5D4F51B49

Существующие стандарты CRC-128 (IEEE) и CRC-256 (IEEE) в настоящее время вытеснены криптографическими хеш-функциями.

Спецификации алгоритмов CRC [ править | править код ]

Одной из самых известных является методика Ross N. Williams [25] . В ней используются следующие параметры: