Luhn-formula
A Wikipédiából, a szabad lexikonbó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ú (checksum) 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, public domain 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.
Tartalomjegyzék |
[szerkesztés] Magyarázat
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:
- 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.
- Adjuk össze ezeket a számokat (ti. számjegyeket). Az előbb kapott 2121-ből így 6 lesz, 7733-ból 20.
- 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 ne é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.
[szerkesztés] Algoritmus
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
}
[szerkesztés] Példa
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.
Based on work by