REKLAMA

Algorytm Luhna

Algorytm Luhna lub metoda Luhna, znany również jako algorytm „modulus 10” lub „mod 10”, nazwany na cześć jego twórcy, naukowca IBM Hansa Petera Luhna, jest prostą formułą sumy kontrolnej używaną do walidacji różnych numerów identyfikacyjnych, takich jak numery kart kredytowych, numery IMEI, numery identyfikatorów krajowych dostawców w Stanach Zjednoczonych, kanadyjskie numery ubezpieczenia społecznego, izraelskie numery identyfikacyjne, greckie numery ubezpieczenia społecznego oraz Survey Code (pierwsze 20 cyfr) pojawiające się na paragonach w amerykańskim McDonald's, Taco Bell i Tractor Supply Co.

Metoda jest opisana w patencie USA nr 2,950,048, złożonym 6 stycznia 1954 r. i udzielonym 23 sierpnia 1960 r.

Algorytm znajduje się w domenie publicznej i jest obecnie powszechnie używany. Jest on określony w normie ISO/IEC 7812-1. Nie jest to kryptograficznie bezpieczna funkcja mieszania; został zaprojektowany w celu ochrony przed przypadkowymi błędami, a nie złośliwymi atakami. Jest prostą metodą rozróżniania prawidłowych numerów od błędnie wpisanych.

Numery takie mają następującą strukturę XXXXXXXC, gdzie XXXXXXX to numer identyfikacyjny (o dowolnej liczbie cyfr), a C to cyfra kontrolna.

Prosty algorytm Luhna

Algorytm sprawdzania poprawności ciągu cyfr liczby zabezpieczonego tą metodą przebiega następująco:

  • zaczynając od cyfry z prawej strony (czyli cyfry kontrolnej) poruszając się w lewą stronę podwajamy co drugą cyfrę (czyli drugą od prawej, czwartą od prawej, itd..),
  • jeżeli podwojona cyfra daje wynik dwucyfrowy, wówczas dodajemy do siebie jej cyfry.
    Czyli jeżeli na parzystej pozycji od strony prawej stoi 1 to zamieniamy ją na 2, jeżeli stoi 6 to zamieniamy ją na 3, bo 6*2=12 i dodajemy cyfry 1+2=3,
  • sumujemy wszystkie cyfry,
  • jeżeli suma dzieli się bez reszty przez 10 to numer ma prawidłową cyfrę kontrolną.

Rozszerzony algorytm Luhna

Rozszerzenie algorytmu Luhna polega na umożliwieniu użycia algorytmu do identyfikatorów alfanumerycznych czyli cyfr od 0 do 9 i liter od A do Z.

Literom od A do Z przydziela się wartości liczbowe od 10 do 36. Tak więc identyfkator ABCD1234 zamienia się na 10 11 12 13 1 2 3 4. Do tego ciągu 101112131234 stosuje się prosty algorytm Luhna.

Algorytm obliczenia nieznanej cyfry kontrolnej jest łatwy gdy robi się obliczenia na papierze.

Cyfra 4 9 9 2 7 6 5 5 C
Mnożnik 1 2 1 2 1 2 1 2 1
Wynik 4 18 9 4 7 12 5 10 C
Suma cyfr 4 1+8 9 4 7 1+2 5 1+0= 42+C

Aby suma cyfr była podzielna bez reszty przez 10, to cyfra kontrolna Ck musi wynosić 8, co daje pełny numer np. konta 499276558.

Sprawdzenie poprawności numeru wykonujemy podobnie:
Cyfra 4 9 9 2 7 6 5 5 8
Mnożnik 1 2 1 2 1 2 1 2 1
Wynik 4 18 9 4 7 12 5 10 8
Suma cyfr 4 1+8 9 4 7 1+2 5 1+0 8 Σ=50

Ponieważ reszta z dzielenia 50 przez 10 wynosi zero, więc sprawdzany numer jest prawidłowy. Prawidłowy w sensie zgodności cyfry kontrolnej.

Algorytm ten wykrywa każdy błąd pojedynczej cyfry, jak również większość zamian sąsiednich cyfr - tzw. czeski błąd - jeżeli ktoś przepisując kod wpisał 12 zamiast 21. Nie wykrywa jednak jednego czeskiego błędu - zamiany cyfr 09 z 90 (i na odwrót).

Uwagi do implementacji algorytmu

Na papierze wyglądo prosto ale gdy chcemy to zapisać jako algorytm programu komputerowego to wymaga to troche pomyślunku - jak zawsze w programowaniu :-)
W praktyce po prostu korzystamy z gotowej tablicy, albo wektora.

wek = new Array( 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 );

Wartośc cyfry mnożonej przez dwa jest indeksem do wektora.
Jeśli więc mnożymy 6*2 =12 -> 1+2 = 3 i 3 bierzemy do sumy, to korzysając z wektora pobieramy wek[6], który to element równa się 3.
Jest też inny sposób: dla parzystych pozycji w numerze, cyfrę mnożymy przez 2; jeżeli wynik > 9 wtedy wynik = wynik - 9
Prosze sprawdzić, że też daje to wyniki zgodne z metodą Luhna.

Przykłady realizacji algorytmu

#javascript function isCheckdigitCorrect(value) { // accept only digits, dashes or spaces if (/[^0-9-\s]+/.test(value)) return false; var nCheck = 0, nDigit = 0, bEven = false; value = value.replace(/\D/g, ""); for (var n = value.length - 1; n >= 0; n--) { var cDigit = value.charAt(n), nDigit = parseInt(cDigit, 10); if (bEven) { if ((nDigit *= 2) > 9) nDigit -= 9; } nCheck += nDigit; bEven = !bEven; } return (nCheck % 10) == 0; }
Inna wersja javaskryptu - rozszerzony algorytm Luhna function CodeOf(znak) { var A = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'; return A.indexOf(znak); } //fun codeOf() function verifyLuhn( ) { /* copyright R.J.Żyłła 2019-2026 */ var Luhn = verifyLuhn.arguments[0]; Luhn = compactNonNum( Luhn ); //usuwa spacje i inne znaki niecyfrowe wynik = ''; for(i=0;i<Luhn.length;i++) // zamiana A B na 10 11 itd wynik = wynik + CodeOf(Luhn[i].toUpperCase()); if(wynik != '') { suma = 0; wlen = wynik.length-1; for (i=0; i<wlen; i++ ) { temp = wynik.charAt(i) * ((wlen-i) % 2 +1); suma += (temp>9)? temp - 9 : temp; } cyfra = (10 - (suma % 10)) % 10; final = (cyfra == wynik[wlen]); } else return false; return final; }// fun verifyLuhn
// CPP program to implement Luhn algorithm #include <bits/stdc++.h> using namespace std; // Returns true if given card number is valid bool checkLuhn(const string& cardNo) { int nDigits = cardNo.length(); int nSum = 0, isSecond = false; for (int i = nDigits - 1; i >= 0; i--) { int d = cardNo[i] - '0'; if (isSecond == true) d = d * 2; // We add two digits to handle cases // that make two digits after doubling nSum += d / 10; nSum += d % 10; isSecond = !isSecond; } return (nSum % 10 == 0); }
inline bool check_luhn_formula( /// The number in the form of a string. No spaces are allowed in the string. std::string const& number) { int ltab[10] = { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 }; if (number.size() < 2) return false; std::string::const_iterator i = number.begin(); int sum = 0; if (number.size() & 1) sum = *i++ - '0'; while (i!=number.end()) { sum += ltab[*i++ - '0']; sum += *i++ - '0'; } return 0 == (sum % 10); } pseudokod algolopodobny function checkLuhn(string CC ) { int sum := integer(CC[length(CC)-1]) int nDigits := length(CC) int parity := nDigits modulus 2 for i from 0 to nDigits - 2 { int digit := integer(CC[i]) if i modulus 2 = parity digit := digit × 2 if digit > 9 digit := digit - 9 sum := sum + digit } return (sum modulus 10) = 0 }

          (serwis działa od stycznia 2001)
          ostatnie poprawki sierpień 2019

Valid HTML 4.01!