# Reproducable pseudorandom permutation

I there a way to calculate two similar pseudorandom periodic sequences by exchanging some sort of initial value and generator polynomial?

Like a linear-feedback shift register but with a finite field of numbers and each number occurring only once in the sequence?

• The terms "pseudorandom permutation" and "finite field" are quite well defined in a crypto context. Are they meant in this sense in the question? What exactly is meant by "similar"? What is there in the question that is not adequately performed by a pseudo-random number generator instantiated twice with a common shared secret seed?
– fgrieu
Jun 20 '18 at 5:15
• @fgrieu A prng is what I am looking for. But I couldn't figure out how I achieve a specific period. In my case i want the numbers from 1 to 75 in a random periodic order. What seed do i use? And if a lfsr is used, what should the polynomial be? Same for Xorshift Jun 20 '18 at 20:46

I'm reading the question as asking for a public pseudorandom number generator seeded by a key $K$, which will output integer values $r_j$ in a specified range $[a,b]$ (here, [1 to 75]) pseudo-randomly according to the key, then cycle after having reached each of them all exactly once. Add that the next output is a function $F_K$ of the previous (rather of some internal state).

All we need is a pseudo-random permutation $P_K$ of the set $[0,n-1]$ with $n=b+1-a$, and it's inverse ${P_K}^{-1}$, from which we define $$r_{j+1}=F_K(r_j)=P_K({P_K}^{-1}(r_j-a)+1\bmod n)+a$$

In other words, to move to the next number, we

• subtract $a$
• apply the inverse permutation ${P_K}^{-1}$
• add one, and if the result is $n$ replace it by zero
• apply the permutation $P_K$
• add $a$

This essentially is applying $P_K$ to a cyclic counter, and an offset. The first two steps are unnecessary if we can keep memory of the counter's state.

Constructing pseudorandom permutation $P_K$ is a classic problem of Format Preserving Encryption. One option is a table built with a Fisher-Yates shuffle. Another is to use a block cipher and cycling:

• compute $w=\lceil\log_2(n)\rceil$, that is the number of bits in $n-1$
• build a $w$-bit block cipher $C$ with key $K$ (assimilate up-to $w$-bit integers to $w$-bit bitstrings per e.g big-endian convention).
• compute $y=P_K(x)$ as
• $y\gets x$
• $y\gets C_K(y)$, that is encrypt $y$ with key $K$ per block cipher $C$
• if $y\ge n$, go to the previous step
• compute $x={P_K}^{-1}(y)$ as
• $x\gets y$
• $x\gets{C_K}^{-1}(x)$, that is decrypt $x$
• if $x\ge n$, go to the previous step

The encryption and decryption loops always terminate, and are executed few times on average.

To construct permutation $C_K$, we can use a symmetric Feistel cipher, except we want to use $\displaystyle w=\min\left(2\left\lceil\frac{\log_2(n+1)}2\right\rceil,4\right)$ which will ensure that $w$ is even, that the Feistel cipher is not so small as to be degenerate, and that in the case where $n$ is a power of four we use a slightly larger block cipher to compensate for it being an even permutation.

Another option is a near-symmetric Feistel cipher when $w$ is odd, and addition instead of XOR for the round loop (fixing the even permutation thing), which let us use $w=\min(\lceil\log_2(n)\rceil,4)$.

If we are not in a hurry, the Feistel round function for round $i$ can be $F_{i,K}(L)=\operatorname{PRF}_K(i\mathbin\|L)$ truncated to $\lceil w/2\rceil$-bit, for some PRF such as HMAC-SHA-256.

In any case (and especially if we use a simpler/weaker round function), we should use a lot of rounds for small $w$, perhaps $\lceil 6+60/w\rceil$.