Cyklický redundantní součet

Cyklický redundantní součet, označovaný také CRC (zkratka anglického Cyclic redundancy check) je speciální hašovací funkce, používaná k detekci chyb během přenosu či ukládání dat. Pro svou jednoduchost a dobré matematické vlastnosti jde o velmi rozšířený způsob realizace kontrolního součtu. Kontrolní součet bývá odesílán či ukládán společně s daty, při jejichž přenosu nebo uchovávání by mohlo dojít k chybě. Po převzetí dat je znovu nezávisle spočítán. Pokud je nezávisle spočítaný kontrolní součet odlišný od přeneseného nebo uloženého, je zřejmé že při přenosu nebo uchovávání došlo k chybě. Pokud je shodný, tak téměř jistě k žádné chybě nedošlo. V určitých případech je možné chybu pomocí CRC opravit.

CRC je vhodný pro zjišťování chyb vzniklých v důsledku selhání techniky, avšak jako metoda pro odhalení záměrné změny dat počítačovými piráty je příliš slabý. V tomto případě je třeba používat speciální hašovací funkce určené pro šifrovací algoritmy.

Ekvivalence polynomů a bitových posloupností

Například posloupnost bitů „100101“ může být interpretována jako polynom x^5 + x^2 + 1, posloupnost bitů „110011“ může být přepsána jako polynom x^5 + x^4 + x + 1. Pokud nad bity těchto dvou posloupností provedeme operaci XOR, dostáváme posloupnost „010110“, která odpovídá polynomu x^4 + x^2 + x.

Stejný výsledek dostaneme při sčítání polynomů v konečném tělese GF(2^n): : (x^5 + x^2 + 1) + (x^5 + x^4 + x + 1) = 2x^5 + x^4 + x^2 + x + 2 \equiv x^4 + x^2 + x

Právě jednoduchá implementace operací nad bitovými posloupnostmi je jedním z hlavních důvodů širokého rozšíření CRC algoritmů.

Princip výpočtu CRC

Výsledek výpočtu CRC je určen vstupní posloupností bitů (polynom M(x)) a zvoleným klíčem (což je také posloupnost bitů, polynom G(x)). Když vstupní posloupnost a klíč interpretujeme jako polynomy nad tělesem GF(2^n), pak CRC je zbytek po dělení (polynom R(x)) polynomu vstupní posloupnosti polynomem klíče. +more Výsledkem je polynom, který následně interpretujeme jako bitovou posloupnost. Při vhodně zvoleném klíči vede i malá změna ve vstupní posloupnosti k podstatně odlišnému výsledku, při náhodné změně vstupní posloupnosti pak pravděpodobnost odhalení chyby roste s šířkou klíče (např. pro klíč stupně 16 by to měla být hodnota 1 - 1/2^{16} \approx 0,999985).

CRC je tedy založen na dělení v konečném tělese GF(2^n), tělese polynomů nad celými čísly modulo 2. Jednodušeji řečeno, je to množina polynomů, jejichž koeficienty mohou nabývat pouze hodnot 0 a 1. +more Tyto polynomy sčítáme, odčítáme, dělíme a násobíme jako obyčejné polynomy, avšak nad výslednými koeficienty provádíme operaci modulo 2 (zbytek po dělení dvěma). Například −2 modulo 2 je 0, −1 modulo 2 je 1, 0 modulo 2 je 0, 1 modulo 2 je 1, 2 modulo 2 je 0, 3 modulo 2 je 1, 4 modulo 2 je 0 atd. :(x^2 + x) + (x + 1) = x^2 + 2x + 1 \equiv x^2 + 1 Ze dvojky se v tomto případě stane 0, protože operace nad koeficienty se provádí modulo 2. Násobení je podobné: :(x^2 + x)(x + 1) = x^3 + 2x^2 + x \equiv x^3 + x Můžeme také dělit polynomy modulo 2. Například :\frac{x^3 + x^2 + x}{x+1} = (x^2 + 1) - \frac1{x+1} To lze přepsat jako :(x^3 + x^2 + x) = (x^2 + 1)(x + 1) - 1 \equiv (x^2 + 1)(x + 1) + 1 Ve výše uvedeném dělení představuje M(x)=x^3 + x^2 + x vstupní bitovou posloupnost „1110“, G(x)=x+1 představuje klíč (jeho bitová posloupnost je „11“, jeho stupeň je 1), zbytkem po dělení je polynom R(x)=1. Hodnota CRC odpovídá zbytku po dělení převedeném na bitovou posloupnost, v tomto případě tedy jde o hodnotu „1“.

Základní vlastnosti CRC

Schopnost detekce chyb záleží na volbě klíče (též generující polynom, G(x)). Při správné volbě hodnoty mají delší klíče lepší schopnost detekce chyb. +more * Číslo za písmeny CRC určuje stupeň řídícího polynomu, např. CRC16 je kontrolní součet typu CRC s řídícím polynomem stupně 16 (nejvyšší koeficient je x^{16}). * Při uvádění číselných hodnot kontrolních polynomů se často zanedbává nejvyšší bit, protože má vždy hodnotu 1. Co tedy znamená „kontrolní součet typu CRC16 s řídícím polynomem 0x1081“. 0x1081 je hexadecimální číslo s binární hodnotou „0001 0000 1000 0001“, bitová posloupnost řídícího polynomu je „1 0001 0000 1000 0001“. Bez jedničky přidané na začátek by se jednalo o polynom pouze 12. stupně. Řídící polynom má v tomto případě tedy hodnotu G(x) = x^{16} + x^{12} + x^7 + 1. * Určení CRC pouze řídícím polynomem je nejednoznačné, protože různé algoritmy mohou vytvářet vstupní bitové posloupnosti různým způsobem. Z různých historických a technických důvodů může při výpočtu docházet například ke změně pořadí bajtů, k otočení pořadí bitů v bajtu, nebo k přidávání různých bitových posloupností před vstupní data a za ně. * Protože CRC je založeno na dělení, nerozezná přidané nuly na začátku vstupních dat M(x). Proto se někdy při výpočtu CRC před vstupní data dává jednička. * Předchozí problém s přidanými nulami na začátku lze v některých implementacích výpočtu odstranit nastavením polynomu R(x) (zbytek po dělení) na nenulovou hodnotu před zahájením vlastního výpočtu (např. 0xFFFF u protokolu Modbus/RTU). * Při některých způsobech výpočtu se za vstupní data přidává stejný počet nul, jako je šířka CRC. CRC vypočtené ze vstupních dat a uloženého CRC je pak nulové.

Příklad výpočtu CRC

Předpokládejme 8bitové CRC s generujícím polynomem G(x)=x^8+x^2+x+1, což odpovídá 9bitovému řetězci „100000111“.

Cílem je spočítat CRC pro 8bitovou zprávu obsahující písmeno „W“, jehož ASCII kód je dekadicky 8710 nebo šestnáctkově 5716. Tato hodnota může být odeslána dvěma způsoby, čemuž odpovídají dva různé polynomy M(x). +more V případě, že nejvýznamnější bit (MSB) bude první (vlevo), bude M(x)=x^6+x^4+x^2+x+1 = 01010111. V případě prvního LSB (nejméně významný bit) bude M(x)=x^7+x^6+x^5+x^3+x = 11101010.

Před vlastním výpočtem je M(x) doplněn zprava osmi nulovými bity. Výpočet zbytku po dělení polynomu M(x) \cdot x^8 polynomem G(x) bude připomínat ruční dělení víceciferných čísel se dvěma zjednodušeními: * počítá se pouze se symboly 0 a 1, navíc v tělese GF(2^n) (takže např. +more 1 + 1 = 0; 0 − 1 = 1), * nezajímá nás podíl, ale pouze zbytek po dělení.

Je vidět, že po každém odčítání lze rozdělit bity do třech skupin: vlevo je skupina nulových bitů; vpravo je skupina zatím původních bitů; uprostřed je zvýrazněna „zajímavá“ část dlouhá 8 bitů. V každém kroku se levá skupina o jeden bit rozšíří a pravá skupina o jeden bit zúží, až vpravo zbude pouze CRC.

V případě prvního MSB je výsledný polynom R(x)=x^7+x^5+x, což lze šestnáctkově zapsat jako A216. V případě prvního LSB je zbytkem po dělení R(x)=x^7+x^4+x^3, což lze zapsat šestnáctkově jako 1916, ovšem za předpokladu, že LSB je první.

Implementace

Při programování výpočtu CRC dle příkladu výše stačí držet v posuvném registru pouze zvýrazněnou střední část.

Následuje první příklad výpočtu CRC o n-bitech v pseudokódu. Na vstupu je pole len bitů obsahující zprávu. +more Operace XOR je použita pro sčítání/odčítání dvou polynomů modulo 2.

function crc(bit array bitString[1. len], int len) { remainderPolynomial := polynomialForm(bitString[1. +moren]) // Prvních n bitů z bitString for i from 1 to len { remainderPolynomial := remainderPolynomial * x + bitString[i+n] * x0 // Předpokládejme, že bitString[j]=0 for j>len if coefficient of xn of remainderPolynomial = 1 { remainderPolynomial := remainderPolynomial xor generatorPolynomial } } return remainderPolynomial }.

Operaci remainderPolynomial * x lze nahradit posunem doleva (shift-left, shl, <<).

Pro příklad v předchozí kapitolce by se tento algoritmus choval následovně:

G = 1 0 0 0 0 0 1 1 1 // n = 8 M = 0 1 0 1 0 1 1 1 // len = 8 R = 0 1 0 1 0 1 1 1 // remainderPolynomial := polynomialForm(bitString[1..n]) // i = 1 R = 0 1 0 1 0 1 1 1 0 // remainderPolynomial := remainderPolynomial * x + bitString[9] // i = 2 R = 1 0 1 0 1 1 1 0 0 // remainderPolynomial := remainderPolynomial * x + bitString[10] R = 0 0 1 0 1 1 0 1 1 // remainderPolynomial := remainderPolynomial xor generatorPolynomial // i = 3 R = 0 1 0 1 1 0 1 1 0 // remainderPolynomial := remainderPolynomial * x + bitString[11] // i = 4 R = 1 0 1 1 0 1 1 0 0 // remainderPolynomial := remainderPolynomial * x + bitString[12] R = 0 0 1 1 0 1 0 1 1 // remainderPolynomial := remainderPolynomial xor generatorPolynomial // i = 5 R = 0 1 1 0 1 0 1 1 0 // remainderPolynomial := remainderPolynomial * x + bitString[13] // i = 6 R = 1 1 0 1 0 1 1 0 0 // remainderPolynomial := remainderPolynomial * x + bitString[14] R = 0 1 0 1 0 1 0 1 1 // remainderPolynomial := remainderPolynomial xor generatorPolynomial // i = 7 R = 1 0 1 0 1 0 1 1 0 // remainderPolynomial := remainderPolynomial * x + bitString[15] R = 0 0 1 0 1 0 0 0 1 // remainderPolynomial := remainderPolynomial xor generatorPolynomial // i = 8 R = 0 1 0 1 0 0 0 1 0 // remainderPolynomial := remainderPolynomial * x + bitString[16]

První vadou výše uvedené ukázky je potřeba mít v paměti n+1 bitů pro remainderPolynomial, druhou vadou je potřeba doplňovat n nulových bitů vpravo za bitString. První problém lze snadno vyřešit vhodným přehozením operací (např. +more rem = (msb(rem)) . ((rem). Druhý problém lze vyřešit úpravou posledních n iterací, ale existuje i vtipnější optimalizace použitá jak v hardwarových i softwarových implementacích .

Protože operace XOR použitá pro odečítání generujícího polynomu od zprávy je asociativní a komutativní, nezáleží na pořadí operandů při výpočtu remainderPolynomial. A navíc bit z pole bitString stačí přidat až na poslední chvíli před testováním, zda provést xor. +more V následující ukázce také není potřeba předvyplňovat remainderPolynomial prvními n bity.

function crc(bit array bitString[1..len], int len) { remainderPolynomial := 0 for i from 1 to len { remainderPolynomial := remainderPolynomial xor (bitString[i] * xn-1) if (coefficient of xn-1 of remainderPolynomial) = 1 { remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial } else { remainderPolynomial := (remainderPolynomial * x) } } return remainderPolynomial }

Tato varianta, která v jednom cyklu vyhodnotí jeden bit, je běžná v hardwarových implementacích CRC. Je dobrá i pro studijní účely, po pochopení provedené optimalizace jsou již další úpravy průhlednější.

Pro příklad v předchozí kapitolce by se tento algoritmus choval následovně:

G = 1 0 0 0 0 0 1 1 1 // n = 8 M = 0 1 0 1 0 1 1 1 // len = 8 R = 0 0 0 0 0 0 0 0 // remainderPolynomial := 0 // i = 1 R = 0 0 0 0 0 0 0 0 // remainderPolynomial := remainderPolynomial xor (bitString[1] * x^7) R = 0 0 0 0 0 0 0 0 // remainderPolynomial := (remainderPolynomial * x) // i = 2 R = 1 0 0 0 0 0 0 0 // remainderPolynomial := remainderPolynomial xor (bitString[2] * x^7) R = 0 0 0 0 0 1 1 1 // remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial // i = 3 R = 0 0 0 0 0 1 1 1 // remainderPolynomial := remainderPolynomial xor (bitString[3] * x^7) R = 0 0 0 0 1 1 1 0 // remainderPolynomial := (remainderPolynomial * x) // i = 4 R = 1 0 0 0 1 1 1 0 // remainderPolynomial := remainderPolynomial xor (bitString[4] * x^7) R = 0 0 0 1 1 0 1 1 // remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial // i = 5 R = 0 0 0 1 1 0 1 1 // remainderPolynomial := remainderPolynomial xor (bitString[5] * x^7) R = 0 0 1 1 0 1 1 0 // remainderPolynomial := (remainderPolynomial * x) // i = 6 R = 1 0 1 1 0 1 1 0 // remainderPolynomial := remainderPolynomial xor (bitString[6] * x^7) R = 0 1 1 0 1 0 1 1 // remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial // i = 7 R = 1 1 1 0 1 0 1 1 // remainderPolynomial := remainderPolynomial xor (bitString[7] * x^7) R = 1 1 0 1 0 0 0 1 // remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial // i = 8 R = 0 1 0 1 0 0 0 1 // remainderPolynomial := remainderPolynomial xor (bitString[8] * x^7) R = 1 0 1 0 0 0 1 0 // remainderPolynomial := (remainderPolynomial * x)

Lze sice odkládat xor na poslední chvíli, ale lze jej provést i dříve a lze provést i xor pro 8 bitů (tedy pro celý bajt) zprávy najednou.

function crc(byte array string[1..len], int len) { remainderPolynomial := 0 for i from 1 to len { remainderPolynomial := remainderPolynomial xor polynomialForm(string[i]) * xn-8 for j from 1 to 8 { // Assuming 8 bits per byte if coefficient of xn-1 of remainderPolynomial = 1 { remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial } else { remainderPolynomial := (remainderPolynomial * x) } } } // A popular variant complements remainderPolynomial here return remainderPolynomial }

Odkazy

Reference

Související články

ECC * Reedovy-Solomonovy kódy * pevný disk * SSD * USB flash disk * VHD soubor * záchrana dat

Kategorie:Kontrolní součty