# Is there a Pseudo Random Permutation Generator that can output all values of the length of N

Is there a pseudo random permutation generator that produces all permutation of any bit length of the plaintext (this may not be clear, please let me know and I will explain). It must be fast, and does not hold numbers in memory.

This is a permutation of (1) (1)

This is a permutation of (1,2) (2,1)

This is a permutation of (1,2,3) (1,3,2) (2,3,1) (2,1,3) (3,1,2) (3,2,1) n!

Note* the above is not in a pseudo random order and not a complete set that I am looking for.

This is a pseudo random permutation with replacements that I am looking to duplicate with a generator of any size.

PRP of (1,2,3) with replacements

(1,1,1)(3,3,3)(2,3,3)(1,1,3)(3,3,2)(2,3,1)(2,2,2)(1,3,3)(3,2,3)(2,1,2)(1,2,2)(3,1,3)(1,1,2)(3,3,1)(2,3,2)(2,2,1)(1,3,2)(3,2,1)(2,1,1)(1,2,3)(3,1,1)(2,2,3)(1,3,1)(3,2,2)(2,1,3)(1,2,1)(3,1,2) N^N

If one does exist could you please post its name, if possible.

If it does not exist could you expound as to the reason why, if it is against a known proof, or it has simply not been made, yet.

The question here is very similar but it needs to be with replacements.

https://math.stackexchange.com/questions/3521660/invertible-pseudo-random-permutation-function

What would it mean if it could be made. Meaning given the length of any plaintext if that order and length is your first permutation of group g than all permutation after that would be your subgroup permutations. Given that the key length that produces the permutation is not an issue (I would be glad to explain this as well).

Another way of writing this would be. What program would generate all permutations of a given string with replacement? The given string is the complete message source or file to encrypt of any size. It will probably be recursive. Once all permutations are calculated it should loop back to the original permutation which is the file.

• Do you mean like maximum length LFSR that output all except all-zero state? Of course, it is not PRP. May 30, 2020 at 17:44
• I understand a LFSR function. I mean if your plain text is n, the output of the PRP generator would be all permutation of n^n including 0, the first permutation being your plaintext. Not a shuffle but one that will output repeating integers. If your plaintext is 4 bits (1,1,1,0) 14 , the generator will produce in a random order all 4 bit permutations using 14 as the group and the following subgroups the complete permutations of 4 bits. But it must also accommodate any file size. May 30, 2020 at 18:16
• Meant to say "produce a pseudo random order of all permutation 4 bits in length. May 30, 2020 at 18:35
• still unclear. what is file size? what the heck is 14 as a group? what is “permutations after that”? use mathematical notation to write a clear question. and why arent LFSRs enough for what you seem to want? May 30, 2020 at 22:38
• I think what you're asking for goes against the permutation being indistinguishable from a random one given that the expected order is way below the number of all possible permutations. May 31, 2020 at 11:47

Use any true random permutation generator that relies on random input. Then replace the random input with the output of a PRNG primitive.

– Nic
Jun 2, 2020 at 16:57
• I like the mapping solution. It would have to be a pseudo random permutation generator to inverse the operation. Then replace the seed input for the prp with the value of the file, or blocks of the file. Jun 3, 2020 at 1:06

You've probably noticed that these combinations are just the numbers 0...N^N-1 written out in base N. (0,0,0), (0,0,1), ..., (2,2,2) is really just counting from 0 to 26, and there's a simple and natural bijection there. So one way of generating them in a pseudo-random order is to shuffle 0-26 with a PRNG in the standard way and use that.

As N gets large, that approach is impractical - you can't hold an array of length N^N in memory. There's the standard trick to use the invertibility of a block cipher to iterate through 0...2^n in pseudorandom order using $$E_k(i)$$, so if N^N is close to 2^n you can use that.

If N gets larger still, you can just use a PRNG to fill in the tuple values directly. You're only probabilistically guaranteed not to repeat, but I can't see a scenario where you sample enough values to detect the difference.

• Thanks for the visual of Heap's algorithm. It needs to have replacements though and pseudo randomness to the permutations. Jun 5, 2020 at 3:23
• @JonathanHutton, please use a mathematical definition of exactly what you require Jun 6, 2020 at 22:12
• This is what I am looking for in python, but the iterations in the output need to be in a pseudo random order. The first iteration is a block or entire bitstream of the file. from itertools import combinations def perm(chars, length): s = ''.join([c * length for c in list(chars)]) combs = combinations(s, length) combs = [''.join(comb) for comb in combs] combs = list(set(combs)) combs.sort() return combs for x in perm('012', 4): print x Output: 0000 0001 0002 0011 0012 0022 0111 0112 0122 0222 1111 1112 1122 1222 2222 Jun 7, 2020 at 0:27
• I mean I don't understand why your sample output list doesn't cover all combinations. Did you intentionally omit 1000? And it's also unclear to me how "the first iteration is the entire bitstream of the file" is represented in the list. 0000 is the entire file? How is 0001 a permutation of that? Jun 15, 2020 at 15:58
• Just encrypt the values 0..2^n-1 Jun 18, 2020 at 15:43