Adler-32 - Adler-32

Adler-32 je kontrolní součet algoritmus který napsal Mark Adler v roce 1995,[1] a je modifikací Fletcherův kontrolní součet. Ve srovnání s a kontrola cyklické redundance stejné délky, vyměňuje spolehlivost za rychlost (upřednostňuje druhou). Adler-32 je spolehlivější než Fletcher-16, a o něco méně spolehlivý než Fletcher-32.[2]

Dějiny

Kontrolní součet Adler-32 je součástí široce používaného zlib kompresní knihovna, protože obě byly vyvinuty Mark Adler.A "průběžný kontrolní součet "verze Adler-32 se používá v rsync nástroj.

Algoritmus

Kontrolní součet Adler-32 se získá výpočtem dvou 16-bit kontrolní součty A a B a zřetězení jejich bitů na 32bitové celé číslo. A je součet všech bajtů v proudu plus jedna a B je součet jednotlivých hodnot A z každého kroku.

Na začátku běhu Adler-32 A je inicializován na 1, B do 0. Součty jsou hotové modulo 65521 (největší prvočíslo menší než 216). Bajty jsou uloženy v síťovém pořadí (velký endian ), B zabírá dva nejvýznamnější bajty.

Funkce může být vyjádřena 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

kde D je řetězec bajtů, pro který se má vypočítat kontrolní součet, a n je délka D.

Příklad

Součet Adler-32 ASCII tětiva "Wikipedia"by se počítalo takto:

CharakterASCII kódAB
(zobrazeno jako základ 10)
Ž871 +87 =880 +88 =88
i10588 +105 =19388 +193 =281
k107193 +107 =300281 +300 =581
i105300 +105 =405581 +405 =986
str112405 +112 =517986 +517 =1503
E101517 +101 =6181503 +618 =2121
d100618 +100 =7182121 +718 =2839
i105718 +105 =8232839 +823 =3662
A97823 +97 =9203662 +920 =4582
A = 920 = 0x398 (základ 16) B = 4582 = 0x11E6 Výstup = 0x11E6 << 16 + 0x398 = 0x11E60398

Provoz modulo neměl v tomto příkladu žádný účinek, protože žádná z hodnot nedosáhla 65521.

Srovnání s kontrolním součtem Fletcher

První rozdíl mezi těmito dvěma algoritmy spočívá v tom, že součty Adler-32 se počítají modulo prvočíslo, zatímco Fletcherovy součty se počítají modulo 24−1, 28-1 nebo 216−1 (v závislosti na počtu použitých bitů), které jsou všechny složená čísla. Použití prvočísla umožňuje Adleru-32 zachytit rozdíly v určitých kombinacích bajtů, které Fletcher nedokáže detekovat.

Druhý rozdíl, který má největší vliv na rychlost algoritmu, spočívá v tom, že Adlerovy sumy jsou počítány přes 8bitový bajtů spíše než 16-bit slova, což má za následek dvojnásobný počet iterací smyčky. To má za následek, že kontrolní součet Adler-32 trvá jeden a půl až dvakrát tak dlouho jako Fletcherův kontrolní součet pro 16bitová data zarovnaná na slovo. U dat zarovnaných po bajtech je Adler-32 rychlejší než správně implementovaný Fletcherův kontrolní součet (např. Jeden nalezený v Hierarchický formát dat ).

Příklad implementace

v C, neefektivní, ale přímá implementace je:

konst uint32_t MOD_ADLER = 65521;uint32_t adler32(nepodepsaný char *data, size_t len) /*     kde data je umístění dat ve fyzické paměti a     len je délka dat v bajtech */{    uint32_t A = 1, b = 0;    size_t index;        // Zpracujte každý bajt dat v pořadí    pro (index = 0; index < len; ++index)    {        A = (A + data[index]) % MOD_ADLER;        b = (b + A) % MOD_ADLER;    }        vrátit se (b << 16) | A;}

Viz zlib zdrojový kód pro efektivnější implementaci, která vyžaduje načtení a dvě přidání na bajt, přičemž operace modulo jsou odloženy dvěma zbytky vypočítanými každých několik tisíc bajtů, což byla technika poprvé objevená pro kontrolní součty Fletcher v roce 1988. js-adler32 poskytuje podobnou optimalizaci s přidáním triku, který zpožďuje výpočet „15“ v letech 65536 - 65521, aby se moduly rychleji zrychlily: lze ukázat, že ((a >> 16) * 15 + (a & 65535))% 65521 je ekvivalentní naivní akumulaci.[3]

Výhody a nevýhody

  • Jako standard CRC-32, kontrolní součet Adler-32 lze snadno kovat, a proto není bezpečný pro ochranu před úmyslné modifikace.
  • Je to rychlejší než CRC-32 na mnoha platformách.[4]
  • Adler-32 má slabost pro krátké zprávy s několika stovkami bajtů, protože kontrolní součty těchto zpráv mají špatné pokrytí 32 dostupných bitů.

Slabost

Adler-32 je slabý pro krátké zprávy, protože součet A nezabalí. Maximální součet 128bajtové zprávy je 32640, což je pod hodnotou 65521 používanou operací modulo, což znamená, že zhruba polovina výstupního prostoru je nevyužita a distribuce v použité části je nerovnoměrná. Rozšířené vysvětlení lze najít v RFC  3309, který nařizuje použitíCRC32C místo Adler-32 pro SCTP Protokol přenosu řízení toku.[5] Adler-32 se také ukázal jako slabý pro malé přírůstkové změny,[6] a také slabý pro řetězce generované ze společné předpony a po sobě jdoucích čísel (jako jsou automaticky generované názvy štítků typickými generátory kódu).[7]

Viz také

Poznámky

  1. ^ První výskyt Adler-32 (viz ChangeLog a adler32.c)
  2. ^ Přehodnocení kontrolních součtů Fletcher a Adler
  3. ^ „adler32.js“. List JS. 3. července 2019.
  4. ^ Theresa C. Maxino, Philip J. Koopman (leden 2009). „Účinnost kontrolních součtů pro integrované řídicí sítě“ (PDF). Transakce IEEE na spolehlivých a bezpečných počítačích.
  5. ^ RFC  3309
  6. ^ http://cbloomrants.blogspot.com/2010/08/08-21-10-adler32.html
  7. ^ http://www.strchr.com/hash_functions

externí odkazy