キーを使用してシャッフルし、元の状態に戻すことができるリバーシブル シャッフル アルゴリズムを C# でコーディングするにはどうすればよいですか?
たとえば、「Hello world」という文字列があります。後でシャッフルされた文字列を「Hello world」に戻すことができるように、どのようにシャッフルできますか。
8282 次
4 に答える
19
キーに基づいて文字列を並べ替える方法については、Fisher-Yatesシャッフルをご覧ください。キーをシードとしてPRNGにフィードし、それを使用してシャッフルで使用される乱数を生成します。
では、プロセスを逆にする方法は？フィッシャー-イェーツは、要素の特定のペアを交換することによって機能します。したがって、プロセスを逆にするには、同じキーを同じ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());
編集：
これはまさにフィッシャー-イェーツシャッフルアルゴリズムの実装です。コードを提供してくれた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 に答える