Контрольная сумма CRC

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

История

Концепция циклических кодов была разработана в 1961 году американским математиком У. Уэсли Питерсоном (W. Wesley Peterson) в статье «Cyclic Codes for Error Detection». Питерсон предложил использовать полиномиальное деление для обнаружения ошибок в двоичных последовательностях. В 1960-х годах CRC был стандартизирован для использования в телекоммуникациях и компьютерных сетях. В 1975 году Национальное бюро стандартов США (ныне NIST) опубликовало спецификацию CRC-16 для протокола HDLC. В 1980-х годах CRC стал обязательным компонентом протокола Ethernet (IEEE 802.3), где используется 32-битная версия CRC-32. В 1990-е годы алгоритм был адаптирован для контроля целостности данных в файловых системах (например, в ZIP-архивах) и в цифровых носителях (CD-ROM, DVD). В 2000-х годах появились более быстрые реализации CRC, включая аппаратные модули в процессорах (например, инструкция crc32 в архитектуре x86-64).

Принцип работы

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

CRC основан на арифметике многочленов над полем GF(2) (двоичное поле без переносов). Исходное сообщение представляется в виде двоичного многочлена M(x) степени n-1, где n — длина сообщения в битах. Порождающий полином G(x) степени k (k — разрядность CRC) выбирается заранее. Алгоритм вычисления включает следующие шаги:

1. Сообщение M(x) умножается на x^k (добавляется k нулевых битов).
2. Результат делится на G(x) по модулю 2 (операция XOR).
3. Остаток R(x) степени k-1 является контрольной суммой CRC.
4. CRC добавляется к исходному сообщению: передаётся M(x) * x^k + R(x).

При проверке принятое сообщение делится на G(x) без остатка, если ошибок нет. Если остаток ненулевой, фиксируется ошибка.

Порождающие полиномы

Выбор порождающего полинома определяет детектирующие свойства CRC. Наиболее распространённые полиномы:

• CRC-8: x^8 + x^2 + x + 1 (0x07) — используется в датчиках, 1-Wire.
• CRC-16: x^16 + x^15 + x^2 + 1 (0x8005) — применяется в протоколах Modbus, USB.
• CRC-32: 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 (0x04C11DB7) — стандарт для Ethernet, ZIP, PNG.
• CRC-64: x^64 + x^4 + x^3 + x + 1 (0x1B) — используется в файловых системах (ZFS, ext4).

Реализация

Алгоритм CRC может быть реализован программно (с использованием таблиц предвычисленных значений для ускорения) или аппаратно (в виде сдвигового регистра с обратной связью, LFSR). Программная реализация обычно использует табличный метод, где для каждого байта данных выполняется XOR с табличным значением, что снижает вычислительную сложность до O(n) операций.

Классификация

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

• 8-битные CRC: CRC-8, CRC-8/ATM, CRC-8/MAXIM — для коротких пакетов (до 256 байт).
• 16-битные CRC: CRC-16, CRC-16/CCITT, CRC-16/IBM — для средних пакетов (до 4 Кбайт).
• 32-битные CRC: CRC-32, CRC-32/C, CRC-32/BZIP2 — для больших объёмов данных (до 1 Гбайт).
• 64-битные CRC: CRC-64, CRC-64/ECMA — для сверхбольших массивов (файловые системы, архивы).

По стандартизации

• Международные стандарты: ISO 3309, ITU-T V.42, IEEE 802.3.
• Промышленные стандарты: Modbus, CAN bus, USB.
• Специфические реализации: CRC-32/MPEG-2, CRC-32/ISO-HDLC.

По способу реализации

• Программные: табличные, битовые, с использованием аппаратных инструкций.
• Аппаратные: встроенные модули в микроконтроллерах, FPGA, сетевых картах.

Применение

Сетевые протоколы

• Ethernet: кадр Ethernet содержит 32-битную CRC-32 в поле FCS (Frame Check Sequence). Ошибка в CRC приводит к отбрасыванию кадра.
• Wi-Fi (IEEE 802.11): используется CRC-32 для проверки целостности заголовка и данных.
• TCP/IP: в протоколе TCP контрольная сумма вычисляется по алгоритму, отличному от CRC (дополнение до единицы), но в IP-пакетах используется CRC-16 для заголовка.
• USB: в пакетах данных применяется CRC-5 для токенов и CRC-16 для данных.

Хранение данных

• Жёсткие диски: в секторах используется CRC-16 или CRC-32 для обнаружения ошибок чтения/записи.
• Оптические диски: CD-ROM использует CRC-32, DVD — CRC-32 с дополнительным кодом Рида-Соломона.
• Файловые системы: ZFS (Zettabyte File System) применяет CRC-64 для проверки целостности блоков данных; ext4 использует CRC-32 для журнала.
• Архиваторы: ZIP, RAR, GZip используют CRC-32 для проверки целостности сжатых данных.

Цифровые коммуникации

• CAN bus: в автомобильной электронике используется CRC-15 для кадров данных.
• Bluetooth: в пакетах применяется CRC-16.
• RS-232: в протоколах Modbus RTU используется CRC-16/Modbus.

Криптография и безопасность

CRC не является криптографической хеш-функцией и не защищает от преднамеренных изменений (легко подделывается). Однако в некоторых системах CRC используется как дополнительная проверка целостности в сочетании с криптографическими методами (например, в протоколах TLS — для проверки целостности заголовков).

Характеристики

Детектирующие способности

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

• Все однобитовые ошибки (при условии, что порождающий полином содержит более одного ненулевого члена).
• Все двубитовые ошибки, если полином имеет степень не менее 2.
• Все ошибки нечётной кратности, если полином является произведением (x+1) на другой полином.
• Все пакетные ошибки длиной до k бит (k — степень полинома).
• Большинство пакетных ошибок длиной более k бит (вероятность необнаружения ≈ 2^(-k)).

Вероятность коллизии

Для CRC-32 вероятность необнаружения случайной ошибки составляет примерно 2^(-32) ≈ 2,3×10^(-10). Для CRC-64 — 2^(-64) ≈ 5,4×10^(-20). На практике это означает, что CRC-32 достаточен для большинства приложений, но для критических систем (например, в авионике или ядерной энергетике) используются более длинные варианты.

Ограничения

• CRC не обнаруживает ошибки, если порождающий полином делит многочлен ошибки (например, если ошибка кратна полиному).
• CRC не защищает от преднамеренных атак — злоумышленник может легко вычислить корректную CRC для изменённых данных.
• CRC не исправляет ошибки (в отличие от кодов Рида-Соломона или свёрточных кодов).

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

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

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

• В 1990-х годах в протоколе Ethernet использовалась CRC-32, которая была оптимизирована для аппаратной реализации на основе сдвиговых регистров.
• В 2000-х годах в процессорах Intel (начиная с архитектуры Nehalem) была добавлена аппаратная инструкция crc32, ускоряющая вычисление CRC-32C (Castagnoli) — варианта, используемого в протоколах iSCSI и SCTP.
• CRC-32 используется в формате PNG для проверки целостности каждого чанка (блока данных).
• В файловой системе ZFS (Zettabyte File System) CRC-64 применяется для каждого блока данных, что позволяет обнаруживать «тихое» повреждение данных (bit rot).
• CRC-16/CCITT (0x1021) является стандартом для протокола X.25 и используется в спутниковой связи.
• В 2013 году была обнаружена уязвимость в реализации CRC-32 в протоколе WPA2, позволяющая злоумышленнику подделывать пакеты (атака «CRC-32 collision»).

Источники

• Peterson, W. W. (1961). «Cyclic Codes for Error Detection». Proceedings of the IRE, 49(1), 228–235.
• IEEE Standard 802.3-2018 — «Standard for Ethernet».
• ITU-T Recommendation V.42 — «Error-correcting procedures for DCEs using asynchronous-to-synchronous conversion».
• Tanenbaum, A. S. (2011). Computer Networks (5th ed.). Prentice Hall.
• Press, W. H., Teukolsky, S. A., Vetterling, W. T., & Flannery, B. P. (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press.
• Спецификация CRC-32 в формате PNG (ISO/IEC 15948:2003).