Luhn algoritme - Luhn algorithm

Den Luhn algoritme eller Luhn formel , også kjent som " modulus 10" eller "mod 10" algoritme , som er oppkalt etter sin skaper, IBM vitenskapsmann Hans Peter Luhn , er en enkel kontrollsum formel brukes for å validere en rekke identifikasjonsnumre, som for eksempel kredittkort kortnumre , IMEI-nummeret , nasjonal leverandør Identifier tall i USA, Canada sosial forsikring tall , israelske ID-numre, sørafrikanske ID-numre, svenske personnummer , svenske bedrifts fødselsnummer (OrgNr), gresk personnummer (ΑΜΚΑ) SIM -kortnumre og undersøkelseskoder som vises på kvitteringer fra McDonald's , Taco Bell og Tractor Supply Co. Det er beskrevet i US patent nr. 2 950 048, gitt 23. august 1960.

Algoritmen er i det offentlige og er i stor bruk i dag. Den er spesifisert i ISO/IEC 7812 -1. Det er ikke ment å være en kryptografisk sikker hashfunksjon ; den var designet for å beskytte mot utilsiktede feil, ikke ondsinnede angrep. De fleste kredittkort og mange offentlige identifikasjonsnumre bruker algoritmen som en enkel metode for å skille gyldige tall fra feil typede eller på annen måte feil tall.

Beskrivelse

Kontrollsifferet beregnes som følger:

1. Ta det opprinnelige nummeret og begynn fra det høyre sifferet som beveger deg til venstre, doble verdien til hvert andre siffer (inkludert sifferet til høyre).
2. Erstatt den resulterende verdien på hver posisjon med summen av sifrene i denne posisjonens verdi.
3. Oppsummere de resulterende verdiene fra alle posisjoner ( s ).
4. Det beregnede kontrollsifferet er lik .${\ displaystyle 10-s \ operatorname {mod} 10}$

Eksempel på beregning av kontrollsiffer

Anta et eksempel på et kontonummer "7992739871" (bare "nyttelast", kontrollsifferet er ikke inkludert ennå):

	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 sifre	7	9 (1+8)	9	4	7	6	9	7 (1+6)	7	2

Summen av de resulterende sifrene er 67.

Kontrollsifferet er lik . ${\ displaystyle 10-67 \ operatorname {mod} 10 = 3}$

Dette gjør hele kontonummeret til 79927398713.

Eksempel på validering av kontrollsiffer

Bare kutt av kontrollsifferet (siste sifferet) i nummeret for å validere. 79927398713 -> 7992739871 Beregn kontrollsifferet (se ovenfor) (3) og sammenlign resultatet med kontrollsifferet du kuttet av (3 = 3). Hvis de samsvarer med antallet bestått testen.

Styrker og svakheter

Luhn-algoritmen vil oppdage enhver ensifret feil, så vel som nesten alle transposisjoner av tilstøtende sifre. Den vil imidlertid ikke oppdage transponering av den tosifrede sekvensen 09 til 90 (eller omvendt). Det vil oppdage de fleste mulige tvillingsfeil (det vil ikke oppdage 22 ↔ 55 , 33 ↔ 66 eller 44 ↔ 77 ).

Andre, mer komplekse kontrollsifrede algoritmer (for eksempel Verhoeff-algoritmen og Damm-algoritmen ) kan oppdage flere transkripsjonsfeil. Den Luhn mod N-algoritmen er en forlengelse som støtter ikke-numeriske strenger.

Fordi algoritmen opererer på sifrene på en høyre-til-venstre måte og null sifre påvirker resultatet bare hvis de forårsaker endring i posisjon, påvirker ikke nullpolstring begynnelsen på en streng med tall beregningen. Derfor kan systemer som padler til et bestemt antall sifre (ved for eksempel å konvertere 1234 til 0001234) utføre Luhn -validering før eller etter polstring og oppnå det samme resultatet.

Algoritmen dukket opp i et amerikansk patent for en håndholdt, mekanisk enhet for beregning av kontrollsummen. Derfor måtte det være ganske enkelt. Enheten tok mod 10 -summen med mekaniske midler. De substitusjon siffer , det vil si resultatet av den doble og redusere prosedyre, ble ikke produsert mekanisk. Sifrene ble heller merket i sin permuterte rekkefølge på maskinkroppen.

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
}

Referanser

Eksterne linker

• Implementering på 88 språk på Rosetta Code -prosjektet