我将如何在 C# 中编写一个可逆的随机播放算法，该算法使用一个密钥来随机播放并且可以反转到原始状态？
例如，我有一个字符串：“Hello world”，我怎样才能将它打乱，以便稍后我可以将打乱的字符串反转回“Hello world”。
问问题
8282 次
4 回答
19
查看Fisher-Yates shuffle以了解基于键置换字符串的方法。将密钥作为种子输入 PRNG，使用它来生成 shuffle 使用的随机数。
现在，如何扭转这个过程？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 是可逆的。
顺便说一句，你为什么要这样做？
于 2010-08-22T15:21:29.903 回答
8
这是您需要的简单实现（如果我做得好的话）：
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的代码
于 2010-08-22T15:05:55.233 回答
1
您可以查看以下问题及其答案。 在 .NET 中加密/解密字符串
于 2010-08-22T12:13:02.420 回答
1
一个java问题也重定向到这里，所以这里是完整的加密强度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));
}
}
于 2015-09-01T17:57:29.713 回答