Symétrique bijective algorithme pour Entiers

Question

je besoin d'un algorithme qui peut faire une à une cartographie (ie. Pas de collision) d'un entier signé 32 bits sur un autre entier signé 32 bits.

Ce qui me préoccupe est suffisamment d'entropie pour que la sortie de la fonction semble être aléatoire. Fondamentalement, je suis à la recherche d'un chiffre similaire à XOR Cipher mais qui peuvent générer des résultats plus arbitraires prospectifs. La sécurité est pas mon vrai problème, bien que l'obscurité est.

Modifier à des fins de clarification:

1. L'algorithme doit être symetric, afin que je puisse inverser l'opération sans keypair.
2. L'algorithme doit être bijective, chaque numéro d'entrée 32 bits doit générer un nombre de 32 bits unique.
3. La sortie de la fonction doit être assez obscure, en ajoutant une seule à l'entrée devrait se traduire par grand effet sur la sortie.

Exemple Résultat attendu:

F (100) = 98456
F (101) = -758
F (102) = 10875498
F (103) = 986541
F (104) = 945451245
F (105) = -488554

Tout comme MD5, changer une chose peut changer beaucoup de choses.

Je cherche une fonction mathmetical, donc des entiers manuellement cartographie est pas une solution pour moi. Pour ceux qui demandent, la vitesse de l'algorithme n'est pas très important.

Answer 1

Utilisez tout chiffrement par blocs de 32 bits! Par définition, un chiffrement par bloc cartes toutes les valeurs d'entrée possible dans sa gamme d'une valeur de sortie unique de façon réversible, et par sa conception, il est difficile de déterminer une valeur donnée à la carte sans la clé. Il suffit de choisir une clé, garder le secret si la sécurité ou l'obscurité est importante, et utiliser le chiffrement comme votre transformation.

Pour une extension de cette idée à des plages non-puissance de 2, voir mon post sur permutations sécurisés avec ciphers Bloquer .

Répondre à vos préoccupations spécifiques:

1. L'algorithme est en effet symétrique. Je ne sais pas ce que vous entendez par « l'opération inverse sans une paire de clés ». Si vous ne souhaitez pas utiliser une clé, un hardcode aléatoire et une partie de considérer l'algorithme.
2. Eh oui -., Par définition, un chiffrement par bloc est bijective
3. Eh oui. Il ne serait pas un bon chiffre si cela ne le cas.

Answer 2

Je vais essayer d'expliquer ma solution à ce sur un exemple beaucoup plus simple, qui peut ensuite être facilement étendu pour votre grand.

Dire que j'ai un numéro à 4 bits. Il y a 16 valeurs distinctes. Regardez comme si elle était un cube à quatre dimensions:
_{(source: ams.org )}
.

Chaque sommet représente l'un de ces numéros, chaque bit représente une dimension. Ainsi, son XYZW basiquement, où chacune des dimensions peut avoir des valeurs que 0 ou 1. Maintenant, imaginez que vous utilisez un autre pour de dimensions. Par exemple XZYW. Chacun des sommets maintenant changé son numéro!

Vous pouvez le faire pour un certain nombre de dimensions, juste permute ces dimensions. Si la sécurité ne vous concerne pas cela pourrait être une belle solution rapide pour vous. D'autre part, je ne sais pas si la sortie sera « obscurcir » assez pour vos besoins et certainement après une grande quantité de cartographie fait, la mise en correspondance peut être inversée (qui peut être un avantage ou un inconvénient, en fonction de vos besoins.)

Answer 3

Le présent document vous donne 4 ou 5 exemples de cartographie, en vous donnant des fonctions plutôt que de construire des ensembles cartographiés: www.cs.auckland.ac.nz/~john-rugis/pdf/BijectiveMapping.pdf

Answer 4

En plus de générer des tables de consultation aléatoires, vous pouvez utiliser une combinaison de fonctions:

• XOR
• symétrique permutation de bits (par exemple décalage de 16 bits, ou bascule 0-31 à 31-0 ou retourner 0-3 à 3-0, 4-7 à 7-4, ...)
• plus?

Answer 5

Si votre objectif est simplement d'obtenir une permutation apparemment aléatoire des nombres d'une à peu près taille définie, alors il est une autre façon possible:. Réduire l'ensemble des nombres à un nombre premier

Ensuite, vous pouvez utiliser une cartographie de la forme

f (i) = (i * a + b)% p

et si p est en effet un premier choix, ce sera une bijection pour tous un! = 0 et tout b. Il se penchera assez aléatoire pour agrandir l'a et b.

Par exemple, dans mon cas pour lequel je suis tombé sur cette question, j'ai utilisé 1.073.741.789 comme choix pour la gamme des nombres inférieurs à 1 << 30. Cela me fait perdre seulement 35 chiffres, ce qui est bien dans mon cas.

Mon encodage est alors

((n + 173741789) * 507371178) % 1073741789

et le décodage est

(n * 233233408 + 1073741789 - 173741789) % 1073741789

Notez que 507371178 * 233233408% 1073741789 == 1, de sorte que ces deux nombres sont inverses le champ des nombres modulo 1073741789 (vous pouvez comprendre inverse des nombres dans ces domaines avec l'algorithme d'Euclide étendu).

J'ai choisi et b assez arbitraire, je simplement assuré qu'ils sont à peu près la moitié de la taille de p.

Answer 6

Pouvez-vous utiliser une recherche sur les tables de hasard? Tant que les nombres aléatoires dans la table sont uniques, vous obtenez une bijection. Ce n'est pas symétrique, cependant.

Un 16 Go recherche-table pour toutes les valeurs 32 bits est probablement pas pratique, mais vous pouvez utiliser deux tables de consultation séparées 16 bits pour le haut-mot et le mot faible.

PS: Je pense que vous pouvez générer une table de recherche bijective symétrique, si c'est important. L'algorithme commencerait par une LUT vide:

+----+        +----+
|  1 |   ->   |    |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |    |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

Pick le premier élément, lui attribuer un mappage aléatoire. Pour rendre le symétrique de mappage, attribuez l'inverse aussi:

+----+        +----+
|  1 |   ->   |  3 |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |  1 |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

Choisissez le numéro suivant, à nouveau attribuer un mappage aléatoire, mais choisir un nombre qui n'est pas encore été attribué. (À savoir, dans ce cas, ne pas choisir 1 ou 3). Répétez jusqu'à ce que la LUT est terminée. Cela devrait générer une application bijective symétrique aléatoire.

Answer 7

Prenez un nombre, multiplie par 9, chiffres inverses, diviser par 9.

123  <> 1107 <> 7011 <> 779
256  <> 2304 <> 4032 <> 448
1028 <> 9252 <> 2529 <> 281

doit être assez obscure !!

Edit: il est une bijection de 0 se terminant entier

900 <> 8100 <> 18 <> 2
2   <> 18   <> 81 <> 9

Vous pouvez toujours ajouter une règle spécifique comme: Prendre un certain nombre, diviser par 10 x fois, multiplie par 9, chiffres inverses, diviser par 9, multipliée par 10 ^ x.

Et

900 <> 9 <> 81 <> 18 <> 2 <> 200
200 <> 2 <> 18 <> 81 <> 9 <> 900

W00t ça marche!

Edit 2:. Pour plus d'obscurness, vous pouvez ajouter un nombre arbitraire, et à la fin substract

900 < +256 > 1156 < *9 > 10404 < invert > 40401 < /9 > 4489 < -256 > 4233
123 < +256 > 379 < *9 > 3411 < invert > 1143 < /9 > 127 < -256 > -129

Answer 8

Voici mon idée simple: Vous pouvez déplacer les bits du nombre, comme PeterK proposé, mais vous pouvez avoir une autre permutation de bits pour chaque numéro, et être encore capable de le déchiffrer.

Le chiffre va comme ceci: Traiter le numéro d'entrée dans un tableau de bits I[0..31], et la sortie en tant O[0..31]. Préparer un K[0..63] de tableau de 64 numéros générés au hasard. Ce sera votre clé. Prenez le bit du numéro d'entrée de la position déterminée par le premier nombre aléatoire (I[K[0] mod 32]) et placez-le au début de votre résultat (O[0]). Maintenant, pour décider quel bit à lieu à O[1], utilisez le bit utilisé précédemment. Si elle est de 0, l'utilisation K [1] pour générer position à partir de laquelle I à prendre, il est 1, en utilisant K [2] (qui simplement des moyens sauter un nombre aléatoire).

Maintenant, cela ne fonctionne pas bien, que vous pouvez prendre le même bit deux fois. Pour éviter, numéroter les bits après chaque itération, en omettant les bits utilisés. Pour générer la position à partir de laquelle prend O[1] utilisation I[K[p] mod 31], où p est 1 ou 2, en fonction de la O[0] binaire, car il y a 31 bits restants, numérotés de 0 à 30.

Pour illustrer cela, je vais vous donner un exemple:

Nous avons un nombre de 4 bits et 8 nombres aléatoires:. 25, 5, 28, 19, 14, 20, 0, 18

I: 0111    O: ____
    _

25 mod 4 = 1, de sorte que nous prendrons bit dont la position est 1 (en partant de 0)

I: 0_11    O: 1___
     _

Nous avons juste pris un peu de valeur 1, donc nous sautons un nombre aléatoire et utiliser 28. Il y a 3 bits à gauche, donc compter position que nous prenons 28 mod 3 = 1. Nous prenons le premier (comptage de 0 ) des bits restants:

I: 0__1    O: 11__
   _

Encore une fois, nous sautons un numéro, et prendre 14 14. mod 2 = 0, donc nous prenons le bit 0e:

I: ___1    O: 110_
      _

Maintenant, il n'a pas d'importance, mais le bit précédent était de 0, donc nous prenons 20. 20 mod 1 = 0:

I: ____    O: 1101

Et ce qu'il est.

Décrypter numéro un est facile, il suffit de faire les mêmes choses. La position à laquelle placer le premier bit du code est connu de la clé, les positions suivantes sont déterminées par les bits insérés précédemment.

Ceci a évidemment tous les inconvénients de tout ce qui ne fait que déplacer les bits autour (par exemple 0 devient 0, et MAXINT devient MAXINT), mais il est semble plus difficile de trouver comment quelqu'un a chiffré le nombre sans connaître la clé, qui doit secret.

Answer 9

Si vous ne voulez pas utiliser des algorithmes de chiffrement appropriés (peut-être pour des raisons de performance et de la complexité), vous pouvez utiliser à la place un chiffrement plus simple comme le Vigenère chiffrement. Ce chiffre a été effectivement décrit comme le indéchiffrable chiffre (français pour 'le chiffrement incassable).

Voici une implémentation simple C # que les valeurs des quarts de travail basées sur une valeur de clé correspondante:

void Main()
{
  var clearText = Enumerable.Range(0, 10);
  var key = new[] { 10, 20, Int32.MaxValue };
  var cipherText = Encode(clearText, key);
  var clearText2 = Decode(cipherText, key);
}

IEnumerable<Int32> Encode(IEnumerable<Int32> clearText, IList<Int32> key) {
  return clearText.Select((i, n) => unchecked(i + key[n%key.Count]));
}

IEnumerable<Int32> Decode(IEnumerable<Int32> cipherText, IList<Int32> key) {
  return cipherText.Select((i, n) => unchecked(i - key[n%key.Count]));
}

Cet algorithme ne crée pas un grand changement dans la sortie lorsque l'entrée est légèrement modifiée. Cependant, vous pouvez utiliser une autre opération bijective au lieu de plus pour y parvenir.

Answer 10

Dessiner un grand cercle sur une grande feuille de papier. Écrire tous les nombres entiers de 0 à MAXINT dans le sens horaire à partir de la partie supérieure du cercle, espacées de manière égale. Écrire tous les nombres entiers de 0 à sens anti-horaire, également MININT encore espacées. Notez que MININT est à côté de MAXINT au bas du cercle. Maintenant, faire un double de ce chiffre sur les deux côtés d'un morceau de carte rigide. Pin la carte raide au cercle par les centres des deux. Choisissez un angle de rotation, ne importe quel angle vous le souhaitez. Maintenant, vous avez une correspondance 1-1 qui répond à certaines de vos exigences, mais probablement pas assez obscure. Détacher la carte, retournez autour d'un diamètre, tout diamètre. Répétez ces étapes (dans l'ordre) jusqu'à ce que vous avez une bijection vous êtes satisfait.

Si vous avez suivi de près, il ne devrait pas être difficile à programmer dans votre langue préférée.

Clarification suivant le commentaire: Si vous faites pivoter uniquement la carte sur le papier la méthode est aussi simple que vous vous plaignez. Cependant, lorsque vous retournez la carte sur la carte ne correspond pas à (x+m) mod MAXINT pour tout m. Par exemple, si on laisse la carte sans rotation et retourner autour du diamètre passant par 0 (ce qui est en haut de la face d'horloge), puis 1 est mappé à -1, de 2 à -2 et ainsi de suite. (x+m) mod MAXINT correspond à la rotation de la carte uniquement.

Answer 11

Diviser le nombre de deux (16 bits les plus significatifs et 16 bits les moins significatifs) et prendre en compte les bits dans les deux cartes que dans deux ponts résultats 16 bits. Mélanger les ponts forçant une dans l'autre.

Donc, si votre numéro initial est b31,b30,...,b1,b0 vous vous retrouvez avec b15,b31,b14,b30,...,b1,b17,b0,b16. Il est rapide et rapide à mettre en œuvre, comme l'inverse.

Si vous regardez la représentation décimale des résultats, la série semble assez obscure.

Vous pouvez mapper manuellement 0 -> maxvalue maxvalue -.> 0 pour éviter de les mapping sur eux-mêmes