Fonction de hachage réversible?
J'ai besoin d'une fonction de hachage réversible (évidemment l'entrée sera beaucoup plus petite que la sortie) qui mappe l'entrée à la sortie d'une manière aléatoire. Fondamentalement, je veux un moyen de transformer un nombre comme " 123 " en un nombre plus grand comme "9874362483910978" , mais pas d'une manière qui préservera les comparaisons, donc il ne doit pas toujours être vrai que, si x1 > x2, f (x1) > f (x2) (mais il ne doit pas non plus être toujours faux).
Le cas d'utilisation pour cela est que je dois trouver un moyen de transformer de petits nombres en plus grands, aléatoires. Ils n'ont pas vraiment besoin d'être aléatoires (en fait, ils doivent être déterministes, donc la même entrée correspond toujours à la même sortie), mais ils doivent regarder aléatoire (au moins quand base64encoded en chaînes, donc le décalage par Z bits ne fonctionnera pas car des nombres similaires auront des MSBs similaires).
Aussi, facile (rapide) calcul et inversion est un plus, mais pas nécessaire.
Je ne sais pas si je suis clair, ou si un tel algorithme existe, mais j'apprécierais toute aide!
5 réponses
Aucune des réponses fournies ne semblait particulièrement utile, compte tenu de la question. J'ai eu le même problème, ayant besoin d'un hachage simple et réversible pour des raisons de sécurité, et j'ai décidé d'aller avec la relocalisation des bits. C'est simple, c'est rapide, et il ne faut pas savoir quoi que ce soit sur les mathématiques booléennes ou les algorithmes cryptographiques ou tout ce qui nécessite une réflexion réelle.
, Le plus simple serait probablement de simplement déplacer la moitié des bits à gauche, et l'autre moitié droite:
def hash(n):
return ((0x0000FFFF & n)<<16) + ((0xFFFF0000 & n)>>16)
Ceci est réversible, dans ce hachage(hash(n)) = n, et a la non-séquentielle des paires {n,m}, n
Pour obtenir une implémentation moins séquentielle, vous pouvez également envisager une réorganisation entrelacée à partir de [msb,z,...une,lsb] à [msb,lsb,z,a,...] ou [lsb,msb,a,z,...] ou tout autre déplacement que vous pensez donne une séquence non séquentielle appropriée pour les numéros que vous traitez.
(la fonction ci-dessus est sans danger pour les nombres qui correspondent à 32 bits, les plus grands nombres sont garantis pour provoquer collisions et aurait besoin d'une couverture de masque de bits plus pour éviter les problèmes. Cela dit, 32 bits est généralement suffisant pour tout uid non-sécurité).
Jetez également un oeil à la réponse multiplicative inverse donnée par Andy Hayden, ci-dessous.
Ce que vous demandez est chiffrement. Un chiffrement de bloc dans son mode de fonctionnement de base, ECB, mappe de manière réversible un bloc d'entrée sur un bloc de sortie de la même taille. Les blocs d'entrée et de sortie peuvent être interprétés comme des nombres.
Par exemple, AES est un chiffrement par bloc de 128 bits, donc il mappe un nombre de 128 bits d'entrée sur un nombre de 128 bits de sortie. Si 128 bits est assez bon pour vos besoins, alors vous pouvez simplement pad votre numéro d'entrée à 128 bits, transformer ce seul bloc avec AES, puis formater la sortie comme un nombre de 128 bits.
Si 128 bits est trop grand, vous pouvez utiliser un chiffrement par bloc de 64 bits, comme 3DES, IDEA ou Blowfish.
Le mode ECB est considéré comme faible, mais sa faiblesse est la contrainte que vous avez postulée comme une exigence (à savoir que le mappage soit "déterministe"). C'est une faiblesse, car une fois qu'un attaquant a observé que 123 correspond à 9874362483910978, à partir de là, chaque fois qu'elle voit ce dernier numéro, elle sait que le texte en clair était 123. Un attaquant peut effectuer une analyse de fréquence et/ou construire un dictionnaire de paires de texte clair / texte chiffré connues.
Une autre solution simple consiste à utiliser des inverses multiplicatifs (voir le blog D'Eri Clippert):
Nous avons montré comment vous pouvez prendre deux entiers positifs coprimes x et m et calculer un troisième entier positif y avec la propriété que (x * y) % m == 1, et donc que (x * z * y) % M = = z % M pour tout entier positif z. autrement dit, il existe toujours un "inverse multiplicatif", qui "défait" les résultats de la multiplication par X modulo m.
, Nous prenons un grand nombre par exemple 4000000000 et un grand nombre Co-premier par exemple 387420489:
def rhash(n):
return n * 387420489 % 4000000000
>>> rhash(12)
649045868
, Nous avons d'abord calculer l'inverse multiplicatif avec modinv qui s'avère être 3513180409:
>>> 3513180409 * 387420489 % 4000000000
1
Maintenant, nous pouvons définir l'inverse:
def un_rhash(h):
return h * 3513180409 % 4000000000
>>> un_rhash(649045868) # un_rhash(rhash(12))
12
Note: Cette réponse est rapide à calculer et fonctionne pour les nombres jusqu'à 4000000000, si vous avez besoin de gérer des nombres plus grands, choisissez un nombre suffisamment grand (et un autre Co-premier).
, Vous pouvez le faire avec hexadécimal (pour emballez l'int):
def rhash(n):
return "%08x" % (n * 387420489 % 4000000000)
>>> rhash(12)
'26afa76c'
def un_rhash(h):
return int(h, 16) * 3513180409 % 4000000000
>>> un_rhash('26afa76c') # un_rhash(rhash(12))
12
Si vous choisissez un co-premier relativement grand, cela semblera aléatoire, ne sera pas séquentiel et sera également rapide à calculer.
Fondamentalement, vous recherchez un cryptage à 2 voies, et qui utilise probablement un salt.
Vous avez un certain nombre de choix:
- TripleDES
- AES
Voici un exemple: "simple "obfuscation bidirectionnelle non sécurisée" pour C #
Quelle langue regardez-vous? Si. net alors regardez l'espace de noms de cryptage pour quelques idées.
Pourquoi ne pas simplement XOR avec un bon nombre long?
Facile. Rapide. Réversible.
Ou, si cela n'a pas besoin d'être terriblement sécurisé, vous pouvez convertir de la base 10 en une base plus petite (comme la base 8 ou la base 4, selon la durée que vous voulez que les nombres soient).