O triku matematycznym ukrytym w numerach kart kredytowych

Przy wszystkich typowych numerach kart kredytowych stosuje się matematyczną sztuczkę w celu wyłapywania najczęstszych błędów. Jest to tzw. algorytm Luhna, opatentowany w 1960 roku przez informatyka z IBM Hansa Petera Luhna. Podobne metody wykrywania błędów dotyczą wielu dużych liczb, z którymi mamy do czynienia na co dzień, jak kody kreskowe, numery śledzonych przesyłek, kont bankowych, a nawet numery ISBN na książkach.

Przyglądając się uważnie karcie kredytowej, można zauważyć, że kryje ona w sobie więcej treści, niż mogłoby się w pierwszej chwili wydawać. Struktura jej numeru obejmuje cztery główne części. Jako przykład posłuży moja karta Visa.

Pierwsza cyfra to identyfikator głównego emitenta (na kartach Visa jest to 4, na kartach Discover 6). Następne od pięciu do siedmiu cyfr oznacza bank lub instytucję, która wydała kartę. Dalsze cyfry (oprócz ostatniej) są numerem konta właściciela karty w danym banku. Ostatnia cyfra, zwana kontrolną, nie ma nic wspólnego z instytucjami finansowymi. Jest po to, aby cały numer karty został poddany testowi matematycznemu – algorytmowi Luhna. Oto schemat działania tego algorytmu:

1. Zapisz numer karty, pomijając ostatnią cyfrę.

2. Zaczynając od prawej strony, podwój każdą co drugą cyfrę (pierwszą, trzecią, piątą, … itd.).

3. Zsumuj wszystkie cyfry (nie liczby; np. po podwojeniu 7 do sumy wchodzi 1+4=5, a nie 14).

4. Do otrzymanej sumy dodaj kontrolną, czyli ostatnią cyfrę numeru karty. Jeśli wynik nie jest wielokrotnością 10, oznacza to, że podany numer karty jest nieprawidłowy.

Poniżej przedstawiam zastosowanie algorytmu Luhna do wpisanego numeru mojej karty (warto sprawdzić działanie algorytmu na swojej karcie). Wynik 75 nie jest wielokrotnością 10, zatem wpisany numer jest błędny.

Przy wydawaniu karty najpierw wpisywany jest numer konta, a potem wykonywane są obliczenia trzech pierwszych kroków algorytmu Luhna, aby znaleźć właściwą cyfrę kontrolną. W podanym przykładzie poprawny numer karty powinien kończyć się cyfrą 3 (a nie 4), ponieważ 67+3=70 (wielokrotność 10).

Ten taniec cyfr zdominował weryfikację kart kredytowych ze względu na funkcjonalność i prostotę. Algorytm Luhna wykrywa wpisanie błędnej cyfry. Wykryje także przypadkową zamianę miejscami sąsiednich cyfr, ale z jednym wyjątkiem – nie wykryje przestawienia cyfr w parze 09 lub 90.

Holenderski matematyk Jacobus Verhoeff ustalił w 1969 roku, że dwa błędy – niewłaściwa cyfra i przestawienie dwóch sąsiednich cyfr – stanowią prawie 90% wszystkich błędów popełnianych przy wprowadzaniu numeru karty. Verhoeff opracował bardziej złożony algorytm, który oprócz wykrywania tych samych błędów co algorytm Luhna, radził sobie z transpozycjami 09/90 oraz z rzadszymi rodzajami pomyłek. Algorytm Verhoeffa okazał się matematycznie doskonały. Dzięki niemu obalone zostały dowody, że żadna jedna cyfra kontrolna nie może umożliwiać wychwycenia wszystkich błędów uwzględnionych w algorytmie Verhoeffa. Algorytm ten nigdy jednak nie został wdrożony – zapewne ze względu na znaczną złożoność oraz dlatego, że algorytm Luhna spisuje się wystarczająco dobrze.

Dzięki algorytmowi Luhna klient oszczędza swój czas, a firma pieniądze. Bez niego sprzedawca w trakcie zakupów weryfikowałby przynależność karty do klienta, przesyłając jego dane do wyspecjalizowanej usługi walidacji kart. Ta operacja jest czasochłonna i wiąże się z opłatami manipulacyjnymi. Wymiana danych z profesjonalną firmą walidacyjną w celu wyłapania cyfrowych odpowiedników literówek byłaby stratą czasu i pieniędzy. Ponieważ algorytm Luhna wymaga znikomej mocy obliczeniowej, komputer obsługujący transakcję może łatwo przeprowadzić weryfikację bez konieczności kontaktowania się z osobami trzecimi.

Należy pamiętać, że zaliczenie testu, jakim jest algorytm Luhna, nie gwarantuje poprawności numeru karty. Tylko jego niezaliczenie oznacza, że numer jest na pewno niewłaściwy. Algorytm stanowi pierwszą linię obrony, przez którą mogą prześlizgnąć się nietypowe błędy lub sprytni oszuści, a wtedy sprawdzanie umożliwiają dokładniejsze i kosztowne usługi walidacyjne.

Jak algorytm Luhna ustala, że palce się potknęły? Każda cyfra w numerze karty kredytowej wpływa na ostatnią cyfrę liczby końcowej algorytmu. Jeśli cyfra znajduje się na pozycji, która nie ulega podwojeniu, to po prostu jest jednym ze składników dających sumę. Gdy cyfra jest podwajana, to albo pozostaje liczbą jednocyfrową, albo najpierw zmienia się w dwucyfrową, a po zsumowaniu jej cyfr w składnik jednocyfrowy. W tabeli podane są wartości wszystkich możliwych składników.

Na przykład niepodwojone 6 nie zmienia się, a podwojone (12) daje 3, bo 1+2=3. Błędne wpisanie jednej cyfry numeru karty powoduje zmianę składnika na położony wyżej lub niżej w danej kolumnie tabeli, a to zmienia sumę algorytmu. Ustalony prawidłowy numer karty kredytowej daje jako sumę wielokrotność 10. Każdy błąd jednocyfrowy zmienia tę sumę o liczbę jednocyfrową, więc błędna suma na pewno nie będzie wielokrotnością 10.

Formalny dowód skuteczności algorytmu Luhna w przypadku zamiany sąsiednich cyfr wymaga metody indukcji zupełnej, ale można to pokazać na przykładzie. Wyobraźmy sobie, że numer karty zawiera parę 31 z podwajaną cyfrą 3, a przypadkowo wpisano 13. W poprawnej sumie ten duet daje 6+1=7, natomiast w błędnej da 2+3=5. Zatem błąd ostatecznie zmienia końcową sumę o 2, więc jeśli poprawna suma była wielokrotnością 10, to nowa na pewno taką nie będzie. Można sprawdzić, że to działa dla każdej pary liczb z wyjątkiem 09 i 90, bo wtedy mimo błędu do końcowej sumy wnoszone są takie same składniki.

Gdy więc przy płatności pojawi się niepokojący komunikat o błędzie, warto przypomnieć sobie, że prosty algorytm matematyczny umożliwia zaoszczędzenie czasu i pieniędzy stron uczestniczących w transakcji.