Re: Modulo tout retourné dans les clefs

Après mûre réflexion, le 3 septembre 2021 à 19:59, Olivier Miakinen eu
l'idée d'écrire :

[Supersedes pour corriger une erreur, j'espère que c'est la seule]
>
Bonjour,
>
Afin de répondre correctement et sans à priori, j'ai fait un petit
programme en python pour évaluer l'efficacité des différents nombres
pris comme modulos. Pour ce programme j'ai fait quelques hypothèses
simplificatrices, qui peuvent avoir influé sur les résultats. Je suis
preneur de tous commentaires à ce propos.
>
Mais j'ai été surpris !
>
Le 28/08/2021 11:42, Benoit me répondait :

>

2. Pourquoi ne pas avoir pris un nombre premier de trois chiffres, voire
9973 ?

 
Ça c'est pour n'avoir à ajouter que deux chiffres au code plutôt que
trois ou quatre. Je pense que 97 (le plus grand nombre premier à
deux chiffres) est le meilleur compromis entre l'économie de place
et la sécurité.

>
Première surprise : ce n'est pas le meilleur compromis.
Deuxième surprise : le meilleur compromis n'est pas un nombre premier.
>

À ce propos, si je passe le nombre premier de deux chiffres à trois,
est-ce que je suis assurément dix fois plus sûr ?

>
Troisième surprise : non, ce n'est pas dix fois plus sûr.
>
1er cas : un seul chiffre est erroné.
>
Ce cas est très facile à traiter. Si le modulo est un nombre premier, ou
même un nombre non premier mais non divisible par 2 ou 5, et qu'il est
plus grand que 10, alors modifier un seul chiffre revient à ajouter ou
retirer un nombre qui ne sera jamais un multiple de ce modulo. Dans ce
cas, la clé de contrôle suffira toujours à détecter l'erreur.

Cf le problème des cartes bancaires ci-dessous.

2e cas : deux chiffres sont erronés.
>
Voici un exemple d'erreur possible : ajouter 1 à un chiffre du code INSEE
(par exemple le passer de 1 à 2 ou de 5 à 6), et simultanément ajouter 7
au chiffre qui se trouve cinq rangs plus loin (par exemple le passer de 0
à 7 ou de 2 à 9). Ceci est possible parce que 100007 est un multiple de
97 (c'est 1031 fois 97). Cette erreur peut concerner 8 paires de chiffres
d'un nombre de 13 chiffres. Par ailleurs, elle peut concerner 9 valeurs
du premier chiffre (de 0 à 8) et 3 valeurs de l'autre chiffre (de 0 à 2).
L'erreur associée au nombre 100007 doit donc être comptée 216 fois car
8×9×3 = 216.

N’y a-t-il pas :

—      3 007 : 97 x 31 ==> 10 x 7 x 3 = 210 erreurs
—  7 000 005 : 97 x 72 165 ==> 7 x 3 x 5 = 105 erreurs
- 50 000 008 : 97 x 515464 ==> 6 X 5 X 2 = 60 erreurs

375 erreurs potentielles. Pas beaucoup, mais pour une fois c’est mieux
d’avoir un 0 en maths :)

Puis 60 000 000 000 007 mais 14 chiffres et je ne sais aller au-delà
avec mon bon vieil Excel.

Le plus petit multiple de 97 concerné est 97 lui-même (+100 -3) compté 693
fois. Le plus grand multiple de 97 est 5 999 999 999 991 (+6.10^12 -9)
compté 4 fois. Au total, pour 97, le nombre de paires de codes donannt la
même clé s'élève à 2798. Est-ce le meilleur nombre à deux chiffres ? Non !
Parmi tous les nombres à deux chiffres (en excluant les multiples de 2 ou
de 5), il en existe un et un seul qui fait mieux que 97, et il s'agit de
93, alors seulement 2167 paires de clés indiscernables.

Il y en a plus pour les comptes bancaires puisque des lettres peuvent
être utilisées et 10 chiffres pour 26 lettres… cela veut dire qu’un
chiffre peut servir de calcul pour plusieurs comptes.

Peut-on faire mieux avec une clé à trois chiffres ? Oui ! Est-ce que le plus
grand nombre premier de trois chiffres (997) fait dix fois mieux que 97 ?
Pas du tout ! Il ne fait même pas trois fois mieux : 1083. Est-ce qu'on peut
quand même faire beaucoup mieux ? Oui ! Jugez plutôt. 993 fait déjà bien mieux
avec 270. 991 et 989 font encore mieux avec 90 et 81. Mais 987 fait beaucoup
plus que ça, et même infiniment mieux, avec 0 !
>
Eh oui, si on calculait un code modulo 987 au lieu de modulo 97, aucune erreur
sur seulement 2 chiffres ne serait indétectable. Et 987 n'est pas le seul
nombre à trois chiffres qui le permette, le plus petit est 279.

Comme c’est utilisé aussi pour les RIB avec leur « clef » il eût été
préférable qu’ils l’utilisent.

Bon, mon message est déjà très long, mais si certains sont intéressés je peux
publier mon programme ainsi que montrer quelques résultats.

Pour les numéros de cartes bancaires c’est la Formule de Luhn qui est
utilisée, mais là je ne sais pas comment calculer pour le problème
énoncé ci-dessus. Si le résultat doit être un multiple de 10 je ne vois
pas comment cela peut être plus sûr.

<https://fr.wikipedia.org/wiki/Formule_de_Luhn>


--
Benoît
Les gens sans humour manquent de sérieux.