Reproducable pseudorandom permutation

Question

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?

Answer 1

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$.