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