Formule 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 code de Luhn, ou encore formule de Luhn est aussi appelé algorithme « modulo 10 » ou « mod 10 ». C'est une formule simple de somme de contrôle utilisée pour valider divers numéros de comptes, comme les numéros de cartes bancaires, les numéros d'assurance sociale canadiens, les numéros IMEI des téléphones mobiles ou les numéros SIRET.

Dans ce numéro d'immatriculation de wagon, le chiffre « 8 » après le tiret est calculé par la formule de Luhn à partir des onze chiffres précédents.

Elle fut développée dans les années 1960 par un ingénieur allemand chez IBM, Hans Peter Luhn, comme méthode de validation d'identification de nombres. Sa notoriété provient principalement de son adoption par les compagnies de cartes de crédit peu 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. La plupart des cartes de crédit et beaucoup de numéros d'identification gouvernementaux utilisent l'algorithme comme un moyen simple de distinguer les nombres valides dans des collections de chiffres aléatoires.

Explications informelles

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 (c'est-à-dire la clef) 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 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) ;
2. 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 ;
3. 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 :

• calculer la somme comme décrit ci-dessus, deux cas de figure se présentent alors :

1. Si la somme est un multiple de 10, le chiffre de contrôle final est é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) où 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

Description

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 le double d'un chiffre est plus grand que neuf (par exemple 2 × 8 = 16), alors il faut le ramener à un chiffre entre 1 et 9 en prenant son reste dans la division euclidienne par 9. Pour cela, il y a deux manières de faire (pour un résultat identique) :
   1. Soit on additionne les chiffres composant le double. Dans l'exemple du chiffre 8, 2 × 8 = 16, puis on additionne les chiffres 1 6 = 7.
   2. Soit on soustrait 9 au double. Avec le même exemple, 16 − 9 = 7.
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.

Exemple

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^e 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 (sauf si ces deux chiffres sont 0 et 9) :

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.

Cas particulier

En France, le numéro SIRET des établissements de La Poste ne respecte pas l'algorithme de Luhn. La Poste a changé de statut en 2010, devenant une société anonyme. Tous les établissements de La Poste possèdent le même numéro SIREN « 356 000 000 ». Comme La Poste a de nombreux établissements et que le nombre de NIC possibles n'est pas assez étendu, la règle de contrôle du numéro SIRET a été modifiée pour cette entreprise. Lors du contrôle, il faut appliquer la vérification classique puis, si la règle classique n’est pas vérifiée, vérifier alors que la somme simple des chiffres du SIRET est un multiple de cinq (réponse officielle de l'INSEE) (ex. : pour le siège de La Poste le numéro SIRET est 35600000000048. Il vérifie la formule classique mais pas l'autre règle ; pour l'établissement de Rennes de numéro SIRET 35600000009075, la règle classique échoue, mais la vérification avec l'autre règle est valide).

En Belgique (avant l'application du standard SEPA qui ajoute « BE » et deux chiffres devant, pour former l’IBAN), les numéros de compte en banque (« BBAN »), sont vérifiés par la simple opération MODULO 97, cela veut dire que les deux derniers chiffres sont le reste de la division par 97 des autres chiffres. Ceci est également valable pour les communications dites « structurées » (12 chiffres) des virements interbancaires.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Luhn algorithm » (voir la liste des auteurs).

Articles connexes

• EAN 13

Liens externes

• (en) Implémentation dans divers langages, sur rosettacode.org