Algorithme de Luhn

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é dans les années 1960 comme une méthode de validation d'identification de nombres. C'est une simple formule de vérification de somme (Checksum) utilisée pour valider une variété de numéros de comptes, comme les numéros de cartes de crédit, 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 sur la fin des années 1960 par Hans Peter Luhn (1896–1964), un scientifique d'IBM.

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.

Sommaire 1 Explications informelles 2 Algorithme 3 Exemple 4 Liens externes

Explications informelles

La formule génère un chiffre de vérification, qui est généralement annexé à un numéro de compte partiel pour générer un numéro de compte complet. Ce numéro de compte (complet, i.e. le numéro partiel et le chiffre de vérification) est soumis à l'algorithme suivant pour vérifier sa correction :

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 1^er, il n'est pas doublé, l'avant-dernier (2^e) sera doublé. Si le double d'un chiffre dépasse 10, on le remplace par la somme de ses chiffres. 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).
2. on additionne ensemble tous les chiffres du nombre ainsi obtenu. Par exemple, 1 111 devient 2 121, alors 2+1+2+1 ce qui nous donne 6 ; tandis que 8 763 devient 7 733, alors 7+7+3+3 ce qui nous donne 20.
3. si le total est un multiple de 10, alors le nombre est valide, étant 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 ce chiffre pour obtenir un multiple de 10, soit 10 - (somme % 10) où somme % 10 désigne le reste de la division entière de la somme calculée par 10.

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 1 + 4 + 6 + 2 + 2 + 0 = 15 non multiple de 10,
• On corrige le chiffre x = 10 - (15 % 10) = 10 - 5 = 5
• Pour x = 5, la vérification de 543215 donne la somme 1 + 4 + 6 + 2 + 2 + 5 = 20 multiple de 10.

Algorithme

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

Considérons l'identification du nombre 972-487-086. La première étape consiste à doubler un chiffre sur deux en partant du deuxième jusqu'à la fin, 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

• Implémentation PHP
• (en) Implémentation C, awk et Python
• Implémentation C++
• Implémentation C#
• Implémentation C
• Implémentation Python
• (en) Implémentation Java avec cas de test
• (en) Implémentation Common Lisp
• (en) Implémentation Perl (anglais)
• (en) Implémentation JavaScript
• (en) Implémentation MS Excel
• (en) Implémentation MySQL
• (en) Implémentation Transact-SQL