Luhn-Algorithmus - Luhn algorithm
Die Luhn - Algorithmus oder Luhn Formel , die auch als „bekannten Modul 10“ oder „mod 10“ Algorithmus , nach seinem Schöpfer, mit dem Namen IBM Wissenschaftler Hans Peter Luhn , ist eine einfache Prüfsumme Formel verwendet , um eine Vielzahl von Identifikationsnummern zu überprüfen, wie Kredit Kartennummern , IMEI-Nummern , Nationale Anbieter-Identifikationsnummern in den Vereinigten Staaten, kanadische Sozialversicherungsnummern , israelische ID-Nummern, südafrikanische ID-Nummern, schwedische nationale Identifikationsnummern , schwedische Unternehmensidentifikationsnummern (OrgNr), griechische Sozialversicherungsnummern (ΑΜΚΑ), SIM-Kartennummern und Umfragecodes, die auf Quittungen von McDonald's , Taco Bell und Tractor Supply Co. erscheinen . Es ist im US-Patent Nr. 2,950,048, erteilt am 23. August 1960, beschrieben.
Der Algorithmus ist gemeinfrei und wird heute häufig verwendet. Es ist in ISO/IEC 7812 -1 spezifiziert . Es soll keine kryptographisch sichere Hash-Funktion sein ; Es wurde entwickelt, um vor versehentlichen Fehlern und nicht vor böswilligen Angriffen zu schützen. Die meisten Kreditkarten und viele staatliche Identifikationsnummern verwenden den Algorithmus als einfache Methode, um gültige Nummern von falsch eingegebenen oder anderweitig falschen Nummern zu unterscheiden.
Beschreibung
Die Prüfziffer wird wie folgt berechnet:
- Nehmen Sie die ursprüngliche Zahl und beginnend mit der ganz rechten Ziffer nach links, verdoppeln Sie den Wert jeder zweiten Ziffer (einschließlich der Ziffer ganz rechts).
- Ersetzen Sie den resultierenden Wert an jeder Position durch die Summe der Ziffern des Werts dieser Position.
- Summieren Sie die resultierenden Werte aus allen Positionen ( s ).
- Die berechnete Prüfziffer ist gleich .
Beispiel für die Berechnung der Prüfziffer
Angenommen, ein Beispiel für eine Kontonummer "7992739871" (nur die "Nutzlast", Prüfziffer noch nicht enthalten):
| 7 | 9 | 9 | 2 | 7 | 3 | 9 | 8 | 7 | 1 | |
| Multiplikatoren | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|
| = | = | = | = | = | = | = | = | = | = | |
| 7 | 18 | 9 | 4 | 7 | 6 | 9 | 16 | 7 | 2 | |
| Summenziffern | 7 | 9 (1+8) | 9 | 4 | 7 | 6 | 9 | 7 (1+6) | 7 | 2 |
Die Summe der resultierenden Ziffern ist 67.
Die Prüfziffer ist gleich .
Dadurch wird die vollständige Kontonummer 79927398713 gelesen.
Beispiel für die Validierung der Prüfziffer
Schneiden Sie einfach die Prüfziffer (letzte Ziffer) der zu validierenden Nummer ab. 79927398713 -> 7992739871 Berechnen Sie die Prüfziffer (siehe oben) (3) und vergleichen Sie Ihr Ergebnis mit der abgeschnittenen Prüfziffer (3 = 3). Wenn sie mit der Zahl übereinstimmen, haben Sie den Test bestanden.
Stärken und Schwächen
Der Luhn-Algorithmus erkennt jeden einstelligen Fehler sowie fast alle Transpositionen benachbarter Ziffern. Es wird jedoch nicht die Vertauschung der zweistelligen Folge 09 in 90 (oder umgekehrt) erkennen. Es werden die meisten der möglichen twin Fehler erkennen (es ist nicht erkennt 22 ↔ 55 , 33 ↔ 66 oder 44 ↔ 77 ).
Andere, komplexere Prüfzifferalgorithmen (wie der Verhoeff-Algorithmus und der Damm-Algorithmus ) können mehr Transkriptionsfehler erkennen. Der Luhn-Mod-N-Algorithmus ist eine Erweiterung, die nicht-numerische Zeichenfolgen unterstützt.
Da der Algorithmus die Ziffern von rechts nach links verarbeitet und Nullstellen das Ergebnis nur dann beeinflussen, wenn sie eine Positionsverschiebung verursachen, wirkt sich das Auffüllen mit Nullen am Anfang einer Zahlenfolge nicht auf die Berechnung aus. Daher können Systeme, die auf eine bestimmte Anzahl von Stellen auffüllen (z. B. durch Umwandeln von 1234 in 0001234), eine Luhn-Validierung vor oder nach dem Auffüllen durchführen und das gleiche Ergebnis erzielen.
Der Algorithmus erschien in einem US-Patent für ein handgehaltenes, mechanisches Gerät zum Berechnen der Prüfsumme. Daher musste es ziemlich einfach sein. Das Gerät nahm die Mod-10-Summe mechanisch auf. Die Substitutionsziffern , also die Ergebnisse des Doppel- und Reduktionsverfahrens, wurden nicht maschinell erzeugt. Vielmehr wurden die Ziffern in ihrer permutierten Reihenfolge auf dem Körper der Maschine markiert.
Pseudocode-Implementierung
function checkLuhn(string purportedCC) {
int nDigits := length(purportedCC)
int sum := integer(purportedCC[nDigits-1])
int parity := (nDigits-1) modulus 2
for i from 0 to nDigits - 2 {
int digit := integer(purportedCC[i])
if i modulus 2 = parity
digit := digit × 2
if digit > 9
digit := digit - 9
sum := sum + digit
}
return (sum modulus 10) = 0
}
Verweise
- ^ a b US-Patent 2950048A , Luhn, Hans P. , "Computer zum Verifizieren von Zahlen", veröffentlicht 1960-08-23
- ^ "Anhang B: Luhn-Formel zur Berechnung von Modulus-10 "Double-Add-Double"-Prüfziffern". Identifikationskarten — Identifizierung der Aussteller — Teil 1: Nummerierungssystem (Standard). Internationale Organisation für Normung , Internationale Elektrotechnische Kommission . Januar 2017. ISO/IEC 7812 -1:2017.