Adler-32

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 14. května 2019; kontroly vyžadují 5 úprav .

Adler-32  je hashovací funkce vyvinutá Markem Adlerem . Jedná se o modifikaci Fletcherova kontrolního součtu . Vypočítá hodnotu kontrolního součtu podle RFC 1950 pro bajtové pole nebo jeho fragment. Tento algoritmus výpočtu kontrolního součtu se liší od CRC32 ve výkonu. Adler-32 se používá v knihovně Zlib . Verze funkce rolujícího kontrolního součtu se používá v obslužném programu rsync .

Historie

Stejně jako u Fletcherova kontrolního součtu byl Adlerův součet navržen tak, aby vytvořil kontrolní součet s účinností detekce chyb srovnatelnou s CRC . Přestože výkon detekce chyb kontrolního součtu Adler a Fletcher je téměř stejný jako u relativně slabých CRC, v některých důležitých případech fungují mnohem hůře než dobré CRC.

Algoritmus

Kontrolní součet Adler-32 se získá výpočtem dvou 16bitových kontrolních součtů A a B a zřetězením jejich bitů do 32bitového celého čísla. A je rovno součtu všech bajtů v řetězci plus jedna a B je součet všech jednotlivých hodnot A v každém kroku. Na začátku provádění funkce Adler-32 je A inicializováno na jedničku a B  je inicializováno na nulu. Součty se berou modulo 65521 (největší prvočíslo menší než 2 16 ). Bajty se zapisují v síťovém pořadí , B zabírá 2 nejvýznamnější bajty.

Funkci lze vyjádřit jako:

A = 1 + D 1 + D 2 + ... + D n (mod 65521) B = (1 + D 1 ) + (1 + D 1 + D 2 ) + ... + (1 + D 1 + D 2 + ... + D n ) (mod 65521) = n × D 1 + ( n -1) × D 2 + ( n -2) × D 3 + ... + D n + 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

Hodnota Adler-32 pro řetězec ASCII „Wikipedia“ se vypočítá takto:

ASCII kód ​​AB (desítkové) 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 (základ 16) B=4582=11E6 hex Výstup = 300286872 = 11E60398 hex

Operace sčítání modulo nemá v tomto příkladu žádný účinek, protože žádná z hodnot nedosáhla 65521.

Porovnání s Fletcherovým kontrolním součtem

Algoritmus kontrolního součtu Adler je totožný s algoritmem Fletcher součtu s několika rozdíly. První rozdíl je v tom, že v případě Adlerovy funkce je součet A inicializován hodnotou 1. Druhý rozdíl mezi oběma algoritmy spočívá v tom, že součet v algoritmu Adler-32 se počítá modulo k prvočíslu 65521, zatímco Fletcherovy součty se počítají modulo -1, - 1, -1 (v závislosti na počtu použitých bitů), což jsou složená čísla . Tato změna v algoritmu byla provedena za účelem dosažení lepšího míchání bitů. Použití prvočísla umožňuje funkci Adler-32 zaznamenat rozdíly v určitých kombinacích bajtů, které funkce Fletcher nedokáže zachytit. Třetím rozdílem, který nejvýrazněji ovlivňuje rychlost algoritmu, je to, že součty funkce Adler-32 jsou počítány přes 8bitová slova spíše než 16bitová slova, což zdvojnásobuje počet iterací smyčky. To má za následek, že kontrolní součet Adler-32 trvá jeden a půl až dvakrát déle než kontrolní součet Fletcher pro 16bitová data slova. Pro data rozdělená na bajty je Adler-32 rychlejší než algoritmus Fletcher.

Ačkoli Adlerův kontrolní součet není oficiálně definován pro jiné délky datových slov, největší prvočíslo menší než 2 4 = 16 a 2 8 = 256 lze použít k implementaci 8 a 16 bitových Adlerových kontrolních součtů pro účely srovnání. Díky podobnému algoritmu má kontrolní součet Adler podobný výkon jako Fletcherův součet. Všechny 2bitové chyby jsou detekovány pro datová slova kratší než M*(k/2) bitů, kde k je velikost kontrolního součtu, M je modul Adlerova součtu. Stejně jako u kontrolního součtu Fletcher platí, že nejhorší hodnota pravděpodobnosti nezjištěné chyby nastane, když je v každém bloku dat stejný počet nul a jedniček. Adler-8 a Adler-16 detekují všechny skupinové chyby kratší než k/2 bitů. Adler-32 detekuje všechny skupinové chyby ne delší než 7 bitů. Obrázek 1 ukazuje závislost pravděpodobnosti nedetekovaných chyb pro kontrolní součty Adlera a Fletchera pro bitovou chybovost 10 −5 .

Lepší míchání bitů poskytované kontrolním součtem Adler by mělo vést k lepšímu výkonu při hledání chyb než Fletcherův součet. Ale jak ukazuje RFC 3385 , Fletcher-32 funguje lépe než Adler-32 při 8 KB. Adlerův kontrolní součet překoná Fletcherův součet pouze v případě 16bitových kontrolních součtů, a to pouze v oblasti těchto součtů, kde je Hammingova vzdálenost 3. Problém je v tom, že i přes to, že použité prvočíslo jako modul operace má za následek lepší míchání bitů, což má za následek méně správných hodnot kontrolních součtů dostupných pro kódová slova. Ve většině případů to neguje pozitivní efekt lepšího míchání. Kontrolní součet Fletcher tedy překonává součet Adler ve všech případech kromě součtu Adler-16 aplikovaného na krátká datová slova. Dokonce ani zvýšení efektivity vyhledávání chyb nemusí stát za zvýšení výpočetní režie, která přichází s použitím modulárních operací.

Porovnání s jinými kontrolními součty

Autoři RFC 3385 porovnávali výkon detekce chyb. Shrnutí jejich výsledků je uvedeno v tabulce:

Algoritmus d blok i/bajt Velikost T T-pohled P udb P uds
Adler-32 3 2 19 3 - - 10 -36 10 -35
Fletcher-32 3 2 19 2 - - 10 -37 10 -36
IEEE-802 3 2 16 2,75 2 18 0,5/b 10 -41 10 -40
CRC32C 3 2 31 −1 2,75 2 18 0,5/b 10 -41 10 -40


V tabulce: d je minimální vzdálenost na bloku délky bloku, blok je délka bloku v bitech, i / byte je počet programových instrukcí na bajt, velikost T je  velikost tabulky (pokud je prohlížení nutné), T-look je počet zobrazení na bajt, P udb  je pravděpodobnost nezjištěných skupinových chyb, P uds  je pravděpodobnost nezjištěných jednotlivých chyb.
Pravděpodobnosti nezjištěných chyb ve výše uvedené tabulce jsou vypočteny za předpokladu rovnoměrného rozložení dat.

Výhody a nevýhody

„Dobrá“ hašovací funkce se vyznačuje víceméně rovnoměrným rozložením vypočtených hodnot. Je zřejmé, že Adler-32 tento požadavek pro krátká data nesplňuje (maximální hodnota A pro 128bajtovou zprávu je 32640, což je méně než 65521, číslo, na kterém se provádí modulo operace). Kvůli tomuto nedostatku dali vývojáři protokolu SCTP přednost před tímto algoritmem CRC32 , protože v síťovém protokolu je nutné hašování krátkých sekvencí bajtů.

Stejně jako pro CRC32 , i pro Adler-32 lze snadno zkonstruovat kolizi , tedy pro daný hash najít další zdrojová data, která mají stejnou funkční hodnotu.

Oproti CRC32 má výhodu v tom, že je rychlejší softwarově.

Příklad implementace v jazyce C

Jednoduchá implementace algoritmu v jazyce C je následující kód:

uint32_t adler32 ( const unsigned char * buf , size_t buf_length ) { uint32_t s1 = 1 ; uint32_t s2 = 0 ; while ( buf_length -- ) { s1 = ( s1 + * ( buf ++ ) ) % 65521 ; s2 = ( s2 + s1 ) % 65521 ; } return ( s2 << 16 ) + s1 ; }

Efektivní implementaci naleznete v kódu knihovny zlib .

Adler-32 v jiných programovacích jazycích

  • Java má třídu java.util.zip.Adler32, která implementuje algoritmus. [jeden]
  • Ve standardní knihovně D std.zlib : adler32

Poznámky

  1. ↑ Adler32 (Java Platform SE 8) . Datum přístupu: 24. prosince 2015. Archivováno z originálu 25. prosince 2015.
  2. ↑ Digest::Adler32 na CPAN . Datum přístupu: 12. ledna 2014. Archivováno z originálu 12. ledna 2014.
  3. ↑ Kód Adler32 Archivováno 4. listopadu 2007 na Wayback Machine Archivováno 4. listopadu 2007.

Literatura

 Hashovací funkce
obecný účel
Kryptografický
Funkce generování klíčů
Kontrolní číslo ( srovnání )
Hashe