Пређи на садржај

Lunov algoritam

С Википедије, слободне енциклопедије

Lunov algoritam ili Lunova formula, takođe poznat i kao "modul 10" ili "mod 10" algoritam, je algoritam koji koristi kontrolnu sumu za potvrdu raznih identifikacionih brojeva, kao što su brojevi kreditne kartice, IMEI brojevi i brojevi zdravstvenog osiguranja u Kanadi. Razvio ga je naučnik zaposlen u IBM-u Hans Piter Lun (engl. Hans Peter Luhn), zahtev za patent je podnet 6. januara 1954. i patent je odobren 23. avgusta 1960. godine i zaveden kao U.S. Patent No. 2,950,048

Algoritam je javno vlasništvo i danas je u širokoj upotrebi. Određen je standardom ISO/IEC 7812-1.[1] Nije nameravano da algoritam bude kriptografska funkcija za sažimanje već zaštita od slučajnih grešaka, a ne od zlonamernih napada. Većina kreditnih kartica kao i mnogi vladini identifikacioni brojevi koriste ovaj algoritam kao jednostavnu metodu za razlikovanje validnih brojeva od pogrešno otkucanih ili netačnih brojeva.

Opis

[уреди | уреди извор]

Ovaj algoritam verifikuje ispravnost broja pomoću kontrolne cifre koja je uključena u sam broj i koja se obično nadovezuje na nepotpun broj računa čime se dobije potpun broj računa. Broj računa mora proći sledeći test:

  1. Počevši od krajnje desne cifre, koja je kontrolna cifra, krećući se nalevo, udvostručiti vrednost svake druge cifre; ako je taj proizvod veći od 9 (npr. 8 × 2 = 16), tada sabrati cifre proizvoda (npr. 16: 1 + 6 = 7, 18: 1 + 8 = 9).
  2. Izračunati sumu svih cifara
  3. Ako je suma kongruentna sa nulom po modulu 10 (ako se suma završava nulom) tada je broj ispravan sudeći po Lunovom algoritmu, inače je neispravan.

Uzmimo na primer broj računa "7992739871" kome se dodaje kontrolna cifra čime dobijamo broj oblika 7992739871x:

Broj računa 7 9 9 2 7 3 9 8 7 1 x
Udvostručena svaka druga cifra 7 18 9 4 7 6 9 16 7 2 -
Zbir cifara 7 9 9 4 7 6 9 7 7 2 =67

Kontrolna cifra (x) se dobija izračunavanjem sume cifara, zatim množenjem sa 9 i izračunavanjem ostatka pri deljenju sa 10 (matematički zapisano, (67 × 9 mod 10)). Algoritamski predstavljeno:

  1. Izračunati sumu svih cifara (67).
  2. Pomnožiti sa 9 (603).
  3. Poslednja cifra, 3, je kontrolna cifra. Odatle, x=3.

(Alternativna metoda) Kontrolna cifra (x) dobija se izračunavanjem sume cifara a zatim oduzimanjem cifre jedinice od 10 (67 = cifra jedinice 7; 10 − 7 = kontrolna cifra 3). Algoritamski predstavljeno:

  1. Izračunati zbir cifara (67).
  2. Uzeti cifru jedinice (7).
  3. Oduzeti cifru jedinice od 10.
  4. Rezultat (3) je kontrolna cifra. U slučaju da se suma cifara završava nulom, 0 je kontrolna cifra.

Odatle je potpun broj računa 79927398713.

Za svaki od brojeva 79927398710, 79927398711, 79927398712, 79927398713, 79927398714, 79927398715, 79927398716, 79927398717, 79927398718, 79927398719 može se utvrditi ispravnost na sledeći način.

  1. Udvostručiti svaku drugu cifru, počevši od krajnje desne cifre: (1×2) = 2, (8×2) = 16, (3×2) = 6, (2×2) = 4, (9×2) = 18
  1. Sabrati sve zasebne cifre (cifre u zagradama su proizvod dobijen u koraku 1): x (kontrolna cifra) + (2) + 7 + (1+6) + 9 + (6) + 7 + (4) + 9 + (1+8) + 7 = x + 67.
  2. Ako je suma deljiva sa 10, broj računa je potencijalno ispravan. Primetimo da je 3 jedina ispravna cifra koja daje zbir (70) koji je deljiv sa 10.
  3. Odatle svi ovi brojevi računa su neispravni osim potencijalno ispravnog broja 79927398713 koji sadrži ispravnu kontrolnu cifru.

Alternativno (ukoliko ne želite da primenjujete algoritam nad celim brojem uključujući kontrolnu cifru), možete koristiti isti algoritam za kreiranje kontrolne cifre (opisan u jednom od paragrafa iznad), ignorišući kontrolnu cifru, kao da već nije izračunata i da se sada računa prvi put. Zatim izračunajte kontrolnu cifru i uporedite je sa originalnom kontrolnom cifrom koja je uključena u broj kreditne kartice. Ako se poklapaju tada je broj ispravan.

Prednosti i mane

[уреди | уреди извор]

Lunov algoritam će detektovati svaku grešku gde je jedna cifra pogrešna, kao i gotovo sve permutacije susednih cifara. Međutim neće detektovati permutaciju dvocifrene sekvence 09 u 90 (ili obrnuto). Detektovaće 7 od 10 mogućih ponavljanja dve neispravne cifre (neće detektovati 22 ↔ 55, 33 ↔ 66 or 44 ↔ 77).

Pored toga, Lunov algoritam ne proverava da li je dužina broja validna. Na primer, posmatrajmo validan broj kreditne kartice "5578249275041923" koji sadrži 16 cifara. Kada izostavimo poslednje tri cifre dobijamo neispravan broj "5578249275041" koji prolazi validaciju Lunovim algoritmom (na način opisan ranije). Takođe Lunov algoritam ne može utvrditi o kom tipu kartice je reč. Naime, ukoliko posmatramo validan broj kreditne kartice, kao što je "5397373822153004", prve dve cifre označavaju da se radi o MasterCard kartici, kada promenimo prve dve cifre dobijamo broj "4697373822153004" gde nam sada prve dve cifre označavaju da se radi o Visa kartici. Broj će takođe proći Lunovu validaciju ali ovaj broj Visa kartice nije validan. U vezi sa tim, predložena su poboljšanja algoritma tako što se implementira provera dužina broja kreditne kartice kao i provera tipa kreditne kartice.[2]

Ostali, složeniji algoritmi za proveru ispravnosti (kao što su Verhoefov algoritam kao i Damov algoritam), mogu detektovati više grešaka u kucanju. Lunov mod N algoritam je proširenje koje podržava i nenumeričke niske.

Pošto se algoritam izvršava sleva nadesno i nule utiču na rezultata samo ako uzrokuju promenu pozicije ostalih cifara, nula na početku niske ne utiče na izračunavanje. Odatle sistemi koji nadovezuju nule da bi broj sadržao određeni broj cifara (koji konvertuju npr. 1234 u 0001234) mogu da izvršavaju Lunovu validaciju pre ili nakon nadovezivanja.

Nadovezivanje nule na početak broja neparne dužine nam omogućava da obrađujemo broj zdesna nalevo pri čemu udvostručujemo cifre na neparnim mestima.

Algoritam je prvobitno patentiran za ručnu mehaničku napravu koja je izračunavala kontrolne cifre. Stoga je morao biti prilično jednostavan. Naprava je izračunavala ostatak pri deljenju sa 10 na mehanički način. Cifre za zamenu, odnosno, rezultati dupliranja i oduzimanja, nisu dobijani na mehanički način. Umesto toga, cifre su upisane u permutovanom redosledu na samoj napravi.

Implementacija mod 10 algoritma

[уреди | уреди извор]

Implementacije koje slede napisane su u programskom jeziku Python.

Verifikacija kontrolne cifre

[уреди | уреди извор]
def luhn_checksum(card_number):
    def digits_of(n):
        return [int(d) for d in str(n)]
    digits = digits_of(card_number)
    odd_digits = digits[-1::-2]
    even_digits = digits[-2::-2]
    checksum = 0
    checksum += sum(odd_digits)
    for d in even_digits:
        checksum += sum(digits_of(d*2))
    return checksum % 10

def is_luhn_valid(card_number):
    return luhn_checksum(card_number) == 0

Izračunavanje kontrolne cifre

[уреди | уреди извор]

Algoritam iznad proverava ispravnost ulaza pomoću kontrolne cifre. Izračunavanje kontrolne cifre zahteva samo manju izmenu algoritma na sledeći način:

  1. Nadovezati nulu kao kontrolnu cifru nepotpunom broju i zatim izračunati kontrolnu sumu
  2. Ako je (suma mod 10) == 0, tada je kontrolna cifra 0
  3. Inače, kontrolna cifra = 10 - (suma mod 10)
def calculate_luhn(partial_card_number):
    check_digit = luhn_checksum(int(partial_card_number) * 10)
    return check_digit if check_digit == 0 else 10 - check_digit

Zaključak

[уреди | уреди извор]

Lunov algoritam je široko rasprostranjen, naročito se intenzivno koristi na internetu za validaciju brojeva kreditnih kartica, međutim ovaj algoritam ima ozbiljnih slabosti. Predloženo je više proširenja originalnog algoritma koje te slabosti delimično rešavaju.

Reference

[уреди | уреди извор]
  1. ^ ISO/IEC 7812-1:2006 Identification cards -- Identification of issuers -- Part 1: Numbering system
  2. ^ Journal: International Journal of Computer Science and Mobile Computing - IJCSMC (Vol.2, No. 7), Khalid Waleed Hussein; Dr. Nor Fazlida Mohd. Sani; Professor Dr. Ramlan Mahmod; Dr. Mohd. Taufik Abdullah, 2013-07-30

Spoljašnje veze

[уреди | уреди извор]
Преузето из „https://sr.wikipedia.org/w/index.php?title=Lunov_algoritam&oldid=28522568”