Luhn-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Loknummer mit Prüfsumme nach dem Luhn-Algorithmus bei der Deutschen Bahn

Der Luhn-Algorithmus oder die Luhn-Formel, auch bekannt als „Modulo 10“- oder „mod 10“-Algorithmus und als Double-Add-Double-Methode ist eine einfache Methode zur Berechnung einer Prüfsumme. Er wurde in den 1950er Jahren[1] von dem deutsch-amerikanischen Informatiker Hans Peter Luhn entwickelt und ist heute gemeinfrei und sehr weit verbreitet. Unter anderem dient der Luhn-Algorithmus der Verifizierung von Kreditkartennummern und kanadischen Sozialversicherungsnummern, ISINs und den siebenstelligen Kontonummern der Deutschen Bank und der Commerzbank sowie vieler Sparkassen. Er kommt auch bei den Nummern der Lokomotiven und Triebwagen nach dem Kennzeichnungsschema der UIC zum Einsatz, ebenso wie seit 1968 schon im Baureihenschema der Bundesbahn.

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.

Informelle Erläuterung[Bearbeiten | Quelltext bearbeiten]

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), was denselben Effekt hat als würde man 9 subtrahieren. 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 Ziffern. 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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Pseudo-Code[Bearbeiten | Quelltext bearbeiten]

 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[Bearbeiten | Quelltext bearbeiten]

  #include <stdlib.h> // für atoi
  #include <string.h> // für strlen
  #include <stdbool.h> // für bool

  bool checkLuhn(const char *pPurported)
  {
    int nSum       = 0;
    int nDigits    = strlen(pPurported);
    int nParity    = (nDigits-1) % 2;
    char cDigit[2] = "\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#[Bearbeiten | Quelltext bearbeiten]

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;
   }

Go[Bearbeiten | Quelltext bearbeiten]

func checkLuhn(purportedCC string) bool {
	var sum = 0
	var nDigits = len(purportedCC)
	var parity = nDigits % 2

	for i := 0; i < nDigits; i++ {
		var digit = int(purportedCC[i] - 48)
		if i%2 == parity {
			digit *= 2
		}
		if digit > 9 {
			digit -= 9
		}
		sum += digit
	}
	return sum%10 == 0
}

PHP[Bearbeiten | Quelltext bearbeiten]

 function checkLuhn($number) {
     $sum = 0;
     $numDigits = strlen($number)-1;
     $parity = $numDigits % 2;
     for ($i = $numDigits; $i >= 0; $i--) {
         $digit = substr($number, $i, 1);
         if (!$parity == ($i % 2)) {$digit <<= 1;}
         $digit = ($digit > 9) ? ($digit - 9) : $digit;
         $sum += $digit;
     }
     return (0 == ($sum % 10));
 }

Java[Bearbeiten | Quelltext bearbeiten]

   public static boolean check(int[] digits) {
       int sum = 0;
       int length = digits.length;
       for (int i = 0; i < length; i++) {

           // get digits in reverse order
           int digit = digits[length - i - 1];

           // every 2nd number multiply with 2
           if (i % 2 == 1) {
               digit *= 2;
           }
           sum += digit > 9 ? digit - 9 : digit;
       }
       return sum % 10 == 0;
   }

Python[Bearbeiten | Quelltext bearbeiten]

    def checkLuhn(purportedCC=''):
        sum = 0
        parity = len(purportedCC) % 2
        for i, digit in enumerate([int(x) for x in purportedCC]):
            if i % 2 == parity:
                digit *= 2
            if digit > 9:
                digit -= 9
            sum += digit
        return sum % 10 == 0

Haskell[Bearbeiten | Quelltext bearbeiten]

checkluhnIntegral:: Integral a => a -> Bool
checkluhnIntegral i = (lunvalIntegral i) == 0

genluhnIntegral:: Integral a => a -> a
genluhnIntegral i = (10*i) + mod (10 - lunvalIntegral (10*i)) 10

lunvalIntegral:: Integral a => a -> a
lunvalIntegral i = mod (singleNext i) 10
                   where
                     singleNext 0 = 0
                     singleNext i = (mod i 10) + doubleNext (div i 10)
                     doubleNext 0 = 0
                     doubleNext i = (luhndouble (mod i 10)) + singleNext (div i 10)

luhndouble a = dsum (2*a)
dsum a | a < 10    = a
       | otherwise = (dsum (div a 10)) + (mod a 10)

ILE-RPG (IBM native)[Bearbeiten | Quelltext bearbeiten]

D ccInvalidChar   C                   CONST('abcdefghi…')
…
 	§nLength = %len( %trim( §cString));

        for §nI = §nLength downto 1;
          §nJ = §nJ + 1;
          §cString1 = %subst( %trim( §cString): §nI : 1);
          MONITOR;
            §nInt = %DEC( %XLATE(ccInvalidChar: '0': §cString1): 1: 0);
          ON-ERROR 105;
            §nInt = 0;
          ENDMON;

          if %rem( §nJ: 2) = 0;
             §nInt = §nInt * 2;
          endif;

          if §nInt > 9;
            §cDigit1 = %subst( %char( §nInt): 1: 1);
            MONITOR;
              §nDigit1 = %dec( §cDigit1: 1: 0);
            ON-ERROR 105;
              §nDigit1 = 0;
            ENDMON;
            §cDigit2 = %subst( %char( §nInt): 2: 1);
            MONITOR;
              §nDigit2 = %dec( §cDigit2: 1: 0);
            ON-ERROR 105;
              §nDigit2 = 0;
            ENDMON;
            §nInt = §nDigit1 + §nDigit2;
          endif;
          §nResult = §nResult + §nInt;
        endfor;

        §nChkDigit = %rem( §nResult: 10);

Beispiel[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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#[Bearbeiten | Quelltext bearbeiten]

        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;
        }

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. U.S. Patent No. 2,950,048, Anmeldung eingereicht am 6. Januar 1954, Patent erteilt am 23. August 1960.

Weblinks[Bearbeiten | Quelltext bearbeiten]