Finding CRC collisions for specific divisor

1
votes

My current textbook (Information Security: Principles and Practice by Mark Stamp) discusses how to determine the CRC of data via long-division, using XOR instead of subtraction to determine the remainder.

If our divisor has N-bits, we append (N-1) 0 bits to the dividend (the data) and then use long-division with XOR to solve for the CRC.

For example:

Divisor: 10011
Dividend: 10101011

101010110000 / 10011 = 10110110 R 1010, where 1010 = CRC

I'm able to perform this computation fine. However, the book mentions that in the case of the divisor being 10011, it's easy to find collisions.

I'm missing something here -- why is it easier to find a collision when the divisor is 10011?

1
algorithmcrc

1 Answers

0
votes

See http://en.wikipedia.org/wiki/Cyclic_redundancy_check#Designing_CRC_polynomials for more details.

10011 corresponds to polynomial x^5+x+1 which is irreducible. And, using such codes decreases the chance of collisions.