使用密钥的可逆混洗算法
我如何在C#中编写一个可逆的混洗算法，它使用一个密钥来进行混洗，并且可以反转到原始状态？
例如，我有一个字符串："Hello world"，我如何对其进行混洗，以便稍后能够将混洗后的字符串反转回"Hello world“。
回答 4
Stack Overflow用户
发布于 2010-08-22 23:21:30
在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"成功！
当然，这样做的缺点是它使用了大量内存进行混洗:索引数组的长度与原始字符数组的长度一样长。因此，对于真正的大型数组，您可能希望选择一个PRNG (或者无论如何是一个序列生成函数)，它可以向前或向后单步执行，而不必存储所有输出。这排除了基于散列的加密安全PRNG，但LFSR是可逆的。
顺便说一句，你为什么要这样做？
Stack Overflow用户
发布于 2010-08-22 23:05:55
下面是您需要的一个简单实现(如果我做得很好的话)：
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混洗算法的实现。感谢杰夫的the code
Stack Overflow用户
发布于 2010-08-22 20:13:02
你可以看看下面的问题，它就是答案。Encrypt/Decrypt string in .NET
https://stackoverflow.com/questions/3541378
复制相似问题
腾讯云开发者
