Алгоритм расчета CRC32: как работает контрольная сумма

Ошибка несовпадения контрольной суммы при распаковке архива или передаче файла по сети почти всегда означает, что данные повредились, а проверка целостности выполняется именно алгоритмом CRC32 — циклическим избыточным кодом с 32-битным результатом. Чтобы понять, почему сумма не сошлась, или реализовать проверку в собственной программе, нужно разобраться в математике алгоритма: полиномиальном делении, битовых сдвигах и табличной оптимизации.

В этой статье разберём алгоритм расчета CRC32 по шагам: от теории до готового кода на Python и C. Вы узнаете, какой полином используется в стандарте, зачем нужны начальное значение и финальное инвертирование, и почему разные реализации иногда выдают разные результаты для одних и тех же данных.

Что такое CRC32 и где он применяется

CRC32 (Cyclic Redundancy Check, 32 бита) — это алгоритм вычисления контрольной суммы, основанный на делении двоичного потока данных на фиксированный многочлен в поле GF(2). Результатом всегда является 32-битное число, которое записывается вместе с данными и позволяет обнаружить случайные искажения при хранении или передаче.

Алгоритм встречается повсюду, где требуется быстрая проверка целостности:

• 📦 Архивы ZIP и RAR — каждый сжатый файл сопровождается значением CRC32;
• 🌐 Сетевые протоколы — кадры Ethernet содержат поле FCS, вычисленное именно этим алгоритмом;
• 🖼️ Формат PNG — каждый блок данных защищён контрольной суммой CRC32;
• 💾 Файловые системы и прошивки — проверка целостности образов и загрузчиков.

Важно понимать ограничение: CRC32 — это не криптографический хеш. Он защищает от случайных ошибок, но не от преднамеренной подмены данных — подобрать коллизию для него несложно.

Математическая основа: полиномиальное деление

В основе алгоритма лежит представление данных как многочлена над полем GF(2), где каждый бит — коэффициент (0 или 1). Данные делятся на порождающий полином, и остаток от деления становится контрольной суммой. Деление здесь выполняется без переносов: сложение и вычитание заменяются операцией XOR.

Стандартный полином CRC32, используемый в ZIP, Ethernet и PNG, выглядит так:

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. Однако в большинстве реализаций используется отражённое (reversed) представление полинома — 0xEDB88320, потому что биты обрабатываются начиная с младшего, а не со старшего. Именно это значение вы встретите в коде практически любой библиотеки.

Пошаговый алгоритм расчета CRC32

Побитовый вариант алгоритма прост для понимания, хотя и медленен. Порядок действий таков:

• 🔢 Инициализируйте регистр значением 0xFFFFFFFF — это начальное заполнение (init value);
• 🔁 Для каждого байта данных выполните XOR байта с младшими 8 битами регистра;
• ➡️ Восемь раз сдвиньте регистр вправо: если выдвинутый бит равен 1, дополнительно выполните XOR с полиномом 0xEDB88320;
• ✅ После обработки всех байтов инвертируйте регистр операцией XOR с 0xFFFFFFFF — это финальное значение CRC32.

Именно начальное значение и финальное инвертирование — частые источники ошибок. Если их опустить, результат будет отличаться от эталонного, хотя сам «движок» алгоритма реализован верно.

⚠️ Внимание: существует несколько вариантов CRC32 (стандартный, CRC32C «Castagnoli», CRC32K и другие) с разными полиномами и параметрами. Перед сравнением контрольных сумм убедитесь, что обе стороны используют один и тот же вариант алгоритма.

Табличный метод: ускорение расчета

Побитовая обработка требует 8 итераций на каждый байт, что медленно при больших объёмах. На практике применяется табличный метод: заранее вычисляется таблица из 256 значений — по одному на каждый возможный байт. Тогда обработка байта сводится к одному сдвигу и одному XOR с элементом таблицы.

Таблица строится один раз при инициализации: для каждого значения от 0 до 255 выполняются те же 8 итераций сдвига и XOR с полиномом. Дальнейший расчёт для потока данных выглядит так:

crc = 0xFFFFFFFF
для каждого байта b:
crc = (crc >> 8) ^ table[(crc ^ b) & 0xFF]
crc = crc ^ 0xFFFFFFFF

Такой подход ускоряет вычисление примерно на порядок и является стандартом в библиотечных реализациях. Существуют и более агрессивные оптимизации с таблицами на несколько килобайт, обрабатывающие по 4–8 байт за шаг, но принцип остаётся тем же.

Примеры реализации на Python и C

Ниже — компактная реализация на Python с генерацией таблицы. Она полностью соответствует варианту, который используется в ZIP и PNG:

def make_crc_table():
table = []
for n in range(256):
c = n
for _ in range(8):
c = (c >> 1) ^ 0xEDB88320 if c & 1 else c >> 1
table.append(c)
return table

TABLE = make_crc_table()

def crc32(data: bytes) -> int:
crc = 0xFFFFFFFF
for b in data:
crc = (crc >> 8) ^ TABLE[(crc ^ b) & 0xFF]
return crc ^ 0xFFFFFFFF

Проверка: для строки "123456789" результат должен быть 0xCBF43926
print(hex(crc32(b"123456789")))  # 0xcbf43926

Эквивалент на C выглядит почти так же — логика идентична, меняется только синтаксис:

uint32_t crc32(const uint8_t *data, size_t len) {
uint32_t crc = 0xFFFFFFFF;
for (size_t i = 0; i < len; i++) {
crc ^= data[i];
for (int j = 0; j < 8; j++)
crc = (crc >> 1) ^ (0xEDB88320 & -(crc & 1));
}
return crc ^ 0xFFFFFFFF;
}

Для самопроверки используйте эталонную строку 123456789: корректная реализация стандартного CRC32 обязана выдать 0xCBF43926. Это общепринятое тестовое значение для верификации кода.

Сравнение вариантов CRC32

Под названием «CRC32» скрывается несколько несовместимых между собой алгоритмов. Их параметры сведены в таблицу:

Различия касаются не только полинома: варианты могут отличаться начальным значением, отражением входных и выходных битов и финальным XOR. Поэтому при интеграции с чужой системой всегда уточняйте полный набор параметров алгоритма, а не только его название.

⚠️ Внимание: несовпадение контрольной суммы при обмене данными между двумя системами — типичный признак того, что стороны используют разные варианты CRC32 либо по-разному обрабатывают порядок байт. Сначала сверьте параметры алгоритма, а уже потом ищите повреждения в данных.

Почему CRC32 не подходит для защиты от подделки

Алгоритм линеен: зная CRC сообщения, можно вычислить, какие биты изменить, чтобы сумма осталась прежней. Для защиты от преднамеренной модификации используйте криптографические хеши (SHA-256) или HMAC. CRC32 предназначен только для обнаружения случайных ошибок — шума в канале, сбоев носителя.

Типичные ошибки при реализации

Даже простой алгоритм легко реализовать с ошибкой. Вот что проверять в первую очередь, если результат не совпадает с эталоном:

• 🧭 Перепутано направление обработки битов — используется прямой полином вместо отражённого или наоборот;
• 🔧 Пропущено начальное значение 0xFFFFFFFF или финальное инвертирование;
• 🔀 Проблемы с порядком байт при чтении многобайтовых значений из файла (endianness);
• 📄 В контрольную сумму ошибочно включены служебные байты — заголовки, маркеры конца строки.

Отдельная категория проблем — переполнение при работе с 32-битными значениями в языках без строгой типизации. В Python следите за маскированием & 0xFFFFFFFF там, где это необходимо, а в C используйте тип uint32_t из stdint.h.

Часто задаваемые вопросы

Чем CRC32 отличается от MD5 и SHA?

CRC32 — это контрольная сумма для обнаружения случайных ошибок, она быстрая, но легко поддаётся преднамеренному подбору коллизий. MD5 и SHA — криптографические хеши, устойчивые к подделке, но заметно медленнее. Для проверки целостности при передаче достаточно CRC32, для проверки подлинности нужен криптографический хеш.

Почему моя реализация выдаёт другой результат, чем онлайн-калькулятор?

Наиболее вероятные причины — разные варианты алгоритма (CRC32, CRC32C и другие), отсутствие начального значения или финального XOR, а также скрытые символы во входных данных: перевод строки или BOM-маркер в начале файла изменяют результат.

Что означает значение 0xEDB88320 в коде?

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

Можно ли вычислить CRC32 для большого файла по частям?

Да, алгоритм потоковый: промежуточное значение регистра передаётся от одного блока данных к следующему. Читайте файл порциями и подавайте каждую порцию в функцию, сохраняя текущее значение crc между вызовами. Финальное инвертирование выполняется один раз после последнего блока.

Гарантирует ли совпадение CRC32, что файлы идентичны?

Нет. Совпадение сумм означает лишь высокую вероятность совпадения данных: коллизии возможны, особенно при преднамеренном подборе. Для критичных проверок используйте SHA-256 или сравнение файлов побайтово.