1
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Do you mean like maximum length LFSR that output all except all-zero state? Of course, it is not PRP. $\endgroup$
    – kelalaka
    May 30, 2020 at 17:44
  • $\begingroup$ 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. $\endgroup$
    – Jonathan Hutton
    May 30, 2020 at 18:16
  • $\begingroup$ Meant to say "produce a pseudo random order of all permutation 4 bits in length. $\endgroup$
    – Jonathan Hutton
    May 30, 2020 at 18:35
  • $\begingroup$ 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? $\endgroup$
    – kodlu
    May 30, 2020 at 22:38
  • 1
    $\begingroup$ 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. $\endgroup$
    – SEJPM
    May 31, 2020 at 11:47

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Was this the answer you were looking for? $\endgroup$
    – Nic
    Jun 2, 2020 at 16:57
  • $\begingroup$ 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. $\endgroup$
    – Jonathan Hutton
    Jun 3, 2020 at 1:06
  • $\begingroup$ I finally have this project codded in python. Compression with this is unique by introducing patterns into the transformed data set without increasing the file size. This results in a higher level of compression without sacrificing data integrity. Lossless Reversibility: An important feature is its ability to maintain lossless reversibility. The reversibility aspect is crucial in applications where data integrity and fidelity are of utmost importance, such as scientific research, data analysis, and archival purposes. Used with Diffie-hellman key exchange. $\endgroup$
    – Jonathan Hutton
    Jul 2 at 15:58
  • $\begingroup$ Now rigorous testing begins $\endgroup$
    – Jonathan Hutton
    Jul 2 at 15:58
1
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Thanks for the visual of Heap's algorithm. It needs to have replacements though and pseudo randomness to the permutations. $\endgroup$
    – Jonathan Hutton
    Jun 5, 2020 at 3:23
  • $\begingroup$ @JonathanHutton, please use a mathematical definition of exactly what you require $\endgroup$
    – kodlu
    Jun 6, 2020 at 22:12
  • $\begingroup$ 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 $\endgroup$
    – Jonathan Hutton
    Jun 7, 2020 at 0:27
  • 2
    $\begingroup$ 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? $\endgroup$
    – bmm6o
    Jun 15, 2020 at 15:58
  • 1
    $\begingroup$ Just encrypt the values 0..2^n-1 $\endgroup$
    – bmm6o
    Jun 18, 2020 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.