Рядки мають форму «АЛГОРИТМ значення», за якою йде відступлений рядок параметрів, тож скопійований результат завжди вказує, який набір параметрів його створив.
CRC — циклічний контроль надлишковості, пояснення з нуля
Одним реченням: CRC розглядає ваші дані як одне величезне двійкове число, ділить його на фіксоване число-«генератор», використовуючи XOR замість віднімання, і повертає остачу — компактний відбиток, що різко змінюється, коли перевертається навіть один біт вхідних даних, тому кожен файл PNG і кожен провід Modbus має такий.
Що таке CRC насправді
Картина ділення. Вишикуйте свої байти в одне довге двійкове число. Оберіть дільник — поліном, напр. 0x04C11DB7 для CRC-32. Виконайте двійкове довге ділення, де «віднімання» — це операція XOR: щоразу, коли старший біт поточного залишку дорівнює 1, виконуйте XOR із дільником, зсувайте вліво, повторіть. Коли все повідомлення пройде, те, що лишилося в регістрі, і є CRC. Жодних ключів, жодних таблиць у визначенні — просто ділення з остачею.
П'ять параметрів. Дві системи можуть обидві казати «CRC-32» і все одно не погоджуватися, бо сама назва нічого не фіксує. Повний рецепт потребує п'яти значень: poly (дільник), init (з чого починається регістр — нулі дозволяють провідним нульовим байтам зникнути, одиниці — ні), refin/refout (чи кожен вхідний байт — і фінальний регістр — має обернуті біти, спадщина послідовного обладнання, що надсилало спершу молодші біти), і xorout (фінальна маска XOR, щоб серія кінцевих нулів усе ще змінювала відповідь). Ця сторінка друкує всі п'ять поруч із кожним результатом саме з цієї причини.
Чому він виявляє помилки. Добре обраний дільник робить остачу повідомлення і остачу того самого повідомлення з кількома перевернутими бітами різними з переважаючою ймовірністю: добрий CRC-32 ловить усі 1-бітні та 2-бітні помилки, усі непарні кількості бітових помилок і кожен сплеск до 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 (промислові PLC, лічильники, інвертори) |
| 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 Greg Cook для решти).
Типові помилки
- «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.
- Шістнадцятковий текст проти байтів. Рядок
"123456789" (9 байтів ASCII, 31 32 33 34 35 36 37 38 39) і число 0x123456789 — різні вхідні дані з різними CRC. Використовуйте вкладку «Шістнадцяткові байти», коли вихідні дані справді двійкові.
Часті запитання (FAQ)
Чому мій CRC-32 не збігається з тим, що в ZIP-файлі? CRC-32 у ZIP — це ISO-HDLC над нестисненими даними. Переконайтеся, що ви хешували ті самі байти (а не стиснений потік), той самий режим (текст чи шістнадцяткові) і той самий набір параметрів — рядок параметрів під кожним результатом потрібен, щоб перевірка була миттєвою.
Що краще, CRC-32C чи CRC-32? Для виявлення випадкових помилок обидва ловлять усі сплески до 32 біт; CRC-32C краще працює на деяких шаблонах помилок і має інструкції ЦП — фактично безкоштовний на гігабітних швидкостях. Причина, чому CRC-32/ISO-HDLC виживає, — сумісність: тридцять років архівів ним говорять.
Чи сильніший CRC-64, ніж CRC-32? Він виявляє довші сплески (до 64 біт) і значно рідше дає колізії при розподіленні по кошиках, але підробити його так само легко — ширина дає гарантії виявлення, а не безпеку.
Чи можна обернути CRC, щоб відновити вхідні дані? Ні — нескінченно багато вхідних даних мають однаковий CRC. Але на відміну від криптографічного хешу, зловмисник може побудувати вхідні дані з будь-яким обраним CRC, і саме в цьому сенсі він взагалі не є односторонім.
