#19. Algorytm Luhna

Cześć!

5 stycznia 2020 roku — czas na Algorytm Luhna. Temat niezwykle przyjemny i często spotykany w różnych systemach między innymi do walidacji poprawności wprowadzonych numerów.

Początek roku jest dla mnie niezwykle intensywny. To już trzeci artykuł, który napisałem w zaledwie 5 dni! W tym wpisie poruszę następujące tematy:

• Kto jest twórcą algorytmu?
• Kiedy został opracowany?
• Jak wygląda implementacja?
• Co możemy weryfikować za pomocą algorytmu?
• Jak inaczej nazywany jest algorytm Luhna?
• Czy można walidować w ten sposób numer PESEL?

Pytań jest sporo, więc szkoda marnować czas.

Zaczynajmy!

Wprowadzenie

Algorytm Luhna został utworzony w latach 50 (został opatentowany 6 stycznia 1954 roku). Twórcą jest naukowiec niemieckiego pochodzenia Hans Peter Luhn, który był w tym okresie pracownikiem firmy IBM. Pierwotnie Luhn opracował maszynę mechaniczną do sprawdzania poprawności numerów z cyfrą kontrolną. 

Algorytm Luhna nazywany jest także algorytmem mod 10.

Pierwotnie algorytm powstał po to, by ochronić przed błędnymi lub odwróconymi cyframi podczas wpisywania numerów kart kredytowych. W kolejnych latach nastąpiła ewolucja i dziś algorytm Luhna stosujemy praktycznie do większości walidacji ciągów cyfr, na przykład: 

• numery telefonu
• NIP
• REGON
• numery identyfikacyjne klientów w różnej formy umowach
• EAN
• ISSN
• numery IMEI
• ISBN
• numery kart kredytowych

Opis działania

Algorytm Luhna bazuje na wyznaczeniu sumy kontrolnej, która podzielona przez 10 da wartość 0. Jest to główne założenie algorytmu. Zazwyczaj wystarczy zmienić jeden znak w ciągu, aby algorytm wykrył zmianę. Oczywiście nic nie jest idealne i są znane przypadki, kiedy zmiana nie zostanie rozpoznana. O tym za chwilę.

Działanie algorytmu jest w zasadzie bardzo proste. Każdą z cyfr numeru musimy przemnożyć przez odpowiednią wagę, zaczynając od prawej strony. Wagi to odpowiednio 2 oraz 1. Następnie wynik sumujemy i sprawdzamy, czy dzieli się bez reszty przez 10. Gdy wynikiem dzielenia będzie liczba bez reszty, to wtedy możemy uznać, że ciąg liczb jest poprawny. 

Nasuwa się jeszcze pytanie, co w przypadku, gdy po pomnożeniu cyfry przez jej wagę dostaniemy dwucyfrową liczbę? Odpowiedź jest prosta, wystarczy zsumować liczby. Dla przykładu – 7 x 2 = 14. Następnie 1 + 4 = 5. 

Jako przykład zaprezentuję wygenerowany losowo numer karty kredytowej. Numer ten składa się z 16 cyfr. Pierwszy z przykładów zawiera błędny ciąg cyfr, drugi natomiast jest poprawny.

Na czarno oznaczyłem numer karty kredytowej, na czerwono wagę a na zielono wynik mnożenia kolejnych liczb przez wagę z uwzględnieniem sumowania cyfr z liczb dwucyfrowych. Następnie sumuję otrzymane wartości z czterocyfrowych bloków i dzielę przez 10, sprawdzając otrzymaną resztę.

Przykład błędny

5332 5006 6001 2978
2121 2121 2121 2121

1362 1006 3001 4958

12 + 7 + 4 + 26 = 49

49 : 10 = 4 oraz reszta 9

Numer 5332 5006 6001 2978 jest błędny, ponieważ wynik reszty z dzielenia nie równa się 0.

Przykład poprawny

4245 5675 8675 0809
2121 2121 2121 2121

8285 1655 7655 0809

23 + 17 + 23 + 17 = 80

80 : 10 = 8 oraz reszta 0
Numer 4245 5675 8675 0809 jest poprawny, ponieważ wynik reszty z dzielenia równa się 0.

Implementacja

Poniższa prezentuję aplikację konsolową, która składa się z metody Main oraz metody typu string o nazwie CheckNumber. Metoda Main ma proste zadanie — pobrać od użytkownika numer do walidacji i wyświetlić informację o jego poprawności.

Cała analiza dzieje się w metodzie CheckNumber. Na wejście otrzymuje ona ciąg znaków, który następnie zostaje poddany sprawdzeniu.

Jak to sprawdzenie przebiega?

Oparte jest na jednej głównej pętli, która iteruje od ostatniego do pierwszego znaku. Mając przed oczami przykład wyżej, wiemy już, że co druga liczba mnożona jest razy 2. Tym zagadnieniem zajmuje się instrukcja warunkowa z linii 22. Sprawdza po prostu czy pozycja analizowanej cyfry jest parzysta, jeżeli tak to wykonuje mnożenie. Dodatkowym problemem do rozwiązania pozostaje kwestia liczb dwucyfrowych, które powstają w momencie mnożenia. Ich sumowanie zostaje wyrażone działaniem odejmowania wartości 9.

Dlaczego?

Przypatrz się następującym przypadkom i zobacz, że wynik sumowania to zawsze liczba o 9 mniejsza od liczby, z której następuje sumowanie cyfr.

• 10 -> 1 + 0 = 1 
• 12 -> 1 + 2 = 3 
• 14 -> 1 + 4 = 5
• 16 -> 1 + 6 = 7
• 18 -> 1 + 8 = 9

Na końcu pozostaje tylko sprawdzić, czy wynik dzielenia przez 10 zwróci zero. Jeżeli tak to zwracamy informację o poprawności numeru.

using System;

namespace AlgorytmLuhna
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Podaj numer: ");
            string number = Console.ReadLine();

            Console.WriteLine("Liczba jest " + CheckNumber(number));
            Console.ReadLine();
        }

        static string CheckNumber(string digits)
        {
            int sum = 0;
            for (int i = digits.Length - 1; i >= 0; i--)
            {
                int temp = int.Parse(digits[i].ToString());
                if (i % 2 == 0)
                {
                    temp *= 2;
                    if (temp > 9)
                    {
                        temp -= 9; 
                    }
                }
                sum += temp;
            }

            if (sum % 10 == 0)
                return "poprawna";
            else
                return "niepoprawna";
        }
    }
}

Problematyczne przypadki

Wspomniałem wyżej, że są przypadki, dla których algorytm Luhna zadziała błędnie.

Jednym z najpoważniejszych problemów jest wykrywanie zmian w kolejności liczb. Jeżeli mnożymy co drugą liczbę przez dwa, to algorytm Luhna nie poradzi sobie na przykład z tego typu zamianą kolejności – 123456 na 143256.

Dodatkowo problemem jest to, że walidacja nie wykryje zamiany sekwencji 90 na 09 i odwrotnie. Pociąga to za sobą problem zamiany niektórych par cyfr, które też nie zostaną „wyłapane„. 

Dla przykładu można podać pary takie jak:

• 22 zamienione na 55
• 33 zamienione na 66
• 44 zamienione na 77

Ciągi alfanumeryczne

Celowo używam wyżej sformułowania ciąg, ponieważ algorytm mimo przeznaczenia w stosunku do liczb może być również stosowany dla ciągów alfanumerycznych. Algorytm taki nazywany jest algorytmem Luhn mod N i jest rozszerzeniem mod 10.

Jak sama nazwa wskazuje, nie ograniczamy się do 10 cyfr, lecz do N znaków. Dla przykładu niech N będzie zawierało w kolekcji 6 znaków (1, 3, 5, a, c, g). Sam proces jest analogiczny jak w przykładzie powyżej — tu jednak dzielnikiem nie będzie 10 tylko N (w naszym przykładzie 6). Do tego musimy utworzyć tablicę wzorów, tak by litery alfabetu miały nadaną cyfrę. Przykład potraktuj jako forma zadania do samodzielnej pracy. Podpowiem Ci, że jest niemal analogiczny jak w przypadku standardowego algorytmu Luhna mod 10.

W razie pytań pisz w komentarzu lub prywatnie w wiadomości mailowej.

Czy wiesz, że…

Wyżej jak mogłeś zauważyć, wymieniałem określony grupy numerów takie jak NIP czy ISBN, które można walidować za sprawą algorytmu Luhna. Co ciekawe numerem, który jest równie unikalny, jest numer PESEL. Nie ma jednak możliwości walidacji go za sprawą tytułowego algorytmu ze względu na jego specyficzną budowę, która składa się z następujących elementów (RRMMDDPPPPK):

• data urodzenia (RR – rok, MM – miesiąc, DD – dzień)
• liczby porządkowej (PPPP – w skład której wchodzi cyfra oznaczająca płeć, dla kobiet parzysta a dla mężczyzn nieparzysta. Ulokowana jest na przedostatnim miejscu w numerze)
• cyfra kontrolna (K – wyliczana jest na podstawie podobnego algorytmu jak algorytm Luhna, jednak z drobnymi różnicami).

Sprawdź swój numer PESEL!

Wyliczenie cyfry kontrolnej

Aby ją wyliczyć, potrzebujemy trzech kroków.

Po pierwsze musimy przemnożyć każdą z cyfr przez odpowiednią wagę 1,3,7,9,1,3,7,9,1,3. W tym przypadku liczenie rozpoczynamy od lewej strony.

Po drugie kolejna drobna zmiana. W przypadku, gdy otrzymujemy liczbę dwucyfrową, nie wykonujemy dodawania cyfr. Przepisujemy po prostu ostatnią cyfrę liczby.

Po trzecie sumowanie wszystkich uzyskanych cyfr, a następnie odjęcie od 10 jej ostatniej cyfry (jeżeli wyszła liczba mniejsza od 10, to po prostu ją odejmujemy). Nic nie zobrazuje tego lepiej niż prosty przykład. 

Wylosowaliśmy numer PESEL o następującej wartości – 63092170727. Sprawdzimy jego poprawność, wyliczając cyfrę kontrolną i sprawdzając, czy równa się ona 7.

6309217072
1379137913

6901239076

6 + 9 + 0 +1 + 2 + 3 + 9 + 0 + 7 + 6 = 43

10 – 3 = 7

PESEL jest poprawny!

Miesiące

Warto na koniec dodać jeszcze informację na temat tego, że PESEL w latach 1900-1999 ma zapisywane miesiące w sposób dla nas znany, czyli styczeń to 01 natomiast grudzień to 12 (cyfry te znajdują się na 3 i 4 miejscu w numerze). Problem zaczyna się dla dat urodzin przed 1900 rokiem i po 1999. Rozwiązano je w ten sposób, że miesiące zapisuje się w sposób niestandardowy:

• 1800 do 1899 – styczeń to 81, grudzień to 92
• 2000 do 2099 – styczeń to 21, grudzień to 32
• 2100 do 2199 – styczeń to 41, grudzień to 52
• 2200 do 2299 – styczeń to 61, grudzień to 72

Jak widać, do roku 2299 nie musimy się martwić o unikalność. 

Implementacja

Na jednym ze szkoleń w 2014 roku, gdy zaczynałem wchodzić na poważnie w świat programowania, miałem zadanie, którego implementacja widnieje poniżej.

Standardowo w tak prostych programach używamy konsoli. Funkcja Main jest bliźniaczo podobna do tej z programu wyżej. Prosimy użytkownika, by podał numer PESEL, a nasz program ma za zadanie określić, czy jest on poprawny. Służą do tego dwie metody — IsValidate oraz metoda pomocnicza ReturnLastDigit.

W metodzie ReturnLastDigit chodzi o to, by zsumować wszystkie cyfry, które otrzymamy poprzez przemnożenie przez wartość zgodnie z tablicą multiplier. Następnie zwracamy wartość cyfry kontrolnej, która wyliczana jest zgodnie z wyżej opisywaną regułą dla liczb jedno i dwucyfrowych.

Metoda IsValidate ma za zadanie jedynie sprawdzić, czy ostatnia cyfra podanego numeru PESEL zgadza się z tą, którą zwróciła metoda ReturnLastDigit.

using System;

namespace PESEL
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Podaj numer PESEL: ");
            string pesel = Console.ReadLine();

            Console.WriteLine("Numer PESEL jest " + IsValidate(pesel));
            Console.ReadLine();
        }

        public static string IsValidate(string pesel)
        {
            bool isValid = false;
           
                if (pesel.Length == 11 && pesel[10].ToString() == ReturnLastDigit(pesel))
                {
                    isValid = true;
                }

            if (isValid)
                return "poprawny";
            else
                return "niepoprawny";

        }
        
        private static string ReturnLastDigit(string pesel)
        {
            int[] multiplier = { 1, 3, 7, 9, 1, 3, 7, 9, 1, 3 };

            int sum = 0;
            for (int i = 0; i < multiplier.Length; i++)
            {
                sum += multiplier[i] * int.Parse(pesel[i].ToString());
            }

            int mod = sum % 10;

            if (mod == 0)
                return mod.ToString();
            else
                return (10 - mod).ToString();
        }
    }
}

Podsumowanie

Dziś na bogato, aż dwie implementacje! To wszystko dlatego, że algorytm Luhna to temat krótki, lecz bardzo przyjemny.

Często można zadać sobie pytanie — a co z numerem PESEL?

Dlatego przy okazji tego artykułu napisałem o nim kilka zdań. Co do samych implementacji jak zwykle pozostawiłem możliwość refaktoryzacji. Podejmij wyzwanie i zmodyfikuj kod (polecam dodanie obsługi błędów na początek).

Jest to już w tym roku mój trzeci wpis, o czym wspominałem między innymi na Newsletterze i grupie na Facebook. Montuję też już pierwszy materiał video, więc następuje kolejny etap mojego internetowego rozwoju — lada moment pojawi się vlog! Jak jeszcze nie widziałeś statystyk za grudzień, to zobacz pod linkiem!

W kolejnym artykule natomiast poruszam zagadnienie przynależności punktu do odcinka.

Źródła

https://romek.info/ut/iso-7064c.html
https://mattomatti.com/pl/a56
http://www.pat2pdf.org/patents/pat2950048.pdf
https://obywatel.gov.pl/dokumenty-i-dane-osobowe/czym-jest-numer-pesel 
http://www.algorytm.org/sumy-kontrolne/algorytm-luhna-mod-10.html

Newsletter

Nie przegap i dołącz już dziś do 838 osób będących w tym Newsletter! Otrzymuj co niedzielę o godzinie 20 listę kilku ciekawych tematów, które miałem okazję obserwować w mijającym tygodniu.

Tematy będą głównie techniczne, ale czasami pojawi się coś, co może wprowadzi Cię w stan zadumy i zmusi do dyskusji w szerszym gronie. Zero spamu!