Algorithme de lecture aléatoire réversible à l'aide d'une touche

Question

Comment coder un algorithme de lecture aléatoire réversible en C# qui utilise une clé pour mélanger et qui peut être inversée à l'état d'origine? Par exemple, j'ai une chaîne: "Bonjour tout le monde", comment puis-je la mélanger pour que plus tard je puisse inverser la chaîne mélangée en "Hello world".

Answer 1

Regardez Fisher-Yates shuffle pour un moyen de permuter la chaîne basée sur une clé. Alimentez la clé comme une graine dans un PRNG, utilisez-la pour générer les nombres aléatoires utilisés par le shuffle.

Maintenant, comment inverser le processus? Fisher-Yates travaille en échangeant certaines paires d'éléments. Donc, pour inverser le processus, vous pouvez introduire la même clé dans le même PRNG, puis parcourir l'algorithme de Fisher-Yates comme si vous étiez en train de mélanger un tableau de la taille de votre chaîne. Mais en réalité vous ne bougez rien, il suffit d'enregistrer les index des éléments qui seraient échangés à chaque étape.

Une fois que vous avez fait cela, parcourez votre liste de swaps en inversant, en les appliquant à votre chaîne mélangée. Le résultat est la chaîne d'origine. Par exemple, supposons que nous avons mélangé la chaîne "bonjour" en utilisant les échanges suivants (je n'ai pas utilisé de PRNG ici, j'ai lancé des dés, mais le point sur un PRNG est qu'il vous donne la même séquence de nombres donnés avec la même graine):

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

Ainsi, la chaîne mélangée est "loelh".

Pour deshuffle, je produis de la même série de nombres "aléatoires", 0, 3, 1, 0. Appliquez ensuite les swaps dans l'ordre inverse:

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

succès! L'inconvénient de ceci est bien sûr qu'il utilise beaucoup de mémoire pour le deshuffle: un tableau d'index aussi long que votre tableau original de caractères. Donc, pour les tableaux vraiment énormes, vous pouvez choisir un PRNG (ou de toute façon une fonction de génération de séquence) qui peut être avancé ou reculé sans avoir à stocker toute la sortie. Cela exclut les PRNG cryptographiquement sécurisés basés sur le hachage, mais les LFSR sont réversibles.

Btw, pourquoi voulez-vous faire cela?

Answer 2

Vous pouvez regarder la question suivante et ses réponses. Encrypt/Decrypt string in .NET

Answer 3

Voici une implémentation simple de ce que vous avez besoin (si je l'ai bien):

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

utilisation:

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

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

La clé doit être un entier, si vous avez besoin d'utiliser une chaîne comme mot de passe, appelez simplement GetHashCode() dessus:

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

EDIT:

Maintenant, c'est exactement une implémentation de l'algorithme aléatoire de Fisher-Yates. Merci à Jeff pour the code

Answer 4

Une question java redirige ici aussi, alors voici la pleine application java cryptographique force:

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

}