The Mighty CRC

Prof Bill Buchanan OBE FRSE
4 min readNov 7, 2024

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:

--

--

Prof Bill Buchanan OBE FRSE
Prof Bill Buchanan OBE FRSE

Written by Prof Bill Buchanan OBE FRSE

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. Based in Edinburgh. Old World Breaker. New World Creator. Building trust.