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. 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. 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)-{\frac {1}{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.
• Čí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 87₁₀ nebo šestnáctkově 57₁₆. Tato hodnota může být odeslána dvěma způsoby, čemuž odpovídají dva různé polynomy $M(x)$. 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ř. 1 + 1 = 0; 0 − 1 = 1),
• nezajímá nás podíl, ale pouze zbytek po dělení.

MSB první

LSB první

0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0

1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0

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 A2₁₆. 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 19₁₆, 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. 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..n])   // 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ř. rem = (msb(rem)) ? ((rem<<1 + bit) xor gen) : (rem<<1 + bit);). 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 ^[zdroj?].

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. 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^[zdroj?]. 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

Související články

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

Portály: Internet