Luhn-formula

A Wikipédiából, a szabad enciklopédiából

A Luhn-algoritmus vagy Luhn-formula, más néven modulus 10 vagy mod 10 algoritmus kifejlesztése az 1960-as években történt azonosító számok ellenőrzésére. Egyszerű ellenőrzőösszeg-alapú képletről van szó, amit mindenféle azonosító számok ellenőrzésére használnak, úgymint hitelkártyák vagy személyi számok. Miután a '60-as évek végén az IBM-nél dolgozó tudós, Hans Peter Luhn megalkotta, a hitelkártya-gyártók alkalmazni kezdték és így hamar ismertté vált.

Az algoritmust, közkincs besorolása miatt is, széles körben használják. Nem szánták kriptográfiailag titkos hash függvénynek; csak a véletlenül fellépő hibák ellen véd, rosszindulatú támadások ellen nem. A hitelkártyák és állami azonosító számok többsége használja ezt az egyszerű eljárást arra, hogy az érvényes számokat megkülönböztesse a véletlen számjegyek csoportjától.

Magyarázat[szerkesztés | forrásszöveg szerkesztése]

Az algoritmus létrehoz egy ellenőrző számot, amit rendszerint hozzátesznek a hitelkártya- vagy személyi számhoz, így jön létre a teljes szám. A teljes számnak meg kell felelnie a következő algoritmusnak:

  1. Az utolsó előtti számmal kezdve bal felé haladva kétszerezzük meg minden második szám értékét. Ha 10-nél magasabb számot kapunk, adjuk össze számjegyeit, az így kapott összeget írjuk a régi számjegy helyére. 1111-ből tehát 2121 lesz, 8763-ból pedig 7733, azaz (1+6)7(1+2)3.
  2. Adjuk össze ezeket a számokat (ti. számjegyeket). Az előbb kapott 2121-ből így 6 lesz, 7733-ból 20.
  3. Ha az összeg 0-ra végződik, akkor a szám a Luhn-formula szerint érvényes, egyébként nem az. 1111 tehát nem érvényes, 8763 azonban igen.

Ebben a két példában ha ellenőrzőszámot tennénk a számok elé, akkor 1111 elé egy 4-est kellene tenni, a 8763 elé pedig egy 0-t. Az ellenőrzőszámokat azonban rendszerint a számsor végére teszik, bár ehhez kissé módosítani kell az algoritmust.

Algoritmus[szerkesztés | forrásszöveg szerkesztése]

Az algoritmus három lépésben hajtódik végre. Először is, minden második számot, kezdve az utolsó előttivel és bal felé haladva, megkettőzünk. Ha az összeg 9-nél nagyobb, számjegyeit összeadjuk (ami a 10 és 18 közti számoknál annyit jelent, hogy 9-et kivonunk belőle.) Így 2-ből 4 lesz, 7-ből 5. Végül a számjegyeket összeadjuk. Ha a maradék 0, a szám érvényes.

 function checkLuhn(string purportedCC) {
     int sum := 0
     int nDigits := length(puportedCC)
     int parity := nDigits AND 1
     for i from 0 to nDigits {
         int digit := integer(purportedCC[i])
         if (i AND 1) XOR parity ≠ 0
             digit := digit × 2
         if digit > 9
             digit := digit – 9 
         sum := sum + digit
     }
     return (sum % 10) = 0
 }

Példa[szerkesztés | forrásszöveg szerkesztése]

Vegyük példának a 456-565-654 számot. Először kettőzzünk meg minden második számot és adjuk össze a számjegyeket az előbb ismertetettek szerint. A következő táblázat ezeket a lépéseket mutatja:

Számjegy „Duplája” Számjegyek összege
4 4 4
5 10 1
6 6 6
5 10 1
6 6 6
5 10 1
6 6 6
5 10 1
4 4 4
Összeg: 30

A kapott 30-at elosztjuk 10-zel; a maradék 0, tehát a szám érvényes.

További információk[szerkesztés | forrásszöveg szerkesztése]