Algoritmo reversibile shuffle utilizzando una chiave

Question

Come si codifica un algoritmo di shuffle reversibile in C# che utilizza una chiave per mescolare e può essere invertito allo stato originale?

Per esempio, ho una stringa: "Hello world", come posso mescolarla in modo che in seguito potrei essere in grado di invertire la stringa rimischiata in "Hello world".

Answer 1

Guardate Fisher-Yates shuffle di un modo per permutare la stringa in base a una chiave. Inserisci la chiave come seme in un PRNG, usala per generare i numeri casuali usati dallo shuffle.

Ora, come invertire la procedura? Fisher-Yates funziona scambiando determinate coppie di elementi. Quindi, per invertire il processo, è possibile alimentare la stessa chiave nello stesso PRNG, quindi eseguire l'algoritmo di Fisher-Yates come se fosse che si mischiasse un array della dimensione della stringa. Ma in realtà non si sposta nulla, basta registrare gli indici degli elementi che verrebbero scambiati in ogni fase.

Dopo aver eseguito questa operazione, scorrere l'elenco degli swap in senso inverso, applicandoli alla stringa mischiata. Il risultato è la stringa originale.

Quindi, per esempio, supponiamo di aver mischiato la stringa "ciao" usando i seguenti swap (non ho usato un PRNG qui, ho tirato i dadi, ma il punto su un PRNG è che ti dà la stessa sequenza di numeri dati lo stesso seme):

(4,0): "hello" -> "oellh" 
(3,3): "oellh" -> "oellh" 
(2,1): "oellh" -> "olelh" 
(1,0): "olelh" -> "loelh" 

Quindi, la stringa mescolata è "loelh".

Per deshuffle, genero la stessa serie di numeri "casuali", 0, 3, 1, 0, quindi applicare lo swap in ordine inverso:

(1,0): "loelh" -> "olelh" 
(2,1): "olelh" -> "oellh" 
(3,3): "oellh" -> "oellh" 
(4,0): "oellh" -> "hello" 

successo!

Lo svantaggio di questo, naturalmente, è che utilizza molta memoria per il disarmo: una serie di indici purché la vostra matrice di caratteri originale. Quindi per array veramente enormi, potresti voler scegliere un PRNG (o comunque una funzione di generazione della sequenza) che può essere scalato avanti o indietro senza dover memorizzare tutta l'uscita. Questo esclude i PRNG crittograficamente sicuri basati su hash, ma gli LFSR sono reversibili.

A proposito, perché vuoi farlo?

Answer 2

Si può guardare la seguente domanda e le sue risposte. Encrypt/Decrypt string in .NET

Answer 3

Ecco una semplice implementazione di quello che vi serve (se ho capito bene):

public static class ShuffleExtensions 
{ 
    public static int[] GetShuffleExchanges(int size, int key) 
    { 
     int[] exchanges = new int[size - 1]; 
     var rand = new Random(key); 
     for (int i = size - 1; i > 0; i--) 
     { 
      int n = rand.Next(i + 1); 
      exchanges[size - 1 - i] = n; 
     } 
     return exchanges; 
    } 

    public static string Shuffle(this string toShuffle, int key) 
    { 
     int size = toShuffle.Length; 
     char[] chars = toShuffle.ToArray(); 
     var exchanges = GetShuffleExchanges(size, key); 
     for (int i = size - 1; i > 0; i--) 
     { 
      int n = exchanges[size - 1 - i]; 
      char tmp = chars[i]; 
      chars[i] = chars[n]; 
      chars[n] = tmp; 
     } 
     return new string(chars); 
    } 

    public static string DeShuffle(this string shuffled, int key) 
    { 
     int size = shuffled.Length; 
     char[] chars = shuffled.ToArray(); 
     var exchanges = GetShuffleExchanges(size, key); 
     for (int i = 1; i < size; i++) 
     { 
      int n = exchanges[size - i - 1]; 
      char tmp = chars[i]; 
      chars[i] = chars[n]; 
      chars[n] = tmp; 
     } 
     return new string(chars); 
    } 
} 

utilizzo:

var originalString = "Hello world"; 
var shuffled = originalString.Shuffle(123); 
var deShuffled = shuffled.DeShuffle(123); 

// shuffled = "lelooH rwld"; 
// deShuffled = "Hello world"; 

La chiave deve essere un numero intero, se è necessario utilizzare una stringa come password, chiama semplicemente GetHashCode() su di esso:

var shuffled = originalString.Shuffle(myStringKey.GetHashCode()); 

MODIFICA:

Ora è esattamente un'implementazione dell'algoritmo di Fisher-Yates shuffle. Grazie a Jeff per the code

Answer 4

Una domanda java reindirizza anche qui, ecco la piena attuazione di crittografia-forza java:

import java.security.*; 
import java.util.*; 

/** Cryptographic strength reversible random shuffle. To be truly secure, the passKey arguments should be 20 chars or more and (obviously) not guessable. */ 
public class SecureShuffle 
{ 
    public static int[] getShuffleExchanges(int size, String passKey) 
    { 
     int[] exchanges = new int[size - 1]; 
     SecureRandom rand = new SecureRandom(passKey.getBytes()); 
     for (int i = size - 1; i > 0; i--) 
     { 
      int n = rand.nextInt(i + 1); 
      exchanges[size - 1 - i] = n; 
     } 
     return exchanges; 
    } 

    public static void shuffle(byte[] toShuffle, String passKey) 
    { 
     int size = toShuffle.length; 
     int[] exchanges = getShuffleExchanges(size, passKey); 
     for (int i = size - 1; i > 0; i--) 
     { 
      int n = exchanges[size - 1 - i]; 
      byte tmp = toShuffle[i]; 
      toShuffle[i] = toShuffle[n]; 
      toShuffle[n] = tmp; 
     } 
    } 

    public static void deshuffle(byte[] shuffled, String passKey) 
    { 
     int size = shuffled.length; 
     int[] exchanges = getShuffleExchanges(size, passKey); 
     for (int i = 1; i < size; i++) 
     { 
      int n = exchanges[size - i - 1]; 
      byte tmp = shuffled[i]; 
      shuffled[i] = shuffled[n]; 
      shuffled[n] = tmp; 
     } 
    } 

    public static void shuffle(char[] toShuffle, String passKey) 
    { 
     int size = toShuffle.length; 
     int[] exchanges = getShuffleExchanges(size, passKey); 
     for (int i = size - 1; i > 0; i--) 
     { 
      int n = exchanges[size - 1 - i]; 
      char tmp = toShuffle[i]; 
      toShuffle[i] = toShuffle[n]; 
      toShuffle[n] = tmp; 
     } 
    } 

    public static void deshuffle(char[] shuffled, String passKey) 
    { 
     int size = shuffled.length; 
     int[] exchanges = getShuffleExchanges(size, passKey); 
     for (int i = 1; i < size; i++) 
     { 
      int n = exchanges[size - i - 1]; 
      char tmp = shuffled[i]; 
      shuffled[i] = shuffled[n]; 
      shuffled[n] = tmp; 
     } 
    } 

    public static void shuffle(int[] toShuffle, String passKey) 
    { 
     int size = toShuffle.length; 
     int[] exchanges = getShuffleExchanges(size, passKey); 
     for (int i = size - 1; i > 0; i--) 
     { 
      int n = exchanges[size - 1 - i]; 
      int tmp = toShuffle[i]; 
      toShuffle[i] = toShuffle[n]; 
      toShuffle[n] = tmp; 
     } 
    } 

    public static void deshuffle(int[] shuffled, String passKey) 
    { 
     int size = shuffled.length; 
     int[] exchanges = getShuffleExchanges(size, passKey); 
     for (int i = 1; i < size; i++) 
     { 
      int n = exchanges[size - i - 1]; 
      int tmp = shuffled[i]; 
      shuffled[i] = shuffled[n]; 
      shuffled[n] = tmp; 
     } 
    } 

    public static void shuffle(long[] toShuffle, String passKey) 
    { 
     int size = toShuffle.length; 
     int[] exchanges = getShuffleExchanges(size, passKey); 
     for (int i = size - 1; i > 0; i--) 
     { 
      int n = exchanges[size - 1 - i]; 
      long tmp = toShuffle[i]; 
      toShuffle[i] = toShuffle[n]; 
      toShuffle[n] = tmp; 
     } 
    } 

    public static void deshuffle(long[] shuffled, String passKey) 
    { 
     int size = shuffled.length; 
     int[] exchanges = getShuffleExchanges(size, passKey); 
     for (int i = 1; i < size; i++) 
     { 
      int n = exchanges[size - i - 1]; 
      long tmp = shuffled[i]; 
      shuffled[i] = shuffled[n]; 
      shuffled[n] = tmp; 
     } 
    } 

    public static void main(String[] args) 
    { 
     String passphrase = "passphrase"; 
     String text = "The rain in Spain stays mainly on the plain"; 

     char[] chars = text.toCharArray(); 
     shuffle(chars, passphrase); 
     System.out.println(new String(chars)); 

     deshuffle(chars, passphrase); 
     System.out.println(new String(chars)); 

     byte[] bytes = new byte[] {0, 1, 2, 3, 4, 5, 6, 7}; 
     shuffle(bytes, passphrase); 
     System.out.println(Arrays.toString(bytes)); 

     deshuffle(bytes, passphrase); 
     System.out.println(Arrays.toString(bytes)); 
    } 

}