Adler-32

Материал из Википедии — свободной энциклопедии

Adler-32 — хеш-функция, разработанная Марком Адлером. Вычисляет значение контрольной суммы в соответствии с RFC 1950 для массива байт или его фрагмента. Данный алгоритм расчёта контрольной суммы отличается от CRC32 производительностью. Adler-32 используется в библиотеке Zlib.

Содержание

1 Пример имплементации на языке Cи
2 Недостатки алгоритма
3 Adler-32 в других языках программирования
4 Ссылки

[править] Пример имплементации на языке Cи

uint32_t adler32(unsigned char* buf, unsigned int buflength)
  {
     uint32_t s1 = 1;
     uint32_t s2 = 0;
 
     for (unsigned int n=0; n<buflength; n++)
     {
        s1 = (s1 + buf[n]) % 65521; // 65521 - наибольшее [[простое число]] < <math>2^{16}</math>
        s2 = (s2 + s1)     % 65521;
     }
     return (s2 << 16) + s1;
  }

[править] Недостатки алгоритма

«Хорошая» хеш-функция отличается более-менее равномерным распределением вычисленных значений. Очевидно, что Adler-32 не удоволетворяет этому требованию для коротких данных (так как s1 не успевает переполниться). Из-за этого недостатка разработчики протокола SCTP предпочли этому алгоритму CRC32, так как в сетевом протоколе необходимо хеширование коротких последовательностей байт.

Точно как и для CRC32, для Adler-32 можно легко сконструировать коллизию, то есть для данного хеша найти другие исходные данные, имеющие то-же значение функции.