Luhn algoritme - Luhn algorithm

Den Luhn algoritme eller Luhn formel , også kendt som " modul 10" eller "mod 10" algoritme , opkaldt efter dens skaber, IBM videnskabsmand Hans Peter Luhn , er en simpel checksum formel anvendes til at validere en række forskellige identifikationsnumre, såsom kredit kortnumre , IMEI-numre , National Provider Identifier numre i USA, canadiske Social Forsikring Numbers , israelske id-numre, sydafrikanske ID-numre, svensk nationale identifikationsnumre , svensk Corporate Identity Numbers (Orgnr), græsk Social Security Numbers (ΑΜΚΑ) SIM -kortnumre og undersøgelseskoder vises på kvitteringer fra McDonald's , Taco Bell og Tractor Supply Co. Det er beskrevet i US patent nr. 2.950.048, udstedt den 23. august 1960.

Algoritmen er i offentligheden og er i vid udstrækning i dag. Det er specificeret i ISO/IEC 7812 -1. Det er ikke beregnet til at være en kryptografisk sikker hash -funktion ; det var designet til at beskytte mod utilsigtede fejl, ikke ondsindede angreb. De fleste kreditkort og mange statslige identifikationsnumre bruger algoritmen som en simpel metode til at skelne gyldige tal fra forkert indtastede eller på anden måde forkerte tal.

Beskrivelse

Kontrolcifret beregnes som følger:

  1. Tag det originale nummer og start fra det højre ciffer, der bevæger dig til venstre, dobbelt værdien af ​​hvert andet ciffer (inklusive det ciffer til højre).
  2. Erstat den resulterende værdi på hver position med summen af ​​cifrene i denne positions værdi.
  3. Opsummere de resulterende værdier fra alle positioner ( s ).
  4. Det beregnede kontrolciffer er lig med .

Eksempel på beregning af kontrolciffer

Antag et eksempel på et kontonummer "7992739871" (kun "nyttelast", checkciffer er endnu ikke inkluderet):

7 9 9 2 7 3 9 8 7 1
Multiplikatorer 1 2 1 2 1 2 1 2 1 2
= = = = = = = = = =
7 18 9 4 7 6 9 16 7 2
Sum cifre 7 9 (1+8) 9 4 7 6 9 7 (1+6) 7 2

Summen af ​​de resulterende cifre er 67.

Kontrolcifret er lig med .

Dette gør hele kontonummeret til 79927398713.

Eksempel til validering af kontrolciffer

Skær bare checkcifret (sidste ciffer) af nummeret af for at validere. 79927398713 -> 7992739871 Beregn checkcifferet (se ovenfor) (3) og sammenlign dit resultat med det checkciffer, du har afskåret (3 = 3). Hvis de matcher antallet bestået testen.

Styrker og svagheder

Luhn-algoritmen vil registrere enhver enkeltcifret fejl samt næsten alle transpositioner af tilstødende cifre. Det registrerer imidlertid ikke transponering af den tocifrede sekvens 09 til 90 (eller omvendt). Det registrerer de fleste mulige tvillingsfejl (det registrerer ikke 2255 , 3366 eller 4477 ).

Andre, mere komplekse checkcifrede algoritmer (såsom Verhoeff-algoritmen og Damm-algoritmen ) kan registrere flere transkriptionsfejl. Den Luhn mod N-algoritmen er en udvidelse, der støtter ikke-numeriske strenge.

Fordi algoritmen fungerer på cifrene på en højre-til-venstre måde, og nul cifre kun påvirker resultatet, hvis de forårsager forskydning i position, påvirker nulpolstring begyndelsen på en række tal ikke beregningen. Derfor kan systemer, der padler til et bestemt antal cifre (ved f.eks. At konvertere 1234 til 0001234), udføre Luhn -validering før eller efter polstring og opnå det samme resultat.

Algoritmen optrådte i et amerikansk patent for en håndholdt, mekanisk enhed til beregning af kontrolsummen. Derfor var det påkrævet at være ret simpelt. Enheden tog mod 10 -summen ved hjælp af mekaniske midler. De substitutions- cifre , det vil sige resultatet af dobbelt og reducere fremgangsmåde blev ikke produceret mekanisk. Cifrene var snarere markeret i deres permuterede rækkefølge på maskinens krop.

Pseudokodeimplementering

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
}

Referencer

  1. ^ a b US patent 2950048A , Luhn , Hans P. , "Computer til verificering af numre", offentliggjort 1960-08-23 
  2. ^ "Bilag B: Luhn-formel til beregning af modul-10" dobbelt-tilføj-dobbelt "tjekcifre". Identifikationskort - Identifikation af udstedere - Del 1: Nummereringssystem (standard). International Organization for Standardization , International Electrotechnical Commission . Januar 2017. ISO/IEC 7812 -1: 2017.

eksterne links