Un hachage simple, répétable d'un UInt32 à un UInt16

Question

J'ai un petit problème où il faut faire un hachage d'un nombre d'environ 10 chiffres en un nombre de 6 chiffres. Le hachage doit être déterministe.

Il est plus important que le hachage ne nécessite pas beaucoup de ressources.

Par exemple, dire que j'ai un certain nombre, x, comme 123456789

Je veux écrire une fonction de hachage qui me donne un certain nombre, y, dos comme 987654.

alors comme je l'avais pour avoir une fonction qui prend les paramètres x et y, réapplique le hachage sur x et vérifie que le résultat est y.

Il devrait être difficile de calculer les valeurs d'entrée possibles étant donné le hachage. Ma première idée de multiplier les paires de chiffres a conduit à beaucoup de valeurs hachées en double. J'ai le sentiment que ce genre de problème a une sorte de solution élégante, mais je ne peux pas y penser moi-même.

Quelqu'un peut-il m'aider ici? Merci d'avance :)

Answer 1

Qu'est-ce que vous voulez faire est d'essayer de répartir les valeurs de hachage aussi régulièrement que possible sur la gamme. Une partie des méthodes intégrées de hachage sont assez bon pour cela, alors vous pourriez peut-être essayer quelque chose comme obtenir le code de hachage de la représentation de la chaîne, et tout simplement jeter la moitié des bits:

ushort code = (ushort)value.ToString().GetHashCode(); 

Cependant, cela dépend aussi sur ce que vous allez utiliser le code de hachage. Les codes de hachage intégrés ne sont pas destinés à être stockés de manière permanente. Les algorithmes de calcul des codes de hachage peuvent changer avec n'importe quelle nouvelle version du framework, donc si vous stockez les codes de hachage dans la base de données, ils peuvent devenir inutiles à l'avenir. Dans ce cas, vous devrez créer vous-même l'algorithme de hachage ou utiliser un algorithme de hachage conçu pour le stockage permanent.

Un algorithme simple qui est utilisé pour les codes de hachage pour certaines valeurs dans le cadre est à l'usage exclusif ou de faire tous les bits de la valeur la matière lorsque le code de hachage est plus petit que les données:

byte[] b = BitConverter.GetBytes(value); 
ushort code = (ushort)(BitConverter.ToUInt16(b, 0)^BitConverter.ToUInt16(b, 2)); 

ou plus efficace, mais de manière moins évidente à faire la même chose:

ushort code = (ushort)((value >> 16)^value); 

Bien sûr, n'a pas de propriétés obscurcissent pour les petites valeurs, de sorte que vous voudrez peut-être jeter quelques morceaux « au hasard » pour rendre le code de hachage significativement différent de la valeur:

ushort code = (ushort)(0x56D4^(value >> 16)^value); 

Answer 2

Pourquoi ne pas jeter les 16 bits inférieurs ou les 4 derniers chiffres?

1234567890 --> 123456 

facilement fait en faisant juste une division entière par 10000.

Answer 3

Qu'est-ce que vous avez besoin est appelé "hashing".

Essayez CRC16.

Answer 4

((X >> 16)^(X)) & 0xFFFF

.......

Answer 5

Votre problème tel qu'indiqué n'est pas résoluble. Vous dites que vous voulez que le système soit "quelque peu difficile à casser", par quoi je suppose que vous voulez dire qu'il est "quelque peu difficile" pour un attaquant de prendre un résumé connu et d'en produire une entrée possible au condensé donné. Comme il n'y a que 4 milliards d'entrées possibles et seulement 65536 hachages possibles dans le système que vous proposez, il est totalement trivial de trouver un message qui correspond à un hachage donné, quel que soit l'algorithme de hachage. En moyenne, l'attaquant aura environ 65000 messages possibles à choisir, et peut donc choisir le message qui sert le mieux son schéma infâme.

je me attends à un problème « un peu difficile » dans l'espace révolutionnaire hachage pour exiger, dédier, disons, quelques millions de dollars de temps de super-ordinateur à briser. Votre proposition peut être brisée par des lycéens inexpérimentés écrivant des programmes Javascript qui prennent quelques minutes à écrire et peut-être une minute à courir, tops; ce n'est même pas vaguement proche de "quelque peu dur".

Pourquoi choisissez-vous ces limites minuscules sur votre algorithme, les limites qui, de par leur nature même, rendent trivial de briser le hachage? Et d'ailleurs, quelle est la valeur de hachage d'une si petite quantité de données qu'un entier de 32 bits?