The Mighty CRC

The more I work in cryptography, the more I see the cross-over into areas of data communications. For example, in post quantum key exchange, we see the usage of the McEliece method, and which uses data coding methods for its implementation. Also, lattice methods use polynomial representations for its operation. So let’s have a look at some error detection in data communications.

There’s a little method that has been working away in the background and protecting our data like little else. This is CRC: Cyclic Redundancy Check. Overall, it is simple, easy to implement, and effective for most of the typical errors we have in data. With error checking, we can either have error detection or error correction.

For error detection, we are able to detect that there are one or more bits in error in a communication, whereas with error correction, we can not only determine if there are errors in the communication but correct the bits that are in error. Obviously, an error correction code will be larger in size and more complex. But, for most circumstances, we just need to determine if there is an error in our transmission, and request a re-transmission from the send.

The basic idea of a CRC can be illustrated using an example. Suppose the transmitter and receiver were both to agree that the numerical value sent by the transmitter would always be divisible by 9. Then, should the receiver get a value which was not divisible by 9, would it know that there had been an error? For example, if a value of 32 were to be transmitted, it could be changed to 320 so that the transmitter would be able to add to the least significant digit, making it divisible by 9. In this case, the transmitter would add 4, making 324. If this transmitted value were to be corrupted in transmission, then there would only be a 10% chance that an error would not be detected.

CRC

With CRC we have a generator polynomial which will divide into a received value. If we receive a remainder of zero, we can determine there are no errors. We must then calculate the required remainder from a modulo-2 divide and add this to the data, in order that the remainder will be zero when we perform the divide.

Let’s take an example. For a 7-bit data code 1001100, determine the encoded bit pattern using a CRC-generating polynomial of P(x)=x³+x²+1.

P(x)=x³+x²+1 (1101)

G(x)=x⁶+x³+x² (1001100)

Multiply by the number of bits in the CRC polynomial:

x³(x⁶+x³+x²) = x⁹+x⁶+x⁵ (1001100000)

We then divide and determine the remainder (Figure 1). The result is “001”, so the transmitted message is thus:

1001100001

Figure 1

Example

For example G(x) is 1001100 and P(x) is 1101:

Binary form:    1001100  divided by  1101

x**6+x**3+x**2
x**3+x**2+1
Binary form (added zeros):      1001100000  divided by  1101
Result is       1111101
Remainder is    001
Working is
   1111101
----------
1001100000
1101
----
 100100000
 1101
 ----
  10000000
  1101
  ----
   1010000
   1101
   ----
    111000
    1101
    ----
     01100
     0000
     ----
      1100
      1101
      ----
       001
Transmitted value is:   10011001111101

C:\Python27>python crc_div.py
Binary form:    1001100  divided by  1101
x**6+x**3+x**2
x**3+x**2+1
Binary form (added zeros):      1001100000  divided by  1101
Result is       1111101
Remainder is    001
Working is
   1111101
----------
1001100000
1101
----
 100100000
 1101
 ----
  10000000
  1101
  ----
   1010000
   1101
   ----
    111000
    1101
    ----
     01100
     0000
     ----
      1100
      1101
      ----
       001
Transmitted value is:   1001100001

The following gives an outline of the code:

import struct
import sys

val1="1001100"
val2="1101"

if (len(sys.argv)>1):
        val1=str(sys.argv[1])
if (len(sys.argv)>2):
        val2=str(sys.argv[2])

def showpoly(a):
 str1 = ""
 nobits = len(a)

     for x in range (0,nobits-2):
  if (a[x] == '1'):
   if (len(str1)==0):
    str1 +="x**"+str(nobits-x-1) 
   else: 
    str1 +="+x**"+str(nobits-x-1)
 if (a[nobits-2] == '1'):
  if (len(str1)==0):
   str1 +="x"
  else:
   str1 +="+x"
 if (a[nobits-1] == '1'):
  str1 +="+1"
 print str1;
 
def toList(x):
 l = []
 for i in range (0,len(x)):
  l.append(int(x[i]))
 return (l)
def toString(x):
 str1 =""
 for i in range (0,len(x)):
  str1+=str(x[i])
 return (str1)
def divide(val1,val2):
 a = toList(val1)
 b = toList(val2)
 working=toString(val1)+"\n"
 res=""
 addspace=""
 while len(b) <= len(a) and a:
      if a[0] == 1:
          del a[0]
          for j in range(len(b)-1):
               a[j] ^= b[j+1]
          if (len(a)>0):
    working +=addspace+toString(b)+"\n"
    working +=addspace+"-" * (len(b))+"\n"
    addspace+=" "
    working +=addspace+toString(a)+"\n"
    res+= "1"
  else:
          del a[0]
   working +=addspace+"0" * (len(b))+"\n"
   working +=addspace+"-" * (len(b))+"\n"
   addspace+=" "
   working +=addspace+toString(a)+"\n"
          res+="0"

 print "Result is\t",res
 print "Remainder is\t",toString(a)
 print "Working is\t\n\n",res.rjust(len(val1)),"\n",
 print "-" * (len(val1)),"\n",working
 return toString(a)
print "Binary form:\t",val1," divided by ",val2
print ""
showpoly(val1)
showpoly(val2)
strzeros=""
strzeros = strzeros.zfill(len(val2)-1)
val3=val1+strzeros
print ""
print "Binary form (added zeros):\t",val3," divided by ",val2
res=divide(val3,val2)
print "Transmitted value is:\t",val1+res

CRC-32

CRC is one of the most reliable error detection schemes and can detect up to 95.5% of all errors. The most commonly used code is the CRC-32 standard code, which is defined by the CCITT and will give a 32-bit CRC signature (8 hex characters). This checksum is normally appended to the data and then checked when the data is read. If the CRC-32 check differs from the stored value, there is likely to be an error in the data. [Theory]. Some sample code is here:

CRC-32