Luhn algoritmus - Luhn algorithm

A Luhn -algoritmus vagy Luhn -képlet , más néven " modulus 10" vagy "mod 10" algoritmus , amelyet az alkotójáról, Hans Peter Luhn IBM tudósról neveztek el , egy egyszerű ellenőrzőösszeg -képlet , amelyet különböző azonosító számok, például hitelek hitelesítésére használnak kártyaszámok , IMEI -számok , nemzeti szolgáltatói azonosítószámok az Egyesült Államokban, kanadai társadalombiztosítási számok , izraeli azonosítószámok, dél -afrikai azonosítószámok, svéd nemzeti azonosító számok , svéd vállalati azonosító számok (OrgNr), görög társadalombiztosítási számok (ΑΜΚΑ), A McDonald's , a Taco Bell és a Tractor Supply Co. nyugtain megjelenő SIM -kártya számok és felmérési kódok . Ezt a 2 950 048 számú amerikai egyesült államokbeli szabadalom írja le, amelyet 1960. augusztus 23 -án adtak ki.

Az algoritmus nyilvános és ma széles körben használatos. Az ISO/IEC 7812 -1 szabvány tartalmazza . Nem kriptográfiailag biztonságos hash függvény ; úgy tervezték, hogy megvédjen a véletlen hibáktól, ne rosszindulatú támadásoktól. A legtöbb hitelkártya és sok kormányzati azonosító szám az algoritmust használja az egyszerű számok megkülönböztetésére az érvénytelen számokat a rosszul beírt vagy más módon helytelen számoktól.

Leírás

Az ellenőrző számjegyet a következőképpen kell kiszámítani:

  1. Vegyük az eredeti számot, és a bal oldali jobb szélső számjegyből kiindulva minden második számjegy értékét megkétszerezzük (beleértve a jobb szélső számjegyet is).
  2. Cserélje ki a kapott értéket minden pozícióban ennek a pozíciónak a számjegyeinek összegével.
  3. Összefoglalva: a kapott értékeket minden pozícióban ( ek ).
  4. A számított ellenőrző számjegy egyenlő .

Példa az ellenőrző számjegy kiszámítására

Tegyünk fel egy példát a "7992739871" számlaszámra (csak a "hasznos terhet", az ellenőrző számjegyet még nem tartalmazza):

7 9 9 2 7 3 9 8 7 1
Szorzók 1 2 1 2 1 2 1 2 1 2
= = = = = = = = = =
7 18 9 4 7 6 9 16 7 2
Összeg számjegyek 7 9 (1+8) 9 4 7 6 9 7 (1+6) 7 2

A kapott számjegyek összege 67.

Az ellenőrző számjegy egyenlő .

Így a teljes számlaszám 79927398713 lesz.

Példa ellenőrző számjegy érvényesítésére

Csak vágja le a szám ellenőrző számjegyét (utolsó számjegye) az érvényesítéshez. 79927398713 -> 7992739871 Számítsa ki az ellenőrző számjegyet (lásd fent) (3), és hasonlítsa össze az eredményt a levágott ellenőrző számjeggyel (3 = 3). Ha megegyezik a számmal, akkor sikeres volt a teszt.

Erősségeit és gyengeségeit

A Luhn-algoritmus észlel minden egyjegyű hibát, valamint a szomszédos számjegyek szinte minden átültetését. Ez azonban nem érzékeli átültetése a kétjegyű szekvencia 09 , hogy a 90 (vagy fordítva). A legtöbb ikerhibát észleli (nem észleli a 2255 , 3366 vagy 4477 értékeket ).

Más, összetettebb ellenőrző számjegyű algoritmusok (például a Verhoeff-algoritmus és a Damm-algoritmus ) több transzkripciós hibát észlelhetnek. A Luhn mod N algoritmus egy kiterjesztés, amely nem numerikus karakterláncokat támogat.

Mivel az algoritmus jobbról balra működik a számjegyeken, és a nulla számjegy csak akkor befolyásolja az eredményt, ha a pozíció eltolódását okozza, a számsor elejének nulla kitöltése nem befolyásolja a számítást. Ezért azok a rendszerek, amelyek meghatározott számjegyre írják be (például az 1234 -et 0001234 -re konvertálva), elvégezhetik a Luhn -érvényesítést a párnázás előtt vagy után, és ugyanazt az eredményt érhetik el.

Az algoritmus egy amerikai szabadalomban jelent meg egy kézi, mechanikus eszköz számára az ellenőrző összeg kiszámításához. Ezért meglehetősen egyszerűnek kellett lennie. A készülék mechanikai eszközökkel vette a mod 10 összeget. A helyettesítő számjegyeket , azaz a dupla és csökkentési eljárás eredményeit nem mechanikusan állították elő. Inkább a számjegyeket permutált sorrendben jelölték a gép testén.

Pseudokód implementáció

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
}

Hivatkozások

  1. ^ a b 2950048A számú amerikai egyesült államokbeli szabadalom , Luhn, Hans P. , "Számítógép a számok ellenőrzéséhez", közzétéve 1960-08-23 
  2. ^ "B. melléklet: Luhn-képlet a 10-es modulus kiszámításához" dupla-add-dupla "ellenőrző számjegyek". Azonosító kártyák. A kibocsátók azonosítása. 1. rész: Számozási rendszer (szabvány). Nemzetközi Szabványügyi Szervezet , Nemzetközi Elektrotechnikai Bizottság . 2017. január ISO/IEC 7812 -1: 2017.

Külső linkek