Adler-32

aus Wikipedia, der freien Enzyklopädie

Adler-32 ist ein einfacher, aber effizienter, von Marc Adler entwickelter Prüfsummenalgorithmus. Er wird unter anderem von der zlib-Bibliothek benutzt, um (zufällige Übertragungs-)Fehler im komprimierten Datenstrom zu erkennen. In RFC 1950 wird der Algorithmus genau beschrieben.

Der Adler-32-Algorithmus ist einfacher und lässt sich schneller berechnen als die bekannte Zyklische Redundanzprüfung (cyclic redundancy check) und bietet dabei eine vergleichbare Sicherheit beim Erkennen von zufälligen Bitfehlern.

[Bearbeiten] Algorithmus

Der Algorithmus berechnet zwei Summen s1 und s2. s1 ist die Summe aller Datenbytes und wird am Anfang des Algorithmus auf 1 initialisiert, s2 ist die Summe aller s1-Werte. Beide Summen werden modulo 65.521 (die größte Primzahl <2¹⁶) berechnet.

Obwohl der Algorithmus sehr einfach ist, sei hier eine Beispielimplementierung in C angegeben:

/* Beispielcode zur Berechnung der Adler-32-Prüfsumme */
 
  uint32_t adler32(unsigned char* buf, size_t buflength)
  {
     uint32_t s1 = 1;
     uint32_t s2 = 0;
 
     for (size_t n=0; n<buflength; n++)
     {
        s1 = (s1 + buf[n]) % 65521;
        s2 = (s2 + s1)     % 65521;
     }
     return (s2 << 16) + s1;
  }

[Bearbeiten] Anmerkung Beispielimplementierung

Diese Beispielimplementierung ist nicht auf Geschwindigkeit, sondern auf Klarheit und Lesbarkeit hin optimiert. So muss etwa die recht langsame Modulo-Operation nicht bei jedem Datenbyte durchgeführt werden, sondern nur, wenn ein Überlauf der Variablen s1 oder s2 droht. Bei einer Bitbreite von 32 Bit (was bei der Verwendung von int nicht gewährleistet ist, daher oben uint32_t gemäß C99) genügt eine Durchführung der Modulo-Operation alle 5552 Bytes. Näheres siehe Restklassenring.

[Bearbeiten] Schwächen von Adler-32

Ein optimaler Prüfsummenalgorithmus erzeugt eine Prüfsumme, die möglichst gleichverteilt über ihren Wertebereich ist. Dies ist bei Adler-32 für kurze Datenfolgen (<128 Byte) nicht gegeben, da der Wert für s1 nicht überläuft.

Aus diesem Grunde wurde unter anderem in der Implementierung des Stream Control Transmission Protocols der verwendete Prüfsummenalgorithmus Adler-32 durch CRC-32 ersetzt, da hier recht oft nur kurze Datenströme benutzt werden und die Schwäche von Adler-32 zutage tritt.

Genau wie auch bei CRC-32 ist es verhältnismäßig leicht, durch beabsichtigte Modifikation einen Datenstrom mit gleicher Prüfsumme zu erzeugen. Deshalb kann auch Adler-32 nicht garantieren, dass die Daten nicht böswillig verändert wurden.