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