Введение

Adler 32 — это алгоритм контрольной суммы, разработанный Марком Адлером в 1995 году на основе алгоритма Флетчера. По сравнению с циклической проверкой избыточности той же длины, он обеспечивает более высокую скорость за счет некоторой потери надежности. Adler 32 надежнее, чем Fletcher 16, но немного менее надежен, чем Fletcher 32.

История

Контрольная сумма Адлера-32 является частью широко используемой библиотеки сжатия zlib, так как обе были разработаны Марком Адлером. В утилите rsync используется версия Адлера-32 с вычисляемой "на лету" контрольной суммой.

Сравнение с контрольной суммой Флетчера

Первое различие между двумя алгоритмами заключается в том, что суммы Адлера 32 вычисляются по модулю простого числа, в то время как суммы Флетчера вычисляются по модулю 24−1, 28−1 или 216−1 (в зависимости от количества используемых бит), которые все являются составными числами. Использование простого числа позволяет алгоритму Адлера 32 обнаруживать различия в определенных комбинациях байтов, которые алгоритм Флетчера не может выявить. Второе различие, оказывающее наибольшее влияние на скорость работы алгоритма, состоит в том, что суммы Адлера вычисляются для 8-битных байтов, а не для 16-битных слов, что приводит к удвоению количества итераций цикла. В результате вычисление контрольной суммы Адлера 32 занимает от полутора до двух раз больше времени, чем вычисление контрольной суммы Флетчера для 16-битных выровненных данных. Для байтово-выровненных данных алгоритм Адлера 32 работает быстрее, чем правильно реализованный алгоритм Флетчера (например, используемый в Иерархическом формате данных).

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

Как и стандартный CRC 32, контрольная сумма Adler 32 легко поддается подделке и поэтому не подходит для защиты от намеренных изменений. Она быстрее, чем CRC 32, на многих платформах. Adler 32 уязвим для коротких сообщений объемом в несколько сотен байт, поскольку контрольные суммы для таких сообщений недостаточно полно используют все 32 доступных бита.

Слабость

Адлер 32 недостаточно надежен для коротких сообщений, поскольку сумма A не переполняется. Максимальная сумма для сообщения размером 128 байт составляет 32640, что меньше значения 65521, используемого в операции взятия по модулю, что означает, что примерно половина выходного пространства остается неиспользованной, а распределение в используемой части неравномерно. Более подробное объяснение можно найти в , где предписывается использовать CRC32C вместо Adler 32 для SCTP – протокола управления потоком передачи. Также было показано, что Adler 32 уязвим к небольшим инкрементным изменениям, а также к строкам, сгенерированным из общего префикса и последовательных чисел (например, автоматически генерируемым именам меток типичными генераторами кода).