Algorithme de Luhn

L' algorithme de Luhn ou formule de Luhn , également connu sous le nom d' algorithme « modulo 10 » ou « mod 10 » , du nom de son créateur, le scientifique d'IBM Hans Peter Luhn , est une formule de contrôle simple utilisée pour valider une variété de numéros d'identification. Il est décrit dans le brevet américain 2950048A, accordé le 23 août 1960.

L'algorithme est dans le domaine public et est largement utilisé aujourd'hui. Il est spécifié dans la norme ISO/IEC 7812-1 . Il n'est pas destiné à être une fonction de hachage cryptographiquement sécurisée ; il a été conçu pour protéger contre les erreurs accidentelles, et non contre les attaques malveillantes. La plupart des numéros de carte de crédit et de nombreux numéros d'identification gouvernementaux utilisent l'algorithme comme une méthode simple pour distinguer les numéros valides des numéros mal saisis ou incorrects.

Le chiffre de contrôle est calculé comme suit :

1. Supprimez le chiffre de contrôle du numéro (s'il est déjà présent). Il ne reste plus que la charge utile.
2. Commencez par les chiffres de la charge utile. De droite à gauche, doublez chaque deuxième chiffre, en commençant par le dernier chiffre. Si le doublement d'un chiffre donne une valeur > 9, soustrayez-lui 9 (ou additionnez ses chiffres).
3. Additionnez tous les chiffres résultants (y compris ceux qui n’ont pas été doublés).
4. Le chiffre de contrôle est calculé par , où s est la somme de l'étape 3. Il s'agit du plus petit nombre (éventuellement zéro) qui doit être ajouté pour former un multiple de 10. D'autres formules valides donnant la même valeur sont , et . Notez que la formule ne fonctionnera pas dans tous les environnements en raison des différences dans la façon dont les nombres négatifs sont traités par l' opération modulo .

Prenons l'exemple d'un numéro de compte 1789372997 (juste la « charge utile », chiffre de contrôle non encore inclus) :

La somme des chiffres résultants est 56.

Le chiffre de contrôle est égal à .

Cela donne comme numéro de compte complet 17893729974.

1. Supprimez le chiffre de contrôle (dernier chiffre) du numéro à valider. (par exemple 17893729974 → 1789372997)
2. Calculer le chiffre de contrôle (voir ci-dessus)
3. Comparez votre résultat avec le chiffre de contrôle d'origine. Si les deux chiffres correspondent, le résultat est valide. (par exemple (givenCheckDigit = calculatedCheckDigit) ⇔ (isValidCheckDigit)).

L'algorithme de Luhn détectera toutes les erreurs sur un seul chiffre, ainsi que presque toutes les transpositions de chiffres adjacents. Il ne détectera cependant pas la transposition de la séquence de deux chiffres de 09 à 90 (ou vice versa). Il détectera la plupart des erreurs jumelles possibles (il ne détectera pas 22 ↔ 55 , 33 ↔ 66 ou 44 ↔ 77 ).

D'autres algorithmes de contrôle plus complexes (tels que l' algorithme de Verhoeff et l' algorithme de Damm ) peuvent détecter davantage d'erreurs de transcription. L' algorithme Luhn mod N est une extension qui prend en charge les chaînes non numériques.

Étant donné que l'algorithme opère sur les chiffres de droite à gauche et que les chiffres nuls n'affectent le résultat que s'ils provoquent un décalage de position, le remplissage par des zéros au début d'une chaîne de nombres n'affecte pas le calcul. Par conséquent, les systèmes qui remplissent jusqu'à un nombre spécifique de chiffres (en convertissant 1234 en 0001234 par exemple) peuvent effectuer une validation Luhn avant ou après le remplissage et obtenir le même résultat.

L'algorithme est apparu dans un brevet américain pour un appareil mécanique simple, portable, permettant de calculer la somme de contrôle. L'appareil prenait la somme mod 10 par des moyens mécaniques. Les chiffres de substitution , c'est-à-dire les résultats de la procédure de double et de réduction, n'étaient pas produits mécaniquement. Au lieu de cela, les chiffres étaient marqués dans leur ordre permuté sur le corps de la machine.

La fonction suivante prend un numéro de carte, y compris le chiffre de contrôle, sous forme de tableau d'entiers et renvoie vrai si le chiffre de contrôle est correct, faux sinon.

fonction isValid(cardNumber[1..length]) somme := 0 parité := longueur mod 2 pour i de 1 à longueur faire 
si i mod 2 != parité alors somme := somme + cardNumber[i] sinon si cardNumber[i] > 4 alors somme := somme + 2 * cardNumber[i] - 9 autre somme := somme + 2 * cardNumber[i] fin si 
fin pour 
retour cardNumber[length] == ((10 - (somme mod 10)) mod 10) fin de fonction

L'algorithme de Luhn est utilisé dans une variété de systèmes, notamment :

• Numéros de carte de crédit
• Numéros IMEI
• Numéros d'identification des fournisseurs nationaux aux États-Unis
• Numéros d'assurance sociale canadiens
• Numéros d'identification israéliens
• Numéros d'identification sud-africains
• Numéros de référence fiscale sud-africains
• Numéros d'identification nationaux suédois
• Numéros d'identité d'entreprise suédois (OrgNr)
• Numéros de sécurité sociale grecs (ΑΜΚΑ)
• ICCID des cartes SIM
• Numéros de demande de brevet européen
• Codes d'enquête apparaissant sur les reçus de McDonald's , Taco Bell et Tractor Supply Co.
• Les numéros de suivi des colis du service postal des États-Unis utilisent un algorithme de Luhn modifié
• Numéros de TVA italiens ( Partita Iva )