Zyklische Redundanzprüfung

Die zyklische Redundanzprüfung (engl. cyclic redundancy check, daher meist CRC, selten ZRP) ist ein Verfahren (bzw. eine bestimmte Klasse von Verfahren) aus der Informationstechnik zur Bestimmung eines Prüfwerts für Daten (z. B. Datenübertragung in Rechnernetzen oder eine Datei), um Fehler bei der Übertragung oder Duplizierung von Daten erkennen zu können.

Vor Beginn der Übertragung bzw. Kopie eines Blocks der Daten wird ein CRC-Wert berechnet. Nach Abschluss der Transaktion wird der CRC-Wert erneut berechnet. Anschließend werden diese beiden Prüfwerte verglichen. CRC ist so ausgelegt, dass Fehler bei der Übertragung der Daten, wie sie beispielsweise durch Rauschen auf der Leitung verursacht werden könnten, fast immer entdeckt werden.

CRC-Werte können jedoch nicht die Integrität der Daten bestätigen. D. h., es ist verhältnismäßig leicht, durch beabsichtigte Modifikation einen Datenstrom zu erzeugen, der den gleichen CRC-Wert wie eine gegebene Nachricht hat. Wenn eine solche Sicherheit gefordert ist, müssen kryptografische Hash-Funktionen wie z. B. MD5 zum Einsatz kommen.

Verfahren

CRC beruht auf Polynomdivision: Die Folge der zu übertragenden Bits wird als dyadisches Polynom betrachtet. Beispiel: Die Bitfolge 10011101 entspricht dem Polynom

$1x^{7}+0x^{6}+0x^{5}+1x^{4}+1x^{3}+1x^{2}+0x^{1}+1x^{0}=x^{7}+x^{4}+x^{3}+x^{2}+1$

Die Bitfolge der Coderepräsentation der Daten wird durch ein vorher festzulegendes Generatorpolynom (das CRC-Polynom) mod 2 dividiert, wobei ein Rest bleibt. Dieser Rest ist der CRC-Wert. Bei der Übertragung des Datenblocks hängt man den CRC-Wert an den originalen Datenblock an und überträgt ihn mit.

Um zu verifizieren, dass die Daten keinen Fehler beinhalten, wird der empfangene Datenblock mit angehängtem CRC-Wert als Binärfolge interpretiert, erneut durch das CRC-Polynom mod 2 geteilt und der Rest ermittelt. Wenn kein Rest bleibt, ist entweder kein Fehler aufgetreten oder es ist ein Fehler aufgetreten, der in Polynomdarstellung das CRC-Polynom als Faktor hat.

Die Datenübertragung erfordert bestimmte unerlässliche Übereinkommen. Zum einen muss dem Empfänger bewusst sein, dass überhaupt eine gesicherte Übertragung der Ursprungsdaten stattfinden soll. An der Art des eintreffenden Datenstromes allein ist dies nicht zu erkennen. Des Weiteren muss der Empfänger dasselbe CRC-Polynom und Rechenverfahren benutzen wie der Sender. Und schließlich muss der Empfänger die Information besitzen, wo im Datenstrom sich die zusätzlich zu den Daten übertragene Prüfsumme befindet.

Beispiel

Es folgt ein Beispiel mit einem Code 9-ten Grades. Das Generatorpolynom lautet 10011 ( $1x^{4}+0x^{3}+0x^{2}+1x^{1}+1x^{0}$ ) und ist somit 4-ten Grades. Der zu übertragenden Bitfolge, Rahmen (engl. frame) genannt, wird eine Kette aus Nullen entsprechend des Grades des Generatorpolynoms angehängt (Rahmen mit Anhang).

Generatorpolynom:	10011
Rahmen:	1101011011
Rahmen mit Anhang:	11010110110000 (das Generatorpolynom hat r-Stellen, also werden r-1 Nullen ergänzt; hier ist r=5)

Nun wird der Rahmen mit Anhang von links her durch das Generatorpolynom dividiert. Dabei wird ausschließlich das exklusive OR (XOR) verwendet. Wenn man stellenweise dividiert wird also aus 11010 durch 10011: 01001 (0 xor 0 = 0; 0 xor 1 = 1; 1 xor 0 = 1; 1 xor 1 = 0). Es folgt das vollständige Beispiel:

11010110110000
10011 <- immer mit der ersten gemeinsamen 1 anfangen (auch wenn der Rahmen z.B. mit 1000 beginnen
         würde und somit kleinwertiger wäre als das Generatorpolynom)
-----
 10011
 10011
 -----
  000010110
      10011 
      -----
       010100
        10011
        -----
         01110 (Rest)

Die vorher angehängte Null-Kette wird nun durch den Rest ersetzt:

übertragener Rahmen: 11010110111110

Diese Nachricht kann jetzt z.B. über ein Netzwerk übertragen werden. Wenn die Nachricht beim Empfänger eintrifft, kann dieser überprüfen, ob sie korrekt angekommen ist.

Durch Division durch das Generatorpolynom kann jetzt die fehlerhafte Übertragung erkannt werden:

Ein Beispiel für eine fehlerhafte Nachricht:	11110110111110
Das Generatorpolynom (wie oben):	10011

11110110111110
10011
-----
 11011
 10011
 -----
  10001
  10011
  -----
   0010011
     10011
     -----
      00001110

Der Rest der Division (1110) ist ungleich Null. Also ist ein Fehler aufgetreten. Bei der Überprüfung auf Richtigkeit können folgende Fälle auftreten:

Der Rest der Division ist Null und die Nachricht ist richtig.
Der Rest der Division ist Null und die Nachricht ist fehlerhaft (dieser Fall kann durchaus vorkommen, wenn die Nachricht an mehreren Stellen verfälscht wird).
Der Rest der Division ist ungleich Null und die Nachricht ist fehlerhaft.

Implementierung

Das CRC-Verfahren lässt sich sowohl in einfachen Hardware-Bausteinen als auch in Software realisieren. Verwendet wird ein

Schieberegister mit n Bits (etwa ein 32 Bit Schieberegister bei CRC-32) und ein
Bit-Datenstrom (String) beliebiger Länge.

Pseudo-Code des Algorithmus, höchstwertiges Bit ganz links:

Schieberegister := 0000... (Startwert)
solange Bits im String verbleiben:
  falls das am weitesten links stehende Bit vom Schieberegister 
        ungleich zum nächsten Bit aus dem String ist:
    Schieberegister := (Schieberegister linksschieben um 1, rechtes Bit 0) 
                      xor CRC-Polynom
  andernfalls:
    Schieberegister := Schieberegister linksschieben um 1, rechtes Bit 0
Schieberegister enthält das Ergebnis

Durch Verwendung einer Tabelle, die etwa bei einer CRC-8 für jedes der 256 möglichen Bytes den zugehörigen CRC-Wert enthält, lässt sich obiger Algorithmus auf das achtfache beschleunigen.

Die Operationen Linksschieben und Exklusiv-Oder machen die CRC hervorragend geeignet zur Verwendung in Logikschaltungen. Die CRC eines Datenstroms kann bitweise (oder auch Byte-weise usf.) berechnet und vom Sender an die Daten angehängt werden. Der Empfänger des Datenstroms kann den CRC genauso wie der Sender berechnen, jedoch unter Einbeziehung des CRC. Das Ergebnis inklusive des CRC muss dann gleich Null sein, sonst enthält der Strom Bitfehler.

CRC-Typen werden oft anhand des als Divisor verwendeten Polynoms unterschieden (im Hexadezimal-Format). Eines der meistverwendeten CRCs (u. a. von Ethernet, FDDI, ZIP und PNG benutzt) ist das Polynom 0x04C11DB7, bekannt als CRC-32. Es stellte sich heraus, dass einige Polynome „besser“ schützen als andere. Für CRC häufig verwendete Polynome sind das Ergebnis umfangreicher mathematischer und empirischer Analysen und keine Zufallszahlen, auch wenn sie so aussehen.

Andere Startwerte

Die Implementierung führt eine Polynomdivision aus, wenn als Startwert 0000... verwendet wird. Oft findet man andere Startwerte, etwa 1111.... Dies entspricht einer Polynomdivision, wenn die ersten n Bits des Datenstroms invertiert werden.

Ein Startwert ungleich 0000... ist vorzuziehen, da fehlende Bits innerhalb führender Nullen im Datenstrom sonst nicht erkannt werden (ebenso wie bei einer gewöhnlichen Division zählen bei einer Polynomdivision führende Nullen nicht).

Nachbearbeitung

Ein weiteres Problem ist das Nullproblem. Wird der Datenstrom aus irgendeinem Grund (einschließlich der CRC) gleich Null, so werden Fehler im Empfänger im Standardalgorithmus nicht mehr erkannt, auch wenn Startwerte ungleich Null verwendet werden. Eine Nullfolge ergibt bei der Polynomdivison stets den Wert Null. Wird das CRC-Ergebnis invertiert, kann man das Nullproblem effektiv vermeiden, da eine Folge von Nullen dann das Ergebnis 1111... erzeugt.

Die bekannte CRC-32 verwendet sowohl 1111... als Startwert als auch ein inverses Ergebnis. Bei CRC-16 wird ebenfalls meist 1111.. verwendet, das Ergebnis jedoch nicht invertiert.

Erkannte Fehler

Ist das CRC-Polynom gut gewählt, können mit dem oben beschriebenen Verfahren alle Einbit- und Zweibitfehler, jede ungerade Anzahl von verfälschten Bits, sowie alle Bündelfehler der Länge $\leq r$ erkannt werden, wobei $r$ der Grad des CRC-Polynoms ist. Zusätzlich werden alle Fehler (also auch unabhängige Vierbit-, Sechsbit-, Achtbitfehler, u.s.w.) erkannt, deren Polynomdarstellung einen kleineren Grad als das CRC-Polynom hat. Warum das so ist bzw. wie das CRC-Polynom zu wählen ist, folgt aus den kommenden Überlegungen.

Sei $G(x)$ das CRC-Polynom (Generatorpolynom) und $T(x)$ die Polynomdarstellung der um den CRC-Wert erweiterten zu übertragenden Bitfolge. Wenn ein Fehler bei der Übertragung auftritt, kommt (in Polynomdarstellung) beim Empfänger nicht $T(x)$ , sondern $T(x)+E(x)$ an. Die zu $E(x)$ gehörende Bitfolge hat an jeder Bitposition, die bei der zu übertragenden Bitfolge invertiert bzw. verfälscht wurde, eine 1. Wenn der Empfänger die um den CRC-Wert erweiterten Bitfolge erhält, berechnet er $(T(x)+E(x))/G(x)$ . Da $T(x)/G(x)=0$ (per Definition von $T(x)$ ), ist das Ergebnis $E(x)/G(x)$ .

Wenn ein Einbitfehler aufgetreten ist, gilt $E(x)=x^{i}$ , wobei $i$ bestimmt, welches Bit invertiert ist. Wenn nun $G(x)$ zwei oder mehr Terme enthält, wird $G(x)$ niemals $E(x)$ teilen.

Sind zwei isolierte Einbitfehler aufgetreten, gilt $E(x)=x^{i}+x^{j}$ , wobei $i>j$ . Klammert man $x^{j}$ aus, lässt sich dies auch als $E(x)=x^{j}(x^{i-j}+1)$ schreiben. Angenommen, $G(x)$ ist nicht durch $x$ teilbar (z.B. wenn $G(x)$ $x^{0}$ enthält), reicht es zu fordern, dass $G(x)$ nicht $x^{k}+1$ teilt (für alle $k$ bis zum maximalen Wert von $(j-i)$ , i.e. der maximalen Rahmenlänge). Einfache Polynome geringen Grades, die eine sichere Übertragung für lange Rahmen ermöglichen, sind bekannt. Zum Beispiel teilt $x^{15}+x^{14}+1$ den Term $x^{k}+1$ nicht für jedes $k$ kleiner 32768.

Ist eine ungerade Anzahl von Bits verfälscht, enthät $E(x)$ eine ungerade Anzahl von Termen (z.B. $x^{7}+x^{2}+1$ , aber nicht z.B. $x^{2}+1$ ). Wählt man das CRC-Polynom so, dass es $(x+1)$ als Faktor hat, werden alle Fehler mit einer ungeraden Anzahl von verfälschten Bits erkannt. Beweis: Bei der Division durch ein Polynom mit gerader Parität (= Anzahl der Therme in dem Polynom, also Anzahl der Einsen in der Bitfolge) bleibt die Geradheit oder Ungeradheit der Parität des Divisors erhalten, denn aus 00 wird 11 und umgekehrt und aus 01 wird 10 und umgekehrt. $(x+1)$ ist das kleinste Polynom mit gerader Parität. Bei $E(x)/G(x)$ wird also stehts $x$ oder $1$ als Rest bleiben, wenn $E(x)$ ungerade Parität hat. Damit ist $E(x)$ nicht durch $G(x)$ teilbar.

Alle Bündelfehler der Länge $k\leq r$ , wobei $r$ der Grad des CRC-Polynoms ist, werden erkannt. Ein Bündelfehler der Länge $k$ lässt sich schreiben als $x^{i}(x^{k-1}+\cdots +1)=x^{i}b(x)$ , wobei $i$ bestimmt, wieviele Bitpositionen von der rechten Seite der empfangenen Bitfolge (bzw. des empfangenen Rahmens) der Bündelfehler entfernt ist. Wenn der Fehler erkannt werden soll, muss die Division von $E(x)=x^{i}b(x)$ durch $G(x)$ einen Rest ergeben. Wenn $G(x)$ einen $x^{0}$ Term enthält, so hat $G(x)$ $x^{i}$ sicher nicht als Faktor. D.h., wenn $G(x)|x^{i}b(x)$ , dann muss $G(x)|b(x)$ . Dies ist jedoch nicht möglich, da per Annahme der Grad von $b(x)$ kleiner ist ( $deg(b(x))=k-1$ ) als der Grad von $G(x)$ . Der Rest kann niemals 0 sein und der Bündelfehler wird erkannt.

Berechnung einer CRC-32-Prüfsumme in C

Das folgende C-Programm berechnet die CRC-32 des 8 Bits langen Datenstroms 10001100:

   #include <stdio.h>
   #define CRC32POLY 0x04C11DB7 /* CRC-32 Polynom */
   
   int datastream[]={1,0,0,0,1,1,0,0};
   int databits=8;
   
   unsigned long crc32; /* Shiftregister */
   void calc_crc32(int bit)
   {	int hbit=(crc32 & 0x80000000) ? 1 : 0;
   	if (hbit != bit)
   		crc32=(crc32<<1) ^ CRC32POLY;
   	else
   		crc32=crc32<<1;
   	crc32 &= 0xffffffff; /* begrenze auf 32 Bits */
   }
   int main()
   {	int i;
   
   	crc32=0; 
   	for (i=0; i<databits; ++i)  
   		calc_crc32(datastream[i]);
   	printf("0x%08X",crc32); 
   }

CRC-32 Implementierung in der Programmiersprache C

Standards wie Ethernet modifizieren den Standardalgorithmus:

Als Startwert wird 111....111 verwendet (dies entspricht einer Invertierung der ersten 32 Bits im Datenstrom)
Besteht der Datenstrom aus Bytes, wird das niederwertigste Bit zuerst verwendet
Alle Bits im Ergebnis werden invertiert und die Bitreihenfolge wird gedreht, d. h. das höchstwertigste Bit erscheint zuerst

Das folgende Programm berechnet eine solche modifizierte CRC:

   #include <stdio.h>
   #define CRC32POLYREV 0xEDB88320 /* CRC-32 Polynom, umgekehrte Bitfolge */
   
   int datastream[]={1,0,0,0,1,1,0,0}; /* ASCII-"1", LSB zuerst */
   int databits=8;
   
   unsigned long crc32_rev; /* Shiftregister */
   void calc_crc32_rev(int bit)
   {	int lbit=crc32_rev & 1;
   	if (lbit != bit)
   		crc32_rev=(crc32_rev>>1) ^ CRC32POLYREV;
   	else
   		crc32_rev=crc32_rev>>1;
   	crc32_rev &= 0xffffffff; /* begrenze auf 32 Bits */
   }
   int main()
   {	int i;
   
   	crc32_rev=0xffffffff; /* Startwert (111...) */
   	for (i=0; i<databits; ++i)  
   		calc_crc32_rev(datastream[i]);
   	printf("0x%08X",crc32_rev ^ 0xffffffff); /* inverses Ergebnis, MSB zuerst */
   }

Modifizierte CRC32: Startwert 111..., invertiertes Ergebnis mit umgekehrter Bitfolge

Polynome und Typen

CRC-CCITT (CRC-4)	$x^{4}+x+1$
CRC-CCITT (CRC-16)	$x^{16}+x^{12}+x^{5}+1$
IBM-CRC-16	$x^{16}+x^{15}+x^{2}+1$
CRC-24 (IETF RFC2440)	$x^{24}+x^{23}+x^{18}+x^{17}+x^{14}+x^{11}+x^{10}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x+1$
CRC-32	$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$
CRC-64 (ISO 3309)	$x^{64}+x^{4}+x^{3}+x+1$
CAN-CRC	$x^{15}+x^{14}+x^{10}+x^{8}+x^{7}+x^{4}+x^{3}+1$
Bluetooth	$x^{5}+x^{4}+x^{2}+1$

CRCs werden häufig als Prüfsummen bezeichnet, obwohl die Berechnung der Kontrollbits nicht nur durch (gewöhnliche) Addition geschieht. Der Begriff „Prüfsumme“ wurde zuerst im Zusammenhang mit Paritätsbits benutzt, welche sich als eine echte Summe über $\mathbb {Z} _{2}$ berechnen lassen. Dabei hat sich der Begriff so sehr eingebürgert, dass er als Bezeichnung für die Berechnung von allgemeinen Kontrollbits übernommen wurde.

Siehe auch: Hash-Funktion und die dort genannten Verfahren, DFÜ.

Weblinks

http://www.jonelo.de/java/jacksum/index_de.html
- Jacksum (Java Checksum) ist ein freies und plattformunabhängiges Programm, u. a. zur Berechnung und Verifizierung von Prüfsummen, CRCs und Message Digests (mit Java-Quelltext)
http://serversniff.de berechnet online verschiedene CRCs für Strings und Dateien
A Painless Guide to CRC Error Detection Algorithms
Understanding Cyclic Redundancy Check