05 Netzwerksicherheit

Hamming Codes

Vielleicht anders als die Hamming Codes aus Digitaltechnik, hier werden Datenwörter immer $4$ Bit Länge besitzen und mit $3$ Bit korrigiert.

$$\begin{array}{cccc}{a}_3& a_2& a_1& a_0\end{array}$$

Über eine Generatorfunktion werden drei Parity-Bits berechnet und dem Wort angehängt.

$$\begin{array}{l}{r}_0=a_2+a_1+a_0\mathrm{mod}2\\ r_1=a_3+a_2+a_1\mathrm{mod}2\\ r_2=a_1+a_0+a_3\mathrm{mod}2\end{array}$$

Übertragen wird also

$$\begin{array}{ccccccc}{a}_3& a_2& a_1& a_0& r_2& r_1& r_0\end{array}$$

Durch die Fehleranfällige Übertragung werden möglicherweise andere Bits empfangen als versendet wurden. Es wird aus den Empfangenen Bits ein Syndrom berechnet, das in der Lage ist eventuelle Fehler zu korrigieren.

$$\begin{array}{l}{s}_0=a_2+a_1+a_0+r_0\mathrm{mod}2\\ s_1=a_3+a_2+a_1+r_1\mathrm{mod}2\\ s_2=a_1+a_0+a_3+r_2\mathrm{mod}2\end{array}$$

Anhand des Syndroms $s_2{s}_1{s}_0$ kann aus dieser Tabelle bestimmt werden, welches Bit falsch übertragen wurde. Bei schwerwiegenden Fehlern mit vielen falschen Bits ist dieses Verfahren nicht mehr anwendbar, es wird nur ein einzelner Fehler korrekt erkannt und korrigiert.

$$\begin{array}{lllllllll}\text{Syndrom}& 000& 001& 010& 011& 100& 101& 110& 111\\ \text{Fehler}& \text{None}& r_0& r_1& a_2& r_2& a_0& a_3& a_1\end{array}$$

Binäre Prüfsummen mit 1er-Komplement

Eine Reihe von Daten soll übertragen werden.
Man bildet ihre Summe.

$$\begin{array}{rr}& 0111\\ & 1101\\ & 1011\\ +& 0110\\ & \boxed{10}0101\\ +& 10\\ & 0111\end{array}$$

In diesem Beispiel hat die Summe mehr Stellen als die Daten selbst. Der markierte Teil des Ergebnis wird umgebrochen und ebenfalls addiert.
Von dieser finalen Summe wird im letzten Schritt das 1er-Komplement gebildet.

$$\begin{array}{cc}0111& 1K\\ 1000& \end{array}$$

Diese Prüfziffer wird an den Block der zu übertragenden Daten angehängt.
Übertragen wird also

$$\begin{array}{r}0111\\ 1101\\ 1011\\ 0110\\ 1000\end{array}$$

Der Empfänger bildet nach dem gleichen Schema die Summe aus allen empfangenen Daten.

$$\begin{array}{rr}& 0111\\ & 1101\\ & 1011\\ & 0110\\ & 1000\\ & \boxed{10}1101\\ +& 10\\ & 1111\end{array}$$

Von dieser Summe wird ebenfalls das 1er-Komplement gebildet. Falls dieses den Wert $0$ berechnet, wurde das Paket korrekt übertragen.

$$\begin{array}{cc}1111& 1K\\ 0000& \end{array}$$

EAN Prüfsummen

Die European Article Number ist eine 13-stellige Artikelbezeichnung. Um Zahlendreher und Tippfehler einzuschränken dient die 13te Ziffer nur als Prüfsumme.

Dabei werden die ersten 12 Ziffern abwechselnd mit $1$ und $3$ multipliziert und addiert.
Die Prüfziffer wird so gewählt, dass die Summe dieser Summe und der Prüfziffer durch 10 teilbar ist.

Beispiel

Wir berechnen die Prüfziffer eines Artikels.
1234-5678-9123-X

$$1\cdot 1+3\cdot 2+1\cdot 3+3\cdot 4+\cdots +1\cdot 2+3\cdot 3=99$$

formell wird die Prüfziffer $p$ aus dieser Summe $n$ bestimmt:

$$p=10-n\mathrm{mod}10$$ $$p=10-99=-89=1\mathrm{mod}10$$