Score:2

Exponentiation of Linear Congruential Generators

us flag

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

Score:2
my flag

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.

us flag
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
poncho avatar
my flag
@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}$
us flag
Sorry, my question was not correct concerning the unknown variables, added an EDIT.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.