Transcodage / hashcode

Je cherche une solution au problème suivant :

Un canal de transmission permet de transmettre un identifiant
numérique à 6 positions (6 caractères numériques).

En raison d'une évolution réglementaire incontournable,
l'identifiant va passer à 12 caractères numériques.

Pendant une période transitoire, on veut permettre
le fonctionnement de l'ancien canal, le temps que les
organismes concernés fassent évoluer leur système
d'information.


Autrement dit : on veut produire l'équivalent d'un hash-code
sur 6 chiffres d'une information sur 12 chiffres,
avec le moins de collisions possibles.
Pour des raisons d'équité, il faut que les collisions
soient bien réparties (et non pas concentrées sur
certains intervalles de la valeur sur 12).

Contrainte supplémentaire :
- le "hash-code" ne doit pas commencer par le
chiffre '3'.


Avez-vous des idées ?


Phil l'ancien-


bon, ça me semble etre un probleme d'informatique plus que de maths.

Résumons

on a une entrée de 12 chiffres qu'on veut hasher vers 6 chiffres
Il est donc obligatoire qu'il y aie des collisions, et donc s'amuser à
trouver un hash sans collision est inutile.
Il y a des fonctions de hashage qui marchent très bien. Elles sont
relativement rapides, offrent diverses assurances dont la normalité des
bits de sortie (en gros la sortie de la fonction de hashage avec des
données arbitrairement grandes est indiscociable d'un flux de données
aléatoires). Par exemple, md5 et Sha-1
Bref, je vous propose de passer ces 12 chiffres en ascii dans un md5, de
ne garder que les 64 premiers bits (8 bytes) qui sont facilement
convertibles en entier dans la plupart des langages.
ensuite, vous appliquez un modulo 10^7. Comme 2^64 >> 10^7, vous
n'introduisez pas de biais dans la sortie.

En résumé, la formule serait (md5(code de 12 chiffres) & 2^64-1) mod 10^7

L'important n'étant pas vraiment la manière de recuperer les chiffres du
hash, mais d'utiliser la meme formule partout !
Je ne pense pas qu'il soit critique de cacher la formule et d'inclure un
HMAC (hash authentifié) vu que la clef de 12 chiffres a le meme niveau
de confidentialité que la clef de 6 chiffres.

Le risque d'avoir une collision dans les 10^7 premiers nombres, après
une génération par cet algo ci, est le meme que si les nombres sont
choisis au hasard. Je ne me souviens plus de la formule du birthday
paradox, mais il suffit de chercher un peu pour la trouver

bien proposé

En résumé, la formule serait (md5(code de 12 chiffres) & 2^64-1) mod 10^7

1er détail, 6 chiffre ca doit faire 10^6 possibilités

il faudrait ajouter la contrainte "pas de 3 au début".
on fait alors juste un modulo 9.10^5
et si >=3.10^5 on ajoute +10^5
ou alors pour les puristes
((hash(x) mod 9e5)+4e5)mod 1e6

sinon je suis ok

L'important n'étant pas vraiment la manière de recuperer les chiffres du
hash, mais d'utiliser la meme formule partout !
Je ne pense pas qu'il soit critique de cacher la formule et d'inclure un
HMAC (hash authentifié) vu que la clef de 12 chiffres a le meme niveau
de confidentialité que la clef de 6 chiffres.

le hash authentifié permettrait de vérifier qu'un tiers ne produit pas
un numéro au hazard... mais ici on a plutot un logique de "numéro de compte"


un problème c'est que ce n'est pas réversible. il faut donc garder une
table inverse, ou sinon tester toutes les possibilités jusqu'a ce que ca
marche.

une autre solution c'est la table de correspondance. c'est un peu au
hash ce que la one-time-pad est au chiffrement.

vu qu'on a besoin de toute facon d'une table de conversion inverse,
pourquoi ne pas l'utiliser pour la traduction, et puis finalement
générer des numéros au hazard ou même en séquence.

pour chaque numéro à 12 chiffres, tu affecte un numéro à 6 pas déjà
pris, au hazard ou en séquence.

Le risque d'avoir une collision dans les 10^7 premiers nombres, après
une génération par cet algo ci, est le meme que si les nombres sont
choisis au hasard. Je ne me souviens plus de la formule du birthday
paradox, mais il suffit de chercher un peu pour la trouver
je crois que c'est la racine carrée du nombre de possibilités.

ca ferait que dès qu'il y a plus de 950 "comptes" il y a probablement
une collision.

les colisions sont donc quasi certaines, a moins que tu n'ai que peu de
comptes.

bien proposé

En résumé, la formule serait (md5(code de 12 chiffres) & 2^64-1) mod 10^7

1er détail, 6 chiffre ca doit faire 10^6 possibilités

Oui bien vu, je me suis embrouillé

il faudrait ajouter la contrainte "pas de 3 au début".
Ah, j'avais pas vu cette contrainte là

le hash authentifié permettrait de vérifier qu'un tiers ne produit pas
un numéro au hazard... mais ici on a plutot un logique de "numéro de
compte"
En plus du fait que sur 6 chiffres c'est difficile de vérifier. Surtout

qu'un numéro au hasard sera forcément mauvais

un problème c'est que ce n'est pas réversible. il faut donc garder une
table inverse, ou sinon tester toutes les possibilités jusqu'a ce que ca
marche.

une autre solution c'est la table de correspondance. c'est un peu au
hash ce que la one-time-pad est au chiffrement.

vu qu'on a besoin de toute facon d'une table de conversion inverse,
pourquoi ne pas l'utiliser pour la traduction, et puis finalement
générer des numéros au hazard ou même en séquence.

Générer en séquence risque d'être problématique vu que ça sert de clef

d'identification secrète. Mais conserver une table et générer des
numéros au hasard est la seule solution pour empêcher une collision

pour chaque numéro à 12 chiffres, tu affecte un numéro à 6 pas déjà
pris, au hazard ou en séquence.

Le risque d'avoir une collision dans les 10^7 premiers nombres, après
une génération par cet algo ci, est le meme que si les nombres sont
choisis au hasard. Je ne me souviens plus de la formule du birthday
paradox, mais il suffit de chercher un peu pour la trouver
je crois que c'est la racine carrée du nombre de possibilités.

ca ferait que dès qu'il y a plus de 950 "comptes" il y a probablement
une collision.

Je viens de me rappeler la regle. La probabilité d'une collision est de

1/2 lorsqu'il y a sqrt(n) échantillons. Donc la proba qu'il existe une
collision si il y a 1000 utilisateurs est de 1/2. Totalement
inacceptable en effet.

les colisions sont donc quasi certaines, a moins que tu n'ai que peu de
comptes.

Al

Aris a écrit

bien proposé

En résumé, la formule serait (md5(code de 12 chiffres) & 2^64-1) mod 10^7

1er détail, 6 chiffre ca doit faire 10^6 possibilités

il faudrait ajouter la contrainte "pas de 3 au début".
on fait alors juste un modulo 9.10^5
et si >=3.10^5 on ajoute +10^5
ou alors pour les puristes
((hash(x) mod 9e5)+4e5)mod 1e6

L'important n'étant pas vraiment la manière de recuperer les chiffres du
hash, mais d'utiliser la meme formule partout !
Je ne pense pas qu'il soit critique de cacher la formule et d'inclure un
HMAC (hash authentifié) vu que la clef de 12 chiffres a le meme niveau de
confidentialité que la clef de 6 chiffres.

le hash authentifié permettrait de vérifier qu'un tiers ne produit pas un
numéro au hazard... mais ici on a plutot un logique de "numéro de compte"

En effet. Les transmissions sont protégées par ailleurs,
et l'émetteur est authentifié. On a juste le problème
pratico-pratique de "transmettre 12 sur 6" avec le
minimum de dégats.

un problème c'est que ce n'est pas réversible. il faut donc garder une
table inverse, ou sinon tester toutes les possibilités jusqu'a ce que ca
marche.
une autre solution c'est la table de correspondance. c'est un peu au hash
ce que la one-time-pad est au chiffrement.
vu qu'on a besoin de toute facon d'une table de conversion inverse,
pourquoi ne pas l'utiliser pour la traduction, et puis finalement générer
des numéros au hazard ou même en séquence.
pour chaque numéro à 12 chiffres, tu affecte un numéro à 6 pas déjà pris,
au hazard ou en séquence.

En effet, et on l'envisage aussi.
D'ailleurs, l'identifiant à 6 chiffres est produit comme
ça depuis toujours : un organisme officiel attribue
des numéros en séquence au fil de l'eau et les publie.

Mais voilà, l'organisme officiel va cesser
de le faire, et le système va passer sur des
identifiants à 12 positions construits autrement.

Théoriquement rien n'empêcherait de prendre
la relève et de continuer d'en attribuer.

Mais c'est difficile... prenons une comparaison :
Au moment où la Banque de France a arrêté
d'imprimer des billets de 500 Fr et est
passée à l'euro, c'était un peu délicat pour un
imprimeur de dire : "bon, je prend la relève pour
un an le temps que tout le monde s'adapte,
et j'imprime des billets de 500 Fr".

Même si techniquement rien ne l'empêchait ;-)

Ce n'est pas à ce point là, mais le principe
est le même.

Le risque d'avoir une collision dans les 10^7 premiers nombres, après une
génération par cet algo ci, est le meme que si les nombres sont choisis
au hasard. Je ne me souviens plus de la formule du birthday paradox, mais
il suffit de chercher un peu pour la trouver

je crois que c'est la racine carrée du nombre de possibilités.
ca ferait que dès qu'il y a plus de 950 "comptes" il y a probablement une
collision.

les colisions sont donc quasi certaines, a moins que tu n'ai que
peu de comptes.

Une collision pour 950 "comptes" serait probablement
acceptable. Je vérifie les probas...


Phil l'ancien-

Aris

Al

Générer en séquence risque d'être problématique vu que ça sert de clef
d'identification secrète. Mais conserver une table et générer des numéros
au hasard est la seule solution pour empêcher une collision

Ca ne sert pas d'identification secrète, c'est un identifiant
de produit.

Si il y a une collision, ça provoquera une erreur
et une régularisation par papier, téléphonique, etc.

Disons que la série 100.000.000.000 - 100.000.000.100
est constituée de voitures bleues qui coutent exactement 15.321 euros.

Un concessionnaire devrait passer commande en transmettant
à l'usine :
"Faites moi une voiture numéro bleue 100.000.000.105
pour 15.321 euros"

L'ennui c'est que le concessionnaire fonctionne avec notre
solution transitoire. Il prend le numéro qu'il souhaite
et applique l'algo, qui donne : 123456.

Il transmet :
"Faites moi une voiture bleue numéro 123456 pour 15.321 euros"

Manque de chance, c'est en collision avec un autre
numéro déjà utilisé pour une voiture rouge à 14.123 euros.
L'usine s'en rend compte parce que le prix et la couleur ne
sont pas bons, et ça se termine par quelques coups de fil,
où le concessionnaire indique le numéro réel sur 12 chiffres.
Embêtant mais pas mortel, si ça n'arrive pas trop
souvent.
(vous allez me dire : oui, mais si par hasard la couleur et
le prix sont les mêmes ? L'usine n'y verra que du feu.
Oui, mais justement, si la couleur et le prix sont les mêmes,
c'est pas très grave de se tromper, du moment que c'est
rare... et ce sera rare : il faudrait une triple collision).

pour chaque numéro à 12 chiffres, tu affecte un numéro à 6 pas déjà pris,
au hazard ou en séquence.

Le risque d'avoir une collision dans les 10^7 premiers nombres, après
une génération par cet algo ci, est le meme que si les nombres sont
choisis au hasard. Je ne me souviens plus de la formule du birthday
paradox, mais il suffit de chercher un peu pour la trouver
je crois que c'est la racine carrée du nombre de possibilités.

ca ferait que dès qu'il y a plus de 950 "comptes" il y a probablement une
collision.

Je viens de me rappeler la regle. La probabilité d'une collision est de
1/2 lorsqu'il y a sqrt(n) échantillons. Donc la proba qu'il existe une
collision si il y a 1000 utilisateurs est de 1/2. Totalement inacceptable
en effet.

Non, c'est probablement acceptable dans le fonctionnement
en question. 0,1% de rejets c'est dans la marge tolérable.

sqrt(n), c'est une approximation ?
En appliquant itérativement ma récurrence
Pn = Pn-1 x (N -n +1)/N je trouve 1117 au lieu de 950

les colisions sont donc quasi certaines, a moins
que tu n'ai que peu de comptes.

(ce sont des produits, pas des comptes)

Oui, à première vue on aura 50% de chances d'avoir une
collision au bout de 6 mois de fonctionnement.
C'est probablement acceptable...
(si la "Banque de France" ne met pas son véto !)


Phil l'ancien-

Phil l'ancien

Aris

Al

Générer en séquence risque d'être problématique vu que ça sert de clef
d'identification secrète. Mais conserver une table et générer des numéros
au hasard est la seule solution pour empêcher une collision

Ca ne sert pas d'identification secrète, c'est un identifiant
de produit.

Si il y a une collision, ça provoquera une erreur
et une régularisation par papier, téléphonique, etc.

Disons que la série 100.000.000.000 - 100.000.000.100
est constituée de voitures bleues qui coutent exactement 15.321 euros.
...

J'ai mouliné quelques simulations pour voir si on ne
se trompait pas trop.
Pas assez de tirages pour que ce soit très précis,
mais les résultats sont cohérents avec ce qu'on a dit :

Nb produits / Nb Moy de produits en collision
2000 / 1
4000 / 9
8000 / 37
10000 / 62

Phil l'ancien-

bonjour

une question bête

pourquoi ne pas adopter une compatibilité ascendante
en gros

si je reçois 6 chiffres
j'effectue une recherche pour caractériser la commande
et à partir de la définition je génère les 12 chiffres
que j'envoie dans les tuyaux à 12 chiffres

si je reçois 12 chiffres je ne fais rien

le problème c'est quand je veux commander un nouveau produit
qui n'a pas de code en 6 chiffres ou que les 6 chiffres ne permettent
pas de caractériser un produit unique cela implique un repli vers le
téléphone en gros


remy

remy

Phil l'ancien

une question bête
pourquoi ne pas adopter une compatibilité ascendante
en gros

si je reçois 6 chiffres
j'effectue une recherche pour caractériser la commande
et à partir de la définition je génère les 12 chiffres
que j'envoie dans les tuyaux à 12 chiffres

Ce n'est pas bête, et d'ailleurs c'est exactement ce
que prévoient les organismes concernés pour
la période de transition prévue où les deux codages
coexisteront : jusqu'à que leur
SI ait évolué, quand ils "recevront du 12", ils
transposeront en 6, puis traitement par le
"backoffice".

Ensuite, lorsque leur SI aura évolué, ils feront
l'inverse : lorsqu'ils "recevront du 6",
ils transposeront en 12, puis traitement par
le backoffice.

A la fin de la période de transition, si tout
va bien tout le monde sera "passé en 12"
et on pourra "oublier le 6".

si je reçois 12 chiffres je ne fais rien

le problème c'est quand je veux commander un nouveau produit
qui n'a pas de code en 6 chiffres ou que les 6 chiffres ne permettent
pas de caractériser un produit unique cela implique un repli vers le
téléphone en gros

En effet, exactement.


Phil l'ancien-

Phil l'ancien dans son message 479650f0$0$877$ba4acef3@news.orange.fr,
nous a fait l'honneur d'écrire:

Autrement dit : on veut produire l'équivalent d'un hash-code
sur 6 chiffres d'une information sur 12 chiffres,
avec le moins de collisions possibles.
Pour des raisons d'équité, il faut que les collisions
soient bien réparties (et non pas concentrées sur
certains intervalles de la valeur sur 12).
Mmouais... question: est il possible d'évaluer l'histogramme de cette

répartition?
Je me rappelle d'un algoritme de tri que j'avais fait il y a 25 ans, qui
utilisait le "tri postal" (mise en place directe à une adresse dépendant
de la valeur à trier) et nécessitait un gistogramme bien réguluer pour
avoir le moins de collisions possibles. L'histogramme ressemblait à une
courbe du 3ème degré, et le cumul ressemblait donc à son intégrale, soit
du 4ème degré. J'avais donc régularisé mon histogramme en donnant pour
l'adresse une fonction du 4ème degré de la valeur.
Mais ici, l'irrégularité de l'histogramme était assez simple, et facile
à modéliser

--
Oncle Dom
_________
http://pagesperso-orange.fr/oncle.dom/