Algoritmo biunivoca simmetrica per gli interi

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

Domanda

Ho bisogno di un algoritmo in grado di fare una mappatura uno-a-uno (es. Nessuna collisione) di un intero con segno a 32 bit su un altro intero con segno a 32 bit.

La mia vera preoccupazione è abbastanza entropia in modo che l'output della funzione sembra essere casuale. Fondamentalmente sto cercando una cifra simile a XOR Cipher, ma in grado di generare più uscite-arbitrari cercando. La sicurezza non è la mia vera preoccupazione, anche se l'oscurità è.

Modifica fini precisazione:

  1. L'algoritmo di deve di essere simmetrica, in modo che possa invertire l'operazione senza una coppia di chiavi.
  2. L'algoritmo di deve è biunivoca, ogni numero di ingresso a 32 bit deve generare una a 32 bit numero unico.
  3. L'output della funzione deve essere abbastanza oscuro, aggiungendo un solo all'ingresso dovrebbe comportare grande effetto sull'uscita.

Esempio risultato atteso:

F (100) = 98.456
F (101) = -758
F (102) = 10.875.498
F (103) = 986.541
F (104) = 945.451.245
F (105) = -488.554

Proprio come MD5, cambiando una cosa può cambiare un sacco di cose.

Cerco una funzione mathmetical, così interi mappatura manualmente non è una soluzione per me. Per coloro che chiedono, la velocità algoritmo non è molto importante.

È stato utile?

Soluzione

Utilizzare qualsiasi cifrario a blocchi a 32 bit! Per definizione, un cifrario a blocchi associa ogni possibile valore di ingresso nella sua gamma ad un valore di uscita univoco, in modo reversibile, e di progettazione, è difficile determinare quale un dato valore verrà convertito senza la chiave. Basta scegliere una chiave, mantenere il segreto, se la sicurezza o l'oscurità è importante, e utilizzare il cifrario come la vostra trasformazione.

Per un'estensione di questa idea di non-potere-su-2 gamme, vedere il mio post su permutazioni sicuri con blocco crittografie .

Affrontare le vostre preoccupazioni specifiche:

  1. L'algoritmo è davvero simmetrica. Non sono sicuro di cosa si intende per "invertire l'operazione senza una coppia di chiavi". Se non si desidera utilizzare una chiave, un hardcode generato in modo casuale uno e considerarlo parte dell'algoritmo.
  2. Yup -. Per definizione, un cifrario a blocchi è biunivoca
  3. Yup. Non sarebbe una buona cifra se non fosse il caso.

Altri suggerimenti

cercherò di spiegare la mia soluzione a questo su un esempio molto più semplice, che poi possono essere facilmente esteso per il vostro grande.

dire che ho un numero di 4 bit. Ci sono 16 valori distinti. Guardate come se fosse un cubo a quattro dimensioni: 4 cubo tridimensionale
(fonte: ams.org )
.

ogni vertice rappresenta uno di quei numeri, ogni bit rappresenta una dimensione. Così la sua XYZW basicaly, in cui ciascuna delle dimensioni può avere solo valori 0 o 1. Ora immaginate di utilizzare un ordine diverso di dimensioni. Per esempio XZYW. Ognuno dei vertici la società ha cambiato il suo numero!

Si può fare questo per qualsiasi numero di dimensioni, solo permutare quelle dimensioni. Se la sicurezza non è la vostra preoccupazione questo potrebbe essere una soluzione veloce piacevole per voi. D'altra parte, non so se l'uscita sarà "oscurare" sufficiente per le vostre esigenze e certamente dopo una grande quantità di mappatura fatto, la mappatura può essere invertito (che può essere un vantaggio o uno svantaggio, a seconda delle esigenze.)

Il seguente articolo vi dà 4 o 5 esempi di mappatura, offrendo funzioni, piuttosto che la costruzione di set di tracciati: www.cs.auckland.ac.nz/~john-rugis/pdf/BijectiveMapping.pdf

Oltre a generare casuali di ricerca-tabelle, è possibile utilizzare una combinazione di funzioni:

  • XOR
  • simmetrica bit permutazione (per esempio spostamento 16 bit, o vibrazione 0-31 al 31-0, o capovolgere 0-3 a 3-0, 4-7 a 7-4, ...)
  • di più?

Se il vostro obiettivo è semplicemente quello di ottenere una permutazione apparentemente casuale di numeri di un circa dimensione definita, poi c'è un altro modo possibile:. Ridurre la serie di numeri per un numero primo

Quindi è possibile utilizzare una mappatura della forma

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

e se p è davvero un numero primo, questo sarà un bijection per tutti a! = 0 e tutto b. Si farà il punto abbastanza casuale per i più grandi a e b.

Per esempio, nel mio caso per il quale mi sono imbattuto su questa questione, ho usato 1.073.741,789 mila come un numero primo per l'intervallo di numeri più piccoli di 1 << 30. Questo mi fa perdere solo 35 numeri, che va bene nel mio caso.

Il mio codifica è poi 

((n + 173741789) * 507371178) % 1073741789

e la decodifica è 

(n * 233233408 + 1073741789 - 173741789) % 1073741789

Si noti che 507371178 * 233233408% 1073741789 == 1, in modo da questi due numeri sono inversamente campo dei numeri con modulo 1073741789 (si può capire inversa numeri in tali campi con l'algoritmo di Euclide esteso).

I scelto ae b abbastanza arbitrariamente, ho solo fatto che essi siano circa la metà delle dimensioni di p.

È possibile utilizzare una ricerca-tabella generata a caso? Finché i numeri casuali nella tabella sono unici, si ottiene una mappatura biunivoca. Non è simmetrica, però.

Una 16 GB ricerca-tavolo per tutti i valori a 32 bit è probabilmente non è pratico, ma si potrebbe usare due tavoli separati di ricerca a 16 bit per l'alta parola e la parola bassa.

PS: Penso che è possibile generare una tabella di ricerca biunivoca simmetrica, se questo è importante. L'algoritmo dovrebbe iniziare con una LUT vuoto: 

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

Selezionare il primo elemento, assegnare una mappatura casuale. Per rendere la simmetrica mappatura, assegnare l'inverso, anche: 

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

Scegli il numero successivo, di nuovo assegnare una mappatura casuale, ma scegliere un numero che non è stato ancora assegnato. (Cioè in questo caso, non selezionare 1 o 3). Ripetere fino a quando la LUT è completa. Questo dovrebbe generare una mappatura simmetrica biunivoca casuale.

Prendere un numero, si moltiplica per 9, cifre inversi, dividere per 9. 

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

Dovrebbe essere abbastanza oscuro !!

Edit: non è una biiezione per 0 finire intero 

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

È sempre possibile aggiungere una regola specifica come: Prendere un numero, dividere per 10 x volte, moltiplica da 9 cifre inversi, dividere per 9 multipli per 10 ^ x.

E così 

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

w00t funziona!

Modifica 2:. Per ulteriori obscurness, è possibile aggiungere un numero arbitrario, e sottrarre alla fine 

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

Qui è la mia semplice idea: È possibile scorrere i bit del numero, come proposto PeterK, ma si può avere una diversa permutazione di bit per ogni numero, e ancora in grado di decifrarlo.

Il cifrario va come questa: Trattare il numero di input come una matrice di bit I[0..31], e l'output come O[0..31]. Preparare una serie di K[0..63] 64 numeri generati casualmente. Questa sarà la chiave. Prendete il pezzo di numero di ingresso dalla posizione determinata dal primo numero casuale (I[K[0] mod 32]) e posizionarlo all'inizio del tuo risultato (O[0]). Ora per decidere quali bit di mettere a O[1], utilizzare il bit precedentemente utilizzato. Se è 0, l'uso K [1] per generare posizione I da cui prendere, esso è 1, utilizzare K [2] (che semplicemente mezzi saltare un numero casuale).

Ora, questo non funzionerà bene, come si può prendere lo stesso bit due volte. Per evitare che, rinumerarli bit dopo ogni iterazione, omettendo i bit utilizzati. Per generare la posizione dalla quale prendere O[1] uso I[K[p] mod 31], dove p è 1 o 2, a seconda del O[0] bit, in quanto ci sono 31 bit sinistra, numerate da 0 a 30.

Per illustrare questo, ti darò un esempio:

Abbiamo un numero a 4 bit e 8 numeri casuali:. 25, 5, 28, 19, 14, 20, 0, 18 

I: 0111    O: ____
    _

25 mod 4 = 1, quindi prenderemo bit la cui posizione è 1 (conteggio da 0) 

I: 0_11    O: 1___
     _

Abbiamo appena preso un po 'di valore 1, in modo da saltare un numero casuale e l'uso 28. Ci sono 3 bit sinistra, così contare posizione prendiamo 28 mod 3 = 1. Prendiamo il primo (conteggio da 0 ) dei bit rimanenti: 

I: 0__1    O: 11__
   _

Ancora si salta un numero e prendiamo 14. 14 mod 2 = 0, quindi prendiamo il bit 0th: 

I: ___1    O: 110_
      _

Ora non importa, ma il bit precedente era 0, quindi prendiamo 20. 20 mod 1 = 0: 

I: ____    O: 1101

E questo è esso.

Decifrare un tale numero è facile, si ha solo per fare le stesse cose. La posizione in cui collocare il primo bit del codice è noto dalla chiave, i prossimi posizioni sono determinate dai bit precedentemente inseriti.

Questo ovviamente ha tutti gli svantaggi di tutto ciò che si muove solo i bit in giro (per esempio 0 scende a 0 e MAXINT diventa MAXINT), ma è sembra più difficile da trovare come qualcuno ha criptato il numero senza conoscere la chiave, che deve essere segreto.

Se non si desidera utilizzare algoritmi crittografici corretti (forse per motivi di prestazioni e complessità) si può invece utilizzare un cifrario semplice come il cifrario di vigenère . Questa cifra è stato effettivamente descritto come Le Chiffre indéchiffrable (francese per 'la cifra indistruttibile').

Ecco una semplice implementazione C # che i valori turni basate su un corrispondente valore chiave: 

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

Questo algoritmo non crea un grande cambiamento nell'uscita quando l'ingresso è leggermente cambiata. Tuttavia, è possibile utilizzare un'altra operazione biunivoca invece di aggiunta a raggiungere questo obiettivo.

Disegna un grande cerchio su un grande foglio di carta. Scrivere tutti i numeri interi da 0 a MAXINT senso orario dalla parte superiore del cerchio, ugualmente distanziati. Scrivere tutti i numeri interi da 0 a MININT in senso antiorario, equidistanti di nuovo. Si osservi che MININT si trova accanto al MAXINT sul fondo del cerchio. Ora fate un duplicato di questa figura su entrambi i lati di un foglio di carta rigida. Pin il cartoncino rigido al cerchio attraverso i centri di entrambi. Scegliere un angolo di rotazione, qualsiasi angolo che ti piace. Ora avete una mappatura 1-1 che soddisfa alcune delle vostre esigenze, ma probabilmente non è abbastanza oscura. Unpin la carta, capovolgere intorno diametro, qualsiasi diametro. Ripetere questi passaggi (in qualsiasi ordine) fino ad ottenere una corrispondenza biunivoca si è soddisfatti.

Se avete seguito da vicino non dovrebbe essere difficile da programmare questo nella vostra lingua preferita.

Per Chiarimento a seguito del commento: Se si ruota solo la scheda contro la carta, allora il metodo è così semplice come si lamentano. Tuttavia, quando si schiaccia la carta sopra la mappatura non è equivalente a (x+m) mod MAXINT per qualsiasi m. Ad esempio, se si lascia la carta non ruotato e ruotarlo attorno al diametro attraverso 0 (che è nella parte superiore del quadrante dell'orologio) allora 1 viene mappata -1, 2 a -2, e così via. (x+m) mod MAXINT corrisponde rotazioni della carta soltanto.

Split il numero a due (16 bit più significativi e 16 bit meno significativi) e considerare bit delle due risultati a 16 bit come carte in due mazzi. Mescolare i ponti costringendo uno dentro l'altro.

Così, se il numero iniziale è b31,b30,...,b1,b0 si finisce con b15,b31,b14,b30,...,b1,b17,b0,b16. E 'veloce e veloce da implementare, come è l'inverso.

Se si guarda alla rappresentazione decimale dei risultati, gli sguardi della serie piuttosto oscuro.

È possibile mappare manualmente 0 -> maxvalue e maxvalue -.> 0 per evitarli mappatura su se stessi

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top