2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – fgrieu Jun 20 '18 at 5:15
  • 1
    $\begingroup$ @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 $\endgroup$ – Noah Hütter Jun 20 '18 at 20:46
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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