CRC

Z Wikipedie, otevřené encyklopedie

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. CRC je vypočten před operací, u níž jsou předpokládány chyby. Je odeslán či uložen spolu s daty. Po převzetí dat je z nich nezávisle spočítán znovu. Pokud vyjde různý CRC, je přenos prohlášen za chybový. V určitých případech je možné chybu pomocí CRC opravit.

[editovat] Výpočet

Výsledkem CRC je zbytek po dvojkovém dělení bez přenášení bitů (místo odčítání se používá XOR). Dělí se vstupní data (zapsaná ve dvojkové soustavě) předem danou krátkou (délky n) posloupností binárních čísel reprezentujících koeficienty polynomu. Před samotným dělením je za vstupní data přidána posloupnost n nul.

CRC je založen na dělení v konečném tělese $G F (2 n)$ , tělese polynomů nad celými čísly modulo 2. Jednodušeji řečeno, je to množina polynomů, ve kterých jsou koeficienty čísla 1 a 0 a aritmetické operace jsou odpovídajícím způsobem upraveny. Například

$(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

Je tedy vidět, že zbytkem po dělení je v tomto případě -1. Nejnižším bitem tohoto čísla je tedy 1.

Každá posloupnost bitů může být interpretována jako posloupnost koeficientů polynomu výše uvedeného druhu. K nalezení CRC vydělíme tento polynom dalším, předem daným polynomem. Dělený polynom předtím vynásobíme $x n$ , kde $n$ je stupeň předem daného polynomu. Koeficienty polynomu, který představuje zbytek po dělení, jsou CRC.

Ve výše uvedeném dělení představuje $x 2 + x + 1$ vstupní data 111, $x + 1$ představuje klíč (předem daný polynom), a zbytek $1$ je CRC. Stupeň klíče je 1, takže jsme za vstupní data přidali jednu nulu a tím získali $x 3 + x 2 + x$ .

[editovat] Detekce chyb

Schopnost detekce chyb záleží na stupni klíče.
Jelikož je CRC založeno na dělení, nerozezná nadbytečné nuly za vstupními daty ani chybějící nuly na začátku vstupních dat.

Citováno z „http://cs.wikipedia.org../../../c/r/c/CRC_1a4b.html“

Kategorie: Počítače | Kryptografie