Symmetrische Bijektive Algorithmus für die ganzen Zahlen

StackOverflow https://stackoverflow.com/questions/3131193

Frage

ich brauche einen Algorithmus, der eine Eins-zu-Eins-Abbildung tun kann (dh. Keine Kollision) eine 32-Bit-Ganzzahl mit Vorzeichen auf einem anderen 32-Bit-Ganzzahl mit Vorzeichen.

Meine große Sorge ist genug Entropie, so dass die Ausgabe der Funktion zufällig zu sein scheint. Im Grunde ist mir die Suche nach einem Chiffre ähnlich wie XOR Cipher aber das kann willkürliche gerichteten Ausgänge erzeugen. Sicherheit ist nicht meine wirkliche Sorge, obwohl Dunkelheit ist.

Bearbeiten zur Klärung Zweck:

  1. Der Algorithmus muss sein symetric, so dass ich den Betrieb ohne Keypair rückgängig machen kann.
  2. Der Algorithmus muss sein bijektiv, jede 32-Bit-Eingangsnummer muss erzeugt eine 32-Bit eindeutige Nummer.
  3. Die Ausgabe der Funktion muss dunkel genug sein, das Hinzufügen nur einer mit dem Eingang sollte großen Einfluss auf den Ausgang zur Folge haben.

Beispiel erwartetes Ergebnis:

F (100) = 98456
F (101) = -758
F (102) = 10875498
F (103) = 986.541
F (104) = 945451245
F (105) = -488.554

Genau wie MD5, eine Sache zu ändern können viele Dinge ändern.

Ich suche eine mathmetical Funktion, so manuell zuordnen ganzen Zahlen ist keine Lösung für mich. Für diejenigen, die fragen, ist Algorithmus Geschwindigkeit nicht sehr wichtig.

War es hilfreich?

Lösung

Verwenden Sie eine 32-Bit-Blockchiffre! Per Definition bildet eine Blockchiffre alle möglichen Eingabewert in seinem Bereich zu einem einzigartigen Ausgangswert, in einer reversiblen Art und Weise und durch Design, ist es schwierig zu bestimmen, was jeder gegebenen Wert abzubilden, ohne den Schlüssel. Sie einfach einen Schlüssel holen, es geheim halten, wenn die Sicherheit oder Unklarheit wichtig ist, und die Chiffre als Transformation verwenden.

Für eine Erweiterung dieser Idee nicht-Power-of-2 Bereiche finden Sie in meinem Beitrag auf Sichere Permutationen mit Blockchiffren .

Addressing Ihre spezifischen Anliegen:

  1. Der Algorithmus ist in der Tat symmetrisch. Ich bin nicht sicher, was Sie unter „Umkehren der Betrieb ohne Keypair“. Wenn Sie nicht über einen Schlüssel verwenden, codieren eine zufällig generierte ein und sehen es als Teil des Algorithmus werden soll.
  2. Yup -. Per definitionem eine Blockchiffre ist bijektiv
  3. Yup. Es wäre keine gute Chiffre sein, wenn das nicht der Fall wäre.

Andere Tipps

Ich werde versuchen, meine Lösung dieses Problem auf ein viel einfacheres Beispiel zu erklären, die dann leicht für große erweitert werden.

sagen, ich habe eine 4-Bit-Zahl. Es gibt 16 verschiedene Werte. Betrachten Sie es als ob es sich um eine vierdimensionale Würfel war:
(Quelle: ams.org )
.

Jeder Knoten stellt eine dieser Zahlen stellt jedes Bit eine Dimension. So seine basicaly XYZW, wo jeder der Dimensionen kann nur Werte 0 oder 1. Jetzt hat sie vorstellen, Sie verwenden eine andere Reihenfolge die Dimensionen. Zum Beispiel XZYW. Jeder der Scheitel nun änderte seine Nummer!

Sie können dies tun, für eine beliebige Anzahl von Dimensionen, nur diese Dimensionen permutieren. Wenn die Sicherheit nicht Ihre Sorge ist, könnte dies eine schöne schnelle Lösung für Sie sein. Auf der anderen Seite, ich weiß nicht, ob der Ausgang genug sein, um für Ihre Bedürfnisse und sicherlich nach einer großen Menge von Mapping-done „verschleiert“ wird, kann die Zuordnung rückgängig gemacht werden (was ein Vorteil oder Nachteil sein kann, je nach Bedarf.)

Das folgende Papier gibt Ihnen 4 oder 5 Mapping Beispiele, die Ihnen Funktionen nicht abgebildet Sets Aufbau: www.cs.auckland.ac.nz/~john-rugis/pdf/BijectiveMapping.pdf

Neben Erzeugung von Zufall Lookup-Tabellen können Sie eine Kombination von Funktionen zur Verfügung:

  • XOR
  • symmetrische Bitpermutation (zB Verschiebung 16 Bits oder Flip 0-31 zu 31-0, oder Flip 0-3 bis 3-0, 4-7 bis 7-4, ...)
  • mehr?

Wenn Ihr Ziel ist einfach eine scheinbar zufällige Permutation der Zahlen von a zu bekommen ungefähr definierte Größe, dann gibt es eine andere Art und Weise. Reduziert die Menge von Zahlen auf eine Primzahl

Dann können Sie eine Abbildung der Form

verwenden

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

und wenn p ist in der Tat eine Primzahl ist, wird dies eine Bijektion für alle sein,! = 0 und alle b. Es sieht ziemlich zufällig für größere a und b.

Zum Beispiel in meinem Fall für die ich auf diese Frage gestolpert, habe ich 1073741789 als Haupt für den Bereich von Zahlen, die kleiner als 1 << 30. Das macht mich verlieren nur 35 Zahlen, die fein in meinem Fall ist.

Meine Codierung ist dann 

((n + 173741789) * 507371178) % 1073741789

und die Decodierung ist 

(n * 233233408 + 1073741789 - 173741789) % 1073741789

Beachten Sie, dass 507371178 * 233233408% 1073741789 == 1, so dass diese beiden Zahlen inversen Bereich der Zahlen Modulo 1073741789 (Sie inverse Zahlen in solchen Bereichen mit dem erweiterten euklidischen Algorithmus herausfinden können).

ich wähle und ziemlich willkürlich b, ich nur dafür gesorgt, sie sind etwa halb so groß wie die p.

Können Sie verwenden, um eine zufällig generierte Lookup-Tabelle? Solange die Zufallszahlen in der Tabelle eindeutig sind, erhalten Sie eine bijektive Abbildung. Es ist nicht symmetrisch, though.

Eine 16 GB-Lookup-Tabelle für alle 32-Bit-Werte ist wahrscheinlich nicht praktisch, aber man zwei getrennte 16-Bit-Lookup-Tabellen für das High-Wort und das niedrigen Wort gebrauchen könnte.

PS: Ich denke, Sie eine symmetrische bijective Lookup-Tabelle erzeugen können, wenn das wichtig ist. Der Algorithmus würde mit einer leeren LUT starten: 

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

Wählen Sie das erste Element, weisen Sie eine zufällige Zuordnung. Um die Zuordnung symmetrisch zu machen, weisen die inverse auch: 

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

Wählen Sie die nächste Nummer, wieder eine zufällige Zuordnung zuweisen, aber eine Nummer wählen, die noch nicht zugewiesen sind. (Das heißt in diesem Fall nicht abholen 1 oder 3). Wiederholen, bis der LUT ist abgeschlossen. Dies sollte ein zufälliges bijective symmetrisches Mapping erzeugen.

Nehmen Sie eine Zahl, multipliziert mit 9, inversen Ziffern, dividieren um 9. 

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

Sollte dunkel genug sein !!

Edit: es ist kein Bijektion für 0 endet integer 

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

Sie können jederzeit eine bestimmte Regel hinzufügen, wie: Nehmen Sie eine Zahl, Division durch 10 x-mal, multipliziert mit 9, inversen Ziffern, Division durch 9, Multiples von 10 ^ x.

So 

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

W00t es funktioniert!

Edit 2:. Weitere obscurness, können Sie eine beliebige Anzahl und subtrahiert am Ende hinzufügen 

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

Hier ist meine einfache Idee: Sie können die Bits der Zahl bewegen, wie PeterK vorgeschlagen, aber Sie können eine andere Permutation von Bits für jede Nummer haben, und noch in der Lage sein, es zu entziffern.

Die Chiffre geht so: Man behandelt die Eingangsnummer als ein Array von Bits I[0..31], und der Ausgang als O[0..31]. Vorbereiten eines Array K[0..63] von 64 zufällig erzeugten Zahlen. Dies wird Ihr Schlüssel sein. Nehmen Sie die Bit der Eingabenummer von der Position durch die erste Zufallszahl (I[K[0] mod 32]) bestimmt und legen Sie sie am Anfang Ihres Ergebnisses (O[0]). Nun zu entscheiden, welche an O[1] zu Ort Bit, verwenden Sie das zuvor verwendete Bit. Wenn es gleich 0 ist, Gebrauch K [1] Position in I zu erzeugen, aus denen zu nehmen, ist es es 1 ist, verwenden K [2] (was einfach bedeutet, eine Zufallszahl überspringen).

Jetzt wird dies nicht gut funktionieren, wie Sie das gleiche Bit zweimal in Anspruch nehmen. Um es zu vermeiden, neu nummerieren die Bits nach jeder Iteration, die verwendeten Bits weggelassen. Um die Position zu erzeugen, aus dem O[1] I[K[p] mod 31] Verwendung zu nehmen, wobei p 1 oder 2 ist, abhängig von der Bit O[0], wie es 31 Bits nach links, nummeriert von 0 bis 30.

Um dies zu veranschaulichen, werde ich ein Beispiel:

Wir haben eine 4-Bit-Zahl, und 8 Zufallszahlen. 25, 5, 28, 19, 14, 20, 0, 18 

I: 0111    O: ____
    _

25 mod 4 = 1, so dass wir Bit, das nehme Position 1 (Zählung von 0) 

I: 0_11    O: 1___
     _

Wir haben nur ein bisschen Wert 1 genommen, so dass wir eine Zufallszahl überspringen und benutzen 28. Es gibt 3 Bits nach links, so Stellung zu zählen, nehmen wir 28 mod 3 = 1. Wir nehmen die erste (Zählung von 0 ) der übrigen Bits: 

I: 0__1    O: 11__
   _

Wieder überspringen wir eine Nummer, und nehmen 14. 14 mod 2 = 0, so dass wir das 0-te Bit annehmen: 

I: ___1    O: 110_
      _

Jetzt spielt es keine Rolle, aber die vorherige Bit 0 war, so dass wir 20 nehmen 20 mod 1 = 0: 

I: ____    O: 1101

Und das ist es.

eine solche Zahl Entzifferung ist einfach, man muss nur die gleichen Dinge tun. Die Position, an die das erste Bit des Codes zu platzieren ist aus dem Schlüssel bekannt ist, die nächsten Positionen, die durch die zuvor eingefügten Bits bestimmt werden.

Dies hat natürlich alle Nachteile alles, was nur die Bits bewegt sich (zum Beispiel 0 0 wird, und MAXINT wird MAXINT), wird aber scheint schwerer zu finden, wie jemand die Nummer ohne zu wissen, den Schlüssel verschlüsselt, der muss sein Geheimnis.

Wenn Sie nicht möchten, dass geeignete Verschlüsselungsalgorithmen verwendet werden (vielleicht für die Leistung und Komplexitätsgründen) Sie können stattdessen eine einfachere Chiffre wie die Verwendung Vigenère-Chiffre . Diese Chiffre wurde tatsächlich beschrieben als Le Chiffre indéchiffrable (Französisch für 'die unzerbrechlich Chiffre').

Hier ist eine einfache C # -Implementierung, dass Verschiebungen Werte basierend auf einem entsprechenden Schlüsselwert: 

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]));
}

Dieser Algorithmus keine große Verschiebung in der Ausgabe erzeugen, wenn der Eingang leicht geändert wird. Sie können jedoch einen anderen bijective Betrieb verwenden, anstatt zusätzlich das zu erreichen.

Zeichnen Sie einen großen Kreis auf einem großen Blatt Papier. Schreiben Sie alle Zahlen von 0 bis MAXINT im Uhrzeigersinn von der Spitze des Kreises, mit gleichem Abstand. Schreiben Sie alle Zahlen von 0 bis MININT gegen den Uhrzeigersinn, gleich wieder Abstand. Beachten Sie, dass MININT zu MAXINT am unteren Rand des Kreises nächsten ist. Jetzt machen ein Duplikat dieser Figur auf beiden Seiten ein Stück steifen Karte. Pin der steifen Karte auf den Kreis durch die Zentren der beiden. Wählen Sie einen Drehwinkel, einen beliebigen Winkel Sie mögen. Jetzt haben Sie eine 1-1-Mapping, die einige Ihrer Anforderungen erfüllt, ist aber wahrscheinlich nicht dunkel genug. Unpin der Karte, es Flip einen Durchmesser herum, jeden Durchmesser. Wiederholen Sie diese Schritte (in beliebiger Reihenfolge), bis Sie eine Bijektion haben Sie sind zufrieden mit.

Wenn Sie werden folgende eng sollte es nicht schwierig sein, dies in Ihrer bevorzugten Sprache zu programmieren.

Zur Klarstellung nach dem Kommentar: Wenn Sie nur die Karte gegen das Papier drehen, dann ist das Verfahren so einfach wie Sie sich beschweren. Wenn Sie jedoch die Karte über die Mapping-Flip ist nicht gleich für jeden (x+m) mod MAXINT m. Zum Beispiel, wenn man die Karte nicht gedreht und dreht sie um den Durchmesser durch 0 lassen (die an der Oberseite des Zifferblatts ist), dann wird 1 auf -1 abgebildet wird, 2 bis -2, und so weiter. (x+m) mod MAXINT entspricht Drehungen der Karte nur.

Split die Zahl in zwei (16 höchstwertigen Bits und 16 am wenigsten signifikanten Bits) und die Bits in den beiden 16-Bit-Ergebnisse als Karten in zwei Decks betrachten. Mischen Sie die Decks zwingt einen in die andere.

Also, wenn Ihre erste Zahl ist b31,b30,...,b1,b0 Sie mit b15,b31,b14,b30,...,b1,b17,b0,b16 enden. Es ist schnell und schnell zu implementieren, da die inverse ist.

Wenn Sie an der Dezimaldarstellung der Ergebnisse aussehen, die Serie sieht ziemlich verschleiern.

Sie können 0 manuell Karte -> maxvalue und maxvalue -.> 0 ihnen Mapping auf sich selbst zu vermeiden

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top