Formule de Luhn

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques et plus précisément en arithmétique modulaire, la formule de Luhn est utilisée pour ses applications en cryptologie. L'algorithme de Luhn ou la formule de Luhn, aussi connu comme l'algorithme « modulo 10 » ou « mod 10 », fut développée dans les années 1960 par un ingénieur allemand de chez IBM, Hans Peter Luhn, comme méthode de validation d'identification de nombres. C'est une simple formule de somme de contrôle (Checksum) utilisée pour valider une variété de numéros de comptes, comme les numéros de cartes bancaires, les numéros d'assurance sociale canadiens ainsi que pour le calcul de validité d'un numéro SIRET. Beaucoup de sa notoriété provient de son adoption par les compagnies de cartes de crédit rapidement après sa création.

L'algorithme fait partie du domaine public et est largement répandu aujourd'hui. Il n'a pas été conçu pour être une fonction de hachage sécurisée cryptologiquement ; il protège contre les erreurs aléatoires, pas contre les attaques malveillantes. La plupart des cartes de crédit et beaucoup de numéros d'identification gouvernementaux utilisent l'algorithme comme une simple méthode de distinction de nombres valides dans des collections de chiffres aléatoires.

Explications informelles[modifier | modifier le code]

La formule génère un chiffre de vérification, qui est généralement annexé à un numéro d'identité partiel pour générer un identifiant complet. Cet identifiant (numéro complet : numéro partiel et son chiffre de vérification) est soumis à l'algorithme suivant pour vérifier sa validité :

  1. on démarre avec le dernier chiffre (à droite) et on se déplace vers la gauche, en doublant la valeur de tous les chiffres de rang pair : le dernier est traité en 1er, il n'est pas doublé, l'avant-dernier (2e) sera doublé. Si le double d'un chiffre dépasse 9, on le remplace par la somme de ses chiffres. Ainsi,
sur les positions paires, 
les chiffres (0;1;2;3;4;5;6;7;8;9)
 deviennent  (0;2;4;6;8;1;3;5;7;9) 

Par exemple, 1 111 devient 2 121, tandis que 8 763 devient 7 733 (car 2×6=12, et 1+2=3 ; 2×8=16, et 1+6=7).

  1. on additionne ensemble tous les chiffres du nombre ainsi obtenu. Par exemple, 1111 devient 2121 dont la somme donne 6 (2+1+2+1) ; tandis que 8763 devient 7733 et 7+7+3+3 donne alors 20.
  2. si le total est un multiple de 10 (le chiffre des unités est un zéro), alors le nombre est valide, en accord avec la formule de Luhn. Sinon il est invalide. Ainsi 1 111 n'est pas valide (comme montré ci-dessus, il aboutit à 6), tandis que 8 763 est valide (comme montré ci-dessus, il aboutit à 20).

Pour déterminer le chiffre de contrôle ajouté à la fin du numéro :

  1. calculer la somme comme décrit ci-dessus pour un chiffre de contrôle final égal à 0,
  2. si la somme n'est pas un multiple de 10, modifier le dernier chiffre pour obtenir un multiple de 10, soit 10 - (somme % 10)somme % 10 désigne le reste de la division entière de la somme calculée par 10 (ce qui revient à ne garder que le chiffre des unités).

Exemple :

  • Soit le numéro 54321x à calculer (x désignant le chiffre de contrôle à calculer),
  • Pour x = 0, la vérification de 543210 donne la somme 0 + 2 + 2 + 6 + 4 + 1 = 15 non multiple de 10 (le chiffre des unités est 5),
  • On corrige le dernier chiffre : x = 10 - 5 = 5
  • Pour x = 5, la vérification de 543215 donne la somme 5 + 2 + 2 + 6 + 4 + 1 = 20 multiple de 10.

Algorithme[modifier | modifier le code]

L'algorithme procède en trois étapes.

  1. L'algorithme multiplie par deux un chiffre sur deux, en commençant par l'avant dernier et en se déplaçant de droite à gauche. Si un chiffre qui est multiplié par deux est plus grand que neuf (comme c'est le cas par exemple pour 8 qui devient 16), alors il faut le ramener à un chiffre entre 1 et 9. Pour cela, il y a 2 manières de faire (pour un résultat identique) :
    1. Soit les chiffres composant le doublement sont additionnés (pour le chiffre 8: on obtient d'abord 16 en le multipliant par 2 puis 7 en sommant les chiffres composant le résultat : 1+6).
    2. Soit on lui soustrait 9 (pour le chiffre 8 : on obtient 16 en le multipliant par 2 puis 7 en soustrayant 9 au résultat).
  2. La somme de tous les chiffres obtenus est effectuée.
  3. Le résultat est divisé par 10. Si le reste de la division est égal à zéro, alors le nombre original est valide.


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

Exemple[modifier | modifier le code]

Considérons l'identification du nombre 972-487-086. La première étape consiste à doubler un chiffre sur deux en partant de l'avant-dernier jusqu'au début, et de faire la somme de tous les chiffres, doublés ou non (si un chiffre est supérieur à 9, on retranche 9, d'où la 3ème ligne). Le tableau suivant montre cette étape (les lignes colorées indiquent les chiffres doublés) :

Chiffre Somme
9 7 2 4 8 7 0 8 6
9 14 2 8 8 14 0 16 6
9 5 2 8 8 5 0 7 6 50

La somme, égale à 50, est divisée par 10 : le reste est 0, donc le nombre est valide.


Si par mégarde, deux chiffres ont été inversés, le code Luhn devient incorrect:

Chiffre Somme
9 2 7 4 8 7 0 8 6
9 4 7 8 8 14 0 16 6
9 4 7 8 8 5 0 7 6 54

La somme n'est pas divisible par 10 donc le nombre n'est pas valide.

Liens externes[modifier | modifier le code]