CRC

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

История

Концепция циклических кодов была разработана в 1961 году американским математиком Уэсли Питерсоном в его работе «Error-Correcting Codes». Питерсон описал теорию циклических кодов, которые являются подклассом линейных блоковых кодов. Практическая реализация CRC для обнаружения ошибок в телекоммуникационных системах была предложена в 1975 году в работе «A Cyclic Redundancy Check (CRC) Algorithm» авторов А. С. Танненбаума и Д. В. Уизерспуна.

Первое массовое применение CRC получил в протоколах передачи данных, разработанных Международным консультативным комитетом по телеграфии и телефонии (CCITT, ныне МСЭ-Т). В 1970-х годах CRC-16 и CRC-32 были стандартизированы для использования в синхронных и асинхронных линиях связи. В 1980-х годах CRC стал обязательным компонентом протоколов Ethernet (IEEE 802.3) и Token Ring (IEEE 802.5). С развитием цифровых носителей (CD, DVD, жёсткие диски) CRC вошёл в стандарты коррекции ошибок для этих устройств.

В России CRC используется в соответствии с ГОСТ Р 34.11-2012 (для хеширования) и в ряде отраслевых стандартов, например, в протоколах передачи данных для железнодорожной автоматики и телемеханики (ГОСТ 33343-2015).

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

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

1. К сообщению M(x) дописывается k нулевых битов (сдвиг влево на k разрядов). Получается многочлен M'(x) = M(x) * x^k.
2. Выполняется деление M'(x) на G(x) по модулю 2 (без переносов). Остаток от деления R(x) имеет степень не выше k-1.
3. Контрольная сумма CRC равна двоичному представлению остатка R(x) длиной ровно k бит (при необходимости дополняется нулями слева).
4. При передаче или хранении CRC добавляется к исходному сообщению. Получатель выполняет ту же операцию деления принятого сообщения (включая CRC) на G(x). Если остаток равен нулю — данные считаются корректными; если ненулевой — обнаружена ошибка.

Пример вычисления CRC-3

Пусть сообщение M = 1101 (биты), порождающий многочлен G = 1011 (x^3 + x + 1). Тогда:

• M'(x) = 1101000 (дописаны три нуля).
• Деление M'(x) на G(x): 1101000 ÷ 1011 = 1110 (частное), остаток R = 001.
• CRC = 001.

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

CRC классифицируются по длине контрольной суммы (разрядности) и по используемому порождающему многочлену. Наиболее распространённые варианты:

Параметры реализации

Помимо порождающего многочлена, реализация CRC может включать дополнительные параметры:

• Начальное значение (init) — значение, которое загружается в регистр CRC перед обработкой данных. Обычно равно 0x0000 или 0xFFFF.
• Финальный XOR (xorout) — значение, которое XOR-ится с результатом после завершения вычислений.
• ReflectIn / ReflectOut — флаги, определяющие, нужно ли отражать порядок бит в байте (Little-Endian / Big-Endian) перед обработкой и после неё.

Эти параметры стандартизированы в документах RFC (например, RFC 1662 для PPP) и в спецификациях производителей.

Применение

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

CRC-32 является обязательным компонентом кадра Ethernet (поле FCS — Frame Check Sequence). Каждый кадр Ethernet содержит 4-байтовую контрольную сумму CRC-32, вычисленную по заголовку и полезным данным. Аналогично CRC-32 используется в протоколах IPv4 (для заголовка) и IPv6 (для псевдозаголовка). В протоколе Wi-Fi (IEEE 802.11) CRC-32 применяется для проверки целостности кадра.

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

• Жёсткие диски (ATA/SATA) — каждый сектор (512 байт) содержит 4-байтовую CRC-32 для обнаружения ошибок чтения/записи.
• Оптические диски (CD, DVD, Blu-ray) — CRC используется в сочетании с кодами Рида-Соломона для коррекции ошибок.
• Файловые системы — CRC-64 применяется в файловых системах ZFS и Btrfs для проверки целостности блоков данных и метаданных.

Архиваторы и сжатие

Форматы ZIP, GZip и RAR используют CRC-32 для проверки целостности каждого сжатого файла. При распаковке вычисляется CRC распакованных данных и сравнивается со значением, хранящимся в архиве. Если значения не совпадают — выводится сообщение об ошибке.

Протоколы последовательной передачи

• Modbus RTU — использует CRC-16-IBM.
• CAN bus — использует CRC-15 для кадров данных.
• USB — использует CRC-5 для пакетов и CRC-16 для данных.

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

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

• Высокая скорость вычисления — CRC может быть реализован аппаратно (на регистрах сдвига) или программно с использованием таблиц предвычисленных значений.
• Хорошая обнаруживающая способность — CRC гарантированно обнаруживает:
• Все одиночные битовые ошибки.
• Все двойные ошибки (при длине сообщения менее 2^k).
• Любое нечётное число ошибок (при соответствующем выборе многочлена).
• Все пакетные ошибки длиной до k бит.
• Простота реализации — CRC не требует сложных математических операций, только XOR и сдвиги.

Недостатки

• Не является криптографически стойким — CRC не защищает от преднамеренной подмены данных. Злоумышленник может изменить данные и подобрать новую CRC, так как алгоритм детерминирован и не использует секретный ключ.
• Ограниченная длина сообщения — при очень длинных сообщениях (более 2^k бит) CRC может пропустить некоторые ошибки.
• Чувствительность к параметрам — неправильный выбор порождающего многочлена или начального значения может снизить эффективность обнаружения.

Критика

Основная критика CRC связана с его применением в системах, требующих криптографической защиты. В протоколах, где возможна атака «человек посередине» (MITM), CRC не обеспечивает защиту от подделки. В таких случаях рекомендуется использовать криптографические хеш-функции (SHA-2, SHA-3) или коды аутентичности сообщений (HMAC). Например, в протоколе WPA2 для Wi-Fi используется CCMP (Counter Mode with Cipher Block Chaining Message Authentication Code Protocol), а не CRC.

Также критикуется использование CRC в некоторых российских стандартах для телеметрии и управления, где возможны преднамеренные помехи. В 2020-х годах в России начался переход на криптографические методы контроля целостности в системах критической информационной инфраструктуры (КИИ) в соответствии с требованиями Федерального закона № 187-ФЗ.

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

• CRC-32 (IEEE 802.3) имеет порождающий многочлен 0x04C11DB7, который является примитивным многочленом степени 32. Это обеспечивает максимальную длину цикла для регистра сдвига.
• В протоколе Ethernet CRC-32 вычисляется не по всему кадру, а по данным, начиная с MAC-адреса назначения и заканчивая полем данных. Преамбула и SFD (Start Frame Delimiter) не учитываются.
• Существуют «катастрофические» многочлены, которые приводят к плохой обнаруживающей способности. Например, многочлен x^16 + x^15 + x^2 + 1 (0x8005) для CRC-16-IBM считается неудачным, так как пропускает некоторые пакетные ошибки длиной 2 бита.
• CRC используется в системе контроля целостности прошивок микроконтроллеров (например, в STM32) — при загрузке вычисляется CRC всей прошивки и сравнивается с эталонным значением.
• В языке программирования C стандартная библиотека не включает функцию CRC, но многие реализации (zlib, Boost) предоставляют готовые функции для CRC-32.

Источники

• Peterson, W. W. (1961). Error-Correcting Codes. MIT Press.
• Tanenbaum, A. S. (2010). Computer Networks (5th ed.). Prentice Hall.
• IEEE Std 802.3-2018 — Standard for Ethernet.
• ГОСТ Р 34.11-2012 — Информационная технология. Криптографическая защита информации. Функция хеширования.
• RFC 1662 — PPP in HDLC-like Framing.
• zlib — A Massively Spiffy Yet Delicately Unobtrusive Compression Library (документация по CRC-32).