Adler-32

Adler-32

Adler-32 ist ein einfacher, von Mark 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), bietet aber auch weniger Sicherheit beim Erkennen von zufälligen Bitfehlern.

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 < 216) berechnet.

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

  /* Beispielcode zur Berechnung der Adler-32-Prüfsumme */
 
  #include <stdint.h> // fuer uint8_t/uint32_t
  #include <stddef.h> // fuer size_t
  uint32_t adler32(const void *buf, size_t buflength) {
 
     const uint8_t *buffer = (const uint8_t*)buf;
 
     uint32_t s1 = 1;
     uint32_t s2 = 0;
 
     for (size_t n = 0; n < buflength; n++) {
        s1 = (s1 + buffer[n]) % 65521;
        s2 = (s2 + s1) % 65521;
     }
 
     return (s2 << 16) | s1;
  }

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. Bei 64 Bit (uint64_t) breiten s1 und s2 würde sogar die Durchführung der Modulo-Operation alle 380.368.439 Bytes genügen, wodurch aber keine merkliche Geschwindigkeitsverbesserung erzielt werden kann. Näheres siehe Restklassenring.

Die hohe Anzahl der Sprünge verringert bei Prozessoren mit Pipeline die effektive Ausnutzung der quasi parallelen Ausführung einzelner Befehle. Es empfiehlt sich daher die einzelnen Daten in maximal 5552 Byte große Teilblöcke zu zerlegen, nach denen erst eine Modulo-Operation ausgeführt wird. Diese Blöcke sollten wiederum in 16 Byte große Untereinheiten zerlegt werden, die in einem Schleifendurchlauf zusammengerechnet werden. Durch dieses sogenannte Loop-Unrolling lässt sich in etwa 25–30 % Geschwindigkeitszuwachs auf modernen Prozessoren bei genügend großen Daten erzeugen.

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.

Durch die einfache arithmetische Struktur von Adler-32 kommt es zudem zu vielen Kollisionen, insbesondere auch bei ähnlichen Eingabewerten. Wird beispielsweise Byte n der Eingabe um k erhöht, Byte n+1 um 2×k erniedrigt und Byte n+2 um k erhöht, bleiben sowohl s1 (die Summe aller Bytes), als auch s2 (die Summe aller Zwischenwerte von s1) unverändert. Dieses gilt für beliebige Positionen n in der Eingabe, und alle positiven oder negativen Werte von k, soweit die betrachteten Bytes nicht überlaufen. Im Ergebnis kann die 32-Bit-Prüfsumme Adler-32 noch nicht einmal eine 24-Bit-Eingabe zuverlässig absichern.

Lediglich einfache und doppelte Bitfehler werden zuverlässig erkannt, und zwar durch die Summen s1 beziehungsweise s2. Treten jedoch Bursts von drei oder mehr Bitfehlern auf, wie im obigen Beispiel, ist eine sichere Erkennung nicht gewährleistet.

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.

Auch ist es verhältnismäßig leicht, durch beabsichtigte Modifikation einen Datenstrom mit gleicher Prüfsumme zu erzeugen. Deshalb kann Adler-32 die Integrität der Daten nicht garantieren. Wenn eine solche Sicherheit gefordert ist, müssen kryptografische Hash-Funktionen wie beispielsweise SHA zum Einsatz kommen.


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Adler — Adler …   Deutsch Wörterbuch

  • Adler — (v. mittelhochdt. adelare, urspr. edelaar zu Aar) steht für: Adler (Familienname), einen Familiennamen Adler (Biologie), Trivialbezeichnung für verschiedene Greifvögel Echte Adler, die Vertreter der Gattung Aquila Adler (Sternbild), ein Sternbild …   Deutsch Wikipedia

  • Adler-32 — Adler 32  хеш функция, разработанная Марком Адлером (англ.). Является модификацией контрольной суммы Fletcher (англ.). Вычисляет значение контрольной суммы в соответствии с RFC 1950 для массива байт или его фрагмента. Данный… …   Википедия

  • Adler — Adler …   Википедия

  • Adler-32 — is a checksum algorithm which was invented by Mark Adler. Compared to a cyclic redundancy check of the same length it trades reliability for speed. Compared to its original form (Fletcher 16), Adler 32 is more reliable than Fletcher 16. However,… …   Wikipedia

  • Adler — es un nombre alemán común; significa águila . El término Adler puede referirse a: ● Adler (automóvil), un automóvilo de principios del siglo XX ● Adler (supermercado), un supermercado en Polonia ● Adler Mannheim, un equipo de hockey alemán ●… …   Enciclopedia Universal

  • Adler I — auf dem N O K p1 …   Deutsch Wikipedia

  • Adler XI — an der Seebrücke Heringsdorf p1 …   Deutsch Wikipedia

  • ADLER — ADLER, family originally from frankfurt . There are different theories as to the origin of the family name. According to one, the early members of the family lived in a house bearing the sign of an eagle (Ger. Adler). The main branch, whose… …   Encyclopedia of Judaism

  • ADLER — ADLER, U.S. theatrical family. The founder was JACOB ADLER (1855–1926), one of the leading Jewish actor managers of his time, and a reformer of the early Yiddish theater. Born in Odessa, he first acted with amateurs, and in 1879 joined one  … …   Encyclopedia of Judaism

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”