Exponentiation of Linear Congruential Generators

Question

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

Answer 1

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.