Tell me more ×
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.
up vote 5 down vote favorite

There are zillions of articles describing CRC. What can I ready to understand more deeply what's really going on? Both from an algebraic perspective and a bit-manipulation perspective, I'd like to understand it well enough to have an intuitive feel for it.

(Also see Brute forcing CRC-32 )

share|improve this question

3 Answers

up vote 7 down vote

You can have a look at the Wikipedia page on the mathematics of CRC. Among freely available resources, see also chapter 2 of the Handbook of Applied Cryptography.

The two main ways to view a CRC-32 are:

  • It is a linear operation in the vector space $\mathbb{Z}_2^{32}$. This means that the $CRC(A \oplus B) = CRC(A) \oplus CRC(B)$ ("$\oplus$" is XOR).

  • It is a reduction modulo a given polynomial in $\mathbb{Z}_2[X]$ (a polynomial of degree 32 for a CRC-32).

Either way, some background on linear algebra and finite field is what you need (i.e. enough math knowledge to recognize the two things I wrote above as a sufficient description of what is to know about CRC). I quite like this book: A Course in Number Theory and Cryptography; but I recognize that it has a relatively steep learning curve, and most of it is about interesting stuff which has little to do with CRC. I have heard a few good reports on that other book but I have not read it.

share|improve this answer
3  
A CRC-32 is a (linear) mapping from $\mathbb Z_2^*$ to $\mathbb Z_2^{32}$, not an operation in $\mathbb Z_2^{32}$, or am I understanding this wrong? – Paŭlo Ebermann♦ Sep 16 '11 at 19:32
1  
The CRCs used in practice are often different from that theoretical definition. They are linear in the weaker sense that $CRC(A \oplus B \oplus C) = CRC(A) \oplus CRC(B) \oplus CRC(C)$ for $A$, $B$, $C$ of identical length. The archetipal 16-bit and 32-bit CRCs used in telecoms are defined in CCITT recommendation V42, sections 8.1.1.6.1 and 8.1.1.6.2. Often, "CRC-32" means the later, minus the details on transparency bits. Variations abound in bit ordering, initialization, finalization, making the field a jungle. – fgrieu Sep 17 '11 at 7:48
up vote 2 down vote

I recently posted an answer describing CRC computations on the math.stackexchange site. It discusses the basics of CRC-16 minus the bells and whistles mentioned in fgrieu's comment, but with minor modifications, applies to CRC-32 as well. Incidentally, CRC-32 uses a degree 32 polynomial, not a degree 33 polynomial as stated in Thomas Pomin's answer.

share|improve this answer
Oh yes, indeed. Degree 32, 33 coefficients because we being at 0. One day I will learn how to count properly. Thanks ! I'll correct it immediately. – Thomas Pornin Sep 22 '11 at 16:24
up vote 0 down vote

If you have the time to spend to really understand CRC's, I would recommend learning from an Error-Correction Coding book. CRC's and (cyclic) Error Correction codes are intimately related, and I've found that in all the literature I've seen, Error Correction Coding texts are the gentlest and most-direct way to learn the math background (linear algebra and finite fields) you need to understand CRC's.

And as a special bonus, you get the math background for AES for free as well!

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.