# Does there exist a CSPRNG that does not require generating prime numbers, but also does not depend on any other cryptographic primitives?

The following excerpt is taken from the “Cryptographically secure pseudorandom number generator” article on Wikipedia:

CSPRNG designs are divided into three classes:

1. those based on cryptographic primitives such as ciphers and cryptographic hashes,
2. those based upon mathematical problems thought to be hard, and
3. special-purpose designs.

The last often introduces additional entropy when available and, strictly speaking, are not "pure" pseudorandom number generators, as their output is not completely determined by their initial state.

I am interested in the question: does there exist a cryptographically secure pseudorandom bits generator that satisfies all of the three following requirements?

1. It belongs to class 2 according to the classification described above. Assuming that CSPRNG uses multiple iterations of some function $$F$$ to generate the output of the desired length, this requirement implies that the description of $$F$$ does not mention different versions of the function that are explicitly constructed for different word sizes. Examples of algorithms that satisfy this requirement: Blum Blum Shub, Blum–Micali algorithm;
2. It does not require generating prime numbers (or testing primality of any number);
3. If the algorithm uses any precomputed values, then there should be an open algorithm that demonstrates how these values are generated (with the detailed explanation of why it is required to use these values and why other values might impact the desired properties of the output).
• Does 2 prevent using a large public provable prime?
– fgrieu
Nov 2 '18 at 9:01
• Unless you define stream cipher tobe a CSPRNG it will be very hard to find a CSPRNG that isn't at least based on one. A stream cipher basically is a CSPRNG that uses a single fixed seed - the key. Nov 2 '18 at 11:51
• @fgrieu: The dependence on primality is definitely undesirable, but I can answer "No" to this question, with the following clarification: the public prime should be replaceable by any other prime of the same (or larger) length. Additionally, there should be no "weak"/"bad" seeds for the algorithm. If you know such algorithm, you can include it in the answer. Nov 3 '18 at 10:41
• I've now read this question multiple times. I'm however more and more curious behind the reason behind the question. What are you trying to accomplish? Nov 3 '18 at 19:05

Yes, at least for a definition of "based on a particular mathematical problem" allowing the problem to be breaking the generator!

Restricting to constructions that can be efficiently implemented, one of the simplest conjecturally Cryptographically Secure Pseudo Random Number Generator in the literature is the Alternating Step Generator, proposed by Christoph G. Günther: Alternating step generators controlled by de Bruijn sequences, in proceedings of Eurocrypt 1987. Its best known cryptanalysys is by Shahram Khazaei, Simon Fischer, and Willi Meier: Reduced Complexity Attacks on the Alternating Step Generator, in proceedings of SAC 2007

The ASG consists of three Linear Feeedback Shift Registers, which have a well known reduction to arithmetic in $$GF(2^k)$$. To produce a bit:

• according to it's low-order bit, advance LFSR0 or LFSR1
• output the XOR of the low order bits of LFSR0 and LFSR1

To choose the (public) LFSR parameters, select the desired security parameter $$n$$. Then pick three binary primitive polynomials of degree $$n_0$$, $$n_1$$, $$n_2$$ with $$\alpha\,n so that $$2^{n_0}-1$$, $$2^{n_1}-1$$, $$2^{n_2}-1$$ are pairwise coprime. The best known attacks are for $$\alpha=\frac32$$, but $$\alpha=2$$ is more reasonable.
Note: in the initial exposition, LFSR2 is modified to generate a de Bruijn sequence, that is the output sequence has an extra zero inserted after $$n_2−1$$ consecutive zeroes. But this detail makes no cryptanalytic difference, since that point in the sequence is reached with negligible probability for $$n_2$$ large enough to thwarts attacks guessing the state of a single LFSR.

Per comment: Checking if two integers are pairwise coprime does not require "testing primality of any number". It can be done with Euclid's algorithm (or others that efficiently compute the Greatest Common Divisor), and checking that the GCD is 1. Also, parameter choice is performed just once, then we can have multiple instances of the generator using these parameters and different keys.

Example, with the help of the compact table of primitive binary trinomials compiled by Jörg Arndt (and a caveat: I have no clear-cut argument that using trinomials leaves the ASG secure): $$n=192$$, $$n_0=385$$, $$n_1=386$$, $$n_2=393$$ and

• LFSR0: $$x^{385}+x^{142}+1$$
• LFSR1: $$x^{386}+x^{83}+1$$
• LFSR2: $$x^{393}+x^{91}+1$$
$$n_0$$ and $$n_1$$ are minimal given the choice $$n=192$$ and $$\alpha=2$$. $$n_2\in\{387, 388, 389, 392\}$$ was not used due to absence of trinomials. $$n_2=390$$ was not used because $$\gcd(2^{386}-1,2^{390}-1)=3\ne1$$. $$n_2=391$$ was not used so that the center terms (otherwise minimal) are farther than 64-bit from each side (in hope to ease constant-time software implementation).

The key is the initial state of the three LFSRs (with say the high-order bit of each LFSR set to the complement of the XOR of the others in order to ensure non degenerate states). This is an inconveniently long key, of $$n_0+n_1+n_2-3>3\,\alpha\,n$$ bits, and the security conjecture is for uniformly random independent key bits.

Some formal definitions of a CSPRNG (and practical robustness) require it's key to be of size equal to the security parameter. If that's wanted, coming up with a safe initialization procedure starting from a key of $$n$$ bits is non-trivial: we need some auxiliary CSPRNG to expand from $$n$$ to $$n_0+n_1+n_2-3$$ bits (from 192 to 1159 in the above example).

• Regarding the "pairwise coprime" property — doesn't this contradict the second requirement? Nov 3 '18 at 10:28