- Luhn-Formel
-
Der Luhn-Algorithmus oder die Luhn-Formel, auch bekannt als „Modulo 10“- oder „mod 10“-Algorithmus, wurde in den 1960er Jahren von Hans Peter Luhn als eine Methode der Überprüfung von Identifikationsnummern entwickelt. Er ist eine simple Prüfsummen-Formel, die benutzt wird, um eine Vielzahl von Identifikationsnummern wie Kreditkartennummern und kanadische Sozialversicherungsnummern zu bestätigen.
Der Algorithmus ist gemeinfrei und heutzutage weit verbreitet. Er ist nicht als kryptografisch sichere Hash-Funktion entworfen. Er schützt vor zufälligen Fehlern, nicht vor absichtlichen Angriffen. Die meisten Kreditkarten und viele behördliche Identifikationsnummern benutzen den Algorithmus als eine simple Methode, um gültige Nummern von zufälligen Nummernkombinationen zu unterscheiden.
Der Luhn-Algorithmus erkennt jeden Fehler an einzelnen Ziffern, ebenso wie die meisten Vertauschungen nebeneinanderstehender Ziffern. Er erkennt jedoch nicht die Vertauschung der Sequenz 09 mit 90 oder umgekehrt.
Inhaltsverzeichnis
Informelle Erläuterung
Die Formel generiert eine Prüfziffer, welche in der Regel an die unvollständige Identifikationsnummer angehängt wird, um die vollständige Nummer zu erhalten. Diese Nummer muss den folgenden Algorithmus bestehen:
- Beginnend mit der zweitletzten Ziffer und nach links durchlaufend, verdopple den Wert jeder zweiten Ziffer. Für jede Ziffer aus welcher 10 oder mehr wird, bilde die Quersumme (heißt: addiere die einzelnen Ziffern). Zum Beispiel wird 1111 zu 2121 und 8763 wird zu 7733 (von (1+6)7(1+2)3).
- Addiere all diese Zahlen zusammen. Beispiel: 1111 wird 2121, dann 2+1+2+1=6; 8763 wird 7733, dann 7+7+3+3=20.
- Wenn die letzte Ziffer der Gesamtsumme 0 ist (anders gesagt: Wenn Gesamtsumme modulo 10 gleich 0 ist), dann ist die Nummer nach dem Luhn-Algorithmus gültig, sonst nicht. Also ist 1111 nicht gültig (siehe oben, die letzte Ziffer der Gesamtsumme ist 6), 8763 aber schon (siehe oben, die letzte Ziffer von 20 ist 0).
Algorithmus
Der Algorithmus läuft in drei Schritten ab. Im ersten Schritt wird jede zweite Ziffer, beginnend der zweiten von rechts, verdoppelt. Wenn das Resultat größer als 9 ist, wird die Quersumme des Resultats der Verdopplung gebildet (2 wird zu 4, 7 wird zu 5). Im zweiten Schritt werden alle Zahlen summiert. Schließlich im letzten Schritt wird das Resultat durch 10 dividiert. Wenn der Rest gleich 0 ist, ist die originale Ziffernfolge, die es zu überprüfen galt, gültig.
Beispielimplementierungen
Pseudo-Code
function checkLuhn(string purportedCC) { int sum := 0 int nDigits := length(purportedCC) int parity := nDigits modulus 2 for i from 0 to nDigits - 1 { 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 }
C
#include <stdlib.h> // für atoi #include<string.h> // für strlen bool checkLuhn(const char *pPurported) { int nSum = 0; int nDigits = strlen(pPurported); int nParity = (nDigits-1) % 2; char cDigit[2] = '\0\0'; // atoi erwartet einen null-terminierten String for (int i = nDigits; i > 0 ; i--) { cDigit[0] = pPurported[i-1]; int nDigit = atoi(cDigit); if (nParity == i % 2) nDigit = nDigit * 2; nSum += nDigit/10; nSum += nDigit%10; } return 0 == nSum % 10; }
C#
Der Code gibt den Luhn für einen int String zurück:
public static int GetLuhn(string data) { int sum = 0; bool odd = true; for (int i = data.Length - 1; i >= 0; i--) { if (odd == false) { int tSum = Convert.ToInt32(data[i].ToString()) * 2; if (tSum >= 10) { tSum = tSum - 9; } sum += tSum; } else sum += Convert.ToInt32(data[i].ToString()); odd = !odd; } return (((sum / 10) + 1) * 10) - sum; }
PHP
function checkLuhn($purportedCC) { $sum = 0; $nDigits = strlen($purportedCC); $parity = $nDigits % 2; for ($i = 0; $i < $nDigits; $i++) { $digit = $purportedCC[$i]; if ($parity == ($i % 2)) $digit = $digit << 1; $digit = ($digit > 9) ? ($digit - 9) : $digit; $sum += $digit; } return (0 == ($sum % 10)); }
Java
public static boolean check(int[] digits) { int sum = 0; int length = digits.length; int parity = length % 2; for (int i = 0; i < length; i++) { // get digits in reverse order int digit = digits[length - i - 1]; // if current digit is not checksum AND mod2 equals parity then multiply with 2 if ( (i > 0) && (i % 2 == parity) ) { digit *= 2; } sum += digit > 9 ? digit - 9 : digit; } return sum % 10 == 0; }
Beispiel
Gegeben sei die Beispiel-Identifikationsnummer 446-667-651.
Ziffer Verdoppelt Reduziert Summe der Ziffern 1 1 1 5 10 1+0 1 6 6 6 7 14 1+4 5 6 6 6 6 12 1+2 3 6 6 6 4 8 8+0 8 4 4 4 Gesamtsumme: 40 Die Summe von 40 wird durch 10 dividiert; der Rest ist 0 - also ist die Nummer gültig.
Weblinks
- Java-Implementierung
- JavaScript-Implementierung
- Perl-Implementierung für Kreditkarten - Funktioniert (getestet)
- Perl-Implementierung - Funktioniert (getestet)
- PHP-Implementierung
- Python-Implementierung
- Online Luhn-Prüfung
Wikimedia Foundation.