Luhn-Algorithmus


Luhn-Algorithmus

Der Luhn-Algorithmus oder die Luhn-Formel, auch bekannt als „Modulo 10“- oder „mod 10“-Algorithmus und als Double-Add-Double-Methode, wurde in den 1960er Jahren von Hans Peter Luhn als eine Methode der Überprüfung von Identifikationsnummern entwickelt. Es 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 keine kryptologische Hashfunktion und schützt deshalb zwar vor zufälligen Fehlern, jedoch nicht vor absichtlichen Angriffen. Die meisten Kreditkarten und viele behördliche Identifikationsnummern, aber auch die Bahn bei den Nummern der Loks und Waggons, benutzen den Algorithmus als einfache 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:

  1. 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). Aus den Ziffern 0,1,2,3,4,5,6,7,8,9 werden also der Reihe nach die Ziffern 0,2,4,6,8,1,3,5,7,9. Damit irrtümliche Vertauschungen der Ziffernreihenfolge die Prüfziffer verändern, wird diese Operation nur auf jede zweite Ziffer angewendet. Insgesamt wird zum Beispiel 1111 zu 2121 oder 8763 wird zu 7733 (von (1+6)=7 und (1+2)=3).
  2. Addiere all diese Zahlen zusammen. Beispiel: 1111 wird 2121, dann 2+1+2+1=6; 8763 wird 7733, dann 7+7+3+3=20.
  3. Wenn die letzte Ziffer der Gesamtsumme 0 ist (anders gesagt: Wenn die 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 bei 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 überprüft, ob ein String nach dem Algorithmus gültig ist:

  public static bool CheckLuhn(string data) {
     int sum = 0;
     int len = data.Length;
     for(int i = 0; i < len; i++) {
        int add = ((int)data[i] - 48) * (2 - (i + len) % 2);
        add -= add > 9 ? 9 : 0;
        sum += add;
     }
     return sum % 10 == 0;
  }

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 Beispielidentifikationsnummer 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.

Anwendung bei EC Karten

Bei EC Karten (Kredit/Debit) unterscheidet sich die Berechnung der Nummer geringfügig. Da die Prüfziffer im Magnetstreifen nur einstellig sein darf, wird aus einer Zahl, die auf "0" endet, eine "0"(10=0,20=0 usw).

Außerdem wird jede zweite Zahl, ausgehend von der ganz rechten (statt der zweiten von rechts) verdoppelt (1010 wird zu 1010, 0101 wird zu 0202).

Der Algorithmus in C#

       public static int GetLuhn(string data)
       {
           int sum = 0;
           bool odd = false;
           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;
           }
           int erg = (((sum / 10) + 1) * 10) - sum;
           if (erg.ToString().EndsWith("0"))
           {
               erg = 0;
           }
           return erg;
       }

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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… …   Deutsch Wikipedia

  • Hans Peter Luhn — (* 1. Juli 1896 in Barmen; † 19. August 1964) war ein deutscher Informatiker bei IBM, Erfinder des Luhn Algorithmus und der KWIC Indexierung. Ihm wurden über 80 Patente zugesprochen. Leben Luhn wurde 1896 als Sohn des Druckereibesitzers Peter… …   Deutsch Wikipedia

  • Extraktionsalgorithmus nach Luhn — Hans Peter Luhns Arbeit Automatic Creation of Literature Abstracts von 1958 beschreibt die erste Implementierung eines Algorithmus zur Satzextraktion. Ziel dieser Satzextraktion war die automatische Auswahl von Sätzen zur Anfertigung eines… …   Deutsch Wikipedia

  • Luhnalgorithmus — 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… …   Deutsch Wikipedia

  • DUNS — D U N S ist die Abkürzung für Data Universal Numbering System, das 1962 von Dun Bradstreet (D B) erfunden wurde. Der heute international als Standard anerkannte Zahlencode dient der eindeutigen Identifizierung von Unternehmen. Eine DUNS® Nummer… …   Deutsch Wikipedia

  • International Securities Identification Number — Die International Securities Identification Number (ISIN) ist eine zwölfstellige Buchstaben Zahlen Kombination und stellt eine Identifikation für ein Wertpapier dar, das an der Börse gehandelt wird. Der Aufbau der ISIN wird in der ISO 6166… …   Deutsch Wikipedia

  • D-U-N-S — ist die Abkürzung für Data Universal Numbering System, das 1962 von Dun Bradstreet (D B) eingeführt wurde. Der heute international als Standard anerkannte Zahlencode dient der eindeutigen Identifizierung von Unternehmen. Eine DUNS Nummer können… …   Deutsch Wikipedia

  • Division mit Rest — Die Division mit Rest oder der Divisionsalgorithmus ist ein mathematischer Satz aus der Algebra und der Zahlentheorie. Er besagt, dass es zu zwei Zahlen n und eindeutig bestimmte Zahlen a und b gibt für die gilt. Die Zahlen a und b lassen sich… …   Deutsch Wikipedia

  • Institutionskennzeichen — Die Institutionskennzeichen (kurz: IK) sind eindeutige, neunstellige Zahlen, mit deren Hilfe Abrechnungen im Bereich der deutschen Sozialversicherung einrichtungsübergreifend abgewickelt werden können. Hierbei erhalten alle Einrichtungen, die… …   Deutsch Wikipedia

  • Kreditkarte — Kreditkarten Eine Kreditkarte ist eine Karte zur Zahlung von Waren und Dienstleistungen. Die meisten Kreditkarten sind weltweit einsetzbar, sowohl im realen täglichen Geschäfts wie Privatleben als auch bei Online Geldtransaktionen. Sie wird im… …   Deutsch Wikipedia