Расчет контрольной суммы CRC (CRC-8/16/32/64)

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

Разные стандартные организации и производители выбрали разные полиномы генератора, начальные значения регистров, настройки отражения битов и конечные значения XOR для соответствия своим требованиям к обнаружению ошибок. Ethernet, ZIP и PNG согласились на CRC-32 (IEEE 802.3), в то время как промышленные протоколы, такие как MODBUS, USB и XMODEM, стандартизировали свои собственные варианты CRC-16. Два варианта с одинаковым разрядом будут генерировать совершенно разные контрольные суммы для одного и того же входа, если хотя бы один параметр отличается, поэтому выбор точного варианта, соответствующего вашей целевой системе, является обязательным.

Отраженные (иногда называемые перевернутыми) варианты обрабатывают каждый байт с наименьшим значением бита в начале и отражают биты регистра перед применением XOR на выходе. Неперевернутые варианты обрабатывают биты в порядке наибольшего значения. Этот выбор возник в ходе разработки аппаратных устройств, где сдвиг регистра в одну сторону был дешевле, чем в другую. Две CRC с одинаковым полиномом, но разными настройками отражения, несовместимы — CRC-32 и CRC-32/BZIP2 используют одинаковый полином 0x04C11DB7, но генерируют совершенно разные значения.

CRC-32C, опубликованный Гуи Кастагноли в 1993 году, использует полином 0x1EDC6F41 вместо 0x04C11DB7. Его свойства обнаружения ошибок математически превосходят стандартный CRC-32 для коротких пакетов, и современные процессоры x86 реализуют его в одном инструкции CRC32. Он используется в iSCSI, SCTP, метаданных ext4, Btrfs и слое фрейминга gRPC от Google. Когда важны как высокая пропускная способность, так и сильное обнаружение ошибок, системы всё чаще предпочитают CRC-32C вместо классического CRC Ethernet.

Никакая система обнаружения ошибок не может обнаружить всё. n-битный CRC гарантирует обнаружение всех буферных ошибок длиной до n бит и всех однобитных ошибок, но приблизительно 1 из 2^n случайных повреждений может ускользнуть. Для CRC-32 это около 1 из 4,3 миллиарда — отличный результат для обычных файлов и фреймов целостности. Для очень больших файлов или долгосрочного хранения CRC-64 расширяет этот предел до примерно 1 из 1,8 × 10^19. В случае вмешательства со стороны злоумышленника ситуация другая: атакующие могут всегда изменять сообщение так, чтобы его CRC соответствовал выбранному значению, поэтому контрольные суммы никогда не должны заменять цифровые подписи для аутентификации.