Fletcherův kontrolní součet

Fletcherův kontrolní součet je algoritmus kontrolního součtu vyvinutý Johnem Fletcherem (1934–2012) z Lawrence Livermore Laboratory na konci 70. let. [1] Cílem Fletcherova kontrolního součtu bylo poskytnout detekci chyb blízkou vlastnostem kódu cyklické redundance , ale s nižší výpočetní složitostí při implementaci na procesorech pro všeobecné použití.

Algoritmus

Přehled jednoduchých kontrolních součtů

Stejně jako u jednodušších algoritmů kontrolního součtu zahrnuje Fletcherův kontrolní součet rozdělení binárního slova, které má být zkontrolováno, na krátké „bloky“ bitů a výpočet modulového součtu těchto bloků. (Data, která je třeba zkontrolovat jako celek, se nazývají „slovo“ a části, na které jsou rozděleny, se nazývají „bloky“).

Pokud se například přenášená zpráva skládá ze 136 znaků, z nichž každý má 8 bitů, pak datové slovo má 1088 bitů. Vhodná velikost bloku by byla 8 bitů, i když to není nutné. A modul pohodlí by byl 255, i když by opět mohl být zvolen jiný. Jednoduchý kontrolní součet je tedy vypočítán sečtením všech 8bitových bloků zprávy a vypočtením výsledku modulo 255 (to znamená, že se vydělí 255 a vezme se pouze zbytek). V praxi se modulo provádí během sčítání, aby se řídila velikost výsledku. Hodnota kontrolního součtu je odeslána spolu se zprávou, čímž se její délka zvětší na 137 bajtů nebo 1096 bitů. Příjemce zprávy může přepočítat kontrolní součet a porovnat jej s přijatou hodnotou kontrolního součtu, aby zjistil, zda byla zpráva při přenosu změněna.

Slabiny jednoduchých kontrolních součtů

První slabinou jednoduchého kontrolního součtu je, že není citlivý na pořadí bloků (bajtů) v datovém slově (zprávě). Pokud bylo jejich pořadí změněno, hodnota kontrolního součtu bude stejná a změna nebude detekována. Druhou slabinou je, že sada možných hodnot kontrolního součtu je malá a rovná se zvolenému modulu. V našem příkladu existuje pouze 255 možných hodnot kontrolního součtu, takže je snadné vidět, že i náhodná data mají asi 0,4% šanci získat stejný kontrolní součet jako naše zpráva (viz kolize hashovací funkce ).

Fletcherův kontrolní součet

Fletcher oba tyto nedostatky opravil výpočtem druhé hodnoty spolu s jednoduchým kontrolním součtem. Toto je modulový součet hodnot vytvořených jednoduchým kontrolním součtem, když je k němu přidán každý blok datového slova. Použitý modul je stejný. Takže pro každý blok datového slova braný za sebou se hodnota bloku přičte k prvnímu součtu a nová hodnota prvního součtu se pak přičte k druhému součtu. Oba součty začínají nulou (nebo jinou předem stanovenou hodnotou). Přidání modulu se použije na konci datového slova a dvě hodnoty se zkombinují, aby vytvořily kontrolní součet Fletcher.

Citlivost na pořadí bloků je zavedena, protože jakmile je blok přidán k prvnímu součtu, je poté znovu přidán k druhému součtu spolu s každým blokem před ním. Pokud dojde například k výměně dvou sousedních bloků, ten, který byl původně první, se jednou přičte k druhému součtu a druhý, který byl původně druhý, se znovu přidá k druhému součtu. Konečná hodnota prvního součtu bude stejná, ale druhý součet bude jiný, detekuje změnu ve zprávě.

Sada všech možných hodnot kontrolního součtu je nyní druhou mocninou stejné hodnoty pro jednoduchý kontrolní součet. V našem příkladu dva součty, každý s 255 možnými hodnotami, vedou k 65025 možným hodnotám pro kombinovaný kontrolní součet.

Přehled různých parametrů algoritmu

Přes nekonečné množství parametrů původní článek studuje případ s délkou bloku 8 bitů a modulem 255 a 256.

16bitové a 32bitové blokové varianty byly odvozeny z původního případu a studovány v následných specifikacích nebo dokumentech.

16bitový Fletcherův součet

Když je datové slovo rozděleno do 8bitových bloků, jako ve výše uvedeném příkladu, jsou dva 8bitové součty spojeny do 16bitového kontrolního součtu Fletcher.

Je zřejmé, že výběr modulu musí být takový, aby výsledky odpovídaly velikosti bloku. 256 je tedy největší možný modul pro Fletcher-16. To je však špatná volba, protože bity, které přetečou na bitu 7, jsou jednoduše zbytečné. Modul, který vezme bit přetečení a smíchá je s nízkými bity, poskytuje lepší detekci chyb. Modul však musí být velký, aby se získal co největší počet hodnot kontrolního součtu. Hodnota 255 je brána v souvislosti s druhou úvahou, ale bylo zjištěno, že má vynikající výkon.

32bitový Fletcherův součet

Když je datové slovo rozděleno do 16bitových bloků, dva 16bitové součty se spojí do 32bitového kontrolního součtu. Obvykle se používá modul 65535 ze stejných důvodů jako 16bitový součet.

64bitový Fletcherův součet

Když je datové slovo rozděleno do 32bitových bloků, dva 32bitové součty se spojí do 64bitového kontrolního součtu. Obvykle se používá modul 4294967295 ze stejných důvodů jako 16 a 32 bitové součty.

Porovnání s kontrolním součtem Adler

Kontrolní součet Adler-32 je specializací kontrolního součtu Fletcher-32 vyvinutého Markem Adlerem. Zvolený modul (pro oba součty) je roven prvočíslu 65521 (65535 je dělitelné 3, 5, 17 a 257). První součet začíná na 1. Volba jednoduchého modulu má za následek vylepšené "shuffle" (chyby jsou detekovány s rovnoměrnější pravděpodobností, což zvyšuje pravděpodobnost nalezení nejméně zjistitelných chyb). Snížení velikosti sady všech možných hodnot kontrolního součtu však působí proti tomu a mírně snižuje výkon. Jedna studie ukázala, že Fletcher-32 byl lepší než Adler-32 ve výkonu i detekci chyb. Protože zbytek modulo 65535 je mnohem jednodušší a rychlejší na implementaci než modulo 65521, kontrolní součet Fletcher-32 je obvykle rychlejší algoritmus. [2]

Slabé stránky

Kontrolní součet Fletcher nedokáže rozlišit mezi bloky, které jsou všechny 0 nebo pouze 1. Pokud se například 16bitový blok v datovém slově změní z 0x0000 na 0xFFFF, kontrolní součet Fletcher-32 zůstane nezměněn.

Implementace

Přímá implementace

Neefektivní, ale jednoduchá C implementace funkce pro výpočet kontrolního součtu Fletcher-16 z pole 8bitových datových položek: