6
$\begingroup$

There are zillions of articles describing CRC. What can I read to (more deeply) understand 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 )

Improve this question
$\endgroup$

3 Answers 3

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ 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? $\endgroup$
    – Paŭlo Ebermann
    Sep 16, 2011 at 19:32
  • 2
    $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Sep 17, 2011 at 7:48
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Thomas Pornin
    Sep 22, 2011 at 16:24
0
$\begingroup$

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!

Improve this answer
$\endgroup$

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