Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

closed as off-topic by e-sushi Jun 17 at 22:17

  • This question does not appear to be about cryptography within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

1  
Did you read this link, it seems to be just what you are looking for: en.wikipedia.org/wiki/Mathematics_of_CRC. – Thomas Jul 29 '12 at 11:04
    
@Thomas, yes but this does not help, thank you though. – user2558 Jul 29 '12 at 11:09
2  
    
I'm voting to close this question as off-topic because it is about a non-cryptographic checksum function. – e-sushi Jun 17 at 22:17
up vote 6 down vote accepted

I guess that CRC 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}+\Sigma_{i=n}^{n+31}{x^i}+\Sigma_{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.
share|improve this answer