Algorytm Luhna - Luhn algorithm

Luhna algorytm lub formuła Luhna , znany również jako „ modułu 10” lub „mod 10” algorytmu , nazwany jego twórcy, IBM naukowiec Hans Peter Luhn , to prosta suma kontrolna formuła używana do sprawdzania różnych numerów identyfikacyjnych, takich jak kredyt numery kart , numery IMEI , numery identyfikatorów krajowym dostawcą w Stanach Zjednoczonych, kanadyjski numery Ubezpieczenia Społecznego , izraelskie numery identyfikacyjne, RPA numery identyfikacyjne, szwedzki numery identyfikacyjne narodowe , szwedzki Corporate Identity Numbers (OrgNr), grecki numery ubezpieczenia społecznego (ΑΜΚΑ) Numery kart SIM i kody ankiet pojawiające się na paragonach McDonald's , Taco Bell i Tractor Supply Co. Opisano go w patencie USA nr 2,950,048, przyznanym 23 sierpnia 1960.

Algorytm jest w domenie publicznej i jest obecnie szeroko stosowany. Jest to określone w normie ISO/IEC 7812 -1. Nie jest to kryptograficznie bezpieczna funkcja mieszająca ; został zaprojektowany w celu ochrony przed przypadkowymi błędami, a nie złośliwymi atakami. Większość kart kredytowych i wiele rządowych numerów identyfikacyjnych wykorzystuje algorytm jako prostą metodę odróżniania prawidłowych numerów od błędnie wpisanych lub w inny sposób niepoprawnych numerów.

Opis

Cyfra kontrolna jest obliczana w następujący sposób:

  1. Weź oryginalną liczbę i zaczynając od skrajnej prawej cyfry przesuwając się w lewo, podwój wartość co drugiej cyfry (łącznie z skrajną prawą cyfrą).
  2. Zastąp wynikową wartość na każdej pozycji sumą cyfr wartości tej pozycji.
  3. Zsumuj otrzymane wartości ze wszystkich pozycji ( s ).
  4. Obliczona cyfra kontrolna jest równa .

Przykład obliczania cyfry kontrolnej

Załóżmy na przykład numer konta „7992739871” (tylko „ładunek”, nie uwzględniono jeszcze cyfry kontrolnej):

7 9 9 2 7 3 9 8 7 1
Mnożniki 1 2 1 2 1 2 1 2 1 2
= = = = = = = = = =
7 18 9 4 7 6 9 16 7 2
Suma cyfr 7 9 (1+8) 9 4 7 6 9 7 (1+6) 7 2

Suma otrzymanych cyfr to 67.

Cyfra kontrolna jest równa .

To sprawia, że ​​pełny numer konta brzmi 79927398713.

Przykład walidacji cyfry kontrolnej

Wystarczy odciąć cyfrę kontrolną (ostatnią cyfrę) numeru, aby zatwierdzić. 79927398713 -> 7992739871 Oblicz cyfrę kontrolną (patrz wyżej) (3) i porównaj swój wynik z odciętą cyfrą kontrolną (3 = 3). Jeśli pasują do liczby, zdał test.

Mocne i słabe strony

Algorytm Luhna wykryje każdy błąd jednocyfrowy, a także prawie wszystkie transpozycje sąsiednich cyfr. Nie wykryje jednak transpozycji dwucyfrowej sekwencji 09 do 90 (lub odwrotnie). Wykryje większość możliwych błędów bliźniaczych (nie wykryje 2255 , 3366 lub 4477 ).

Inne, bardziej złożone algorytmy cyfr kontrolnych (takie jak algorytm Verhoeffa i algorytm Damma ) mogą wykryć więcej błędów transkrypcji. Luhna mod N algorytm jest rozszerzeniem, które obsługuje ciągi non-numeryczne.

Ponieważ algorytm operuje na cyfrach od prawej do lewej, a cyfry zerowe wpływają na wynik tylko wtedy, gdy powodują przesunięcie pozycji, dopełnienie zerami początku ciągu liczb nie ma wpływu na obliczenia. Dlatego systemy, które dopełniają określoną liczbę cyfr (na przykład poprzez konwersję 1234 na 0001234), mogą przeprowadzić walidację Luhna przed lub po uzupełnieniu i osiągnąć ten sam wynik.

Algorytm pojawił się w patencie Stanów Zjednoczonych na ręczne, mechaniczne urządzenie do obliczania sumy kontrolnej. Dlatego musiało być dość proste. Urządzenie przejęło sumę mod 10 za pomocą środków mechanicznych. W cyfry podstawienia , to znaczy, że wyniki procedury podwójne i redukcji, nie zostały przedstawione w sposób mechaniczny. Zamiast tego, cyfry zostały zaznaczone w ich permutowanej kolejności na korpusie maszyny.

Implementacja pseudokodu

function checkLuhn(string purportedCC) {
    int nDigits := length(purportedCC)
    int sum := integer(purportedCC[nDigits-1])
    int parity := (nDigits-1) modulus 2
    for i from 0 to nDigits - 2 {
        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
}

Bibliografia

  1. ^ a b Patent USA 2950048A , Luhn, Hans P. , "Komputer do weryfikacji liczb", opublikowany 1960-08-23 
  2. ^ „Załącznik B: wzór Luhna do obliczania modułu-10 „podwójnie-dodaj-podwójne” cyfry kontrolne”. Karty identyfikacyjne — Identyfikacja wydawców — Część 1: System numeracji (standard). Międzynarodowa Organizacja Normalizacyjna , Międzynarodowa Komisja Elektrotechniczna . Styczeń 2017. ISO/IEC 7812 -1:2017.

Zewnętrzne linki