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.

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.

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