CRC Перевірки: Виловлювання Помилок За Допомогою Поліномного Ділення

Розглядайте ваше повідомлення як поліном

CRC (перевірка циклічної редундантності) не додає біти — вона виконує ділення многочлена над GF(2), двохелементним полем, де додавання є XOR і немає переносу. Біти повідомлення стають коефіцієнтами біноміального полінома M(x), а відправник ділить його на фіксований генераторний поліном G(x), узгоджений заздалегідь, зберігаючи лише залишок як контрольний сумарійний код:

передано = M(x) * x^r XOR залишок, де залишок = [M(x)*x^r] mod G(x) приймач перераховує те саме ділення на отримані біти; залишок ≠ 0 → виявлено помилку жива демонстрація · оберіть CRC-8/16/32, переверніть біт, подивіться, як він буде виловлений● LIVE r – це степінь G(x) – 8, 16 або 32 для типових налаштувань — і вся ця хитрість працює тому, що ділення на основі XOR розподіляється над додаванням: залишок пошкодженого повідомлення дорівнює залишку від оригінального повідомлення XOR залишку від шаблону помилок само по собі. Це означає, що потужність виявлення помилок CRC повністю залежить від того, які шаблони помилок G(x) випадково ділять без залишку — якщо це не так, то помилки можуть прослиснути непоміченими; обираючи його правильно, конкретні класи помилок виявляються з абсолютною впевненістю.

transmitted = M(x) · x^r  XOR  remainder,  where remainder = [M(x)·x^r] mod G(x)
receiver recomputes the same division on the received bits;
remainder != 0  ⇒  error detected

Чому CRC-32 надійно виявляє помилки послідовного типу

Генераторний поліном степені r гарантує виявлення будь-якої помилки послідовного типу довжиною ≤ r — це називається помилкою послідовного типу, коли помилка обмежена r або меншою кількістю поспіль розташованих бітів. Це точно відповідає шаблону шуму, який створюють подряпані диски, слабкий радіоканал або пошкоджений комір пам'яті. CRC-32, що лежить в основі кадрів Ethernet, файлів PNG/zip та більшості систем зберігання даних, тому надійно виявляє всі помилки послідовного типу довжиною до 32 біт з певністю, а також однобітові та двоелементні помилки (якщо G(x) обрано таким чином, щоб не містив множника (x+1)), а також будь-яку непарну кількість бітових помилок, коли G(x) містить множник (x+1). Однак воно не може гарантувати виявлення кожної можливої ​​довшої або спеціально створеної схеми пошкодження даних – якщо пошкодження випадково є точним кратним G(x), залишок дорівнює нулю, і воно проходить непомітно.

CRC не є криптографічно безпечним

Оскільки CRC лінійний у GF(2), нападник, який може перевернути біти, може точно обчислити, які додаткові біти потрібно перевернути, щоб залишити контрольні суми незмінними — це розрахунок з двома рядками, а не грубий пошук. Таким чином, CRC захищає лише від випадкового шуму, але не від навмисного супротивника; TLS, підписання коду та зберігання паролів використовують SHA-2/SHA-3 або HMAC, які розроблені таким чином, що жоден ефективний алгоритм не може знайти друге повідомлення з відповідним хешем. Плутанина між цими двома є реальною та поширеною помилкою безпеки — CRC-32 у мережевому протоколі є перевіркою цілісності проти шуму передачі, а не автентифікацією.

Три загальні попередні налаштування

CRC-8 (SMBus) G(x) = x^8 + x^2 + x + 1 8-бітний контроль, наприклад, шини датчиків CRC-16 (CCITT) G(x) = x^16 + x^12 + x^5 + 1 16-бітний, наприклад, Bluetooth, XMODEM CRC-32 (IEEE 802.3) G(x)= x^32+x^26+x^23+...+x^2+x+1 (0xEDB88320) 32-бітний, наприклад, Ethernet, zip, PNG Усі три реалізовані однаково апаратно та програмно: переміщають повідомлення через лінійну-зворотну ширму, з’єднану відповідно до коефіцієнтів G(x), або – значно швидше – попередньо обчислюють таблицю пошуку з 256 записів, щоб кожен байт коштував одного пошуку в таблиці та одного XOR замість восьми кроків переміщення та XOR. Кожна сучасна мережева карта та контролер зберігання обчислює CRC-32 у окремому кремнії, оскільки операція відбувається для кожного окремого кадру або сектора, що проходить через нього.

CRC-8   (SMBus)     G(x) = x^8  + x^2 + x  + 1                    8-bit check, e.g. sensor buses
CRC-16  (CCITT)     G(x) = x^16 + x^12 + x^5 + 1                  16-bit, e.g. Bluetooth, XMODEM
CRC-32  (IEEE 802.3) G(x)= x^32+x^26+x^23+...+x^2+x+1 (0xEDB88320) 32-bit, e.g. Ethernet, zip, PNG

Виявлення, а не виправлення

Залишок CRC повідомляє вам лише про те, що відбулося зміна, але ніколи не вказує, що саме змінилося або де. Неможливо обернути ділення та відновити оригінальні біти лише на основі ненульового залишку. Це свідомий компроміс: CRC використовує лише *r* додаткових біт для захисту будь-якого довжини повідомлення, тоді як код корекції помилок, такий як Reed-Solomon або Hamming code, потребує пропорційно більшої надмірності для також визначення та виправлення пошкоджених бітів.

У практичному застосуванні ці два методи часто комбінуються – Ethernet використовує CRC-32 лише для виявлення пошкодженого кадру та просто запитує повторний відправлення, замість того, щоб намагатися виправити його безпосередньо.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте CRC Checksum і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.