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

Контрольная сумма Adler-32 — это алгоритм вычисления контрольной суммы, используемый для обнаружения случайных или намеренных изменений в данных. Относится к классу хеш-функций (некриптографических). Разработана Марком Адлером в 1995 году как более быстрая альтернатива контрольной сумме Fletcher-32, с улучшенными свойствами обнаружения ошибок, но с меньшей вычислительной сложностью, чем CRC (циклический избыточный код). Широко применяется в протоколах сжатия данных (zlib, gzip) и в сетевых протоколах (например, в реализации протокола PPP).

История

Алгоритм Adler-32 был предложен Марком Адлером, сотрудником компании Info-ZIP, в 1995 году. Первоначально он был разработан для использования в библиотеке сжатия zlib (созданной Жан-Лу Гайи и Марком Адлером). Целью было создание алгоритма, который был бы значительно быстрее CRC-32 (который требует битовых операций и таблиц подстановки) и при этом обеспечивал бы приемлемую вероятность обнаружения ошибок. Adler-32 основывается на идее контрольных сумм Fletcher, но с модификацией, повышающей чувствительность к определённым типам ошибок (например, к вставке или удалению нулевых байтов). Алгоритм был стандартизирован в RFC 1950 (zlib compressed data format specification) и RFC 1951 (DEFLATE compressed data format specification).

Алгоритм работы

Adler-32 вычисляет 32-битное значение, которое является суммой двух 16-битных контрольных сумм: A и B. Обе суммы вычисляются по модулю 65521 (наибольшее простое число, меньшее 2^16). Выбор простого числа 65521, а не 65536 (2^16), как в Fletcher-32, повышает чувствительность к ошибкам, связанным с перестановками байтов.

Формула

Пусть входные данные представлены как последовательность байтов D[1], D[2], ..., D[n] (где каждый байт — целое число от 0 до 255). Алгоритм начинается с инициализации:

• A = 1
• B = 0

Затем для каждого байта D[i] выполняются следующие шаги:

1. A = (A + D[i]) mod 65521
2. B = (B + A) mod 65521

После обработки всех байтов контрольная сумма Adler-32 вычисляется как:

• Adler-32 = B * 65536 + A

То есть старшие 16 бит (биты 31..16) содержат значение B, а младшие 16 бит (биты 15..0) — значение A.

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

Для строки ASCII «Wikipedia» (байты: 87, 105, 107, 105, 112, 101, 100, 105, 97):

1. Начальные значения: A=1, B=0.
2. После первого байта (87): A=1+87=88, B=0+88=88.
3. После второго (105): A=88+105=193, B=88+193=281.
4. После третьего (107): A=193+107=300, B=281+300=581.
5. После четвёртого (105): A=300+105=405, B=581+405=986.
6. После пятого (112): A=405+112=517, B=986+517=1503.
7. После шестого (101): A=517+101=618, B=1503+618=2121.
8. После седьмого (100): A=618+100=718, B=2121+718=2839.
9. После восьмого (105): A=718+105=823, B=2839+823=3662.
10. После девятого (97): A=823+97=920, B=3662+920=4582.
11. Итоговая контрольная сумма: 4582 * 65536 + 920 = 300286872 + 920 = 300287792 (в десятичной системе). В шестнадцатеричной системе: 0x11E60398.

Свойства

Сильные стороны

• Высокая скорость вычисления: Алгоритм использует только операции сложения и взятия модуля, что делает его значительно быстрее CRC-32 на процессорах без аппаратной поддержки CRC.
• Простота реализации: Требует минимального объёма кода и не использует таблицы подстановки.
• Хорошая чувствительность к ошибкам: Обнаруживает большинство однобитовых ошибок, а также многие двухбитовые и пакетные ошибки, хотя и уступает CRC-32 по вероятности обнаружения.

Слабые стороны

• Не является криптографически стойким: Легко поддаётся коллизиям (два разных набора данных могут дать одинаковую контрольную сумму). Не предназначен для защиты от злонамеренных изменений.
• Чувствительность к порядку байтов: Как и большинство контрольных сумм, Adler-32 зависит от порядка байтов во входных данных.
• Ограниченная длина данных: При очень длинных последовательностях (более 4 ГБ) возможны переполнения, если не использовать промежуточные операции по модулю.

Применение

Adler-32 используется в следующих областях:

• Сжатие данных: В библиотеке zlib и форматах gzip, PNG (Portable Network Graphics) для проверки целостности сжатых блоков данных. В формате PNG контрольная сумма Adler-32 вычисляется для сжатых данных (после применения алгоритма Deflate).
• Сетевые протоколы: В протоколе PPP (Point-to-Point Protocol) для проверки целостности кадров (как альтернатива CRC-16/32).
• Проверка целостности файлов: В некоторых утилитах (например, cksum в Unix-подобных системах) может использоваться для быстрой проверки изменений в файлах, хотя чаще применяется CRC-32 или MD5.
• Компьютерные игры: В некоторых игровых движках (например, в ранних версиях Quake) для быстрой проверки целостности игровых ресурсов.

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

Критика

Основной недостаток Adler-32 — его уязвимость к коллизиям при злонамеренных модификациях. В отличие от CRC-32, который использует полиномиальное деление, Adler-32 основан на простом сложении, что делает его легко предсказуемым. Для задач, где требуется защита от намеренных искажений (например, в криптографии или цифровых подписях), Adler-32 непригоден. Кроме того, при обработке данных, содержащих длинные последовательности нулевых байтов, алгоритм может давать одинаковые значения для разных наборов данных (например, строка из 100 нулевых байтов даёт ту же сумму, что и строка из 200 нулевых байтов, если модуль не переполняется).

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

• Название «Adler-32» происходит от фамилии автора и длины контрольной суммы (32 бита). Существует также вариант Adler-16, который вычисляет 16-битную сумму, но он используется редко.
• В библиотеке zlib для ускорения вычислений используется оптимизация: вместо взятия модуля на каждом шаге (что дорого), операция выполняется только после накопления определённого количества байтов (обычно 5552 байта, чтобы избежать переполнения 32-битного целого числа).
• Алгоритм Adler-32 не является патентованным и свободно используется в любых проектах, включая коммерческие.

Источники

• RFC 1950 — ZLIB Compressed Data Format Specification (IETF, 1996).
• RFC 1951 — DEFLATE Compressed Data Format Specification (IETF, 1996).
• Марк Адлер, «Adler-32 — A New Checksum Algorithm», 1995.
• Документация библиотеки zlib (zlib.net).
• Стандарт PNG (ISO/IEC 15948:2004).