Prüfsummen - EinerkomplementDie Standards des IP und TCP nennen die Operation zur Berechnung der Prüfsumme Einerkomplement (one's complement). Dieses ist etwas irreführend, da Einerkomplementzahlen (ähnlich wie Zweierkomplementzahlen) nur definiert sind, wenn der Wertebereich nicht überschritten wird. Wird der Wertebereich überschritten, so rechnet man falsch, und dann ist das Ergebnis nicht notwendigerweise definiert. Da hier aber gerade diese Eigenschaft ausgenutzt werden soll, ist genau zu definieren, wie die Prüfsumme gebildet wird. Die genaue Operation wird hier beschreiben (RFC 1071/1141/1624). Da die ursprünglichen Angaben fehlerhaft waren (insbesondere bei der Neuberechnung der Prüfsumme in Routern) sollten die drei oben genannten RFCs verglichen werden. Die Bitfolgen werden als Dualzahlen (0 .. 65535) aufgefasst und deren Werte addiert. Wird bei einer Addition ein Überlauf beobachtet (Summe größer als 65535), so wird der Überlauf entfernt und eine 1 zu der Summe addiert. Das folgende Beispiel zeigt dieses. Es soll für die folgenden Daten die Prüfsumme gebildet werden:
Die Addition erfolgt dann nach dem folgenden Schema, wobei wir jeweils einen Übertrag addieren, auch wenn dessen Wert null ist.
Wird eine null (0000 0000 0000 0000) addiert, so ändert sich das Ergebnis nicht. Wird eine 1111 1111 1111 1111 addiert, so ändert sich das Ergebnis auch nicht, da für n>1:
Diese Operation erzeugt einen Überlauf, so dass jeweils 1 addiert wird, also wieder n herauskommt, z.B.:
Daher gibt es zwei Operanden, welche die Eigenschaften einer null haben, was auch beim Einerkomplement der Fall ist. Die obige Rechnung ließe sich auch anders darstellen (und wird in einigen Implementierungen auch so durchgeführt). Als erstes werden sämtliche Daten addiert und dann werden die Werte, die größer sind als 216, durch 216 dividiert und auf das Ergebnis addiert. Dieses muss evtl. wiederholt werden, da das zu einem weiteren Überlauf führen kann. Mit Hilfe dieses Verfahrens werden scheinbar 1 Bit-Fehler stets erkannt, aber nicht alle ungeraden. So ist etwa
und für einen 3 Bit-Fehler erhalten wir:
was im Vergleich zu einem einfachen Paritätsprüfverfahren relativ schwach ist. Ebenso gilt für einen 2 Bit-Fehler mit dem obigen Beispiel:
Damit ist dieses Prüfverfahren anderen deutlich unterlegen, so dass bei den verbreiteten Internet-Verfahren (insbesondere TCP) in der Regel mit relativ großen Fehlerwahrscheinlichkeiten zu rechnen ist. |