Cyklický redundantní součet

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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í[editovat | editovat zdroj]

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

Stejný výsledek dostaneme při sčítání polynomů v tělese :

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[editovat | editovat zdroj]

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


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

Ze dvojky se v tomto případě stane 0, protože operace nad koeficienty se provádí modulo 2. Násobení je podobné:

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

To lze přepsat jako

Ve výše uvedeném dělení představuje vstupní bitovou posloupnost "1110", představuje klíč (jeho bitová posloupnost je "11", jeho stupeň je 1), zbytkem po dělení je polynom . 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[editovat | editovat zdroj]

  • Schopnost detekce chyb záleží na volbě klíče (též generující polynom, ). 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 ).
  • 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 .
  • 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 . 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 (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[editovat | editovat zdroj]

Předpokládejme 8-bitové CRC s generujícím polynomem , což odpovídá 9-bitovému řetězci "100000111".

Cílem je spočíst CRC pro 8-bitovou 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 . V případě, že nejvýznamnější bit (MSB) bude první (vlevo), bude = 01010111. V případě prvního LSB (nejméně významný bit) bude = 11101010.

Před vlastním výpočtem je doplněn zprava osmi nulovými bity. Výpočet zbytku po dělení polynomu polynomem 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 (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 , což lze šestnáctkově zapsat jako A216. V případě prvního LSB je zbytkem po dělení , což lze zapsat šestnáctkově jako 1916, ovšem za předpokladu, že LSB je první.

Implementace[editovat | editovat zdroj]

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.

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. 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 proé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[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]


Související články[editovat | editovat zdroj]