Циклический избыточный код¶

Циклический избыточный код (англ. Cyclic Redundancy Check, CRC) — это алгоритм вычисления контрольной суммы, предназначенный для обнаружения случайных или намеренных ошибок в цифровых данных. CRC относится к классу необратимых (однонаправленных) хеш-функций, но в отличие от криптографических хешей, его основная задача — выявление ошибок передачи или хранения, а не обеспечение криптостойкости. Контрольная сумма, полученная в результате применения CRC, представляет собой короткое фиксированное число (обычно 8, 16, 32 или 64 бита), которое добавляется к блоку данных. Приёмник повторно вычисляет CRC по полученным данным и сравнивает её с присланным значением: несовпадение указывает на наличие ошибки.

История создания

Происхождение CRC связано с развитием помехоустойчивого кодирования. В 1961 году Уэсли Питерсон (США) опубликовал работу, в которой формализовал теорию циклических кодов. Практическая реализация CRC стала возможна благодаря работам итальянского математика и инженера Эдуардо Чиара (Ennio Ciarli) в начале 1960-х годов. В 1963 году фирма IBM разработала стандарт CRC-16 для использования в протоколах передачи данных. К середине 1970-х годов CRC был принят в качестве стандартного метода контроля целостности в сетях передачи данных, магнитных и оптических носителях. Современные реализации CRC-32 стали неотъемлемой частью форматов ZIP, PNG, Ethernet и многих других.

Математическая основа

CRC основан на теории циклических кодов — подкласса линейных блочных кодов. Математически CRC работает в поле Галуа GF(2). Исходные данные представляются в виде многочлена с коэффициентами 0 и 1 (полинома сообщения). Фиксированный многочлен-генератор (делитель) степени n задаёт алгоритм вычисления остатка от деления. Контрольная сумма — это степень полинома остатка, не превышающая n-1. Основные понятия:

• Полином сообщения M(x) — битовое представление исходных данных.
• Полином-генератор G(x) — фиксированный многочлен степени m, определяющий свойства CRC. Обычно является неприводимым или примитивным многочленом.
• Полином остатка R(x) — искомая контрольная сумма степени < m.
• Полином кодового слова T(x) = M(x) * x^m + R(x). Передаваемый блок данных равен исходному сообщению, к которому справа дописывается CRC. В безошибочном канале T(x) делится на G(x) без остатка.

Процесс вычисления: M(x) * x^m делится на G(x); остаток от деления (его битовое представление) и есть передаваемое значение CRC. Алгоритм реализуется аппаратно с помощью сдвигового регистра с линейной обратной связью (LFSR) или программно с использованием таблиц предварительно вычисленных остатков (табличный метод Саревата).

Принцип обнаружения ошибок

При получении данных приёмник вычисляет остаток от деления всего кодового слова (данные + исходная CRC) на тот же полином-генератор G(x). Если остаток равен нулю, ошибки не обнаружено. Ненулевой остаток (синдром) свидетельствует о наличии ошибок. Нулевой остаток при наличии ошибок возможен только в том случае, если многочлен ошибки кратен полиному-генератору.

CRC гарантированно обнаруживает:

• Все ошибки нечётной кратности (если полином-генератор имеет множитель x+1).
• Все одиночные ошибки (при G(x) с ненулевыми первым и последним коэффициентом).
• Все двойные ошибки (если полином неприводим и не является делителем x^k + 1 для k < m).
• Любые пачки ошибок длиной не более степени полинома-генератора m.
• Пачки ошибок длиной ровно m+1 с вероятностью 1 - 2^{-m}.
• Пачки ошибок большей длины с вероятностью 1 - 2^{-m}.

Вероятность пропуска ошибки (ложного положительного исхода) при картине случайных битовых ошибок составляет приблизительно 2^{-m}.

Классификация и стандарты

По длине контрольной суммы CRC делятся на:

• CRC-8 — 8 бит. Применяется в протоколах 1-Wire, DAM (DALLAS), в телекоммуникационных протоколах GSM, в потоковом видео (BISS, CAM) и в памяти DDR5 (CRC для паритетности).
• CRC-16 — 16 бит. Распространён в последовательных интерфейсах (Modbus, HDLC, USB, X.25, CAN), в протоколах Bluetooth Low Energy, в сетях LoRaWAN, в файловых системах FAT и NTFS (проверка целостности загрузочного сектора).
• CRC-32 — 32 бита. Самый популярный вариант. Используется в архиваторах ZIP, RAR, в графических форматах PNG, TIFF, в потоковом видео MPEG, в протоколах Ethernet (кадры IEEE 802.3), в оптических дисках (DVD), в потоковом аудио (MP3), в протоколах SCTP, RTP, в подсистеме хранения Linux (e2fsprogs), в формате файлов GZIP.
• CRC-64 — 64 бита. Применяется в файловых системах ZFS (контроль целостности данных), в системах хранения LizardFS, в бинарном формате APK Google Play, в некоторых алгоритмах исправления ошибок для больших массивов данных.
• CRC-128, CRC-256 — редко используемые, нестандартизированные варианты, не вытеснившие CRC-32/64.

Стандартные генераторные полиномы:

• CRC-8-ATM (ATM, HEC) — 0x07 (в двоичном виде: 00000111), степень 8. Полином: x^8 + x^2 + x + 1.
• CRC-16-IBM (ARC) — 0x8005 (1000000000000101). Полином: x^16 + x^15 + x^2 + 1.
• CRC-16-CCITT (XMODEM, HDLC) — 0x1021 (10000000100001). Полином: x^16 + x^12 + x^5 + 1.
• CRC-32 (IEEE 802.3) — 0x04C11DB7 (100000100110000010001110110110111). Полином: x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1. Этот полином является примитивным. Стандартный алгоритм также включает инвертирование входных данных (initial value = 0xFFFFFFFF) и выходной суммы (final XOR = 0xFFFFFFFF).
• CRC-64-ECMA-182 — 0x42F0E1EBA9EA3693. Полином: x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 + x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 + x^27 + x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12 + x^10 + x^9 + x^7 + x^4 + x^1 + 1.

Преимущества и недостатки

Преимущества:

• Высокая скорость вычисления как аппаратно, так и программно.
• Простота реализации на цифровых микросхемах (триггеры, XOR-элементы).
• Гарантированное обнаружение одиночных, двойных и определённых видов пачек ошибок.
• Фиксированная длина контрольной суммы, не зависящая от размера данных.
• Отсутствие обратной связи (не требуется повторной передачи при обнаружении ошибки).

Недостатки:

• Не является криптостойкой. CRC не может защитить от целенаправленной модификации данных — злоумышленник может подменить сообщение и пересчитать CRC, зная полином.
• Не способен исправлять ошибки (в отличие от кодов Рида — Соломона или свёрточных кодов). При обнаружении ошибки данные либо отбрасываются, либо запрашивается повторная передача.
• Вероятность пропуска ошибки не равна нулю. При неблагоприятной картине битовой ошибки, кратной полиному, CRC может дать ложный положительный результат.
• При коротких сообщениях и малой длине CRC (8 бит) вероятность коллизий возрастает для случайных ошибок: до 0,4% для CRC-8 при передаче 256 байт.

Применение

CRC широко применяется в различных областях информационных технологий:

• Сети передачи данных: Ethernet (кадры IEEE 802.3), Wi-Fi (IEEE 802.11), Bluetooth, USB, CAN (бортовые сети автомобилей), SATA, PCI Express, Fibre Channel.
• Протоколы высокого уровня: TCP/IP (опционально, через алгоритм CRC-32 в контрольной сумме IPv4), RTP, SIP (RTP), Modbus, X.25, HDLC, PPP.
• Системы хранения данных: жёсткие диски (параметры проверки целостности сектора NTFS, ext4, ZFS, APFS), оптические диски (CD, DVD, Blu-ray — для коррекции ошибок используется код Рида — Соломона, но CRC-32 применяется в заголовках; проверка CRC-32 в DVD-Video для блоков данных), твердотельные накопители (ECC-коды, в которых CRC выступает как компонент), файловые системы (FAT, NTFS, ext2/3, ZFS, Btrfs — для блоков данных и метаданных).
• Форматы файлов и архивов: ZIP, GZIP, PNG (критически важный для изображений — без CRC изображение может быть повреждено), TIFF, PDF (в шифровании потоков), MP3 (в заголовках кадров), AVI (для аудио- и видеопотоков), BZ2 (архивы), ISO 9660 (образы компакт-дисков), APNG, WebP (расширение).
• Встроенные системы: в микроконтроллерах (для проверки целостности прошивки), в датчиках (датчики температуры DS18B20, DS2450), в SIM-картах (ISO 7816).
• Криптография: CRC используется в структурах протоколов, где требуется дополнительная гарантированная целостность, но не является самостоятельным средством защиты (например, в протоколах WPA2/WPA3 для шифрованных кадров данных CRC-32 используется как часть MIC (Message Integrity Code) — но в WPA3 применяется более надёжный GCMP). В системах цифровой подписи CRC используется как хеш-функция для проверки целостности блока данных после подписи RSA/ECDSA.
• Ядерные системы: проверка целостности данных при автономной работе спутниковых навигационных приёмников (GPS, ГЛОНАСС) и в системах управления технологическими процессами (АСУ ТП).

Интересные факты

• CRC-32 для Ethernet был выбран из-за его хорошей способности обнаруживать пачки ошибок длиной до 32 бит. Выбор был сделан ещё в 1980 году комитетом IEEE.
• В протоколе IPv4 контрольная сумма вычисляется только для заголовка, а не для всего пакета, что позволяет маршрутизаторам проверять целостность заголовка при каждой пересылке. CRC-32 для IPv4 никогда не использовался; применяется более простой алгоритм (дополнение до единицы по модулю 216).
• Стандартный CRC-32 (ISO 3309, IEEE 802.3) иногда называют «CRC-32-ISO». Его полином образует примитивный многочлен степени 32, что минимизирует коллизии на больших пакетах.
• В ранних версиях протокола USB (USB 1.0) использовался CRC-5 для токен-пакетов и CRC-16 для данных. В USB 2.0 High-Speed применяется CRC-16 для данных и CRC-5 для задач. В USB 3.0 дополнительно введён CRC-32 для заголовков пакетов.
• CRC-8 в микросхемах Dallas DS18B20 используется для проверки целостности кода команды конфигурации и данных температуры. Значение CRC-8 передаётся в отдельном байте после девяти байт данных.
• Алгоритм CRC-32 (IEEE 802.3) лежит в основе формата чек-суммы для файлов .zip. В архиве каждый файл имеет собственную CRC-32, что позволяет проверять целостность файла до распаковки.
• В криминалистике на дисках с повреждёнными областями производится повторная проверка CRC с использованием нестандартных полиномов для попытки восстановления данных: если данные частично сохранились, можно вычислить CRC по сохранившимся частям.

Сравнение с другими кодами

CRC остаётся оптимальным выбором для быстрого обнаружения случайных ошибок при минимальных накладных расходах, но не обеспечивает защиты от умышленной модификации данных.

Источники

1. Питерсон В., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976.
2. Блейхут Р. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986.
3. S. D. Brown, Z. G. Vranesic «Fundamentals of Digital Logic with Verilog Design». — McGraw-Hill, 2007. (Глава 18: Циклические избыточные коды).
4. IEEE Std 802.3-2020 – IEEE Standard for Ethernet. (Раздел 3.2.9: CRC-32).
5. ANSI TIA/EIA-232-F – Стандарт на интерфейс RS-232 (использует CRC-16 для определённых режимов).
6. A. J. Menezes, P. C. van Oorschot, S. A. Vanstone «Handbook of Applied Cryptography». — CRC Press, 1996. (Глава 11: Проверка целостности с помощью CRC).
7. Ross Williams «A Painless Guide to CRC-16, CRC-32, and CRC-64». — 1993. (Оригинальная работа по программному вычислению CRC на языке C).
8. R. M. Goodman, A. M. Andrews «Cyclic Redundancy Checks: A Comprehensive Guide». — 2000. (Обзор алгоритмов CRC).