5
$\begingroup$

I want to calcuate the CRC32 algorithm using polynomials directly but I don't know how. I found the generating polynomial listed here https://en.wikipedia.org/wiki/Cyclic_redundancy_check. This corresponds to 0xedb88320 in the example code.

Can someone please define a mathematical specification that calculates the same result as this algorithm?

$\endgroup$
  • 1
    $\begingroup$ Did you read this link, it seems to be just what you are looking for: en.wikipedia.org/wiki/Mathematics_of_CRC. $\endgroup$ – Thomas Jul 29 '12 at 11:04
  • $\begingroup$ @Thomas, yes but this does not help, thank you though. $\endgroup$ – user2558 Jul 29 '12 at 11:09
  • 2
    $\begingroup$ Does "A Painless Guide to CRC Error Detection Algorithms" help? $\endgroup$ – David Cary Jul 30 '12 at 16:28
  • $\begingroup$ I'm voting to close this question as off-topic because it is about a non-cryptographic checksum function. $\endgroup$ – e-sushi Jun 17 '16 at 22:17
6
$\begingroup$

The most common CRC32 is borrowed from the 32-bit Frame Check Sequence in the 1988 edition of CCITT V.42, section 8.1.1.6.2, available here, which gives a mathematical definition (note: remove the obviously spurious $1$ after $x^{30}$ in the English edition).

I prefer this alternate definition with some of the math on polynomial replaced by equivalent operations on bits:

  1. Consider the message as a sequence of $n$ bits in chronological order (if the message is structured in words or bytes: with low-order bit first unless otherwise specified).
  2. Append $32$ one bits, forming a sequence of $n+32$ bits.
  3. Complement the first $32$ bits of that sequence.
  4. Form the binary polynomial of degree (at most) $n+31$, with term $x^{n+32-j}$ present (resp. absent) when the $j$th bit in the result of the previous step is one (resp. zero), for $j$ with $0<j\le n+32$.
  5. Compute the remainder of the polynomial division of that polynomial by the binary polynomial $x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x+1$, forming a binary polynomial of degree (at most) $31$.
  6. Form the $32$-bit sequence with the $j$th bit one (resp. zero) when the term $x^{32-j}$ is present (resp. absent) in that polynomial, for $j$ with $0<j\le 32$.
  7. Append that $32$-bit sequence to the ORIGINAL message (if it is to be converted to bytes: the first bit of that sequence shall be the low-order bit of the first byte unless otherwise specified).

Note: Inserting $32$ bits at step 2 allows a receiver to process bits of the message and $32$-bit sequence uniformly as they are being received, without knowing the frontier between the message and the final 32-bit sequence until after the end of that sequence. Step 3 makes it likely that suppression of bits in the message is detected including for zero bits at the beginning of the message.

Note: In term of binary polynomials (according to the conventions in steps 4 and 6), the combination of steps 2 and 3 changes $M(x)$ to $M(x)\cdot x^{32}+\displaystyle\sum_{i=n}^{n+31}{x^i}+\sum_{i=0}^{31}{x^i}$.

Note: Steps 4, 5 and 6 can be replaced by:

  • repeat until the sequence has exactly 32 bits:
    • if the first bit is one:
      • complement the 7th, 10th, 11th, 17th, 21th, 22th, 23th, 25th, 26th, 28th, 29th, 31th, 32th and 33th bit.
    • remove the first bit.
$\endgroup$