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 odahlení 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 kryptovací algoritmy.

[editovat] Ekvivalence polynomů a bitových posloupností

Například posloupnost bitů "100101" může být přepsá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 tělese $G F (2 n)$ :

(x 5 + x 2 + 1) + (x 5 + x 4 + x + 1) = 2 x 5 + x 4 + x 2 + x + 2 = 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ů.

[editovat] Výpočet CRC

Výsledek výpočtu CRC je určen vstupní posloupností bitů a zvoleným klíčem (což je také posloupnost bitů). Když vstupní posloupnost a klíč interpretujeme jako polynomy nad tělesem $G F (2 n)$ , pak CRC je zbytek po dělení polynomu vstupní posloupnosti polynomem klíče. 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$ ).

CRC je tedy 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ů, jejichž koeficienty mohou nabývat pouze hodnot 0 a 1. 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 $x 3 + x 2 + x$ vstupní bitovou posloupnost "1110", $x + 1$ představuje klíč (jeho bitová posloupnost je "11", jeho stupeň je 1), zbytkem po dělení je polynom $1$ . Hodnota CRC odpovídá zbytku po dělení převedeném na bitovou posloupnost, v tomto případě tedy jde o hodnotu "1".

[editovat] Detekce chyb

Schopnost detekce chyb záleží na volbě klíče. Při správné volbě hodnoty mají delší klíče lepší schopnost detekce chyb.
Protože CRC je založeno na dělení, nerozezná přidané nuly na začátku vstupních dat. Proto se někdy při výpočtu CRC před vstupní data dává jednička.
Někdy se při výpočtu 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é.
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ě.
Čí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"? 1081 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 12. stupně! Řídící polynom má v tomto případě tedy hodnotu $x 16 + x 12 + x 7 + 1$ .

Kategorie: Kódování

Cyklický redundantní součet v jiných jazycích: Български, Català, Deutsch, English, Español, Euskara, Suomi, Français, עברית, Bahasa Indonesia, Italiano, 日本語, 한국어, Nederlands, Polski, Português, Русский, Simple English, Slovenčina, Svenska, Tiếng Việt, 中文

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/Cyklick%C3%BD_redundantn%C3%AD_sou%C4%8Det“
Stránka byla naposledy upravena v Stránka byla naposledy editována 16. 8. 2008 v 18:37.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).