Algoritmo di Luhn - Luhn algorithm
Il Luhn algoritmo o formula Luhn , conosciuto anche come il " modulo 10" o "mod 10" algoritmo , dal nome del suo creatore, IBM scienziato Hans Peter Luhn , è una semplice somma di controllo formula utilizzata per convalidare una serie di numeri di identificazione, come il credito numeri di carta , i numeri IMEI , numeri identificativi fornitore nazionale negli Stati Uniti, Canada numeri di assicurazione sociale , israeliani numeri ID, Sud Africa numeri ID, svedese numeri di identificazione nazionali , svedese Numbers Corporate Identity (OrgNr), greca codice fiscale (ΑΜΚΑ), Numeri di carte SIM e codici di indagine che appaiono sulle ricevute di McDonald's , Taco Bell e Tractor Supply Co. È descritto nel brevetto USA n. 2.950.048, concesso il 23 agosto 1960.
L'algoritmo è di dominio pubblico ed è ampiamente utilizzato oggi. È specificato nella norma ISO/IEC 7812 -1. Non intende essere una funzione hash crittograficamente sicura ; è stato progettato per proteggere da errori accidentali, non da attacchi dannosi. La maggior parte delle carte di credito e molti numeri di identificazione governativi utilizzano l'algoritmo come un metodo semplice per distinguere i numeri validi da numeri errati o altrimenti errati.
Descrizione
La cifra di controllo viene calcolata come segue:
- Prendi il numero originale e partendo dalla cifra più a destra spostandoti a sinistra, raddoppia il valore di ogni seconda cifra (inclusa la cifra più a destra).
- Sostituisci il valore risultante in ogni posizione con la somma delle cifre del valore di questa posizione.
- Somma i valori risultanti da tutte le posizioni ( s ).
- La cifra di controllo calcolata è uguale a .
Esempio per il calcolo della cifra di controllo
Assumi un esempio di un numero di conto "7992739871" (solo il "payload", cifra di controllo non ancora inclusa):
| 7 | 9 | 9 | 2 | 7 | 3 | 9 | 8 | 7 | 1 | |
| moltiplicatori | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|
| = | = | = | = | = | = | = | = | = | = | |
| 7 | 18 | 9 | 4 | 7 | 6 | 9 | 16 | 7 | 2 | |
| Somma cifre | 7 | 9 (1+8) | 9 | 4 | 7 | 6 | 9 | 7 (1+6) | 7 | 2 |
La somma delle cifre risultanti è 67.
La cifra di controllo è uguale a .
Questo fa leggere il numero di conto completo 79927398713.
Esempio per la convalida della cifra di controllo
Basta tagliare la cifra di controllo (ultima cifra) del numero da convalidare. 79927398713 -> 7992739871 Calcola la cifra di controllo (vedi sopra) (3) e confronta il tuo risultato con la cifra di controllo che hai tagliato (3 = 3). Se corrispondono al numero superato il test.
Punti di forza e di debolezza
L'algoritmo di Luhn rileverà qualsiasi errore a una cifra, così come quasi tutte le trasposizioni di cifre adiacenti. Tuttavia, non rileverà la trasposizione della sequenza a due cifre da 09 a 90 (o viceversa). Rileverà la maggior parte dei possibili errori singoli (non rileverà 22 ↔ 55 , 33 ↔ 66 o 44 ↔ 77 ).
Altri algoritmi di cifra di controllo più complessi (come l' algoritmo di Verhoeff e l' algoritmo di Damm ) possono rilevare più errori di trascrizione. L' algoritmo Luhn mod N è un'estensione che supporta stringhe non numeriche.
Poiché l'algoritmo opera sulle cifre in modo da destra a sinistra e le cifre zero influiscono sul risultato solo se causano uno spostamento di posizione, l'aggiunta di zero all'inizio di una stringa di numeri non influisce sul calcolo. Pertanto, i sistemi che utilizzano un numero specifico di cifre (ad esempio convertendo 1234 in 0001234) possono eseguire la convalida Luhn prima o dopo l'imbottitura e ottenere lo stesso risultato.
L'algoritmo è apparso in un brevetto degli Stati Uniti per un dispositivo meccanico portatile per il calcolo del checksum. Pertanto, doveva essere piuttosto semplice. Il dispositivo ha preso la somma mod 10 con mezzi meccanici. Le cifre di sostituzione , cioè i risultati della procedura double and reduce, non sono state prodotte meccanicamente. Piuttosto, le cifre sono state contrassegnate nel loro ordine permutato sul corpo della macchina.
Implementazione dello pseudocodice
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
}
Riferimenti
- ^ a b Brevetto USA 2950048A , Luhn, Hans P. , "Computer per la verifica dei numeri", pubblicato il 23/08/1960
- ^ "Allegato B: formula di Luhn per il calcolo del modulo-10 "doppia-aggiungi-doppio" cifre di controllo" . Carte di identificazione — Identificazione degli emittenti — Parte 1: Sistema di numerazione (standard). Organizzazione internazionale per la standardizzazione , Commissione elettrotecnica internazionale . Gennaio 2017. ISO/IEC 7812 -1:2017.