Vérificateur de l’algorithme de Luhn

Qu’est-ce que l’algorithme de Luhn ?

L’algorithme de Luhn est une somme de contrôle : une règle qui transforme les chiffres d’un numéro en un chiffre supplémentaire à la fin, de sorte qu’une coquille n’importe où dans le numéro empêche l’ensemble de tomber juste. On le trouve sur toutes les cartes bancaires, sur l’IMEI qui identifie un téléphone, et sur les identifiants nationaux de plusieurs pays.

La règle est brève. En partant de la droite, doublez un chiffre sur deux ; si le doublement dépasse neuf, retranchez neuf. Additionnez le tout. Si le total est divisible par dix, le numéro est cohérent.

Il existe pour attraper les erreurs, non pour prouver quoi que ce soit. Un formulaire de paiement l’exécute avant l’envoi afin de pouvoir dire « revérifiez ce numéro » sans aller-retour vers la banque, et un lecteur d’entrepôt l’exécute pour rejeter sur-le-champ un IMEI mal scanné.

Comment l’utiliser

1. Collez un numéro avec ou sans espaces. Les espaces et les tirets sont ignorés : un numéro de carte copié par groupes de quatre fonctionne tel quel. Tout ce qui fait moins de huit chiffres est refusé — une somme de contrôle sur une poignée de chiffres n’apprend pas grand-chose, et aucun identifiant réel protégé par Luhn n’est aussi court.
2. Lisez le verdict. Lorsque la somme de contrôle échoue, l’outil indique quel chiffre les autres impliquent, ce qui suffit généralement à repérer celui qu’on a mal saisi. Lorsqu’elle passe, il note ce que suggère la longueur — un indice sur la forme du numéro, non une identification.
3. Regardez l’avertissement en dessous. Si le numéro comporte un 0 à côté d’un 9, il vous dit où. C’est le seul endroit où une coquille peut se cacher, pour la raison exposée plus bas.

Ce qu’il attrape, compté et non cité

On dit d’ordinaire que Luhn attrape toutes les erreurs d’un seul chiffre et toutes les inversions sauf une. Plutôt que de le répéter, nous l’avons mesuré. En prenant des numéros valides de seize chiffres et en changeant un chiffre à la fois, à chaque position, pour toutes les autres valeurs : 2 880 000 altérations testées, aucune n’est passée. Tout chiffre mal saisi casse la somme de contrôle.

Intervertir deux chiffres voisins est l’autre maladresse courante, et là Luhn est presque parfait sans l’être tout à fait. Sur 351 536 inversions voisines, 7 731 sont passées, soit 2,20 %. Et il s’agit d’une seule paire de chiffres : le 0 et le 9. Aucune autre paire de voisins ne peut être intervertie sans que la somme de contrôle s’en aperçoive.

La raison tient au doublement. Zéro doublé fait zéro. Neuf doublé fait dix-huit, qui se réduit à neuf. Ainsi, à la frontière entre une position doublée et une position non doublée, le 0 et le 9 apportent le même total dans un sens comme dans l’autre, et l’inversion est invisible. Toute autre paire modifie la somme. L’outil confronte cette prédiction aux quatre-vingt-dix paires ordonnées de chiffres : l’affirmation repose donc sur l’arithmétique et pas seulement sur le balayage.

Pourquoi Luhn l’emporte sur l’autre somme modulo dix

L’ISBN-13, la somme de contrôle de tous les livres publiés depuis 2007, est lui aussi modulo dix. Ce site l’a mesuré de la même façon : il laisse passer cinq paires de chiffres — 0 et 5, 1 et 6, 2 et 7, 3 et 8, 4 et 9 — soit 10,21 % des transpositions voisines. Luhn en laisse passer une paire, et 2,20 %.

Ce n’est donc pas le module qui les sépare. L’ISBN-13 pondère ses chiffres alternativement par 1 et 3, ce qui est linéaire : intervertir deux voisins décale le total du double de leur écart, et tout écart de cinq disparaît modulo dix. Le double-puis-retranche-neuf de Luhn n’est pas linéaire, et cette seule brisure lui coûte une paire aveugle au lieu de cinq.

C’est une jolie illustration du fait que la force d’une somme de contrôle tient à sa pondération et non à son module — et qu’un schéma conçu en 1954 pour des machines à cartes perforées fait mieux, sur cette mesure, qu’un autre adopté en 2007.

Limites honnêtes

Une somme de contrôle valide signifie que les chiffres sont cohérents entre eux. Elle ne signifie pas que le numéro a été émis, appartient à quelqu’un ou fonctionne. Les numéros de carte, les IMEI et les identifiants sont des enregistrements dans la base de données de quelqu’un, et le seul moyen de savoir si l’un est réel est de le demander à celui qui la tient. Toute page prétendant vérifier une carte sans contacter un émetteur fait exactement ce que fait celle-ci : de l’arithmétique.

Cet outil n’identifie pas non plus l’émetteur. Les premiers chiffres d’une carte l’encodent bien, via un registre tenu par les réseaux de paiement, mais ce registre n’est pas intégralement public, il change, et une copie périmée serait fausse avec assurance — l’objection permanente de ce site au fait d’embarquer des données qui bougent. La note de longueur est un indice sur la forme, rien de plus.

Luhn est une vérification de coquilles, non une mesure de sécurité, et n’a jamais prétendu l’être. Il empêche un chiffre inversé d’atteindre un prestataire de paiement ; il ne fait rien contre quiconque sait exécuter les mêmes trois lignes d’arithmétique. Toutes ses implémentations sont publiques, y compris celle-ci.

Enfin, les chiffres ci-dessus proviennent d’un balayage de numéros engendrés et non réels, car la propriété est arithmétique et ne dépend pas des numéros effectivement émis. La paire aveugle se démontre à partir de la règle de doublement, et la page donne cette démonstration plutôt que de s’appuyer sur l’échantillon.

Pourquoi est-ce gratuit ?

Parce que c’est une addition et un reste. Aucune base de données, rien à télécharger, aucun serveur : tout s’exécute dans votre navigateur, et rien de ce que vous tapez n’est envoyé, journalisé ni conservé où que ce soit.

Ce dernier point compte ici plus que sur la plupart des pages. Il n’y a donc ni compte, ni inscription, ni rien de réservé. Le moteur et ses 218 vérifications se trouvent dans le dépôt, à côté de la page, y compris les balayages derrière chacun des chiffres cités plus haut.