Реверсивный алгоритм тасования с использованием ключа

Как бы я закодировал алгоритм обратимого тасования в C #, который использует ключ для перетасовки и может быть изменен на исходное состояние?

Например, у меня есть строка: «Hello world», как я могу перетасовать ее, чтобы позже я смог перевернуть перетасованную строку обратно в «Hello world».

Посмотрите на Fisher-Yates shuffle , чтобы переставить строку на основе ключа. Подайте ключ как семя в PRNG, используйте его для генерации случайных чисел, используемых в случайном порядке.

Теперь, как изменить процесс? Фишер-Йейтс работает путем замены некоторых пар элементов. Таким образом, чтобы обратить вспять процесс, вы можете передать тот же ключ в тот же PRNG, а затем запустить алгоритм Fisher-Yates, как если бы вы перетасовывали массив размером вашей строки. Но на самом деле вы ничего не двигаете, просто записывайте индексы элементов, которые будут заменены на каждом этапе.

Как только вы это сделаете, запустите свой список свопов в обратном порядке , применив их к вашей перетасованной строке. Результатом является исходная строка.

Так, например, предположим, что мы перетасовали строку «привет», используя следующие свопы (я не использовал 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: массив индексов до тех пор, пока ваш оригинальный массив символов. Таким образом, для действительно огромных массивов вы можете выбрать PRNG (или, в любом случае, функцию генерации последовательности), которая может быть ступенчато или вперед или назад без необходимости хранить весь вывод. Это исключает криптографически защищенные PRNG, основанные на хеше, но LFSR являются обратимыми.

Кстати, почему вы хотите это сделать?

Вот простая реализация того, что вам нужно (если я хорошо это понял):

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

РЕДАКТИРОВАТЬ:

Теперь это реализация алгоритма Shuffle Fisher-Yates. Благодаря Джеффу для кода

Вы можете посмотреть на следующий вопрос, и это ответы. Шифрование / Расшифровка строки в .NET.

Вопрос 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)); } } 
  • Алгоритм обнаружения столкновений в кольцевом сегменте?
  • Округление до произвольного количества значащих цифр
  • Как сравнивается алгоритм Дейкстры и A-Star?
  • Лучший алгоритм для согласования цветов.
  • Как вычислить энтропию файла?
  • Точка в алгоритме многоугольника
  • Лучший алгоритм хеширования с точки зрения hash-коллизий и производительности для строк
  • найти элемент в отсортированной матрице
  • Как найти, какие элементы находятся в сумке, используя алгоритм Knapsack Algorithm ?
  • Лучший алгоритм для оценки математического выражения?
  • Распечатайте самые большие K-элементы в заданной куче в O (K * log (K))?
  • Interesting Posts

    Команды npm не работают на WSL с zsh

    Есть ли ярлык Win7 для позиционирования мыши в центре основного экрана?

    Правильное чтение текстового файла utf-16 в строку без внешних библиотек?

    Маршрутизация ASP.NET MVC через атрибуты метода

    Как восстановить Windows 7 из системного образа в раздел Boot Camp без форматирования?

    Haskell: Как произносится ?

    Захваченная ориентация фото меняется в андроиде

    Мониторинг сборщика мусора в C #

    PCA в matlab, который выбирает верхние n компонентов

    Можно ли зашифровать домашнюю папку на окнах 7?

    В C # в какой категории двоеточие «:» попадает и что это значит?

    Как определить функцию в ghci через несколько строк?

    Как отключить защиту от записи на USB-накопителе?

    Selenium: загрузите файл в Internet Explorer в указанную папку без прямой ссылки, без форм Windows, без AutoIt или Robot

    Внешняя разница в производительности по сравнению с встроенным стилем?

    Давайте будем гением компьютера.