Parfois, une tâche se pose pour protéger la chaîne d'identification des erreurs accidentelles commises par une personne. Par exemple, le numéro de carte de paiement. Pour ce faire, un chiffre de contrôle calculé d'une manière spéciale est ajouté à la ligne, et lorsqu'une personne entre ce numéro, vous pouvez effectuer une vérification d'erreur initiale sans accéder à la base de données. L'option la plus simple consiste à ajouter le reste de la division de la somme de tous les chiffres par 10, auquel cas la distorsion de n'importe quel chiffre (y compris celui de contrôle) sera facile à détecter, et une telle ligne ne passera pas le test. Mais certaines autres erreurs telles qu'une somme de contrôle manqueront, par exemple, une permutation de deux chiffres à certains endroits, et c'est également une erreur assez courante.
Pour protéger les numéros de cartes bancaires, un algorithme un peu plus complexe,
l' algorithme
Moon , a été choisi. Une modification y a été ajoutée: les chiffres se tenant à des endroits pairs sont multipliés par 2 avant de sommer (et s'il s'avère plus de neuf, alors 9 est soustrait). Cela vous permet de capturer, en plus de déformer n'importe quel chiffre, la plupart (mais pas la totalité) des permutations des chiffres adjacents.
Existe-t-il des algorithmes capables de détecter les permutations de chiffres adjacents (en plus de déformer un seul chiffre)? Oui, ils existent, bien que pour une raison quelconque ils ne soient pas très courants. Il s'agit de
l'algorithme Verhuff basé sur des groupes dièdres et de
l'algorithme Damm , qui est basé sur des quasigroupes Damm. Cela semble effrayant, mais en fait il n'y a rien de compliqué (pour ceux qui connaissent le concept de "groupe").
Jacobus Verhoeff, un mathématicien et sculpteur néerlandais (l'une de ses sculptures sur la photo), a proposé un algorithme basé sur
des groupes dièdres . Un groupe dièdre est un groupe de symétries d'un N-gon régulier, comprenant à la fois des rotations et des symétries axiales. Un tel groupe n'est pas commutatif: si un polygone régulier avec des sommets renumérotés est d'abord affiché symétriquement puis pivoté, alors dans la plupart des cas, ce ne sera pas la même chose que si vous faites d'abord pivoter puis afficher. Et par conséquent, lors de la "multiplication" séquentielle des chiffres de la chaîne d'origine en utilisant le fonctionnement du groupe dièdre, c'est-à-dire en appliquant successivement les opérations de rotation et de cartographie symétrique sur le N-gon régulier, nous obtenons une protection contre la plupart des permutations. De la majorité, mais toujours pas de tout le monde. Verkhuff a suggéré d'améliorer cet algorithme, et avant de multiplier chaque chiffre pour le remplacer par un autre selon un tableau spécial, en fonction de la place du chiffre dans la ligne. Le tableau est obtenu à partir d'une permutation en l'appliquant séquentiellement au résultat précédent, et après 8 de ces applications, nous arrivons à l'ordre d'origine, vous pouvez donc pré-construire le tableau 8x10 et prendre la valeur à partir de là. Certaines de ces permutations nous permettent de déterminer toutes les 100% d'erreurs possibles dans l'ordre des chiffres adjacents de la chaîne source, c'est-à-dire que c'est une solution complète et correcte au problème de trouver un chiffre de contrôle qui protège contre ces deux types d'erreurs. Apparemment, Verkhuff a trouvé une permutation réussie par sélection aléatoire, il y en a pas mal.
La question de savoir s'il existe des groupes qui permettent de trouver des permutations de chiffres adjacents sans modifications supplémentaires est restée ouverte pendant longtemps. Et déjà au XXIe siècle, en 2004, le mathématicien allemand Michael Damm a prouvé l'existence de tels groupes, ils sont appelés quazigroupes faiblement totalement anti-symétriques. Je n'ai pas entièrement compris comment les construire; ceux qui le souhaitent peuvent essayer de le faire eux-mêmes en le
publiant . Et même si cela ne semble pas si compliqué lors d'un examen rapide (il est même étrange que la question soit restée ouverte pendant si longtemps), pour une implémentation pratique, il existe un moyen plus simple: utiliser
des tableaux prêts à l' emploi.
Passons maintenant à la question suivante et principale: que se passe-t-il si je dois protéger non pas une chaîne de chiffres décimaux, mais une chaîne de caractères arbitraires, par exemple hexadécimal ou base64 ou base58? Autrement dit, pour résoudre le problème non pas dans le cas particulier du système numérique décimal, mais sous une forme générale.
L'algorithme de la Lune s'étend à ce cas sans problème, mais il n'est pas si intéressant, car il ne trouve pas toutes les permutations des chiffres voisins. La méthode de construction d'un quasigroupe antisymétrique de taille arbitraire n'est pas entièrement claire. Pour l'algorithme Verhuff, un groupe dièdre de taille N est facile à construire, mais vous avez toujours besoin d'une table de permutation, qui ne sait pas non plus où l'obtenir (et il n'est même pas clair s'il existe). Ceci est l'étude de la dernière question, et j'ai commencé.
La recherche sur Google n'a donné que des tentatives distinctes et l'utilisation de solutions «assez bonnes» (c'est-à-dire la détection de presque toutes les permutations) pour N = 64.
Je ne décrirai peut-être pas toutes les méthodes éprouvées pour trouver la permutation souhaitée, qui n'a pas donné de résultat. J'ai essayé de résoudre un problème particulier: trouver une permutation pour base64 et base58, qui offre une protection contre la modification de l'ordre des chiffres voisins. Je peux seulement dire que les tentatives pour trouver une telle permutation par recherche aléatoire ou séquentielle avec différentes options d'optimisation ont échoué. Mais à la fin, j'ai trouvé une solution générale pour tout n pair.
La permutation est la suivante:
0, N-1 .. N/2+1, 1 .. N/2
Par exemple, pour N = 10, ce serait:
0, 9, 8, 7, 6, 1, 2, 3, 4, 5
Cette permutation a une autre propriété remarquable: elle a toujours une période (pour N> = 8) de 12, ce qui vous permet de pré-construire une table 12xN et d'en prendre un chiffre.
Voici un exemple de mise en œuvre de l'extension proposée de l'algorithme Verhuff pour base58 (à proprement parler, ce n'est pas
l' algorithme
de Verkhuff , mais sa généralisation). Pas une bibliothèque complète, mais juste une utilité, pour ainsi dire, une preuve de concept.
La preuve que cette permutation a la propriété nécessaire, et qu'elle a une période de 12, je la fournirai un peu plus tard. Il y a trop peu d'espace dans la marge pour l'adapter ici.