CRC

Идея: деление вместо суммирования

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

Арифметика здесь особая — по модулю 2, в поле GF(2). Сложение и вычитание совпадают и равны XOR, переносов между разрядами нет. На практике это означает, что деление реализуется циклом из сдвигов и операций XOR, без единого умножения. Наивная реализация обрабатывает бит за битом, промышленная — по байту за такт через таблицу на 256 элементов, а аппаратная в процессорах Intel считает CRC32C одной инструкцией.

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

Какие ошибки CRC ловит гарантированно

Сила CRC не в средней вероятности, а в доказуемых гарантиях. Правильно выбранный полином степени r обнаруживает:

• любую одиночную ошибку в бите;
• любое нечётное число ошибочных бит — при условии, что полином делится на (x + 1);
• любые две ошибки, если длина сообщения меньше периода полинома;
• любой пакет искажений длиной не больше r бит подряд — а именно так выглядят реальные сбои в канале связи и на носителе.

Пакеты длиннее r проскакивают с вероятностью примерно 2^−r: для CRC-32 это порядка одного случая на четыре миллиарда. Для проверки реализации существует контрольная строка: CRC-32 от ASCII-строки 123456789 должен дать 0xCBF43926, а классический CRC-16/CCITT-FALSE от неё же — 0x29B1. Если ваш код выдаёт другое, дело почти всегда в отражении бит или в начальном значении регистра.

Практическая шкала избыточности говорит сама за себя: 4 байта CRC-32 защищают кадр Ethernet длиной до 1500 байт, то есть накладные расходы меньше трети процента. Хеш SHA-256 на той же задаче стоил бы 32 байта и на порядки больше вычислений, а гарантий по пакетным ошибкам не дал бы вовсе.

Где CRC работает каждый день

В сетях и файлах: кадры Ethernet, PPP, USB, CAN-шина в автомобиле, архивы ZIP и gzip, чанки PNG — все они несут CRC-32. Файловые системы и жёсткие диски проверяют CRC на каждом секторе. Технически это тот же класс задач, что решает контрольная цифра в штрих-коде, только с гарантией по пакетным сбоям.

В платёжных QR-кодах CRC встречается на виду. Спецификация EMVCo завершает payload полем 63, где четыре шестнадцатеричных символа в верхнем регистре — это CRC-16/CCITT-FALSE с полиномом 0x1021 и начальным значением 0xFFFF. Считается сумма по всей строке, включая идентификатор поля 63 и его длину 04, но не включая сами четыре символа. Терминал пересчитывает CRC перед оплатой, и если пользователь дорисовал в ссылке лишнюю цифру, код просто не примут. Подробности разбора этого поля — в термине контрольная сумма CRC (EMVCo QR), а структура самого payload — в статье про EMV QR.

В промышленных протоколах: Modbus RTU использует CRC-16 с полиномом 0xA001 в отражённой форме, и без него шумная линия RS-485 давала бы ложные команды на исполнительные механизмы. Считыватели штрихкодов и весы общаются с кассой по тем же принципам.

В двумерных кодах CRC как таковой не применяется: там нужна не только проверка, но и восстановление данных, поэтому используются коды Рида — Соломона, а служебные поля QR защищены кодами BCH. Логика уровней избыточности описана в термине уровни коррекции ошибок.

Чего CRC не умеет

CRC линеен, и это его слабое место. Зная данные и желаемую контрольную сумму, злоумышленник за доли секунды подберёт изменения, которые оставят CRC прежним. Более того, XOR двух сообщений даёт XOR их контрольных сумм — свойство, полезное инженеру и губительное для безопасности. Ставить CRC на защиту от подделки нельзя ни в каком виде: для этого существуют криптографические хеши и подписи, начиная с SHA-256.

Второе ограничение: CRC только обнаруживает ошибку, но не исправляет. Обнаружил — значит, кадр отбрасывается и запрашивается повтор. В печатном коде на упаковке повтора не запросишь, поэтому там работает избыточность другого класса. Третье: CRC ничего не говорит о том, где именно повреждение, — только о факте несовпадения.

Частые вопросы

Чем CRC отличается от бита чётности?

Бит чётности — вырожденный случай CRC с полиномом x + 1: он даёт один бит и ловит только нечётное число ошибок. CRC-16 или CRC-32 дают 16 или 32 бита и гарантированно обнаруживают пакеты искажений длиной до ширины полинома, что для реальных каналов связи принципиально: сбои там приходят группами, а не поодиночке.

Почему у одного и того же CRC-16 бывают разные значения?

Потому что полином — лишь один из пяти параметров. Различаются начальное значение регистра (0x0000 или 0xFFFF), направление обработки бит, финальный XOR и порядок бит в результате. Варианты CCITT-FALSE, XMODEM, MODBUS и KERMIT используют одну и ту же математику, но дают разные числа. При интеграции всегда сверяйте контрольное значение для строки 123456789.

Можно ли по CRC восстановить испорченный байт?

В общем случае нет: CRC не является корректирующим кодом. Если известно, что ошибка ровно одна и данные короткие, позицию иногда удаётся вычислить перебором, но это трюк, а не свойство алгоритма. Когда нужно именно восстановление, применяют коды Рида — Соломона, BCH или коды Хэмминга — они несут для этого достаточную избыточность.

Что произойдёт, если в платёжном QR-коде CRC не сойдётся?

Банковское приложение откажется обрабатывать такой код и покажет ошибку формата. Это штатная защита: чаще всего причина не в атаке, а в том, что payload собрали вручную и забыли включить в расчёт символы 6304 или посчитали сумму по уже готовой строке вместе со старым значением. Правильный порядок — собрать строку, дописать 6304, посчитать CRC, приписать четыре символа.

Насколько CRC-32 медленнее SHA-256?

Существенно быстрее, а не медленнее: табличная реализация CRC-32 обрабатывает байт за несколько операций, а аппаратная в современных процессорах считает по восемь байт за такт. SHA-256 требует 64 раунда на каждые 64 байта. Разница в пропускной способности достигает порядка величины, поэтому CRC и остаётся стандартом там, где проверка идёт на каждом кадре.