Adler-32

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 14.5.2019 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .

Adler-32  on Mark Adlerin kehittämä hash-funktio . Se on muunnos Fletcherin tarkistussummasta . Laskee tarkistussumman arvon RFC 1950 :n mukaisesti tavujoukolle tai sen fragmentille. Tämä tarkistussumman laskentaalgoritmi eroaa CRC32 :sta suorituskyvyltään. Adler-32:ta käytetään Zlib -kirjastossa . Rsync -apuohjelmassa käytetään funktion liukuvaa tarkistussummaversiota .

Historia

Aivan kuten Fletcher-tarkistussumma, Adler-summa on suunniteltu tuottamaan tarkistussumma, jonka virheiden havaitsemisteho on verrattavissa CRC :hen . Vaikka Adlerin ja Fletcherin tarkistussummavirheiden havaitsemissuorituskyky on lähes sama kuin suhteellisen heikkojen CRC:iden, joissakin tärkeissä tapauksissa ne toimivat paljon huonommin kuin hyvät CRC:t.

Algoritmi

Adler-32-tarkistussumma saadaan laskemalla kaksi 16-bittistä tarkistussummaa A ja B ja yhdistämällä niiden bitit 32-bittiseksi kokonaisluvuksi. A on merkkijonon kaikkien tavujen summa plus yksi, ja B on A : n kaikkien yksittäisten arvojen summa kussakin vaiheessa. Adler-32-funktion suorittamisen alussa A alustetaan ykköseksi ja B  nollaksi. Summat otetaan modulo 65521 (suurin alkuluku pienempi kuin 2 16 ). Tavut kirjoitetaan verkkojärjestyksessä , B varaa 2 merkittävintä tavua.

Funktio voidaan ilmaista seuraavasti:

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

missä D on tavujono, jolle tarkistussumma lasketaan, ja n on D:n pituus.

Esimerkki

Adler-32-arvo ASCII-merkkijonolle "Wikipedia" lasketaan seuraavasti:

ASCII-koodi AB (desimaali) L: 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 (kanta 16) B=4582=11E6 hex Lähtö = 300286872 = 11E60398 hex

Modulo-lisäystoiminnolla ei ole vaikutusta tässä esimerkissä, koska mikään arvoista ei saavuttanut arvoa 65521.

Vertailu Fletcherin tarkistussummaan

Adlerin tarkistussumma-algoritmi on identtinen Fletcherin summa-algoritmin kanssa muutamalla erolla. Ensimmäinen ero on, että Adler-funktion tapauksessa summa A alustetaan arvolla 1. Toinen ero näiden kahden algoritmin välillä on, että Adler-32-algoritmin summa lasketaan modulo alkuluvusta 65521, kun taas Fletcherin summat lasketaan modulo -1, - 1, -1 (riippuen käytettyjen bittien määrästä), jotka ovat yhdistelmälukuja . Tämä algoritmin muutos tehtiin paremman bittisekoituksen saavuttamiseksi. Alkuluvun käyttäminen antaa Adler-32-funktiolle mahdollisuuden havaita eroja tietyissä tavuyhdistelmissä, joita Fletcher-funktio ei pysty kaappaamaan . Kolmas ero, joka eniten vaikuttaa algoritmin nopeuteen, on se, että Adler-32-funktion summat lasketaan 8-bittisiltä sanoilta 16-bittisten sanojen sijaan, mikä kaksinkertaistaa silmukan iteraatioiden määrän. Tämä johtaa siihen, että Adler-32-tarkistussumma kestää puolitoista tai kaksi kertaa niin kauan kuin Fletcherin tarkistussumma 16-bittiselle sanadatalle. Tavuihin jaettujen tietojen osalta Adler-32 on nopeampi kuin Fletcher-algoritmi.

Vaikka Adler-tarkistussummaa ei ole virallisesti määritelty muille datasanojen pituuksille, suurinta alkukokonaislukua, joka on pienempi kuin 2 4 =16 ja 2 8 =256, voidaan käyttää 8- ja 16-bittisten Adler-tarkistussummien toteuttamiseen vertailua varten. Koska Adler-tarkistussummalla on samanlainen algoritmi, sen suorituskyky on sama kuin Fletcherin summalla. Kaikki 2-bittiset virheet havaitaan M*(k/2) bittiä lyhyemmille datasanoille, missä k on tarkistussumman koko, M on Adlerin summan moduuli. Kuten Fletcher-tarkistussummassa, havaitsemattoman virheen todennäköisyyden pahin arvo ilmenee, kun kussakin tietolohkossa on sama määrä nollia ja ykkösiä. Adler-8 ja Adler-16 havaitsevat kaikki alle k/2 bitin pituiset ryhmävirheet. Adler-32 havaitsee kaikki ryhmävirheet enintään 7 bittiä. Kuva 1 esittää havaitsemattomien virheiden todennäköisyyden riippuvuuden Adlerin ja Fletcherin tarkistussummille bittivirhesuhteelle 10 -5 .

Adler-tarkistussumman tarjoaman paremman bittisekoituksen olisi pitänyt johtaa Fletcher-summaa parempaan virheenetsintäsuorituskykyyn. Mutta kuten RFC 3385 osoittaa , Fletcher-32 toimii paremmin kuin Adler-32 8 kilotavulla. Adler-tarkistussumma ylittää Fletcher-summan vain 16-bittisten tarkistussummien tapauksessa ja sitten vain näiden summien alueella, jossa Hamming-etäisyys on 3. Ongelmana on, että huolimatta siitä, että alkulukua käytetään operaation moduulina johtaa parempaan bittisekoitukseen, jolloin koodisanoille on saatavilla vähemmän oikeita tarkistussumma-arvoja. Useimmissa tapauksissa tämä tekee tyhjäksi paremman sekoituksen positiivisen vaikutuksen. Näin ollen Fletcher-tarkistussumma ylittää Adler-summan kaikissa tapauksissa paitsi Adler-16-summan, jota sovelletaan lyhyisiin datasanoihin. Edes virheenetsintätehokkuuden lisäys ei välttämättä ole modulaaristen toimintojen käytön aiheuttaman laskennallisen yleiskuorman lisäyksen arvoista.

Vertailu muihin tarkistussummiin

RFC 3385 :n kirjoittajat vertasivat virheiden havaitsemisen suorituskykyä. Yhteenveto niiden tuloksista on esitetty taulukossa:

Algoritmi d lohko i/tavu T koko T-look 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 _


Taulukossa: d on pienin etäisyys lohkon lohkossa, lohko on lohkon pituus bitteinä, i / tavu on ohjelmakäskyjen määrä tavua kohden, T koko  on taulukon koko (jos katselu on välttämätön), T-look on näyttökertojen lukumäärä tavua kohden, P udb  on havaitsemattomien ryhmävirheiden todennäköisyys, P uds  on havaitsemattomien yksittäisten virheiden todennäköisyys.
Yllä olevan taulukon havaitsemattomien virheiden todennäköisyydet on laskettu olettaen tasaisen tiedon jakautumisen.

Edut ja haitat

"Hyvälle" hash-funktiolle on ominaista laskettujen arvojen enemmän tai vähemmän tasainen jakautuminen . Ilmeisesti Adler-32 ei täytä tätä lyhyen datan vaatimusta ( 128-tavuisen viestin A :n maksimiarvo on 32640, mikä on pienempi kuin 65521, numero, johon modulo-operaatio suoritetaan). Tämän puutteen vuoksi SCTP -protokollan kehittäjät suosivat CRC32 :ta tälle algoritmille , koska lyhyiden tavusekvenssien hajautus on välttämätöntä verkkoprotokollassa.

Aivan kuten CRC32 :lle, Adler-32:lle voidaan helposti rakentaa törmäys , eli tietylle hashille löytää muita lähdetietoja, joilla on sama funktioarvo.

Sillä on etu CRC32 :een verrattuna, että se on nopeampi laskea ohjelmistossa.

Esimerkki toteutuksesta C-kielellä

Yksinkertainen algoritmin toteutus C-kielellä on seuraava koodi:

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 ; } paluu ( s2 << 16 ) + s1 ; }

Katso zlib - kirjastokoodi tehokkaasta toteutuksesta .

Adler-32 muilla ohjelmointikielillä

  • Javassa on luokka java.util.zip.Adler32, joka toteuttaa algoritmin. [yksi]
  • D - standardikirjastossa std.zlib : adler32

Muistiinpanot

  1. ↑ Adler32 (Java Platform SE 8) . Käyttöpäivä: 24. joulukuuta 2015. Arkistoitu alkuperäisestä 25. joulukuuta 2015.
  2. ↑ Digest::Adler32 CPAN:lla . Käyttöpäivä: 12. tammikuuta 2014. Arkistoitu alkuperäisestä 12. tammikuuta 2014.
  3. ↑ Adler32-koodi Arkistoitu 4. marraskuuta 2007 Wayback Machinessa Arkistoitu 4. marraskuuta 2007.

Kirjallisuus

 Hash-funktiot
yleinen tarkoitus
Kryptografinen
Avainten luontitoiminnot
Tarkista numero ( vertailu )
Hashes