Algorithme bijectif symétrique pour les entiers

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

Disons que j'ai un nombre de 4 bits. Il y a 16 valeurs distinctes. Regardez-le comme s'il s'agissait d'un cube à quatre dimensions: cube à 4 dimensions http://www.ams.org/featurecolumn/images/january2009/klee8.jpg .

Chaque sommet représente un de ces nombres, chaque bit représente une dimension. Donc, son xyzw de base, où chacune des dimensions peut avoir seulement valeurs 0 ou 1. Imaginez maintenant que vous utilisez un ordre différent {[8] } de dimensions. Par exemple XZYW. Chacun des sommets a maintenant changé de numéro!

Vous pouvez le faire pour n'importe quel nombre de dimensions, il suffit de permuter ces dimensions. Si la sécurité n'est pas votre préoccupation cela pourrait être une belle solution rapide pour vous. D'un autre côté, Je ne sais pas si la sortie sera assez "obscure" pour vos besoins et certainement après une grande quantité de mappage fait, le mappage peut être inversé (ce qui peut être un avantage ou un inconvénient, selon vos besoins.)

L'article suivant vous donne 4 ou 5 exemples de mappage, vous donnant des fonctions plutôt que de construire des ensembles mappés: www.cs.auckland.ac.nz/ ~ john-rugis / pdf / BijectiveMapping. pdf

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

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

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

Ensuite, vous pouvez utiliser un mappage de la forme

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

Et si p est bien un premier, ce sera une bijection pour tout a!= 0 et tout b. il semblera assez aléatoire pour les plus grands a et B.

Par exemple, dans mon cas pour lequel je suis tombé sur cette question, j'ai utilisé 1073741789 comme premier pour la gamme de nombres inférieurs à 1

Mon encodage est alors

((n + 173741789) * 507371178) % 1073741789

Et le décodage est

(n * 233233408 + 1073741789 - 173741789) % 1073741789

Notez que 507371178 * 233233408% 1073741789 = = 1, donc ces deux nombres sont inverses le champ des nombres modulo 1073741789 (vous pouvez trouver des nombres inverses dans de tels champs avec l'algorithme euclidien étendu).

J'ai choisi a et b assez arbitrairement, je me suis simplement assuré ils sont à peu près la moitié de la taille de P.

Pouvez-vous utiliser une table de recherche générée aléatoirement? Tant que les nombres aléatoires dans la table sont uniques, vous obtenez un mappage bijectif. Il n'est pas symétrique, si.

Une table de recherche de 16 Go pour toutes les valeurs 32 bits n'est probablement pas pratique, mais vous pouvez utiliser deux tables de recherche 16 bits distinctes pour le mot haut et le mot bas.

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

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

Choisissez le premier élément, attribuez - lui un mappage aléatoire. Pour rendre le mappage symétrique, affectez également l'inverse:

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

Choisissez le numéro suivant, attribuez à nouveau un mappage aléatoire, mais choisissez un numéro qui n'a pas encore été attribué. (c.-à-d. dans ce cas, ne choisissez pas 1 ou 3). Répétez jusqu'à ce que la LUT soit terminée. Cela devrait générer un mappage symétrique bijectif aléatoire.

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

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

Devrait être assez obscur !!

Edit: ce n'est pas une bijection pour 0 entier de fin

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

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

Et donc

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

W00t ça marche !

Edit 2: pour plus d'obscurcissement, vous pouvez ajouter un nombre arbitraire, et soustraire à la fin.

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

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 nombre, et être encore capable de le déchiffrer.

Le chiffre va comme ceci: Traiter le nombre d'entrée dans un tableau de bits I[0..31], et la sortie comme O[0..31]. Préparer un tableau K[0..63] de 64 nombres générés aléatoirement. Ce sera votre clé. Prenez le bit de nombre d'entrée à partir de la position déterminée par le premier nombre aléatoire (I[K[0] mod 32]) et placez-le à le début de votre résultat (O[0]). Maintenant, pour décider quel bit placer à O[1], utilisez le bit précédemment utilisé. Si c'est 0, utilisez K [1] pour générer la position dans I à partir de laquelle prendre, c'est 1, utilisez K [2] (ce qui signifie simplement ignorer un nombre aléatoire).

Maintenant, cela ne fonctionnera pas bien, car vous pouvez prendre le même bit deux fois. Pour l'éviter, renuméroter les bits après chaque itération, en omettant les bits utilisés. Pour générer la position à partir de laquelle prendre O[1], utilisez I[K[p] mod 31], où p vaut 1 ou 2, en fonction du bit O[0], car il reste 31 bits, numérotés de 0 à 30.

Pour illustrer cela, je vais 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, donc nous allons prendre bit dont la position est 1 (en comptant à partir de 0)

I: 0_11    O: 1___
     _

Nous venons de prendre un peu de valeur 1, donc nous sautons un nombre aléatoire et utilisons 28. Il reste 3 bits, donc pour compter la position nous prenons 28 mod 3 = 1. Nous prenons le premier (à partir de 0) des bits restants:

I: 0__1    O: 11__
   _

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

I: ___1    O: 110_
      _

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

I: ____    O: 1101

Et ça y est.

Déchiffrer un tel nombre est facile, il suffit de faire les mêmes choses. La position à laquelle placer le premier bit du code est connue à partir de la clé, les positions suivantes sont déterminées par le précédemment inséré bit.

Cela a évidemment tous les inconvénients de tout ce qui déplace simplement les bits (par exemple 0 devient 0, et MAXINT devient MAXINT), mais il semble plus difficile de trouver comment quelqu'un a crypté le nombre sans connaître la clé, qui doit être secrète.

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

Voici une implémentation C # simple qui déplace les valeurs en fonction d'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 décalage dans la sortie lorsque l'entrée est légèrement changé. Cependant, vous pouvez utiliser une autre opération bijective au lieu d'addition pour y parvenir.

Dessiner un grand cercle sur une grande feuille de papier. Écrivez tous les entiers de 0 à MAXINT dans le sens horaire à partir du haut du cercle, également espacés. Ecrire tous les entiers de 0 à MININT dans le sens antihoraire, également espacés à nouveau. Observez que MININT est à côté de MAXINT au bas du cercle. Maintenant, faites un double de cette figure des deux côtés d'un morceau de carte rigide. Épinglez la carte rigide au cercle à travers les centres des deux. Choisissez un angle de rotation, n'importe quel angle que vous aimez. Maintenant, vous avez une cartographie 1-1 qui répond à certaines de vos exigences, mais n'est probablement pas assez obscure. Détachez la carte, retournez-la autour d'un diamètre, n'importe quel diamètre. Répétez ces étapes (dans n'importe quel ordre) jusqu'à ce que vous ayez une bijection qui vous satisfait.

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

Pour plus de précision suite au commentaire: si vous ne faites que tourner la carte contre le papier, la méthode est aussi simple que vous vous plaignez. Cependant, lorsque vous retournez la carte sur le mappage n'est pas équivalent à (x+m) mod MAXINT pour tout m. Par exemple, si vous laissez la carte non tournée et la retournez autour du diamètre à travers 0 (qui est en haut de la face d'horloge), alors 1 est mappé à -1, 2 à -2, et ainsi de suite. (x+m) mod MAXINT correspond uniquement aux rotations de la carte.

Divisez le nombre en deux (16 bits les plus significatifs et 16 bits les moins significatifs) et considérez les bits dans les deux résultats de 16 bits comme des cartes en deux ponts. Mélanger les ponts forçant l'un dans l'autre.

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

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

Vous pouvez mapper manuellement 0 -> maxvalue et maxvalue -> 0 à éviter leur cartographie sur eux-mêmes.