reverse deterministic shuffle -> derive key

Question

I'am looking for an algorithm with which it is possible to derive a key from an already happened shuffling-process.

Assume we've got the string "Hello" which was shuffled:

"hello" -> "loelh"

Now I would like to derive a key k from it which i could use to undo the shuffling. So if we use k as input parameter for a deterministic shuffling-algorithm like for example Fisher-Yates and shuffle "loelh" again, we would restore the initial string "hello".

What i do not mean is to simply use one and the same deterministic shuffling algorithm to shuffle and de-shuffle. That's because in my case the first string would not have been really shuffled in the classical sense. Actually there would be two sets of data (byte or bit-arrays) which are just given and we want to get from the first to the second one with just a key which has been derived before.

I hope it's clear what I want to achieve and I would appreciate all hints or proposed solutions.

Regards, Merrit

UPDATE:

Another attemp: basically, one could also call it deterministic transformation of a bunch of data e.g. a byte-array, but I will stick with the "hello"-string example.

Assume we've got a transformation-algorithm transform(data, "unknown seed") where data is "hello" and unknown seed is what we are looking for. The result of transform is "loelh". We are looking for this "unknown seed" which we could use to reverse the process. At the time of the "unknown seed"-generation, both, the input data AND the result are known of course.

Later on I want to use the "unknown seed" (which should be known already ;-) to get the original string again: so this transform("loelh", seed) should lead to "hello" again.

So you could also see it as a form of equation like data*["unknown value"]=resultdata and we are trying to find the unknown value (the operator * could be any kind of operation).

Answer 1

Shuffling is just creating a random permutation of a given sequence. The typical way to do that is something like the Fisher-Yates Shuffle that you pointed out. The problem is that the shuffle program generates multiple random numbers based on a seed, and unless you implement the random number generator there's no easy way to reverse the sequence of random numbers.

There is another way to do it. What if you could generate the nth permutation of a sequence directly? That is, given the string "Fast", you define the first few permutations as:

0  Fast
1  Fats
2  Fsat
3  Fsta
... etc. for all 24 permutations

You want a random permutation of those four characters. Select a random number from 0 to 23 and then call a function to generate that permutation.

If you know the key, you can call a different function, again passing that key, to have it reverse the permutation back to the original.

In the fourth article in his series on permutations, Eric Lippert showed how to generate the nth permutation without having to generate all of the permutations that come before it. He doesn't show how to reverse the process, but doing so shouldn't be difficult if you understand how the generator works. It's well worth the time to study the entire series of articles.

If you don't know what the key (i.e. the random number used) is, then deriving the sequence of swaps required to get to the original order is expensive.

Edit

Upon reflection, it just might be possible to derive the key if you're given the original sequence and the transformed sequence. Since you know how far each symbol has moved, you should be able to derive the key. Consider the possible permutations of two letters:

0. ab  1. ba

Now, assign the letter b the value of 0, and the letter a the value of 1. What permutation number is ba? Find a in the string, swap to the left until it gets to the proper position, and multiply the number of swaps by one.

That's too easy. Consider the next one:

0. abc  1. acb  2. bac
3. cab  4. bca  5. cba

a is now 2, b is 1, and c is 0. Given cab:

swap a left one space. 1x2 = 2. Result is `acb`
swap b left one space. 1x1 = 1. Result is `abc`

So cab is permutation #3.

This does assume that your permutation generator numbers the permutations in the same way. It's also not a terribly efficient way of doing things. Worst case will require n(n-1)/2 swaps. You can optimize the swaps by moving things in an array, but it's still an O(n^2) algorithm. Where n is the length of the sequence. Not terrible for 100 or maybe even 1,000 items. Pretty bad after that, though.

Answer 2

First of all, let's simplify the problem greatly. Instead of permuting "hello", let's assume that you are always permuting "abcde", as that will make it easier to understand.

A shuffle is the random generation of a permutation. How the shuffle generates the permutation is irrelevant; shuffles generate permutations, that's all we need to know.

Let's state a permutation as a string containing the numbers 1 through 5. Suppose the shuffle produces permutation "21453". That is, we take the first letter and put it in position 2: _a___. We take the second letter and put it in position 1, ba___. We take the 3rd letter and put it in position 5: ab__c. We take the fourth letter and put it in position 3, bad_c, and we take the fifth letter and put it in position 4, badec.

Now you wish to deduce a "key" which allows you to "unpermute" the permutation. Well, that's just another permutation, called the inverse permutation. To compute the inverse permutation of "21453" you do the following:

• find "1". It's in the 2nd spot.
• find "2". It's in the 1st spot.
• find "3". It's in the 5th spot.
• find "4". It's in the 3rd spot.
• Find "5". It's in the 4th spot.

And now read down the second column; the inverse permutation of "21453" is "21534". We are unpermuting "badec". We put the first letter in position 2: _b___. We put the second letter in position 1: ab___. We put the third letter in position 4: ab_d_. We put the fourth letter in position 5: ab_de. And we put the fifth letter in position 3: abcde.