使用密钥的可逆混洗算法

Question

我如何在C#中编写可逆混洗算法,该算法使用密钥进行混洗并可以反转为原始状态？

例如,我有一个字符串:"Hello world",我怎么能将它洗牌以便以后我能够将洗牌后的字符串反转回"Hello world".

Answer 1

看看Fisher-Yates shuffle是一种基于键来置换字符串的方法.将密钥作为种子输入PRNG,使用它来生成随机播放使用的随机数.

现在,如何扭转这个过程？Fisher-Yates通过交换某些元素来工作.因此,要反转该过程,您可以将相同的密钥输入到同一个PRNG中,然后运行Fisher-Yates算法,就好像您正在调整字符串大小的数组一样.但实际上你不移动任何东西,只记录每个阶段交换的元素的索引.

完成此操作后,反向运行您的交换列表,将它们应用到您的混洗字符串中.结果是原始字符串.

因此,例如,假设我们使用以下交换将字符串"hello"洗牌(我在这里没有使用PRNG,我掷骰子,但关于PRNG的一点是它给出了相同的数字序列给出相同的种子):

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

所以,洗牌的字符串是"loelh".

为了去混乱,我生成相同系列的"随机"数字,0,3,1,0.然后以相反的顺序应用交换:

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

成功!

这当然的缺点是它为deshuffle使用了大量的内存:一个索引数组,只要你的原始数组chars.因此,对于真正庞大的数组,您可能想要选择PRNG(或者无论如何是序列生成函数),它可以向前或向后步进,而不必存储所有输出.这排除了基于散列的加密安全PRNG,但LFSR是可逆的.

顺便问一下,你为什么要这样做？

Answer 2

这是您需要的简单实现(如果我做得好):

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

用法:

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

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

密钥必须是整数,如果需要使用字符串作为密码,只需在其上调用GetHashCode():

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

编辑:

现在正是Fisher-Yates shuffle算法的实现.感谢Jeff 的代码