Cyclic redundancy check

From Exampleproblems

A cyclic redundancy check (CRC) is a type of hash function used to produce a checksum - which is a small number of bits - against a byte or a larger block of data, such as a packet of network traffic or a block of a computer file. The checksum is used to detect and correct errors after transmission or storage. A CRC is computed and appended before transmission or storage, and verified afterwards by recipient to confirm that no changes occurred on transit. Correction can also be done if information lost is lower than information held by the checksum. CRCs are popular because they are simple to implement in binary hardware, are easy to analyze mathematically, and are particularly good at detecting common errors caused by noise in transmission channels.

1 Introduction
2 Polynomials and types
3 Polynomial CRC Specifications [ITU-IEEE Syntax]
4 CRCs and data integrity
5 Computational costs of CRCs vs Hashes
- 5.1 See also
6 External links

Introduction

CRCs are based on division in a commutative ring, namely the ring of polynomials over the integers modulo 2. In simpler terms, this is the set of polynomials where each coefficient is only one bit, and arithmetic operations wrap around. For example:

(x 2 + x) + (x + 1) = x 2 + 2 x + 1 = x 2 + 1

Two becomes zero because 2 is 10 in binary, and we discard all bits except the last one. Multiplication is similar:

(x 2 + x)(x + 1) = x 3 + 2 x 2 + x = x 3 + x

We can also divide polynomials mod 2 and find the quotient and remainder. For example, suppose we're dividing x³ + x² + x by x + 1. We would find that

x 3 + x 2 + x = (x + 1)(x 2 + 1) - 1 = (x + 1)(x 2 + 1) + 1.

In other words, the division yields a quotient of x² + 1 with a remainder of -1, which, since it is odd, has a last bit of 1.

Any string of bits can be interpreted as the coefficients of a polynomial of this sort, and to find the CRC, we divide by another fixed polynomial. The coefficients of the remainder polynomial are the CRC, and there are simple, efficient algorithms for computing this remainder, such as the one shown below. CRCs are often referred to as "checksums," but such designations are not strictly accurate since, technically, a checksum is calculated through addition and not through division as is the case with CRCs.

The main portion of the algorithm can be expressed in pseudocode as follows:

 function crc(bit array bitString[1..len], int polynomial) {
     shiftRegister := initial value // commonly all 0 bits or all 1 bits
     for i from 1 to len {
         if most significant bit of shiftRegister xor bitString[i] = 1 {
             shiftRegister := (shiftRegister left shift 1) xor polynomial
             least significant bit of shiftRegister = 1
         } else
             shiftRegister := (shiftRegister left shift 1)
     }
     return shiftRegister
 }

Note: A common speedup uses a lookup table indexed by multiple most-significant bits of the shiftRegister to process multiple bits at once. A 256-entry lookup table is a particularly common choice.

There are two variations which can be applied to the above implementation; applying one or both gives a total of four equivalent ways to compute a checksum:

The shiftRegister can be reversed, so its least-significant bit is tested and it is shifted to the right by 1 bit each step. This requires a polynomial with its bits reversed, and produces a bit-reversed result. This variant is actually the one most commonly in use.
Instead of changing multiple bits in the shiftRegister based on the xor of one bit of the shiftRegister and one bit of the bitString, it is possible to xor (compute the parity of) all the bits of the shiftRegister selected by the polynomial and the bitString and add that single bit to the shiftRegister. With suitable adjustments to the polynomial, this also produces the same remainder. This variation is difficult in software, but used in some hardware implementations, and is often used when describing the close relative to a CRC, the linear feedback shift register.

The specific CRC is defined by the polynomial used. To produce an n-bit CRC requires a degree-n polynomial, of the form xⁿ + … + 1. This is naturally expressed as an n+1-bit string, but the leading (xⁿ) term is normally implicit, leaving an n-bit string Thus, depending on the bit-order convention used, the standard CRC-16, x¹⁶+x¹⁵+x²+1, will be represented as the hexadecimal number 0x8005 or as 0xa001.

One of the most commonly encountered is known as CRC-32, used by (among others) Ethernet, FDDI, PKZIP, WinZip, and PNG. Its polynomial can be written 0x04C11DB7 or 0xEDB88320.

Polynomials and types

There are many more CRC types than indicated here.

at least 5 separate versions of CRC-16, CRC-32 and CRC-64 are existent and in common use
CRC-64, CRC-128 and CRC-256 exist and are standardized but are not in common use
CRCs greater than CRC-32 have been replaced by hash functions like MD2, MD4 and MD5 in modern telecommunications, data storage and authentication practices
the current state of the art in hash functions is SHA-1, WHIRLPOOL-512 (and others in development and testing)

Polynomial CRC Specifications [ITU-IEEE Syntax]

CRC-1	x + 1 (Used in hardware, also known as parity bit)
CRC-7	x^7 + x^3 + 1 [used in some telecom systems]
CRC-8-Fletcher	A := A + D[i], B := B + A
CRC-8	x⁸ + x² + x + 1
CRC-12	$x 12 + x 11 + x 3 + x + 1$ [used in telecom systems]
CRC-16-Fletcher	(A basis for CRC-16 Adler)
CRC-16-Adler_A	[A = 1 + D₁ + D₂ + ... + D_n (mod 65521)]
CRC-16-Adler_B	[B = n×D₁ + (n-1)×D₂ + (n-2)×D₃ + ... + D_n + n (mod 65521)]
CRC-16-CCITT	x¹⁶ + x¹² + x⁵ + 1
CRC-16-IBM	x¹⁵ +x¹⁴ + x¹⁰ + x⁸ + x¹ + 1
CRC-32-Adler	[Adler-32(D) = B × 65536 + A]
CRC-32-IEEE 802.3	x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1
CRC-32C (Castagnoli)	x³² + x²⁸ + x²⁷ + x²⁶ + x²⁵ + x²³ + x²² + x²⁰ + x¹⁹ + x¹⁸ + x¹⁴ + x¹³ + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁶ + 1
CRC-64-ISO	$x 64 + x 4 + x 3 + x + 1$ (as described in ISO 3309)
CRC-64-ECMA-182	$x 64 + x 62 + x 57 + x 55 + x 54 + x 53 + x 52 + x 47 + x 46 + x 45 + x 40 + x 39 + x 38 + x 37 + x 35 + x 33 + x 32 + x 31 + x 29 + x 27 + x 24 + x 23 + x 22 + x 21 + x 19 + x 17 + x 13 + x 12 + x 10 + x 9 + x 7 + x 4 + x + 1$ (as described in ECMA-182 p.63)
CRC-128	(IEEE? / ITU?)

Adler-32 Note: D is the string of bytes for which the checksum is to be calculated, and n is the length of D.

CRCs and data integrity

While useful for error detection, CRCs cannot be safely relied upon to verify data integrity (that no changes whatsoever have occurred), since, because of the linear structure of CRC polynomials, it is extremely easy to intentionally change data without modifying its CRC. Cryptographic hash functions can be used to verify data integrity.