Алгоритм обратимого перемешивания с использованием ключа
Как бы я кодировал алгоритм обратимого перемешивания в C #, который использует ключ для перемешивания и может быть возвращен в исходное состояние?
Например, у меня есть строка: «Hello world», как я могу перетасовать его так, чтобы позже я смог перевернуть перетасованную строку обратно в «Hello world».
3 ответа
Посмотрите на Fisher-Yates shuffle для способа перестановки строки на основе ключа. Введите ключ в качестве затравки в ГПСЧ, используйте его для генерации случайных чисел, используемых в перестановке.
Итак, как обратить процесс вспять? Фишер-Ятс работает, меняя местами определенные пары элементов. Поэтому для обратного процесса вы можете передать тот же ключ в тот же ГПСЧ, а затем выполнить алгоритм Фишера-Йейтса так, как если бы вы перетасовывали массив размером с вашу строку. Но на самом деле вы ничего не перемещаете, просто записываете индексы элементов, которые будут меняться местами на каждом этапе.
Как только вы это сделали, пройдитесь по списку замен в обратном порядке, применяя их к вашей перетасованной строке. В результате вы получите исходную строку.
Например, допустим, мы перетасовали строку "hello", используя следующие замены (я не использовал ГПСЧ, я бросил кости, но суть ГПСЧ в том, что она дает одну и ту же последовательность чисел при одинаковых затравках):
(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"
Успех!
Недостатком этого метода, конечно, является то, что он использует много памяти для перестановки: массив индексов такой же длины, как ваш исходный массив символов. Поэтому для действительно огромных массивов лучше выбрать ГПСЧ (или любую другую функцию генерации последовательности), которую можно перебирать как вперед, так и назад без необходимости хранить все выходные данные. Это исключает криптографически безопасные ГПСЧ на основе хэшей, но LFSR обратимы.
Btw, почему вы хотите это сделать?
Вот простая реализация того, что вам нужно (если я правильно понял):
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());
EDIT:
Теперь это именно реализация алгоритма Fisher-Yates shuffle. Спасибо Джеффу за код
Вы можете посмотреть на следующий вопрос и ответы на него. Шифрование/дешифрование строки в .NET