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

Question

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

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

Answer 1

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

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

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

Так, например, предположим, что мы перетасовали строку «привет», используя следующие перестановки (здесь я не использовал 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 обратимы.

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

Answer 2

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

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

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

Теперь это точно реализация алгоритма тасования Фишера-Йейтса.Спасибо Джеффу за код

Answer 3

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

}

Answer 4

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