Exponentiation of Linear Congruential Generators

Linear Congruential Generators, that class of pseudo random generators with recursive rule

$$x_{n+1}\equiv a\cdot x_n +b\ \ (\mod m)$$, $$a,b,x_n\in Z/mZ$$, $$m,n\in N$$

are considered inapt for use in cryptography, as the constants $$a$$, $$b$$ may by deduced from a small set of outputs $$x_n$$. Now, when you choose $$m=p-1$$ for some odd prime $$p$$, the sequence $$(x_n)_{n\in N}$$ may live as exponents of some generator $$g$$ of the multiplicative cyclic group $$Z/pZ^*$$, as $$y_n:=g^{x_n}, n\in N$$:

$$y_{n+1}\equiv g^{x_{n+1}}\equiv g^{a\cdot x_n+b}\equiv (g^{x_n})^a\cdot g^b\equiv y_n^a\cdot g^b\ (\mod p)$$

This is an equivalent power series.

Equal distribution comes with maximum period. Conditions for maximum period $$m$$ of the sequence $$(y_n)_{n\in N}$$ are given by Knuth's Theorem

1. $$gcd(m,b)=1$$
2. For prime decomposition $$m=:\prod p_i^{\alpha_i}$$ and all prime factors $$p_i$$: $$\ \ \ p_i/(a-1)$$
3. $$m\equiv 0\ (\mod 4) \implies a-1\equiv 0\ (\mod 4)$$

As $$m=p-1$$ is even and there are very few primes with shape $$p=2^k+1$$, the easiest common composition of $$p-1$$ from primes would be $$p-1=2^k\cdot p'$$, $$k\geq 1$$ with $$p'$$ another prime.

According to 2nd condition smallest choice of $$a$$ is by $$a-1=2\cdot p'$$. To avoid trivial case $$a-1=m$$, $$k\geq 2$$ is necessary. With this we run into 3rd condition, so that $$a-1$$ has at least two times the factor $$2$$. Again, avoidance of the trivial case requires $$k\geq 3$$.

Now, a prime pair $$(p,p')$$ fitting the linear equation $$p=8p'+1$$ allows non-trivial choice $$a-1=4p'$$ and with this the power series $$(y_n)$$ may have maximum period $$m$$.

Question: As we have 3 hidden parameters $$g, g^a,g^b$$ and finding logarithms in multiplicative groups is considered difficult, can the random sequence $$(y_n){n\in N}$$ be considered secure for use in cryptography; are there better choices for constant $$a$$?

EDIT $$g$$ is actually not important as parameter, as we raise powers to $$a$$, where in addition $$p$$ is not known from the output, i.e. the unknown parameters are $$(p, a, g^b)$$ .

Several observations:

• Keeping $$a$$ secret is crucial. If the adversary knows that and sees $$y_i, y_{i+1} = (y_i^a) \cdot g^b$$, he can compute $$g^b = y_{i+1} \cdot y_i^{-a}$$, and then go ahead and compute the rest of the sequence.

You may say "but we assume the discrete log is hard" - however, you also suggest $$p = 8p'+1$$ and $$a-1 = 4p'$$, that is, $$a = (p+1)/2$$; that would make recovering $$a$$ easy.

• The real acid test for CSRNGs is whether an adversary (who knows everything except the secret values) can distinguish the output of the CSRNG from a truly random sequence with the same probability distribution.

Now, if $$g$$ is a generator of the entire group, it turns out to be easy to determine whether $$x$$ is even or odd from $$g^x \bmod p$$. With your generator, this lower bit will always alternate between 'even' and 'odd' with successive $$y_i$$ values, hence making it distinguishable.

What we usually do when using finite fields is to deliberately work in a prime-sized subgroup (which obviously cannot be the entire $$\mathbb{Z}_p^*$$ group); that prevents the attacker recovering any information of $$x$$ from $$g^x$$.

Of course, doing this reduces the size of the period - however, as long as the period is longer than, say, $$2^{64}$$ (which is far larger than the number of outputs we would practically generate), it is large enough.

Putting this together, I would suggest this similar alternate idea:

• Drop $$b$$; instead, use a simple $$y_{i+1} = (y_i)^a \bmod p$$ generator.

• Select a prime $$p = kp' + 1$$, where $$p'$$ is a Sophie-Germain prime, that is, $$(p'-1)/2$$ is also prime. $$p$$ should be large enough to make the discrete log problem hard (e.g. at least 2048 bits), and $$p'$$ should be large enough to make the discrete log problem within the subgroup hard (e.g. at least 256 bits; however, it can be much larger, for example, $$k=2$$ is practical).

• Select $$y_0$$ to be a member (other than 1) of the subgroup of size $$p'$$

• Select $$a > 0$$ to be a random value for which $$a^{(p'-1)/2} \bmod p' \ne 1$$ (which will be true for half the possible values of $$a$$)

This will generate a sequence of period $$p'-1$$ (which is plenty long); see Theorem 3.2.1.2.C from Knuth. And, because $$a$$ can be selected from a large number of possibilities, it cannot be guessed.

Now, neither version would be a practical CSRNG (doing a modular exponentiation per output is quite slow - we have much better CSRNGs); I believe it does address your question.

• Thank you, accurate response! So, you would drop equal distribution for better hiding a. Will consider this. Not sure, how p and thus a is easily detected: Usually you truncate the output some 2^n range and there are a lot of primes between 2^n+1 and 2^(n+1)-1 Jan 4, 2022 at 17:01
• @SamGinrich: well, if $p$ is also secret, that changes things considerably. Of course, if $p$ is an $n+1$ bit prime, and you truncate to $n$ bits, those bits would not be even distributed (unless you were careful to select a $p$ just over $2^n$ or just under $2^{n+1}$ Jan 4, 2022 at 17:23
• Sorry, my question was not correct concerning the unknown variables, added an EDIT. Jan 4, 2022 at 18:39