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

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

История

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

В 1961 году Вернер Бухгольц (IBM) предложил циклический избыточный код (CRC), который стал стандартом де-факто для обнаружения ошибок в сетях передачи данных и накопителях. В 1970-х годах, с появлением первых компьютерных сетей (например, ARPANET), возникла необходимость в более надёжных алгоритмах. В 1977 году Рональд Ривест, Ади Шамир и Леонард Адлеман разработали алгоритм MD5 (Message Digest 5), который, хотя и предназначался для криптографических целей, долгое время использовался как контрольная сумма для проверки целостности файлов. В 1990-х годах Национальный институт стандартов и технологий США (NIST) разработал семейство алгоритмов SHA (Secure Hash Algorithm), которые являются криптостойкими хеш-функциями и применяются в современных системах для проверки целостности и аутентификации.

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

Процесс работы с контрольной суммой включает два этапа:

1. Вычисление: На стороне отправителя (или при записи данных) к исходным данным применяется алгоритм, который преобразует их в короткое значение — контрольную сумму. Этот алгоритм является детерминированным: одинаковые входные данные всегда дают одинаковую контрольную сумму.
2. Проверка: Полученные данные (или данные, считанные с носителя) снова обрабатываются тем же алгоритмом. Полученное значение сравнивается с эталонной контрольной суммой. Если значения совпадают, данные считаются неповреждёнными с высокой, но не абсолютной, вероятностью.

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

Классификация и виды

Контрольные суммы можно классифицировать по нескольким признакам.

По назначению

• Обнаружение случайных ошибок: Основная задача. Используются в протоколах передачи данных (TCP/IP, Ethernet), в файловых системах (ZFS, Btrfs), в архиваторах (RAR, ZIP). Примеры: CRC, простые суммы.
• Криптографические хеш-функции: Помимо обнаружения ошибок, обеспечивают устойчивость к целенаправленным подделкам (коллизионная стойкость). Используются для проверки цифровых подписей, паролей, целостности программного обеспечения. Примеры: SHA-256, SHA-3, BLAKE2.
• Контроль целостности в базах данных: Используются для обнаружения неявных изменений данных (например, при репликации). Могут вычисляться как хеш от строки или столбца.

По алгоритму

• Простые арифметические суммы: Суммирование всех байтов или слов данных по модулю 2^n. Очень быстры, но крайне ненадёжны (не обнаруживают перестановки байтов или чётное число одинаковых ошибок).
• Циклические избыточные коды (CRC): Основаны на делении двоичного многочлена, представляющего данные, на фиксированный порождающий многочлен. Остаток от деления и есть контрольная сумма. CRC очень эффективны для обнаружения одиночных, двойных и пакетных ошибок. Широко распространены: CRC-16, CRC-32 (используется в Ethernet, ZIP), CRC-64.
• Криптографические хеш-функции: MD5 (сейчас считается небезопасным для криптографии, но всё ещё используется для проверки целостности), SHA-1 (устарел), SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512), SHA-3, BLAKE2.
• Контрольные суммы на основе контрольных битов: Например, бит чётности (parity bit) — простейший метод, где к каждому байту добавляется один бит, делающий общее количество единиц чётным или нечётным.

Применение

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

В компьютерных сетях и протоколах

• Ethernet: Кадр Ethernet содержит поле Frame Check Sequence (FCS) длиной 4 байта, которое вычисляется по алгоритму CRC-32. Если при передаче произошла ошибка, контрольная сумма не совпадёт, и кадр будет отброшен.
• TCP/IP: Пакеты TCP и UDP содержат контрольные суммы для заголовка и данных. Это позволяет обнаруживать ошибки, возникающие на уровне сети.
• Протоколы передачи файлов (FTP, HTTP): При скачивании файлов часто предоставляется контрольная сумма (например, MD5 или SHA-256) для проверки целостности скачанного файла.

В системах хранения данных

• Файловые системы: Современные файловые системы, такие как ZFS, Btrfs и ReFS, хранят контрольные суммы для каждого блока данных. При чтении данных система автоматически проверяет контрольную сумму и, в случае обнаружения ошибки, может попытаться восстановить данные из резервной копии или с помощью избыточности (RAID).
• Жёсткие диски и SSD: Внутренние алгоритмы коррекции ошибок (ECC) используют сложные коды (например, коды Рида-Соломона), которые не только обнаруживают, но и исправляют ошибки.
• Архиваторы (ZIP, RAR, 7z): При создании архива для каждого файла вычисляется контрольная сумма. При распаковке она проверяется, чтобы убедиться, что файл не повреждён.

В криптографии и безопасности

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

В повседневной жизни

• Номера банковских карт: Последняя цифра номера карты (контрольная цифра) вычисляется по алгоритму Луна. Это позволяет быстро выявить опечатки при вводе номера.
• ISBN (Международный стандартный книжный номер): Последняя цифра ISBN является контрольной суммой, вычисляемой по модулю 11.
• Штрихкоды (EAN-13): Последняя цифра штрихкода также является контрольной суммой, вычисляемой по определённому алгоритму.

Ограничения и критика

• Вероятность коллизии: Ни один алгоритм контрольной суммы не даёт абсолютной гарантии. Существует ненулевая вероятность, что разные наборы данных дадут одинаковую контрольную сумму (коллизия). Для простых сумм и CRC эта вероятность выше, для криптографических хешей — ничтожно мала, но не равна нулю.
• Уязвимость к целенаправленным атакам: Для некриптографических контрольных сумм (например, CRC) злоумышленник может легко подобрать такие искажения данных, которые приведут к той же контрольной сумме. Поэтому CRC непригодны для защиты от намеренных изменений.
• Не исправляют ошибки: Большинство контрольных сумм (кроме кодов коррекции ошибок) только обнаруживают факт наличия ошибки, но не могут указать, где именно она произошла и как её исправить.
• Затраты на вычисление: Вычисление сложных криптографических хешей (SHA-256) требует значительных вычислительных ресурсов, особенно для больших объёмов данных. Для некоторых приложений (например, встраиваемые системы) это может быть критично.

Источники

• Таненбаум Э., Уэзеролл Д. «Компьютерные сети». 5-е изд. — СПб.: Питер, 2012.
• Шнайер Б. «Прикладная криптография». 2-е изд. — М.: Триумф, 2002.
• Кнут Д. «Искусство программирования». Том 2. — М.: Вильямс, 2007.
• RFC 1321 (MD5), RFC 4634 (SHA-2), RFC 3385 (CRC).
• Официальная документация по файловым системам ZFS и Btrfs.