Který polynom — a co doopravdy zaručuje
Tohle je ta část, kvůli které se CRC používá místo součtu. Nejsou to statistiky — jsou to záruky, které plynou z toho, jak je polynom postavený.
Tři záruky, které platí vždycky
- Každý shluk chyb do délky n bitů se pozná. Ne „skoro vždycky“ — vždycky. Shluk kratší než polynom nemůže být jeho násobkem, a jen násobek projde.
- Každý lichý počet převrácených bitů se pozná, pokud je polynom dělitelný (x + 1). To se u používaných polynomů hlídá právě proto.
- Dvě libovolně vzdálené chyby se poznají, dokud je zpráva kratší než perioda polynomu — u dobrých CRC-32 je to přes čtyři miliardy bitů.
shluk = n + 1 bitů → projde s pravděpodobností 2−nCRC šířky n
Ta druhá řádka je taky užitečná: shluk delší než šířka projde s pravděpodobností 2−n. U CRC-16 to je jednou z 65 536, u CRC-32 jednou ze čtyř miliard. To není nula, a v protokolech, kde je bezpečnost součástí zadání, se s tím počítá — proto mají bezpečnostní varianty průmyslových sběrnic kontrolu navíc nad tou, kterou má linka.
Jak se pozná dobrý polynom
Ne každé číslo se hodí. Podstatná je Hammingova vzdálenost: nejmenší počet převrácených bitů, který projde nepoznaně. Polynom s HD = 4 do určité délky zprávy pozná každou trojici chyb — a ta délka je součástí zadání, protože nad ní záruka končí.
Toho je dobré si všimnout: záruka polynomu závisí na délce zprávy. CRC-32 v Ethernetu má HD = 4 do 11 450 bitů, což pokrývá celý rámec; u delší zprávy klesne na HD = 3. Proto se nedá vzít CRC z jednoho protokolu a nasadit na zprávy jiné délky s tím, že „to je stejné CRC“.
Co CRC NENÍ
CRC není zabezpečení. Chrání proti šumu, ne proti útočníkovi. Kdo zprávu mění schválně, si spočítá nové CRC — je to veřejný, deterministický a levný výpočet. Na integritu proti záměrné změně slouží kryptografický otisk s klíčem, a to je jiná úloha i jiná matematika.
A CRC neopravuje. Řekne „tohle je vadné“, ne „tady je chyba“. Oprava se dělá buď zopakováním (což stojí čas), nebo samoopravným kódem, který stojí místo. Volba mezi tím je zadání, ne technikálie: ve smyčce, která běží každou milisekundu, není na opakování čas.