Luhn-Algorithmus

Der Luhn-Algorithmus oder die Luhn-Formel (Entwickler: IBM- Wissenschaftler Hans Peter Luhn ), auch bekannt als „ Modulus 10“- oder „Mod 10“ -Algorithmus , ist eine einfache Prüfziffernformel zur Validierung verschiedener Identifikationsnummern. ^{[ a ]} Ziel ist es, ein Nummerierungsschema so zu gestalten, dass ein Computer die eingegebene Zahl schnell auf Fehler überprüfen kann.

Der Algorithmus ist gemeinfrei und weit verbreitet. Er ist in ISO/IEC 7812-1 spezifiziert . ^{[ 2 ]} Er ist nicht als kryptografisch sichere Hash-Funktion gedacht ; er wurde zum Schutz vor versehentlichen Fehlern, nicht vor böswilligen Angriffen, entwickelt. Die meisten Kreditkartennummern und viele amtliche Ausweisnummern verwenden den Algorithmus als einfache Methode, um gültige Nummern von falsch eingegebenen oder anderweitig fehlerhaften Nummern zu unterscheiden.

Die Prüfziffer wird wie folgt berechnet:

1. Entfernen Sie die Prüfziffer aus der Nummer (falls sie bereits vorhanden ist). Dadurch bleibt die Nutzlast übrig.
2. Beginnen Sie mit den Nutzlastziffern und verdoppeln Sie jede zweite Ziffer (eine Ziffer an einer ungeraden Position in umgekehrter Reihenfolge), wenn Sie von links nummerieren.
3. Verarbeite die Nutzdaten von rechts nach links. Wenn eine verdoppelte Ziffer größer als 9 ist , subtrahiere 9 von der Ziffer.
4. Addiere alle resultierenden Ziffern (einschließlich derer, die nicht verdoppelt wurden).
5. Die Prüfziffer wird durch die Formel berechnet , wobei s die Summe aus Schritt 4 ist. Dies ist die kleinste Zahl (möglicherweise Null), die zu addiert werden muss, um ein Vielfaches von 10 zu erhalten.${\displaystyle (10-(s{\bmod {10}})){\bmod {10}}}$${\displaystyle s}$
6. Andere gültige Formeln, die denselben Wert liefern, sind , , und . Beachten Sie, dass die Formel aufgrund von Unterschieden in der Behandlung negativer Zahlen durch die Modulo- Operation nicht in allen Umgebungen funktioniert.${\displaystyle 9-((s+9){\bmod {10}})}$${\displaystyle (10-s){\bmod {10}}}$${\displaystyle 10\lceil s/10\rceil -s}$${\displaystyle (10-s){\bmod {10}}}$

Nehmen wir als Beispiel die Kontonummer 1789372997 (nur die „Nutzdaten“, Prüfziffer noch nicht enthalten):

Die Summe der resultierenden Ziffern beträgt 56.

Die Prüfziffer ist gleich . ${\displaystyle (10-(56{\bmod {10}})){\bmod {10}}=4}$

Die vollständige Kontonummer lautet somit 17893729974.

1. Die Prüfziffer (letzte Ziffer) der Zahl wird zur Validierung entfernt. (z. B. 17893729974 → 1789372997)
2. Berechnen Sie die Prüfziffer (siehe oben).
3. Vergleichen Sie Ihr Ergebnis mit der ursprünglichen Prüfziffer. Stimmen beide Zahlen überein, ist das Ergebnis gültig. (z. B. (gegebene Prüfziffer = berechnete Prüfziffer) ⇔ (gültige Prüfziffer)).

Der Luhn-Algorithmus erkennt alle Fehler einzelner Ziffern sowie nahezu alle Vertauschungen benachbarter Ziffern. Er erkennt jedoch nicht die Vertauschung der zweistelligen Ziffernfolge 09 zu 90 (oder umgekehrt). Die meisten möglichen Zwillingsfehler werden erkannt (ausgenommen sind 22 ↔ 55 , 33 ↔ 66 und 44 ↔ 77 ).

Andere, komplexere Prüfziffernalgorithmen (wie der Verhoeff-Algorithmus und der Damm-Algorithmus ) können mehr Übertragungsfehler erkennen. Der Luhn-mod-N-Algorithmus ist eine Erweiterung, die nicht-numerische Zeichenketten unterstützt.

Da der Algorithmus die Ziffern von rechts nach links verarbeitet und Nullziffern das Ergebnis nur dann beeinflussen, wenn sie eine Positionsverschiebung verursachen, hat das Auffüllen einer Zahlenfolge mit Nullen keinen Einfluss auf die Berechnung. Systeme, die auf eine bestimmte Anzahl von Ziffern auffüllen (z. B. durch Umwandlung von 1234 in 0001234), können daher die Luhn-Validierung vor oder nach dem Auffüllen durchführen und erzielen dasselbe Ergebnis.

Der Algorithmus wurde in einem US-Patent ^{[ 1 ]} für ein einfaches, handliches, mechanisches Gerät zur Berechnung der Prüfsumme beschrieben. Das Gerät ermittelte die Summe modulo 10 mechanisch. Die Ersatzziffern , d. h. die Ergebnisse der Verdopplungs- und Reduktionsprozedur, wurden nicht mechanisch erzeugt. Stattdessen waren die Ziffern in ihrer permutierten Reihenfolge auf dem Gehäuse des Geräts markiert.

Die folgende Funktion nimmt eine Kartennummer einschließlich der Prüfziffer als Array von ganzen Zahlen entgegen und gibt true aus , wenn die Prüfziffer korrekt ist, andernfalls false .

Funktion isValid(Kartennummer[1..Länge]) sum := 0 Parität := Länge mod 2 für i von 1 bis (Länge - 1) tue wenn i mod 2 == Parität dann sum := sum + cardNumber[i] elseif cardNumber[i] > 4 then sum := sum + 2 * cardNumber[i] - 9 anders sum := sum + 2 * cardNumber[i] Ende falls Ende für Rückgabe Kartennummer[Länge] == ((10 - (Summe mod 10)) mod 10) Ende Funktion

Der Luhn-Algorithmus wird in einer Vielzahl von Systemen verwendet, darunter:

• Kreditkartennummern
• IMEI-Nummern
• CUSIP- Nummern für nordamerikanische Finanzinstrumente
• Nationale Anbieteridentifikationsnummern in den Vereinigten Staaten
• Kanadische Sozialversicherungsnummern
• Israelische Ausweisnummern
• Südafrikanische Ausweisnummern
• Südafrikanische Steuerreferenznummern
• Schwedische Personenkennnummern
• Schwedische Unternehmensidentifikationsnummern (OrgNr)
• Griechische Sozialversicherungsnummern (ΑΜΚΑ)
• ICCID von SIM-Karten
• Europäische Patentanmeldenummern
• Umfragecodes auf Kassenbons von McDonald's , Taco Bell und Tractor Supply Co.
• Die Sendungsverfolgungsnummern des United States Postal Service verwenden einen modifizierten Luhn-Algorithmus ^{[ 3 ].}
• Italienische Umsatzsteuer-Identifikationsnummern ( Partita Iva ) ^{[ 4 ]}

• Luhn-Test von Kreditkartennummern auf Rosetta Code : Implementierung des Luhn-Algorithmus/der Luhn-Formel in 160 Programmiersprachen (Stand: 22. Juli 2024)