Cyclic Redundancy Check: Datensicherung mit Prüfsummen

Im Zeitalter von Datenübertragung, Rechnernetzen und Computerviren ist die Datensicherung mittels Prüfsummen zu einem unverzichtbaren Bestandteil der Computertechnik geworden. In diesem Beitrag wird aufgezeigt, was sich hinter den geheimnisvollen Prüfsummen verbirgt.

Es ist in nahezu allen Bereichen der Datenverarbeitung von Bedeutung, die jeweiligen Daten zu sichern, d.h. deren ungewollte Veränderung zu verhindern, rückgängig zu machen oder zumindest zu entdecken.

Ein typisches Beispiel ist die Kommunikation zwischen zwei Computern über eine Verbindungsstrecke. Tritt nun eine Störung auf der Verbindungsleitung auf, was bei Kupferkabeln z.B. von Übersprechen, Blitzschlag oder von Einschalten eines elektrischen Verbrauchers herrühren kann, können die übertragenen Daten verfälscht werden. Bei Finanz- und Versicherungsdaten, aber auch bei Daten, welche z.B. ein Walzwerk steuern, können hierbei schwerwiegende Folgen auftreten. Ein weiteres Beispiel für den Bedarf an Datensicherung zeigt sich bei Computervirenbefall. Auch hier können fatale Folgen auftreten, die von zerstörten Dateien bis zur Kopflandung der Festplatte reichen.

Neben den genannten Datenzerstörern gibt es auch zunächst weniger offensichtliche Gefahren für Datenbestände. Alterungserscheinungen von Speichermedien, Temperatureffekte, aber auch radioaktive α-Teilchen können zu allmählich umfangreicher werdenden Datenveränderungen führen, die oft lange Zeit unentdeckt bleiben. Die tatsächliche Ursache für einen irgendwann auftetenden Fehler ist dann meist nur sehr schwierig nachzuvollziehen. Es ist also wünschenswert, sich gegen ungewollte Datenänderungen zu schützen bzw. diese überhaupt zu diagnostizieren. Das vermutlich bekannteste Verfahren zur Datensicherung ist die Einführung von Parity-Bits. Die einfachste Variante ist, ein zusätzliches Bit an den zu sichernden Datensatz anzuhängen und das Parity-Bit auf 1 zu setzen, falls die Anzahl an Einsen in dem Datensatz selbst eine ungerade Zahl ergibt. Die Anzahl der Einsen ist dann insgesamt wieder eine gerade Zahl, weswegen man auch von „even parity“ spricht (even = geradzahlig). Der gesamte Datensatz inklusive Parity-Bit wird nun bei einer Fehlerüberprüfung, z.B. nach einer erfolgten Datenübertragung, daraufhin getestet, ob die Anzahl der Einsen gerade ist. Ist das nicht der Fall, muß ein Fehler vorliegen. Alternativ dazu läßt sich das ganze Überprüfungsschema auch mit „odd parity“ (odd = ungeradzahlig) aufbauen, es ergibt sich hierbei jedoch nichts prinzipiell Neues. So einfach das gesamte Verfahren ist, so wenig leistungsfähig ist es auch. Es braucht nämlich nur eine gerade Anzahl an Bits im Datensatz inklusive Parity-Bit verfälscht zu werden, ohne daß das Parity-Bit hier eine Warnung melden könnte .Die Chance für eine Fehlerentdeckung ist demnach nur 50%, je nachdem ob eine gerade oder eine ungerade Anzahl an Bits verändert wurde.

Die Grundidee, an den Datensatz zusätzliche Prüf-Bits anzuhängen, ist jedoch der richtige Ansatz und führt in der Verallgemeinerung zu einem an den Datensatz angehängten Prüfwort, auch Prüfsumme genannt, dessen Berechnung auf unterschiedliche Weise vorgenommen werden kann.

Prüfsummenberechnung durch CRC

Bild 1: Wird an die zu sichernden Daten eine Prüfsumme angehängt, lassen sich Datenverfälschungen mit hoher Wahrscheinlichkeit entdecken.

Eine besonders leistungsfähige Variante zur Prüfsummenberechnung ist die zyklische Prüfsummenberechnung, auch CRC (CRC = Cyclic Redundancy Check) genannt, welche im folgenden besprochen werden soll. Das übergeordnete Prinzip ist in Bild 1 schematisch dargestellt. Der zu sichernde Datensatz wird mit zusätzlichen Prüf-Bits, der Prüfsumme, versehen, welche nach einem noch zu besprechenden CRC-Algorithmus berechnet wurde. Bei der Fehlerüberprüfung, z.B. nach einer Datenübertragung, wird die Kombination aus Datenwort und Prüfsumme wieder dem selben CRC-Algorithmus unterzogen, welcher bei Fehlerfreiheit das Resultat 0 liefern sollte. Mit Hilfe von CRC-Algorith-men lassen sich fehlerhafte Daten ausgezeichnet entdecken und unter gewissen Umständen sogar korrigieren. Wir wollen uns hier jedoch nur mit der Fehlerentdek-kung beschäftigen. Die prinzipielle Wirkungsweise eines CRC-Algorithmus soll nun näher betrachtet werden.

CRC-Berechnungen basieren darauf, sowohl den Daten-Bitstring als auch den Prüfsummen-Bitstring jeweils als Polynom aufzufassen. Ein Polynom vom nten Grad hat generell die Gestalt

p(x) = pn * xn + pn-1 * xn-1 +
... + p2 * x2 + p1 * x + p0 (1)

wobei ein Koeffizient pi als Koeffizient der Ordnung i bezeichnet wird. Ein Bitstring wird nun so dargestellt, daß das niederwertigste Bit den Koeffizienten p0 bildet, das nächsthöherwertige den Koeffizienten p1, usw. Der Bitstring 1101011 wird demnach durch

p(x) = x6 + x5 + x3 + x + 1 (2)

repräsentiert. Um das Verfahren der CRC-Prüfsummenberechnungen verstehen zu können, muß man zunächst wissen, daß man alle Grundoperationen der ganzen Zahlen, also +, -, *, / und die Modulo-Funktion (siehe Erläuterungskasten), auch auf Polynome anwenden kann. Die Koeffizienten des Polynoms müssen dabei Elemente eines festgelegten Zahlenkörpers sein. In diesem Zahlenkörper ist u.a. definiert, welche Werte dessen Elemente annehmen dürfen. In der Schule arbeitet man vornehmlich im Körper der reellen Zahlen, in welchem ein Polynom p(x) z.B. p(x) = 2.5 *x2 + √3 * x + 1.1 lauten kann. Der Körper der reellen Zahlen enthält unendlich viele Elemente, nämlich die reellen Zahlen von -∞ bis +∞. Bei den CRC-Berechnungen stammen die Koeffizienten meist aus dem sogenannten Galois-Körper GF(2) (GF = Galois Field), einem mathematischen Zahlenkörper, der lediglich die beiden Elemente 0 und 1 enthält. Alle oben erwähnten Grundoperationen erfolgen dort modulo 2, d.h., beim Addieren, Subtrahieren etc. wird das Endergebnis modulo 2 genommen, was durch den Operator <...>2 angedeutet wird. Die Modulo-2-Rechnung führt in GF(2) dazu, daß Addition und Subtraktion identisch sind, wie man leicht anhand der Gleichungen

<0 ± 0>2 = 0 (lies: 0 plus minus 0 modulo 2 ist gleich 0) (3a)
<0 ± 1>2 = 1 (3b)
<1 ± 0>2 = 1 (3c)
<1 ± 1>2 = 0 (3d)

nachprüfen kann. Weiterhin erkennt man durch Vergleich der Gleichungen (3a - d) und Bild 2, daß Addition bzw. Subtraktion in GF(2) offensichtlich der EXOR-Operation der Booleschen Algebra entsprechen.

a b a EXOR b
0 0 0
0 1 1
1 0 1
1 1 0

Bild 2: Wertetabelle für die Exklusiv-Oder-Verknüpfung (EXOR) zweier Boolescher Variablen a und b.

Nun zu den CRC-Berechnungen selbst: sie stützen sich auf die Division zweier Polynome. Wie jede Division wird auch die Polynomdivision durch eine Folge von Subtraktionen ausgeführt und liefert analog zur Division von ganzen Zahlen einen Quotienten und einen Rest (Erinnerungsbeispiel: 7/2 = 3 mit Rest 1). Genau dieser Rest ist es, der bei der Prüfsummenbildung mittels CRC interessiert. Um das Prinzip der Polynomdivision zu verstehen, nehmen wir das Polynom p(x) = x6 + x5 + x3 + x+1 von vorhin als Beispiel. Wir wollen nun x3 * p(x) durch ein weiteres Polynom g(x) = x3 + 1 dividieren. Warum wir dazu p(x) mit x? multipliziert haben, werden wir später noch sehen. Im ersten Schritt der Division erhält man

was im folgenden kurz erläutert werden soll: bei einer Division von Polynomen werden stets nur die Terme höchster Ordnung der beiden Polynome dividiert, in unserem Beispiel also x9 / x3 = x6. Anschließend wird der Divisor, also g(x) = x3 + 1, mit dem Divisionsergebnis, hier x6, multipliziert und das Resultat, hier x9 + x6 von p(x) abgezogen. Dabei zieht man gemäß den Subtraktionsregeln bei Polynomen immer die Koeffizienten der gleichen Ordnung voneinander ab. Da wir für unsere CRC-Berechnungen in dem speziellen Zahlenkörper GF(2) arbeiten, müssen wir das jeweilige Subtraktionsergebnis noch modulo 2 nehmen, so daß sich wegen Glg. (3b) nie ein negativer Wert ergibt, da <-1>2 = 1 ist. Für x9 rechnet man demnach für das vorliegende Beispiel <1 - 1>2 = 0 und für x6 ebenfalls <1-1>2 = 0. Übrig bleibt ein Restpolynom x8 + x4 + x. Kann das Restpolynom nochmals durch den Divisor g(x) geteilt werden, d.h. ist die Ordnung des Restpolynoms größer oder gleich jener von g(x), muß eine weitere Division nach den eben erläuterten Regeln durchgeführt werden. Die Divisionen werden so lange durchgeführt, bis die Ordnung des Restpolynoms kleiner als die Ordnung von g(x) ist. Das letzte Restpolynom repräsentiert dann die gesuchte Prüfsumme. Wir können nun auch den Grund verstehen, warum p(x) zuvor mit x3 multipliziert wurde: da g(x) ein Polynom vom Grad 3 ist, wird durch die Multiplikation mit x3 gewährleistet, daß jedes durch p(x) repräsentierte Bit auch einer vollen Division mit g(x) unterzogen wird. Allgemein wird in der Codierungstheorie p(x) also mit xm multipliziert, bevor es durch ein Polynom g(x) vom Grade m dividiert wird. Im gewählten Beispiel sieht die Gesamtrechnung damit wie in Bild 3.

Das Restpolynom r(x) = x2 + x + 1 entspricht dem Bitstring 111, welcher die gesuchte Prüfsumme darstellt. Da das Restpolynom r(x) aus einer Division durch ein Polynom g(x) hervorgeht, wird g(x) auch als Generatorpolynom bezeichnet.

Die Division zweier Polynome in GF(2) kann man auch mit Hilfe von Bitstrings darstellen, wie in Bild 4 zu sehen ist. Diese Form der Darstellung wird später auch für die Computerprogrammierung herangezogen.

Bild 3

Um die Wirkungsweise der CRC-Berechnung auf die Fehlerüberprüfung beurteilen zu können, eignet sich die Polynomschreibweise jedoch besser, weswegen wir nochmals zu dieser zurückkehren wollen. Die oben durchgeführten Rechnungen lassen sich auch kompakt über

xm * p(x) / g(x) = q(x) + r(x) / g(x) (6)

bzw.

r(x) = <xm * p(x)>g(x) (7)

ausdrücken (siehe Erläuterungskasten), wobei m der Grad des Generatorpolynoms g(x) ist. Wir wollen uns diese Gleichung nochmals vergegenwärtigen, xm * p(x) dividiert durch g(x) ergibt ein Quotientenpolynom q(x), welches keine weitere Bedeutung besitzt, plus einen Rest r(x) / g(x). r(x) ist das für p(x) charakteristische Restpolynom. Die Anwendungsmöglichkeiten des CRC-Verfahrens werden nun verständlich: Man faßt z.B. eine Datei als sehr langen Bitstring und damit als Polynom p(x) hoher Ordnung auf, indem man gedanklich alle Datenwörter hintereinander anordnet. Nun dividiert man das Polynom xm * p(x) durch ein Generatorpolynom g(x) vom Grade m, welches ein Restpolynom r(x) generiert. Das Polynom r(x) ist charakteristisch für die gesamte Datei. Wird die Datei nun z.B. durch einen Fehler im Speichermedium oder einen Virus verändert, so entspricht dies der Addition eines Fehlerpolynoms e(x) zu dem Dateipolynom p(x), wobei die Addition wieder modulo 2 bezüglich der Polynomkoeffizienten zu verstehen ist. Ein Fehler in einem einzigen Bit würde z.B. durch e(x) = xk dargestellt, wobei _k genau jene Stelle der Datei anzeigt, an welcher das Bit geändert wurde. Bei der CRC-Überprüfung einer Datei bildet man in diesem Fall den veränderten Rest r’(x) gemäß

welcher nur dann gleich dem ursprünglichen Rest r(x) ist, wenn das Polynom xm * e(x) durch g(x) ohne Rest teilbar, d.h. <xm * e(x)>g(x) gleich Null ist. Dieser Fall ist aber sehr unwahrscheinlich, falls für g(x) ein geeignetes Generatorpolynom gewählt wird. Zwei Generatorpolynome, welche für viele Anwendungen geeignet sind, lauten

g(x) = x16 + x12 + x5 + 1 (9)

oder

g(x) = x16 + x15 + x2 + 1 (10)

[3], welche beide eine 16-Bit-Prüfsumme liefern. Man sieht sofort, daß z.B. ein Einzelfehler e(x)=xk immer entdeckt wird, da xm * xk nur durch ein Polynom der Gestalt g(x) = x1 ohne Rest geteilt wird. Link-Viren produzieren i.a. sehr komplizierte Fehlerpolynome e(x), deren Teilbarkeit durch g(x) unwahrscheinlich ist, weswegen Link-Viren mit CRC-Verfahren relativ leicht auf gespürt werden können.

In der Praxis werden zu sichernde Daten stets zusammen mit ihrem charakteristischem Restpolynom, der Prüfsumme, abgespeichert, wie es auch in Bild 1 dargestellt ist. Das Restpolynom wird einfach an die Daten „angehängt“. Mathematisch entspricht dies einfach der Addition von r(x) zu xm * p(x). Sollen die Daten auf Veränderung überprüft werden, bildet man einfach (hier für den fehlerfreien Fall e(x) = 0)

<xm * p(x) + r(x)>g(x)

was gemäß den Rechenregeln aus dem Erläuterungskasten

<<xm * p(x)>g(x) + <r(x)>g(x)>g(x) = <r(x) + r(x)>g(x) = 0 (11)

ergibt, da ja jeder Koeffizient modulo 2 genommen werden muß und die Koeffizienten von r(x) + r(x) entweder <0>2 = 0 oder <2>2 = 0 sind. Bild 5 zeigt die Bitstring-Darstellung dieser Rechnung für das verwendete Textbeispiel.

Das nachfolgend angegebene C-Programm setzt die präsentierte Theorie in die Praxis um. Es bildet die Prüfsumme über einen Datensatz anhand des Generatorpolynoms nach Gig. (9) und gestattet somit dem Anwender, seine Datenbestände ausreichend zu sichern.

Literatur:

[1] Berlekamp, E.R., Algebraic Coding Theory, McGraw-Hill, 1968.

[2] McClellan, J.H. and Rader CM., Number Theory in Digital Signal Processing, Prentice-Hall, Englewood Cliffs, N.J., 1979.

[3] Tanenbaum, A.S., Computer Networks, Prentice-Hall, Englewood Cliffs, 1989.

Bild 4: Bitstring-Darstellung der Polynomdivision x3 *p(x) / g(x) aus dem Textbeispiel
Bild 5: Bitstring-Darstellung der Rechnung nach Glg. (11) für das Textbeispiel

Modulo-Funktion

Neben den Operationen +, -, * und / befindet sich die Modulo-Funktion als fünfte Grundoperation der ganzzahligen Arithmetik im Repertoire nahezu jeder Programmiersprache. Berechnet wird hiermit ein Rest r, der sich nach der ganzzahligen Division einer Integer-Variablen x durch einen Modulus M ergibt. In Kurzform schreibt sich diese Berechnung als

r = <x>M (lies: r ist gleich x modulo M) (a)

und wird in den verschiedenen Programmiersprachen unterschiedlich dargestellt So schreibt man z.B.

in C: r = x % M;
in Pascal: r := x MOD M;
oder in Fortran: R = MOD(X,M).

Im folgenden werden wir uns jedoch an die mathematische Schreibweise nach Glg. (a) halten.

Computerintern wird die Modulo-Funktion i.a. per

r = x - floor(x/M) * M (b)

berechnet, wobei floor(x/M) jene ganze Zahl berechnet, welche möglichst dicht an x/M liegt, aber nicht größer als x/M ist. So ist also beispielsweise

floor(1.3) = 1

und

floor(-4.7) = -5

Eine zu Glg. (b) alternative Beschreibung dessen, was bei der Moduloberechnung r = <x>M passiert, lautet:

1) Falls x positiv ist, ziehe M von x so oft ab, bis ein Ergebnis r mit 0 ≤ r < M übrigbleibt.

2) Falls x negativ ist, addiere M zu x so oft hinzu, bis ein Ergebnis r mit 0 ≤ r < M übngbleibt.

Damit ist das Wesen der Modulo-Funktion ausreichend beschrieben, so daß sich nun die Rechenbeispiele

<17>5 = 2

oder z.B.

<-1 >4 = 3

leicht nachvollziehen lassen. Für die Rechnung mit der Modulo-Funktion existieren einige nützliche Gesetze. So gelten u.a. die Beziehungen

<x1 ± x2>M = <<x1>M ± <x2>M>M ( c )

und

<x1 * x2>M = <<x1>M ± <x2>M>M. (d)

Sämtliche Rechenoperationen für ganze Zahlen existieren auch für Polynome. Im Fälle der Modulo-Funktion bedeutet die Schreibweise

c(x) = <a(x)>b(x) (lies: c(x) = a(x) modulo b(x)), (e)

daß c(x) als Rest aus der Polynomdivision a(x)/b(x) hervorgeht. Analog zu den Gleichungen (c) und (d) für ganze Zahlen gilt für Polynome

<a1(x) ± a2(x)>b(x) = <<a1(x)>b(x)± <a2(x)>b(x)>b(x) (f)

sowie

<a1(x) * a2(x)>b(x) = <<a1(x)>b(x) * <a2(x)>b(x)>b(x) (9)

/* Pruefsummenberechnung durch CRC  */
/* (c) MAXON Computer 1993          */

#include "stdio.h"

/*----Funktionsdeklarationen-----*/

void main(void);
unsigned int crc_16(unsigned char *start, int len);
unsigned int crc_update(unsigned int crc, unsigned char c);

/*----Funktionsdefinitionen----*/

unsigned int crc_16(unsigned char *start, int len) 
/***********************************
** Berechnet ein 16 bit CRC Wort  **
** fuer den Speicherblock, welcher**
** an der Stelle "start" beginnt  **
** und "len" Bytes lang ist.      **
** crc_16() verwendet die Funktion**
** crc_update(), welche ein von   **
** CC1TT empfohlenes Generator-   **
** polynom vom Grad 16 benutzt.   **
***********************************/
{
    unsigned int crc; /* crc beherbergt das Restpolynom r(x) und */
                      /* muß 16bit breit sein, damit das Resultat */
                      /* vollstaendig aufgenommen werden kann. */

/*------Starte CRC-Berechnung-----*/

crc = 0;

while(len—-) /* Fuehre CRC-Berechnung solange durch, bis */
{            /* alle Bytes abgearbeitet sind. */
    crc = crc_update(crc, *start++); /* Bearbeite ein Byte */
}

return(crc_update(crc_update(crc,'\0'),'\0'));
        /* Haenge 16 Nullen an fuer korrektes Resultat */
        /* (Entspricht der Multiplikation (x^16)*p(x). */
}

unsigned int crc_update(unsigned int crc, unsigned char c)

/***********************************
** Kernroutine für CRC-Berechnung.**
** Hier werden 8 aufeinander-     **
** folgende Schritte einer        **
** Polynomdivision im Galois-     **
** Koerper GF(2) mit Hilfe des    **
** Generatorpolynoms              **
** g(x) = x^16 + x^12 + x^5 +1    **
** vorgenommen. Die einzelnen     **
** Rechenschritte bestehen aus    **
** EXOR-Operationen.              **
***********************************/
{
    unsigned long x; /* Puffervariable z.Aufnahme */ 
                     /* der Zwischenergebnisse */ 
    int i;           /* Schleifenzaehler */

    x = ((unsigned longiere << 8) + (unsigned long)c;

    /*-----Führe 8 EXOR-Schritte durch------*/

    for (i = 0; i<8; i++)
    {
        X = X << 1;

        /* Falls erstes Bit des Dividenden 1 ist, fuehre EXOR */
        /* Operation mit g(x) durch, ansonsten EXOR-Operation */
        /* mit Nullen, d.h. keine Veraenderung */

        if ((x & 0x01000000) != 0)
        {
            x = x ^ 0x01102100; /* g(x) ist x^16+x^12+x^5+1 und ist */
        }                       /* 8 bits nach links verschoben. */
    }

    /* Blende Ergebnis aus und gib es als 16bit-Variable zurück */

    return((unsigned int)((x & 0x00ffff00) >> 8));
}

void main(void) 
/************************************************ 
** Mini-Testtreiber für CRC-Berechnungsroutine.** 
** Dient lediglich zur Demonstration des       **
** Gebrauchs von crc_16().                     **
************************************************/

{
    unsigned char ary[2]; /* Nimmt p(x) auf, welches hier lediglich */
                          /* 2 Byte lang ist. */
    unsigned int  result;

    ary[0] = 52;         /* Willkeuerliche Vorbelegung von p(x) */
    ary[1] = 86;

    result = crc_16(ary,2);

    printf("\nResultat r(x) in Bitstring-Form: %x", result);
}

Rainer Storn
Links

Copyright-Bestimmungen: siehe Über diese Seite