Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
The inversive congruential generator over the prime field $k=Z/pZ$ is given by the iterations of the map $x\mapsto a/x+b$ if $x\neq 0$ or $b$ if $x=0$. One can choose $a,b$ in $k$ such that the orbit length of the iteration is exactly $p$. My question is very simple:
Is the Inversive Congruential Generator actually used in Cryptography? Is there any known attack against it?
The inversive congruential generator is not commonly used in cryptography. Its basic description, in fact, makes it entirely unsuitable for it—once you know a single value of $x$, you can predict the remainder of the sequence, which is something a secure pseudorandom generator should not allow.
To avoid the above trivial attack, you could truncate the output to, say, half of the bits of $x$. But the truncated inversive generator is also predictable by more elaborate means, as long as you truncate fewer than half the bits.
To top it off, inversion modulo $p$ is a very slow operation, which makes this generator very inefficient. So even for non-cryptographic purposes this is not a good generator to use.
There are some inconsistencies with the arguments in the above answer.
You want to compare ICG with a cryptographically secure pseudorandom number generator.
Consider the cryptographically secure Blum Blum Shub (it should be one of the best, according to the abstract of this paper for example: https://pdfs.semanticscholar.org/8074/d7df08e2bcbe8f433ec368a5d84c8061f9be.pdf )
The pseudorandom number generator is simply given by $x_n= x_{n-1}^2$ modulo $M=pq$ that is the product of two large primes: see https://en.wikipedia.org/wiki/Blum_Blum_Shub for a quick introduction.
Observing even one iteration $x_n$ results in knowing exactly all the other terms of the sequence. The whole point is that only the "least significant bits" (notice: not "the most significant bits", in contrast with the setting of the attack mentioned in Samuel's answer) are sent or even only the bit parity of the element in the sequence (see again https://en.wikipedia.org/wiki/Blum_Blum_Shub for a reference)
Notice that this strategy of sending only the bit parity of $x_n$ is directly applicable to the Inversive Congruential Generator (ICG) and then the problem of predicting the sequence looks immediately untreatable (of course, if $a,b$ are hidden).
Concerning the computational cost: the ICG costs essentially one inversion mod p (notice that if in the definition of the ICG one chooses $a,b$ "very small", the multiplication of $a$ and $1/x$ can be counted as an addition). On the other hand, Blum Blum Shub costs one multiplication. The ratio of the cost of an inversion and a multiplication is only $O(log log log(p))$, which make the two generators very similar from a computational point of view.
On the other hand, ICG has the advantage of covering the entire space $\mathbb F_p$ is $a,b$ are suitably chosen.
That is never possible for the Blum Blum Shub generator: modulo $M=pq$, you will never get an element multiple of $p$ and also even the multiplicative group $(\mathbb Z/pqZ)^*$ (meaning the invertible elements modulo $pq$) is never cyclic for odd $p,q$.
