Строки имеют вид «АЛГОРИТМ значение», за которым следует строка параметров с отступом, поэтому скопированный результат всегда показывает, какой набор параметров его создал.
CRC — циклический избыточный код, с нуля
Коротко: CRC рассматривает ваши данные как одно огромное двоичное число, делит его на фиксированное «порождающее» число, используя XOR вместо вычитания, и сообщает остаток — компактный отпечаток, который резко меняется даже от одного перевёрнутого бита входных данных, поэтому всё, от файлов PNG до проводов Modbus, его несёт.
Что такое CRC на самом деле
Картина деления. Выстройте байты в одно длинное двоичное число. Выберите делитель — полином, например 0x04C11DB7 для CRC-32. Выполните двоичное деление в столбик, где «вычитание» — это операция XOR: всякий раз, когда старший бит текущего остатка равен 1, применяйте XOR с делителем, сдвигайте влево и повторяйте. Когда пройдёт всё сообщение, то, что останется в регистре, и есть CRC. Никаких ключей и таблиц в определении нет — просто деление с остатком.
Пять параметров. Две системы могут обе говорить «CRC-32» и всё же расходиться, потому что одно название ничего не фиксирует. Полный рецепт требует пяти значений: poly (делитель), init (с чего начинается регистр — нули позволяют ведущим нулевым байтам исчезнуть, единицы — нет), refin/refout (побитно ли инвертируется каждый входной байт — и итоговый регистр; наследие последовательного оборудования, которое передавало биты от младшего к старшему), и xorout (финальная маска XOR, чтобы серия завершающих нулей всё равно меняла результат). Эта страница печатает все пять значений рядом с каждым результатом именно поэтому.
Почему он обнаруживает ошибки. Хорошо подобранный делитель делает так, что остаток сообщения и остаток того же сообщения с несколькими перевёрнутыми битами почти наверняка различаются: хороший CRC-32 ловит все однобитовые и двухбитовые ошибки, все нечётные количества битовых ошибок и любой пакет до 32 подряд повреждённых битов — гарантированно, а не вероятностно. Эта гарантия касается случайного повреждения, и именно поэтому CRC — правильный инструмент для шумных проводов и ненадёжных дисков.
Чем CRC не является
Не криптографический хеш. В нём нет секрета и односторонности: любой, кто знает параметры, может подделать сообщение с любым нужным CRC за миллисекунды, дописав четыре корректирующих байта. CRC обнаруживает случайности, но никогда злоумышленников. Для загрузок, которые вы проверяете у незнакомцев, важны подписи — см. Генератор хешей (MD5/SHA/BLAKE2). Та страница также объясняет, почему MD5 и SHA-1 выведены из употребления во враждебных условиях, а SHA-256 остаётся надёжным.
Не код с исправлением ошибок. CRC говорит вам, что что-то изменилось, но не что именно. Исправление ошибок на лету — задача таких кодов, как Рида–Соломона или Хэмминга, которые намеренно хранят избыточную структуру, способную инвертировать декодер.
Не сжатие и не шифрование. Остаток занимает несколько байт независимо от размера входных данных, и по нему нельзя восстановить вход — но в отличие от криптографического хеша это лишь потому, что информация была отброшена, а не потому, что обратить её трудно.
Семейства на этой странице
Четвёрка CRC-32. Четыре записи этой страницы имеют общий полином 0x04C11DB7, но дают разные значения: ISO-HDLC (отражённый, init и xorout из единиц) — это «тот самый» CRC-32 из zlib, gzip, PNG и ZIP; BZIP2 — та же математика без отражения; MPEG-2 — BZIP2 без финального XOR; POSIX начинается с нуля и лежит в основе команды cksum (которая дополнительно добавляет длину файла к делению, поэтому cksum файла и CRC-32/POSIX тех же байтов различаются). CRC-32C (Кастаньоли, полином 0x1EDC6F41) — пятый собрат: другой полином, выбранный для лучшей производительности обнаружения ошибок, и тот, который современные процессоры x86 и ARM вычисляют на скорости памяти одной инструкцией.
Четвёрка CRC-64. XZ использует полином ECMA-182 в отражённой форме с init и xorout из единиц; ECMA-182 — исходный неотражённый вариант с нулевым init из стандарта ленты DLT-1; GO-ISO — это crc64.ISO из Go, с крошечным полиномом 0x1B, по-прежнему отражённый; REDIS использует полином, выбранный за хорошую лавинность при назначении хеш-слотов. Шестьдесят четыре бита — тот размер, при котором CRC начинают использовать как хеш-функции (для распределения по корзинам), а не как чистые контрольные суммы.
Adler-32 — чужак: это вообще не деление. Он суммирует байты (A, начиная с 1) и суммирует эти суммы (B), обе по модулю 65521, и объединяет две 16-битные суммы. Программно он быстрее CRC-32, и zlib использует его для потоков deflate — но для коротких входов (меньше нескольких сотен байтов) сумма несёт слишком мало информации, поэтому zlib переключается обратно на CRC-32 для небольших блоков.
CRC-8 и CRC-16 выживают там, где байты дороги: CRC-8/CCITT (полином 0x07) защищает отдельные байты заголовков в протоколах SMBus и сотовой радиосвязи; CRC-16/CCITT-FALSE защищает блоки смарт-карт; CRC-16/MODBUS — контрольная сумма каждого кадра Modbus RTU на заводах по всему миру.
Где живёт каждый из них
| Набор параметров | Где встречается |
|---|
| CRC-32/ISO-HDLC | zlib, gzip, PNG, ZIP, Ethernet (FCS), многие форматы архивов |
| CRC-32C | iSCSI, ext4, btrfs, ZFS, аппаратная инструкция CRC32C в SSE4.2/ARMv8 |
| CRC-32/BZIP2 | поток архива .bz2 |
| CRC-32/MPEG-2 | транспортные потоки MPEG-2 |
| CRC-32/POSIX & cksum | вывод команды POSIX cksum (cksum file.txt) |
| CRC-16/MODBUS | кадры Modbus RTU (промышленные ПЛК, счётчики, инверторы) |
| CRC-16/CCITT-FALSE | смарт-карты, связи, родственные X.25, некоторые протоколы GPS |
| CRC-8/CCITT | SMBus (байт PEC), заголовки сотовой радиосвязи |
| CRC-64/XZ | проверки целостности контейнера .xz |
| CRC-64/ECMA-182 | стандарт ленты ECMA-182 / DLT-1 |
| CRC-64/GO-ISO | стандартная библиотека Go, crc64.ISO |
| CRC-64/REDIS | назначение хеш-слотов кластера Redis |
| Adler-32 | потоки zlib (deflate), другие контексты быстрых контрольных сумм |
Таблица эталонов — check(“123456789”)
Конвенция каталога CRC — публиковать результат для ASCII-строки 123456789 (9 байт). Каждое значение ниже воспроизводится на этой странице: введите 123456789 в поле «Текст», отметьте алгоритм и нажмите «Вычислить».
| Набор параметров | Ширина | Контрольное значение (hex) |
|---|
| CRC-8/CCITT | 8 | 0xf4 |
| CRC-16/CCITT-FALSE | 16 | 0x29b1 |
| CRC-16/MODBUS | 16 | 0x4b37 |
| CRC-32/ISO-HDLC | 32 | 0xcbf43926 |
| CRC-32C | 32 | 0xe3069283 |
| CRC-32/BZIP2 | 32 | 0xfc891918 |
| CRC-32/MPEG-2 | 32 | 0x0376e6e7 |
| CRC-32/POSIX | 32 | 0x765e7680 |
| cksum (POSIX command) | 32 | 0x377a6011 |
| CRC-64/XZ | 64 | 0x995dc9bbdf1939fa |
| CRC-64/ECMA-182 | 64 | 0x6c40df5f0b497347 |
| CRC-64/GO-ISO | 64 | 0xb90956c775a41001 |
| CRC-64/REDIS | 64 | 0xe9c6d914c4b8d9ca |
| Adler-32 | 32 | 0x091e01de |
Источники: каждое значение перекрёстно проверено независимой побитовой эталонной реализацией и, где такая есть, системной библиотекой, содержащей алгоритм (zlib для CRC-32 и Adler-32; каталог CRC Грега Кука для остальных).
Частые ошибки
- «CRC-32» без параметров. Между ISO-HDLC, BZIP2, MPEG-2, POSIX и CRC-32C под одним названием циркулируют пять разных значений. Всегда записывайте poly/init/refin/refout/xorout вместе с результатом — эта страница печатает их за вас.
- Сравнение CRC-32 файла с выводом
cksum. Это разные алгоритмы: cksum добавляет длину и использует другой init. Числа не совпадут, и оба будут «правильными».
- Доверие CRC против подмены. Подделать совпадающий CRC — хрестоматийное упражнение (исправить последние 4 байта). Используйте ключевой MAC (HMAC) или подпись, когда другая сторона может быть враждебной.
- Ожидание лавинности. CRC линейна: родственные сообщения дают родственные CRC. Годится для шума, но не для хеширования — если нужно распределение по корзинам, CRC-64 или настоящий хеш безопаснее, чем CRC-32.
- Текст hex против байтов. Строка
"123456789" (9 ASCII-байт, 31 32 33 34 35 36 37 38 39) и число 0x123456789 — разные входы с разными CRC. Используйте вкладку «Байты hex», когда исходные данные действительно двоичные.
Частые вопросы
Почему мой CRC-32 не совпадает с тем, что в ZIP-файле? CRC-32 в ZIP — это ISO-HDLC по распакованным данным. Убедитесь, что вы хешировали те же байты (не сжатый поток), тот же режим (Текст или Hex) и тот же набор параметров — строка параметров под каждым результатом нужна именно для мгновенной проверки этого.
Что лучше, CRC-32C или CRC-32? Для обнаружения случайных ошибок оба ловят все пакеты до 32 бит; CRC-32C работает лучше на некоторых шаблонах ошибок и имеет аппаратную инструкцию процессора — фактически бесплатно на гигабитных скоростях. Причина, по которой CRC-32/ISO-HDLC выжил, — совместимость: тридцать лет архивов говорят на нём.
CRC-64 надёжнее CRC-32? Он обнаруживает более длинные пакеты (до 64 бит) и гораздо реже даёт коллизии при распределении по корзинам, но подделывается так же легко — ширина даёт гарантии обнаружения, а не безопасность.
Можно ли обратить CRC, чтобы раскрыть вход? Нет — бесконечно много входов имеют один CRC. Но в отличие от криптографического хеша злоумышленник может построить вход с любым выбранным CRC, и именно в этом смысле это вовсе не односторонняя функция.
