Алгоритм вычисления контрольной суммы¶

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

¶История

Потребность в контроле целостности данных возникла с появлением первых систем передачи информации. В телеграфии и ранних компьютерных сетях использовались простейшие методы, такие как бит чётности. В 1940-х годах Ричард Хэмминг разработал код Хэмминга, позволяющий не только обнаруживать, но и исправлять одиночные ошибки. В 1961 году Вернер Бухгольц предложил циклический избыточный код (CRC), который стал одним из наиболее распространённых алгоритмов контрольной суммы. С развитием интернета и протоколов передачи данных (TCP/IP, Ethernet) появились более сложные алгоритмы, такие как MD5 (1992) и SHA-1 (1995), которые, хотя и изначально разрабатывались как криптографические хеш-функции, часто используются для проверки целостности файлов. В XXI веке, в связи с обнаружением уязвимостей в MD5 и SHA-1, их применение в качестве контрольных сумм для критически важных данных сокращается, уступая место алгоритмам семейства SHA-2 и SHA-3.

¶Классификация алгоритмов

Алгоритмы вычисления контрольной суммы можно разделить на несколько категорий по сложности, области применения и устойчивости к коллизиям.

¶Простейшие алгоритмы

• Бит чётности (Parity bit) — самый простой метод. Для каждого блока данных (например, байта) вычисляется дополнительный бит, который делает общее количество единиц в блоке чётным или нечётным. Позволяет обнаружить только нечётное количество ошибок.
• Контрольная сумма по модулю (Checksum) — данные суммируются как целые числа, и результат берётся по модулю некоторого числа (например, 256). Используется в протоколах TCP и UDP (Internet Checksum). Обнаруживает большинство одиночных ошибок, но неэффективен против перестановок байтов.
• Сложение с дополнением до единицы (One's complement sum) — модификация предыдущего метода, применяемая в IP-заголовках. Даёт лучшую защиту от ошибок, чем простое сложение.

¶Циклические избыточные коды (CRC)

CRC (Cyclic Redundancy Check) — это семейство алгоритмов, основанных на делении двоичного полинома, представляющего данные, на фиксированный порождающий полином. Остаток от деления и является контрольной суммой. CRC широко применяются в цифровых сетях (Ethernet, USB, Bluetooth), устройствах хранения данных (жёсткие диски, CD/DVD) и архиваторах. Основные характеристики:

• Длина полинома — определяет разрядность контрольной суммы (например, CRC-8, CRC-16, CRC-32, CRC-64).
• Порождающий полином — фиксированное двоичное число, от которого зависит эффективность алгоритма.
• Обнаруживающая способность — CRC-32, например, гарантированно обнаруживает все одиночные, двойные и пакетные ошибки длиной до 32 бит.

¶Криптографические хеш-функции

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

• MD5 (Message Digest 5) — выдаёт 128-битный хеш. В настоящее время считается уязвимым для коллизий и не рекомендуется для использования в системах, требующих криптостойкости.
• SHA-1 (Secure Hash Algorithm 1) — выдаёт 160-битный хеш. С 2017 года считается устаревшим и небезопасным для криптографических целей.
• SHA-2 (SHA-256, SHA-512) — семейство алгоритмов, выдающих хеши длиной 224, 256, 384 или 512 бит. Является текущим стандартом для большинства приложений.
• SHA-3 — новейшее семейство, разработанное в 2015 году, основанное на алгоритме Keccak. Обеспечивает высокую устойчивость к атакам.

¶Специализированные алгоритмы

• Адлер-32 — используется в протоколе zlib и в потоковых архиваторах. Быстрее CRC-32, но менее надёжен.
• Fletcher-16/32 — применяется в протоколах UDP-Lite и в некоторых протоколах промышленной автоматизации. Обладает лучшей обнаруживающей способностью, чем простое сложение.

¶Принцип работы (на примере CRC-32)

Алгоритм CRC-32, один из самых распространённых, работает следующим образом:

1. Инициализация: Регистр (обычно 32-битный) заполняется начальным значением (часто 0xFFFFFFFF).
2. Обработка данных: Каждый байт входных данных последовательно обрабатывается. Байт объединяется с текущим значением регистра с помощью операции XOR (исключающее ИЛИ).
3. Деление на полином: Результат XOR сдвигается влево, и, если старший бит стал равен 1, выполняется XOR с порождающим полиномом (например, 0x04C11DB7 для CRC-32). Этот процесс повторяется для каждого бита в байте (или для байта целиком, если используется табличный метод).
4. Финализация: После обработки всех данных выполняется операция XOR с конечным значением (часто 0xFFFFFFFF), и полученное число является контрольной суммой.

Для повышения скорости вычислений CRC часто реализуется с помощью таблиц предварительно вычисленных значений (табличный метод), что позволяет обрабатывать данные по байтам или словам, а не по битам.

¶Применение

¶Передача данных

• Сетевые протоколы: Ethernet (CRC-32), TCP (Internet Checksum), Wi-Fi (CRC-32).
• Беспроводная связь: Bluetooth, Zigbee, LoRaWAN.
• Цифровое телевидение и радиовещание: DVB, ATSC.

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

• Файловые системы: NTFS, ext4, Btrfs (используют CRC для метаданных и данных).
• Архиваторы: ZIP, RAR, 7z (хранят CRC-32 для каждого файла).
• Образы дисков: ISO, BIN/CUE.
• Носители информации: CD/DVD (CRC-32 для каждого сектора), жёсткие диски (CRC для каждого сектора).

¶Программное обеспечение

• Проверка целостности загрузочных файлов: Дистрибутивы Linux, Windows, macOS часто предоставляют MD5, SHA-1 или SHA-256 суммы для скачиваемых образов.
• Системы контроля версий: Git использует SHA-1 для идентификации коммитов.
• Базы данных: Контрольные суммы для проверки целостности страниц данных (например, в PostgreSQL, MySQL).

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

• Цифровые подписи: Хеш-функции (SHA-256) используются для создания дайджеста сообщения перед подписанием.
• Пароли: Хеширование паролей (с солью) для хранения в базах данных.
• Блокчейн: Каждый блок содержит хеш предыдущего блока (SHA-256 в Bitcoin).

¶Примеры

¶Критика и ограничения

• Неустойчивость к коллизиям: Простые алгоритмы (CRC, Internet Checksum) не гарантируют уникальности контрольной суммы для разных данных. Злоумышленник может целенаправленно подобрать данные с той же контрольной суммой. Для защиты от подделки необходимо использовать криптографические хеш-функции и цифровые подписи.
• Устаревание криптоалгоритмов: MD5 и SHA-1 признаны небезопасными для криптографических целей, хотя для простой проверки целостности (без атак) они могут быть приемлемы.
• Производительность: Криптографические хеш-функции (SHA-2, SHA-3) требуют значительно больше вычислительных ресурсов, чем CRC или простые суммы. В высокоскоростных сетях или на встраиваемых устройствах это может быть критично.
• Ограниченная обнаружение: Ни один алгоритм не гарантирует обнаружение 100% ошибок. Например, CRC-32 не обнаружит ошибку, если она преобразует данные в другое сообщение с тем же остатком от деления.

¶Источники

• Таненбаум Э., Уэзеролл Д. «Компьютерные сети». 5-е изд. — СПб.: Питер, 2012.
• Шнайер Б. «Прикладная криптография». 2-е изд. — М.: Триумф, 2002.
• RFC 1071: «Computing the Internet Checksum».
• RFC 3385: «Internet Protocol Small Computer System Interface (iSCSI) CRC Considerations».
• ISO 3309: «High-level data link control (HDLC) — Frame structure».
• ГОСТ Р 34.11-2012 «Информационная технология. Криптографическая защита информации. Функция хеширования».