(thing) by yerricde Tue Feb 12 2002 at 0:59:06

The cyclic redundancy check (CRC for short) computes a check word for a bit string by using multiplication and addition in a finite field of p = 2. CRC has more resistance to multiple errors than a simple sum of the bytes in the string; an n-bit CRC can detect all errors of up to n - 1 bits but cannot correct any error. However, because it is a linear function of the input string, it reveals more information about the source string than MD5 or SHA-1 does, and it should not be used for storing passwords. The state of the least significant bit after each step of a CRC given the sequence [1, 0, 0, 0, 0, 0, ...] is equivalent to the output of a linear feedback shift register.

The most commonly used polynomial for 32-bit CRC, used in such applications as PKZIP, Ethernet, and FDDI, is 0x04C11DB7.

As 0mnidirecti0nal Hal0 mentioned, computing a CRC is similar to long division: 

 shiftreg = initial value (commonly 0)
 while bits remain in string:
   if MSB of shiftreg is set:
     shiftreg = (shiftreg shl 1) xor polynomial
   else:
     shiftreg = shiftreg shl 1
   xor next bit from the string into LSB of shiftreg
 output shiftreg

Use of a lookup table containing the CRC of all bytes allows an eight-fold speedup in the algorithm.

References

  • http://www.4d.com/ACIDOC/CMU/CMU79909.HTM
I like it!