CRC Checksums: Catching Errors With Polynomial Division

Treat your message as a polynomial

A CRC (cyclic redundancy check) does not add up bytes — it does polynomial division over GF(2), the two-element field where addition is XOR and there is no carrying. The message's bits become the coefficients of a binary polynomial M(x), and the sender divides it by a fixed generator polynomial G(x), agreed in advance, keeping only the remainder as the checksum:

transmitted = M(x) · x^r  XOR  remainder,  where remainder = [M(x)·x^r] mod G(x)
receiver recomputes the same division on the received bits;
remainder != 0  ⇒  error detected

r is the degree of G(x) — 8, 16 or 32 for the common presets — and the whole trick works because XOR-based polynomial division distributes over addition: the remainder of a corrupted message equals the remainder of the original message XOR the remainder of the error pattern alone. That means CRC's error-catching power depends entirely on which error patterns G(x) happens to divide evenly — get that wrong and errors slip through undetected; choose it well and specific classes of error are caught with certainty.

Why CRC-32 catches burst errors so reliably

A generator polynomial of degree r guarantees detection of every burst error of length ≤ r — a burst is any error confined to r or fewer consecutive bits, which is exactly the noise pattern a scratched disk, a fading radio channel or a corrupted memory cell tends to produce. CRC-32, the standard behind Ethernet frames, PNG/zip files and most storage systems, therefore catches all burst errors up to 32 bits with certainty, plus all single-bit and double-bit errors (if G(x) is chosen to have no factor of (x+1) shared incorrectly), plus any odd number of bit errors when G(x) contains the factor (x+1). What it cannot promise is catching every possible longer or specially crafted error pattern — a corruption that happens to be an exact multiple of G(x) produces a zero remainder and slips through silently.

CRC is not cryptographically secure

Because CRC is linear over GF(2), an attacker who can flip bits can compute exactly which additional bits to flip to leave the checksum unchanged — this is a two-line calculation, not a brute-force search. CRC therefore protects only against random noise, not against a deliberate adversary; TLS, code signing and password storage use SHA-2/SHA-3 or HMAC, which are designed so that no efficient algorithm can find a second message with a matching digest. Conflating the two is a real, recurring security bug — CRC-32 in a network protocol is an integrity check against transmission noise, never authentication.

The three common presets

CRC-8   (SMBus)     G(x) = x^8  + x^2 + x  + 1                    8-bit check, e.g. sensor buses
CRC-16  (CCITT)     G(x) = x^16 + x^12 + x^5 + 1                  16-bit, e.g. Bluetooth, XMODEM
CRC-32  (IEEE 802.3) G(x)= x^32+x^26+x^23+...+x^2+x+1 (0xEDB88320) 32-bit, e.g. Ethernet, zip, PNG

All three are implemented identically in hardware and software: shift the message through a linear-feedback shift register wired according to G(x)'s coefficients, or — far faster — precompute a 256-entry lookup table so each byte costs one table lookup and one XOR instead of eight shift-and-XOR steps. Every modern network card and storage controller computes CRC-32 in dedicated silicon because the operation happens on every single frame or sector that passes through it.

Detection, not correction

A CRC's remainder tells you that something changed, never what changed or where — there is no way to invert the division and recover the original bits from a non-zero remainder alone. That is a deliberate trade: a CRC uses only r extra bits to protect an arbitrarily long message, whereas an error-correcting code like Reed-Solomon or a Hamming code needs proportionally more redundancy to also pinpoint and fix the damaged bits. In practice the two are often layered together — Ethernet uses CRC-32 purely to detect a corrupted frame and then simply asks for a retransmission, rather than trying to correct it in place.

Frequently asked questions

Try it live

Everything above runs in your browser — open CRC Checksum and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.