Is there an algorithm that uses prime numbers in symmetric encryption?

Question

It is well known that there are algorithms developed for asymmetric encryption that take advantage of the fact that the product of two prime numbers cannot be factored in polynomial time. Usually, prime numbers are not used in symmetric encryption. Do you know of any algorithm where prime numbers are used at any stage of symmetric encryption?

Answer 1

There are a few such systems. A few excerpted below from a related mathoverflow question:

The Blum-Blum-Shub deterministic random bit generator: Let $N = pq$ be the product of two large safe primes, and consider the sequence defined by $x_{i+1} = x_i^2 \pmod{N}$, where $x_0$ is the random seed (which can be any value in $(\mathbb{Z}/N\mathbb{Z})^\times\setminus\{1\}$). After each squaring, you extract some of the bits of $x_i$ to form the pseudorandom stream. The security of the bit generator - that is, the indistinguishability from a uniform random stream - can be reduced to number-theoretic problems. The idea is that if you only take the least significant bit of $x_i$ (or up to $O(\log\log N)$) at each iteration, then breaking this generator reduces to solving the Quadratic Rediduosity Problem $\bmod N$.

See the accepted answer the linked question for a description of Carter-Wegman message authentication based on primes.