Bijective "Integer <-> String" function

Question

Ecco un problema per cui sto cercando di creare la soluzione migliore. Ho un insieme finito di numeri interi non negativi nell'intervallo [0 ... N]. Devo essere in grado di rappresentare ogni numero in questo set come una stringa ed essere in grado di convertire tale stringa all'indietro al numero originale. Quindi questa dovrebbe essere una funzione biettiva.

Ulteriori requisiti sono:

1. rappresentazione String di un numero dovrebbe offuscare numero originale, almeno in una certa misura. Una soluzione così primitiva come f (x) = x.toString() non funzionerà.
2. La lunghezza della stringa è importante: minore è, meglio è.
3. Se si conosce la rappresentazione di stringa di K, vorrei che fosse non banale (in una certa misura) di indovinare la rappresentazione di stringa di K + 1.

Per p.1 & p.2 la soluzione ovvia è utilizzare qualcosa come Base64 (o qualunque BaseXXX per adattarsi a tutti i valori) notazione. Ma possiamo inserirci in p.3 con uno sforzo minimo aggiuntivo? Il buon senso mi dice che ho anche bisogno di una funzione "String < -> String" bijective per i valori BaseXXX. Eventuali suggerimenti? O forse c'è qualcosa di meglio di BaseXXX da utilizzare per soddisfare tutti e 3 i requisiti?

Answer 1

Quindi è necessaria una stringa che offusca il numero originale, ma consente di determinare str (K + 1) quando è noto lo str (K)?

Che ne dici di fare semplicemente f(x) = (x + a).toString(), dove a è segreto? Quindi un utente esterno non può determinare x da f(x), ma possono essere certi che se hanno una stringa "1234", ad esempio, per uno sconosciuto x, quindi "1235" esegue il mapping su x+1.

Answer 2

Se non è necessario che sia sicuro, è sufficiente utilizzare un semplice codice simmetrico dopo la codifica in BaseXXX. Ad esempio è possibile scegliere una sequenza di tasti di numeri interi [n₁, n₂, n₃ ...] e quindi utilizzare uno Vigenere cipher.

L'idea di base dietro il cifrario è semplice: codifica ogni carattere C come C + K (mod 26) dove K è un elemento della chiave. Mentre procedete, prendete il prossimo numero dalla chiave per il prossimo personaggio, avvolgendolo una volta esauriti i valori nella chiave.

Hai davvero due opzioni qui: puoi prima convertire un numero in una stringa in baseXXX e quindi criptare, oppure puoi usare la stessa idea per crittografare ogni numero come un singolo carattere. In tal caso, vorrai cambiarlo da mod 26 a mod N + 1.

Vieni a pensarci, un'opzione ancora più semplice sarebbe solo l'elemento xor dalla chiave e il valore. (Invece di usare la formula di Vigenere). Penso che questo potrebbe funzionare altrettanto bene per l'offuscamento.

Answer 3

p. 1 e p. 3 sono leggermente contraddittori e anche un po 'vaghi.

Propongo di utilizzare la rappresentazione esadecimale dei numeri interi.

17 => 0x11 
123123 => 1E0F3 

Answer 4

Questo metodo soddisfa i requisiti 1-3, ma è forse un po 'troppo costoso computazionalmente:

1. trovare un primo p > N+2, non troppo grande
2. trovare una radice primitiva g modulo p, ovvero un numero il cui ordine moltiplicativo modulo p è p-1
3. per 0 <= k <= N, diciamo enc(k) = min {j > 0 : g^j == (k+2) (mod p)}
4. f(k) = enc(k).toString()

Answer 5

costruire una tabella di lunghezza M. Questa tabella dovrebbe mappare i numeri da 0 a M-1 a stringhe corte distinte con un ordinamento casuale. Esprimi il numero intero come numero base M, utilizzando le stringhe della tabella per rappresentare le cifre nel numero. Decodifica con una semplice inversione.

Con M=26, è possibile utilizzare solo una lettera per ciascuna delle cifre. Oppure prendere M=256 e utilizzare un byte per ogni cifra.

Neanche lontanamente un buon approccio crittografico!