Adler-32

Wikipedia:Weryfikowalność
Niektóre z zamieszczonych tu informacji od 2025-11 wymagają weryfikacji.
Uwagi: patrz dyskusja.
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.
Adler-32
Rodzaj algorytmu

suma kontrolna

Autorzy

Mark Adler

Wielkość bloku wejściowego

zmienny [bit]

Wielkość bloku wyjściowego

32 bity

Data złamania

2001

Złamany przez

Jonathan Stone

Skuteczne ataki

nieoptymalne wykorzystanie bitów przy krótkich paczkach danych

Adler-32 – suma kontrolna opracowana przez Marka Adlera w oparciu o sumę kontrolną Fletchera. Jest trochę mniej efektywna przy wykrywaniu przypadkowych przekłamań danych w porównaniu do CRC-32, ale za to znacznie szybciej obliczana przez oprogramowanie.

Algorytm

Sumę kontrolną Adler-32 uzyskuje się poprzez obliczenie dwóch 16-bitowych sum kontrolnych A i B oraz poprzez powiązanie ich bitów w 32-bitową liczbę całkowitą. A jest sumą wszystkich bajtów w danym ciągu danych, a B jest sumą indywidualnych wartości zmiennej A z każdego kroku obliczenia.

Na samym początku A jest inicjalizowane jako 1, a B jako 0. Obydwie zmienne sumowane modulo 65521 (największa liczba pierwsza mniejsza od 216). Bajty są w kolejności Big Endian.

Funkcja może być zdefiniowana jako:

 A = 1 + D1 + D2 + ... + Dn (mod 65521)
 B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
   = n×D1 + (n-1)×D2 + (n-2)×D3 + ... + Dn + n (mod 65521)
 Adler-32(D) = B × 65536 + A

gdzie D to ciąg bajtów, dla których jest obliczana suma kontrolna, a n jest długością D.

Przykładowe obliczenie

Suma Alder-32 dla ciągu znaków „Wikipedia” w formacie ASCII jest obliczana następująco:

   Kod ASCII A B
   W: 87 1 + 87 =  88 0 + 88 =   88
   i: 105 88 + 105 = 193 88 + 193 =  281
   k: 107 193 + 107 = 300 281 + 300 =  581
   i: 105 300 + 105 = 405 581 + 405 =  986
   p: 112 405 + 112 = 517 986 + 517 = 1503
   e: 101 517 + 101 = 618 1503 + 618 = 2121
   d: 100 618 + 100 = 718 2121 + 718 = 2839
   i: 105 718 + 105 = 823 2839 + 823 = 3662
   a: 97 823 + 97 = 920 3662 + 920 = 4582
   A = 920  =  398 hex
   B = 4582 = 11E6 hex
   Suma = 11E60398 hex

W tym przykładzie pominięto operację sumy modulo, ponieważ wartość żadnej ze zmiennych nie mogła przekroczyć 65521.

Przykładowa implementacja

Zoptymalizowana implementacja w języku C wygląda następująco:

 #define MOD_ADLER 65521
        uint8_t *data;   /* Pointer to the data to be summed */
        size_t len;      /* Length in bytes */
        uint32_t a = 1, b = 0;

        while (len) {
                unsigned tlen = len > 5550 ? 5550 : len;
                len -= tlen;
                do {
                        a += *data++;
                        b += a;
                } while (--tlen);
                a = (a & 0xffff) + (a >> 16) * (65536-MOD_ADLER);
                b = (b & 0xffff) + (b >> 16) * (65536-MOD_ADLER);
        }
        /* It can be shown that a <= 0x1013a here, so a single subtract will do. */
        if (a >= MOD_ADLER)
                a -= MOD_ADLER;
        /* It can be shown that b can reach 0xffef1 here. */
        b = (b & 0xffff) + (b >> 16) * (65536-MOD_ADLER);
        if (b >= MOD_ADLER)
                b -= MOD_ADLER;
        return (b << 16) | a;

Sztuczki wykorzystane dla zwiększenia wydajności:

Zalety i wady

Krótkie paczki danych

W przypadku krótkich paczek danych sumy cząstkowe nie osiągają magicznej wartości 65521. Na przykład dla paczki 128 bajtów maksymalna wartość sumy cząstkowej A wynosi 32640 i nie jest na niej przeprowadzana operacja modulo. Słabość tę odkrył w 2001 roku Jonathan Stone i opisał ją: „W skrócie, dla krótkich paczek danych Adler-32 nie gwarantuje optymalnego wykorzystania dostępnych bitów. Nie wierzcie mi na słowo, zapytajcie Marka Adlera. :-)”. Dokładny opis problemu można znaleźć w specyfikacji RFC 3309, która wymaga używania CRC-32 dla SCTP -- Stream Control Transmission Protocol.

Zobacz też

Linki zewnętrzne