Reversible shuffle algorithm using a key

问题:

How would I code a reversible shuffle algorithm in C# which uses a key to shuffle and can be reversed to the original state?

For instance, I have a string: "Hello world", how can I shuffle it so that later I could be able to reverse the shuffled string back to "Hello world".

回答1:

Look at Fisher-Yates shuffle for a way to permute the string based on a key. Feed the key as the seed into a PRNG, use that to generate the random numbers used by the shuffle.

Now, how to reverse the process? Fisher-Yates works by swapping certain pairs of elements. So to reverse the process you can feed the same key into the same PRNG, then run through the Fisher-Yates algorithm as if you were shuffling an array the size of your string. But actually you don't move anything, just record the indexes of the elements that would be swapped at each stage.

Once you've done this, run through your list of swaps in reverse, applying them to your shuffled string. The result is the original string.

So for example, suppose we've shuffled the string "hello" using the following swaps (I haven't used a PRNG here, I rolled dice, but the point about a PRNG is it gives you the same sequence of numbers given the same seed):

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

So, the shuffled string is "loelh".

To deshuffle, I generate the same series of "random" numbers, 0, 3, 1, 0. Then apply the swaps in reverse order:

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

Success!

The downside of this of course is that it uses a lot of memory for the deshuffle: an array of indexes as long as your original array of chars. So for truly huge arrays, you might want to choose a PRNG (or anyway a sequence-generation function) that can be stepped either forwards or backwards without having to store all the output. This rules out hash-based cryptographically secure PRNGs, but LFSRs are reversible.

Btw, why do you want to do this?

回答2:

Here's a simple implementation of what you need (if I got it well):

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

usage:

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

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

The key must be an integer, if you need to use a string as password, just call GetHashCode() on it:

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

EDIT:

Now is exactly a Fisher–Yates shuffle algorithm implementation. Thanks to Jeff for the code

回答3:

You may look at the following question and it's answers. Encrypt/Decrypt string in .NET

回答4:

A java question also redirects here, so here is the full cryptographic-strength java implementation:

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

}