Der Luhn Algorithmus ist der Grund, warum eine Kartennummer mit einer Ziffer endet, die willkürlich wirkt. Er ist eine Prüfsumme – eine kleine arithmetische Zusammenfassung aller Ziffern davor – und er ist die häufigste automatische Prüfung, die eine Kartennummer bestehen muss, bevor irgendetwas anderes passiert. Entwickelt wurde er in den 1950er Jahren bei IBM von Hans Peter Luhn; später wurde er durch die internationale Norm für die Kartennummerierung zur Konvention für Zahlungskarten.
Dieser Beitrag erklärt, wozu die Prüfziffer dient, wie man sie auf Papier ausrechnet, warum sie die meisten Tippfehler abfängt und warum ihr Bestehen weit weniger bedeutet, als viele annehmen.
Was der Luhn Algorithmus leistet
Nehmen Sie eine Kartennummer, legen Sie die letzte Ziffer beiseite und lassen Sie die übrigen Ziffern durch ein festes Verfahren laufen. Das Ergebnis bestimmt, welche Ziffer am Ende stehen muss. Eine Nummer wird akzeptiert, wenn die Schlussziffer mit allem davor zusammenpasst.
An diesem Verfahren ist keine Bank, keine Kontenliste und kein Geheimnis beteiligt. Es ist Arithmetik, die in Lehrbüchern steht, in nahezu jeder Programmiersprache nachgebaut ist und in Bruchteilen einer Millisekunde berechnet werden kann. Sie beantwortet genau eine enge Frage: Enthält diese Zeichenfolge einen offensichtlichen Übertragungsfehler?
Diese Enge wird leicht vergessen. Weil die Prüfsumme die sichtbarste automatische Prüfung in einem Checkout-Formular ist, beginnen Menschen zu glauben, sie sage mehr aus, als sie kann.
Wie berechnet man eine Prüfziffer von Hand?
Das Verfahren läuft von rechts nach links über die Ziffern, die übrig bleiben, wenn man die Schlussziffer entfernt.
- Schreiben Sie die Ziffern auf und nummerieren Sie ihre Positionen von rechts, beginnend bei eins.
- Verdoppeln Sie jede Ziffer auf einer geraden Position.
- Übersteigt ein verdoppelter Wert die Neun, ziehen Sie neun davon ab. Das ist dasselbe wie das Addieren der beiden Ziffern des Ergebnisses.
- Addieren Sie alle Werte.
- Ermitteln Sie, wie viel Sie addieren müssten, um das nächste Vielfache von zehn zu erreichen. Dieser Betrag ist die Prüfziffer.
Ein kurzes Beispiel macht es greifbar. Nehmen Sie die fünf Ziffern 1, 2, 3, 4 und 5 als Rumpf einer längeren Nummer und nummerieren Sie sie von rechts: Die 5 steht auf Position eins, die 4 auf Position zwei, die 3 auf Position drei, die 2 auf Position vier und die 1 auf Position fünf. Das Verdoppeln der geraden Positionen macht aus der 4 eine 8 und aus der 2 eine 4. Die Werte lauten dann 1, 4, 3, 8 und 5, zusammen 21. Das nächste Vielfache von zehn ist 30, die Prüfziffer ist also 9, und die fertige Folge endet auf 9.
Diese Rechnung von Hand für eine vollständige Kartennummer durchzuführen ist mühsam, aber nie mehrdeutig. Software geht die Zeichenfolge von ihrem Ende aus durch, und deshalb weist eine Implementierung, die von der falschen Seite startet, einwandfreie Nummern zurück.
Warum erkennt die Verdopplung vertauschte Ziffern?
Die Verdopplungsregel ist nicht willkürlich gewählt. Sie macht das Gewicht jeder Ziffer von ihrer Position abhängig, sodass das Vertauschen zweier Nachbarn die Summe in der Regel verändert.
Das ist wichtig, weil die beiden häufigsten menschlichen Fehler in einem Zahlenfeld das Vertippen einer einzelnen Ziffer und das Vertauschen zweier benachbarter Ziffern sind. Eine falsche Ziffer verschiebt die Summe um einen Wert ungleich null, die Prüfsumme scheitert also fast immer. Auch ein Tausch zwischen Nachbarn verschiebt die Summe, weil eine der beiden verdoppelt wurde und die andere nicht.
Fast immer, aber nicht immer. Einige Vertauschungen bleiben für diese Prüfung unsichtbar. Der klassische blinde Fleck ist das Paar aus null und neun direkt nebeneinander: Neun verdoppelt und um neun verringert ergibt wieder neun, die beiden können also die Plätze tauschen, ohne die Summe zu ändern. Andere Paarungen verhalten sich genauso. Die treffende Beschreibung lautet daher: Die Prüfung fängt jeden einzelnen Ziffernfehler ab und die meisten, aber nicht alle benachbarten Vertauschungen.
Was die Prüfziffer nicht verrät
Sie kann nicht sagen, ob eine Nummer echt ist. Nichts in der Arithmetik bezieht sich auf einen Herausgeber; jedes Präfix lässt sich mit beliebigen mittleren Ziffern verbinden, und eine passende Schlussziffer lässt sich dazu berechnen.
Sie kann nicht sagen, ob ein Konto offen ist, ob eine Karte gesperrt wurde oder ob die Person, die die Nummer eintippt, die Karte tatsächlich in der Hand hält. Jede dieser Fragen erfordert eine Autorisierungsanfrage beim Herausgeber, also genau den Vorgang, den eine Testumgebung vermeiden muss.
Sie bürgt auch nicht für das Ablaufdatum, den Namen des Karteninhabers oder den Sicherheitscode. Diese Felder stehen neben der Prüfziffer und haben eigene Regeln; eine Nummer, die die Prüfsumme erfüllt, lässt sich mit einem bereits vergangenen Datum und einem Code kombinieren, der zu nichts passt.
Das ist die ehrliche Beschreibung dessen, was der Erzeuger auf dieser Seite zurückgibt: Jeder Wert ist strukturell gültig und mit dieser Prüfsumme verträglich, und jeder einzelne davon wurde nie an jemanden ausgegeben.
Wo dieselbe Prüfsumme sonst auftaucht
Zahlungskarten sind der bekannteste Nutzer dieses Verfahrens, aber nicht der einzige. Nummerierungssysteme, die einen billigen Schutz gegen Tippfehler brauchen, greifen häufig zu derselben öffentlichen Arithmetik. Darunter sind mehrere nationale Identifikationsnummern, verschiedene Kundenkarten- und Geschenkkartensysteme und zahlreiche interne Kennungen.
Diese Wiederverwendung hat eine praktische Folge. Eine gemeinsame Hilfsfunktion, die eine bestandene Prüfsumme als Beweis für eine Kreditkarte behandelt, wird alles andere falsch einordnen, was die Prüfung ebenfalls besteht. Benennen Sie die Routine nach dem, was sie tut, nämlich nach einer Modulo-zehn-Prüfsumme, und nicht nach dem Bereich, in dem Sie sie zuerst kennengelernt haben.
Für Entwickler: Prüfreihenfolge und typische Fallen
Die Reihenfolge der Prüfungen ist wichtiger, als man erwartet, und die Prüfsumme ist nicht der richtige Anfang.
Prüfen Sie zuerst die Länge, denn das Verfahren hat keine Meinung dazu, wie viele Ziffern man ihm übergibt; ein fünfstelliges Fragment kann prüfsummenkonsistent und trotzdem unbrauchbar sein. Prüfen Sie als Nächstes den Zeichensatz, damit Buchstaben, verirrte Leerzeichen und Trennzeichen zurückgewiesen werden, bevor irgendeine Arithmetik läuft. Berechnen Sie danach die Prüfsumme, und versuchen Sie erst dann, ein Netzwerk am Präfix zu erkennen.
Drei Fallen tauchen immer wieder auf:
- Eine führende Null für bedeutungslos zu halten. Kartennummern sind Zeichenketten und keine ganzen Zahlen, und ein numerisches Parsen kann still eine Ziffer verlieren, was zu einem Prüfsummenfehler führt, der nichts mit der Eingabe des Nutzers zu tun hat.
- Den Verdopplungsdurchlauf von links zu starten. Die Position ist von rechts definiert; die Richtung gehört daher zur Spezifikation und ist kein Implementierungsdetail.
- Eine gescheiterte Prüfsumme als abgelehnte Karte zu melden. Sie bedeutet fehlerhafte Eingabe, und die Meldung an den Nutzer sollte genau das sagen.
Für Testdaten ist das nützliche Muster, Paare zu halten: eine Nummer, die besteht, und dieselbe Nummer mit einer geänderten Ziffer, sodass sie scheitert. Damit hat die Suite einen positiven und einen negativen Fall, die sich in genau einem Zeichen unterscheiden, und eine Regression fällt sofort ins Auge. Der Leitfaden zum Kartenformat behandelt die Längen- und Präfixregeln, die vor der Prüfsumme laufen sollten, und die Prüfschritte im Code setzen die ganze Reihenfolge zusammen.
Eine Prüfsumme an einer echten Zeichenfolge nachvollziehen
Der schnellste Weg zu einem Gefühl für die Sache ist, ein paar Zeichenfolgen durch den Kartennummern-Generator zu schicken. Erzeugen Sie ein Paket, ändern Sie von Hand eine Ziffer und beobachten Sie, wie die Prüfung fehlschlägt. Erzeugen Sie erneut und stellen Sie fest, dass sich nur die Schlussziffer bewegt, während alles davor unverändert bleibt. Der Netzwerkvergleich lohnt sich als Nächstes, weil dieselbe Arithmetik sich bei fünfzehn- und sechzehnstelligen Schemata unterschiedlich verhält und genau dieser Unterschied handgeschriebene Hilfsfunktionen stolpern lässt.
Nächste Schritte
Schreiben Sie Ihre Prüfreihenfolge auf, bevor Sie den Code schreiben, mit der Prüfsumme an vorletzter Stelle, und legen Sie für jede gültige Nummer in Ihrer Suite eine absichtlich verfälschte Vorlage ab. Wenn Sie sehen möchten, wie Längen und Präfixe mit der Schlussziffer zusammenspielen, gehen Sie weiter zum Leitfaden zum Kartenformat.