Tento článek potřebuje doplnit či upravit literaturu.

Můžete Wikipedii pomoci tím, že na konec článku přidáte (resp. upravíte) kapitolu Literatura a uvedete vhodné knihy, ze kterých lze o daném tématu čerpat více informací. Knihy by měly být uváděny standardní formou citace.

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 ${\displaystyle x^{5}+x^{2}+1}$, posloupnost bitů „110011“ může být přepsána jako polynom ${\displaystyle 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 ${\displaystyle x^{4}+x^{2}+x}$.

Stejný výsledek dostaneme při sčítání polynomů v konečném tělese ${\displaystyle GF(2^{n})}$:

${\displaystyle (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 ${\displaystyle M(x)}$) a zvoleným klíčem (což je také posloupnost bitů, polynom ${\displaystyle G(x)}$). Když vstupní posloupnost a klíč interpretujeme jako polynomy nad tělesem ${\displaystyle GF(2^{n})}$, pak CRC je zbytek po dělení (polynom ${\displaystyle R(x)}$) 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 ${\displaystyle 1-1/2^{16}\approx 0,999985}$).

CRC je tedy založen na dělení v konečném tělese ${\displaystyle 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. 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.

${\displaystyle (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é:

${\displaystyle (x^{2}+x)(x+1)=x^{3}+2x^{2}+x\equiv x^{3}+x}$

Můžeme také dělit polynomy modulo 2. Například

${\displaystyle {\frac {x^{3}+x^{2}+x}{x+1}}=(x^{2}+1)-{\frac {1}{x+1}}}$

To lze přepsat jako

${\displaystyle (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 ${\displaystyle M(x)=x^{3}+x^{2}+x}$ vstupní bitovou posloupnost „1110“, ${\displaystyle G(x)=x+1}$ představuje klíč (jeho bitová posloupnost je „11“, jeho stupeň je 1), zbytkem po dělení je polynom ${\displaystyle 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, ${\displaystyle G(x)}$). Při správné volbě hodnoty mají delší klíče lepší schopnost detekce chyb.
• Čí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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 87₁₀ nebo šestnáctkově 57₁₆. Tato hodnota může být odeslána dvěma způsoby, čemuž odpovídají dva různé polynomy ${\displaystyle M(x)}$. V případě, že nejvýznamnější bit (MSB) bude první (vlevo), bude ${\displaystyle M(x)=x^{6}+x^{4}+x^{2}+x+1}$ = 01010111. V případě prvního LSB (nejméně významný bit) bude ${\displaystyle M(x)=x^7+x^6+x^5+x^3+x}$Zdroj:https://cs.wikipedia.org?pojem=Cyclic_redundancy_check
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.