Reversibly shuffle a set of a million numbers

Question

I need to issue a series {1, 2, 3, 4 …} of tickets that are (at least seemingly) random numbers {10,934, 3,453,867, 122, 4,386,564 …}. When presented back, I must be able to compute their original index (e.g. 122 → 3.)

In other words, I need a seemingly random permutation p on the interval [1 … N] that has an inverse permutation p^-1. N is about 10⁷.

The reasons for that are:

It is a cipher: When receiving a ticket, it should not be easy to guess the tickets that where issued before.
The tickets should be short alphanumeric strings that can be noted down.
I want to avoid recording every ticket issued.

Implement the [Hasty pudding cipher](https://en.wikipedia.org/wiki/Hasty_Pudding_cipher), then you can use PRP of [1 .. 2^{ceil(log_2(N))}] — Artjom B., Dec 23 '15 at 21:40
@DavidEisenstat: Alright! You put me on track. What I need is called a *22-bit block cipher*. — Laurent CAPRANI, Dec 24 '15 at 02:37
@ArtjomB.: Does the [Hasty pudding cipher](https://en.wikipedia.org/wiki/Hasty_Pudding_cipher) handle 22-bit blocks? — Laurent CAPRANI, Dec 24 '15 at 03:33
@LaurentCAPRANI Yes, the Hasty pudding cipher can handle 22-bit blocks, but it's a cipher that is notoriously hard to implement, because the specification is quite complex. — Artjom B., Dec 24 '15 at 11:51

score 2 · Answer 1 · answered Dec 23 '15 at 23:58

2

I would use some well-known cipher (e.g., DES) in counter mode.

DES is generally considered fairly broken for normal purposes, but it seems to fit your needs reasonably well, and has a smaller block size than most newer algorithms. For you, that means it produces a smaller result (64 bits, if memory serves). Once you've converted that to readable characters (e.g,. base 64) you end up with something like 10 characters or so.

To retrieve the original number, you simply decrypt with your secret key.

Results look quite random--essentially the only known way to sort them back into order would be to break DES, which can be done (has been done) but the resources to do so are quite non-trivial.

If you really do need a lot better security than that, you can use something like AES instead of DES (at the expense of producing a longer "key" value).

answered Dec 23 '15 at 23:58

Jerry Coffin

476,176
80
629
1,111

You guessed well: A highly secure algorithm is not needed. But I wish I could generate numbers as short as their indexes, that is 22 bit (or 23, not sure). 64-bit is too long a block. – Laurent CAPRANI Dec 24 '15 at 02:52
@LaurentCAPRANI: Well, there is the [Skip32](http://www.anvilon.com/software/crypt-skip32/) algorithm which uses a 32-bit block size. The small block size means it *can't* be really secure, but it might well be adequate for your purposes. – Jerry Coffin Dec 24 '15 at 03:04
Unfortunately, 32 is still too many bits. Is there an algorithm that uses an arbitrary block size? ArtjomB suggests the [Hasty Pudding cipher](https://en.wikipedia.org/wiki/Hasty_Pudding_cipher). I wonder whether HPC-Tiny can handle blocks of 22 bits. Does it? – Laurent CAPRANI Dec 24 '15 at 03:39
For arbitrary size you'd want to use a stream cipher (e.g. rc4). – Jerry Coffin Dec 24 '15 at 05:28
You are right, my expression is confusing. "Arbitrary size" calls for a stream cipher. I definitely need a block cipher, but a "variable length block cipher" that can be adapted to the length I use. – Laurent CAPRANI Dec 25 '15 at 19:19

score 0 · Answer 2 · edited Mar 17 '17 at 10:45

You can generate such sequence using a Linear congruential generator. X0 is the seed (or the index of the permutation if you wish). m should be equal to N+1. Select c and a to assure full period length (as described in the section 'period length' in the link above). This will give you a one-to-one mapping with size N.

To restore the index, you can crack the LCG using a small number of consecutive pseudo-random numbers from the series, which is not too hard. Of course you can keep m, a and c and save the trouble.

For more secure methods look at David Eisenstat's comment. You'll need only the secret key to restore the index. On the downside, if you'll use a standard FPE, N would have to be 2^x-1 (e.g. 2^128-1).

score 0 · Answer 3 · edited May 23 '17 at 12:00

1 to generate a pseudo random shuffle, you could use Fisher-Yates algo:

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

What distribution do you get from this broken random shuffle?

for (int i = tickets.Length - 1; i > 0; i--)
{
int n = random(i + 1);
Swap(tickets[i], tickets[n]);
}

beware of not using the "wrong" algorithm (he has bias).

You will get the permutation, then the inverse permutation.

2 Problem comes with the randomness of the shuffle.

As there is 10000000 ! permutations, you should have a very big size of seed

Then problem is in the random generator. standard ones are about 32 bits, perhaps a little more, but far from 10000000!

you should see at something like fortuna :

https://en.wikipedia.org/wiki/Fortuna_%28PRNG%29

Reversibly shuffle a set of a million numbers

3 Answers3