Adventskalender Türchen 7 - Prüfsummen

Die 7

Heute gibt es ein trockenes Thema, dass aber hoffentlich wenigstens interessant ist - Prüfsummen. Was zum Teufel sind Prüfsummen?

Prüfsummen sind eigentlich typische Informatiker- und Mathematiker-Sachen und Otto-Normalverbraucher will es überhaupt nicht wissen bzw. weiss nicht einmal, dass es sowas Komisches gibt. Jeder kommt aber täglich damit in Berührung bzw. die meisten modernen Sachen funktionieren nur noch mit bzw. nur zuverlässig durch Prüfsummen. Also was sind Prüfsummen?

Die Wikipedia sagt dazu: "In der Informatik ist eine Prüfsumme (engl.: checksum) eine einfache Maßnahme zur Gewährleistung von Datenintegrität bei der Datenübermittlung oder -speicherung. Sie wird hauptsächlich bei der Datensicherung und bei der Datenübertragung verwendet."

Festplatten, CDs, DVDs und die komplette Datenübertragung im Internet brauchen Prüfsummen. Eure Bank nutzt Prüfsummen für Kontonummern, Eure Kreditkartennummer ist mit einer Prüfsumme behütet. Aber wozu braucht man das denn nun wirklich?

Als einfaches Beispiel möchte ich Eure Kontonummer nehmen. Wenn Ihr eine Überweisung macht und Euch beim Eintippen verschusselt, dann würde das Geld erstmal ins Leere gehen, denn keine Bank kennt die gültigen und vergebenen Kontonummern der anderen Bank. Um also wenigstens gegen den offensichtlichen Eingabefehler gewappnet zu sein, nutzt man Prüfsummen. Die letzte Stelle Eurer Kontonummer, bzw. bei Unterkonten oft die letzte Stelle des Accounts, ist die Prüfziffer für den Rest der Nummer. Immer noch unklar?

Ok, hier ein einfaches Beispiel. Nehmen wir an, Eure Kontonummer wäre die 1234566. Dann wäre die letzte 6 die Prüfsumme/-ziffer für die Kontonummer. Wenn Ihr also zu schnell tippt und versehentlich 123466 eintippt oder 1235466, dann weiss die Bank noch vor Annahme der Überweisung, dass die Nummer falsch ist. Wie geht das?

Für einfache Zahlenreihen wird der Luhn-Algorithmus genutzt. Mit einer simplen Rechnung wird die letzte Stelle aus den anderen Stellen berechnet bzw. geprüft, ob das Gesamtergebnis korrekt ist. Der Rechenweg ist sehr einfach und locker auf dem Papier nachvollziehbar:

  • Beginnend mit der zweitletzten Ziffer und nach links durchlaufend, verdopple den Wert jeder zweiten Ziffer. Für jedes Ergebnis grösser oder gleich 10, bilde die Quersumme.
  • Addiere all diese Zahlen zusammen.
  • Wenn die letzte Ziffer der Gesamtsumme 0 ist (anders gesagt: Wenn Gesamtsumme modulo 10 gleich 0 ist), dann ist die Nummer gültig, sonst nicht.

Für die Kontonummer 1234566 würden wir jetzt rechnen - beginnend am Ende:
6 + Quersumme(2 * 6) + 5 + 2 * 4 + 3 + 2 * 2 + 1 = 30.
30 ist durch 10 teilbar, also stimmt die Kontonummer im Sinne von Zahlendrehern (die Nummer kann natürlich durchaus nicht vergeben sein). Nehmen wir unseren Auslasser 123466, so wäre es
6 + Quersumme(2 * 6) + 4 + 2 * 3 + 2 + 2 * 1 = 23.
23 ist überhaupt nicht durch 10 teilbar, also ist was faul. Schauen wir uns noch den Dreher 1235466 an
6 + Quersumme(2 * 6) + 4 + 2 * 5 + 3 + 2 * 2 + 1 = 22
also auch wieder falsch.

So, jetzt kennt Ihr eine der einfachsten Prüfsummen und ihre Anwendung. Natürlich kann diese einfache Variante nicht alles "sehen". Sind viele Zahlen falsch, dann wird es wieder richtig und vertauschen sich Zahlen über entfernte Stellen, also z.B. 1254366, dann merkt es der Algorithmus auch nicht.

CRC32 in Action

Sollte mehr Sicherheitsnetz erforderlich sein, dann kann man umfangreichere Algorithmen nutzen, wie z.B. CRC-32 oder MD5. So ist z.B die CRC-32 Prüfsumme des Satzes "Sie lesen YetAnotherBlog." gleich 3641265714. Vertausche ich Zeichen "Sie lesen YetAnotherBolg.", dann kommt 3388628869 raus usw.

Genau mit diesen Mitteln wird erkannt, ob eine CD zerkratzt ist oder ob ein ZIP-File ramponiert wurde. Denn ein einziges gekipptes Bit (aus 0 wird 1 oder aus 1 wird 0) von Millionen Bits reicht aus, um eine Datei unbrauchbar zu machen. Es gibt auch Verfahren, wo ein Bit egal ist. MP3 oder MPEG zum Beispiel. Da fällt ein falsches Bit überhaupt nicht auf. Aber oft ist es mehr als notwendig zu sehen, ob auch das letzte kleine Bit heil angekommen ist. Schliesslich ist sowas bei der Überweisung von Lottogewinnen extrem wichtig.

Photo by exfordy under CC-BY-2.0

YetAnotherBlog - Adventskalender Türchen 7 - Prüfsummen Heute gibt es ein trockenes Thema, dass aber hoffentlich wenigstens interessant ist - Prüfsummen. Was zum Teufel sind Prüfsummen? Prüfsummen sind eigentlich typische Informatiker- und Mathematiker-Sachen und Otto-Normalverbraucher will es übe...

Watson

Ab dem 7. Absatz hat mein Gehirn abgeschaltet und das mit Mathe-Leistungskurs ;) Aber jetzt weiß ich, daß es eine Prüfsumme gibt, ich erinnere mich ganz dunkel, schon mal davon gehört zu haben.
2007-12-07 - 08:41:12 - Watson

Marco Kaiser

MD5 ist nicht mehr kollisionsfrei.
http://www.hackszine.com/bl...
Für alle die sich dafür interessieren.
2007-12-07 - 10:37:47 - Marco Kaiser

Rene99

@Marco: MD5 war noch nie als kollisionsfrei angenommen, nur man dachte, dass es nicht einfach werden würde zwei identische Strings/Datensätze zu finden, die die gleiche Summe bilden.
2007-12-07 - 10:41:15 - Rene99

Andreas

das dumme ist nur das mir das bei einem beschädigten zip oder rar usw. auch nicht mehr viel bringt (wenn keine repair infos bei sind)... wie so oft...
ok man weis nun das die datei quasi durch das/beim komprimieren/ beschädigt wurde... bzw das paket defekt ist...
2007-12-07 - 10:59:59 - Andreas

Rene99

@Andreas: Aber immerhin weisst Du es und wirst nicht in Sicherheit gewogen und wunderst Dich Wochen später, warum Deine Dokumente alle nicht zu öffnen gehen.
2007-12-07 - 11:01:36 - Rene99

Andreas

da fällt mir noch was ein... warum kann es vorkommen das wenn ich komprimierte datein aus dem netz lade diese defekt sein können (ich diese also nochmals herunter lade) wo es doch hier eigentlich auch eine prüfsumme gibt... bzw CRC checks/interleaving?
Oder kann das nur bei fastpath/interleaving off vorkommen. Von abgebrochenen Downloads jetzt mal abgesehen...
2007-12-07 - 15:49:51 - Andreas

CountZero

es sei noch angemerkt, daß es allein in deutschland über 100 verschiedene kontonummern-prüfziffern-algorithmen gibt, da nicht nur jede bank ihr eigenes süppchen kocht, sondern allzu oft auch verschiedene niederlassungen desselben instituts historisch gewachsen eigene algorithmen verwenden.

man kann <a href="http://www.bundesbank.de/za...">bei der bundesbank</a> eine stets aktuelle liste der verschiedenen derzeit eingesetzten algorithmen herunterladen, die nicht nur aufgelistet, sondern auch umfassend erklärt sind.

viele dieser algorithmen sind abwandlungen der klassischen modulo11-prüfung, aber es gibt auch deutlich absurdere verfahren.

ach ja, und noch etwas: nicht immer ist die letzte ziffer die prüfziffer. es gibt auch banken, die ZWEI prüfziffern verwenden, manchmal steht die prüfziffer außerdem vorne oder sogar mitten in der kontonummer drin, und einige verfahren haben die prüfziffern sogar in der kontonummer verteilt abgelegt.

die ISBN, der EAN-barcode auf unsseren lebensmitteln und viele weitere für den verbraucher alltägliche nummern sind übrigens ebenfalls durch die bank hinweg mit prüfziffern gegen übertragungsfehler abgesichert.
2007-12-07 - 19:48:15 - CountZero

Mit der Einführung der Europäischen Datenschutzgrundverordnung schliesse ich die Kommentarfunktion dieses Blogs, weil ich einfach keinen Bock auf die Arbeit habe, die dabei entsteht. Wer sich bei mir melden möchte, meine Mailadresse steht im Impressum. Hier der unnötige Hinweis, dass ich natürlich durch die Zusendung einer E-Mail in den Besitz von personenbezogenen Daten gelange. Der restliche Kram steht dann bei mir im Datenschutz.