Take the 2-minute tour ×
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.

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
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  
add comment

1 Answer 1

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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.