Fletcher kontrolsum

Fletcher checksum er en checksum algoritme udviklet af John Fletcher (1934-2012) fra Lawrence Livermore Laboratory i slutningen af ​​1970'erne. [1] Fletchers checksum-mål var at give fejldetektion tæt på egenskaberne for cyklisk redundanskode , men med lavere beregningskompleksitet, når den blev implementeret på processorer til generelle formål.

Algoritme

En oversigt over simple kontrolsummer

Som med simplere kontrolsumalgoritmer involverer Fletchers kontrolsum opdeling af det binære ord, der skal fejltjekkes, i korte "blokke" af bit og beregning af modulosummen af ​​disse blokke. (De data, der skal kontrolleres som en helhed, kaldes et "ord", og de dele, de er opdelt i, kaldes "blokke").

For eksempel, hvis den transmitterede meddelelse består af 136 tegn, som hver er 8 bit, så er dataordet 1088 bit. En bekvem blokstørrelse ville være 8 bit, selvom dette ikke er påkrævet. Og bekvemmelighedsmodulet ville være 255, selvom der igen kunne vælges et andet. Således beregnes en simpel kontrolsum ved at summere alle 8-bit blokke af meddelelsen og beregne resultatet modulo 255 (det vil sige at dividere med 255 og kun tage resten). I praksis udføres modulo under summering for at kontrollere størrelsen af ​​resultatet. Kontrolsumværdien sendes sammen med meddelelsen og øger dens længde til 137 bytes eller 1096 bits. Modtageren af ​​meddelelsen kan genberegne kontrolsummen og sammenligne den med den modtagne kontrolsumværdi for at afgøre, om meddelelsen er blevet ændret under overførsel.

Svagheder ved simple kontrolsummer

Den første svaghed ved en simpel kontrolsum er, at den er ufølsom over for rækkefølgen af ​​blokkene (bytes) i dataordet (meddelelse). Hvis deres ordre er blevet ændret, vil kontrolsumværdien være den samme, og ændringen vil ikke blive opdaget. Den anden svaghed er, at sættet af mulige kontrolsumværdier er lille og lig med det valgte modul. I vores eksempel er der kun 255 mulige kontrolsumværdier, så det er nemt at se, at selv tilfældige data har omkring 0,4 % chance for at få samme kontrolsum som vores besked (se hash-funktion kollision ).

Fletchers kontrolsum

Fletcher korrigerede begge disse mangler ved at beregne den anden værdi sammen med en simpel kontrolsum. Dette er modulosummen af ​​værdierne produceret af den simple kontrolsum, når hver blok af dataordet tilføjes til det. Det anvendte modul er det samme. For hver blok af dataordet taget i rækkefølge lægges værdien af ​​blokken således til den første sum, og den nye værdi af den første sum tilføjes derefter til den anden sum. Begge summer starter ved nul (eller en anden forudbestemt værdi). Modulo-addition anvendes i slutningen af ​​dataordet, og de to værdier kombineres for at danne Fletcher-kontrolsummen.

Følsomhed over for blokrækkefølge introduceres, fordi når en blok er tilføjet til den første sum, føjes den derefter til den anden sum sammen med hver blok før den. Hvis der for eksempel udveksles to naboblokke, vil den, der oprindeligt var den første, blive tilføjet til den anden sum én gang, og den anden, som oprindeligt var den anden, vil blive tilføjet til den anden sum igen. Den endelige værdi af den første sum vil være den samme, men den anden sum vil være anderledes og registrerer en ændring i meddelelsen.

Sættet af alle mulige kontrolsumværdier er nu kvadratet af den samme værdi for en simpel kontrolsum. I vores eksempel resulterer to summer, hver med 255 mulige værdier, i 65025 mulige værdier for den kombinerede kontrolsum.

En oversigt over de forskellige parametre i algoritmen

På trods af det uendelige antal parametre studerer det originale papir sagen med en bloklængde på 8 bit og et modul på 255 og 256.

16-bit og 32-bit blokvarianterne blev afledt af den oprindelige sag og studeret i efterfølgende specifikationer eller dokumenter.

16-bit Fletcher sum

Når dataordet er opdelt i 8-bit blokke, som i eksemplet ovenfor, kombineres de to 8-bit summer til en 16-bit Fletcher kontrolsum.

Det er klart, at valget af modul skal være sådan, at resultaterne matcher blokstørrelsen. 256 er derfor det størst mulige modul til Fletcher-16. Dette er dog et dårligt valg, da bits, der flyder over på bit 7, simpelthen er spildt. Et modul, der tager overløbsbitten og blander dem med de lave bits, giver bedre fejldetektion. Modulet skal dog være stort for at opnå det største antal mulige kontrolsumværdier. Værdien 255 er taget i forbindelse med den anden betragtning, men har vist sig at have fremragende ydeevne.

32-bit Fletcher sum

Når dataordet er opdelt i 16-bit blokke, kombineres de to 16-bit summer til en 32-bit kontrolsum. 65535-modulet bruges normalt af samme årsager som 16-bit summen.

64-bit Fletcher sum

Når dataordet er opdelt i 32-bit blokke, kombineres de to 32-bit summer til en 64-bit kontrolsum. Modulet 4294967295 bruges normalt af samme årsager som 16 og 32 bit summer.

Sammenligning med Adler kontrolsum

Adler-32 checksum er en specialisering af Fletcher-32 checksum udviklet af Mark Adler. Det valgte modul (for begge summer) er lig med primtallet 65521 (65535 er deleligt med 3, 5, 17 og 257). Den første sum starter ved 1. Valg af et simpelt modul resulterer i forbedret "shuffle" (fejl opdages med mere ensartet sandsynlighed, hvilket forbedrer sandsynligheden for at finde de mindst detekterbare fejl). Men at reducere størrelsen af ​​sættet af alle mulige kontrolsumværdier modvirker dette og reducerer ydeevnen lidt. En undersøgelse viste, at Fletcher-32 var overlegen i forhold til Adler-32 i både ydeevne og fejldetektion. Da modulo 65535-resten er meget nemmere og hurtigere at implementere end modulo 65521, er Fletcher-32-kontrolsummen normalt den hurtigere algoritme. [2]

Svagheder

Fletcher-kontrolsummen kan ikke skelne mellem blokke, der alle er 0'ere eller kun 1'ere. For eksempel, hvis 16-bit blokken i dataordet ændres fra 0x0000 til 0xFFFF, vil Fletcher-32 kontrolsum forblive uændret.

Implementering

Direkte implementering

En ineffektiv, men simpel C -implementering af en funktion til at beregne en Fletcher-16-kontrolsum fra et array af 8-bit dataelementer: