# Custom linear random number generator

I've made an implementation of a linear RNG. It has two constants: b and p. Every time new value of a is generated. Every time a value of x is also generated secretly.

The generator computes the number c as following: (a * x + b) mod p == c

All values of a b x p are 256-bit numbers and additionaly p is prime. I assume the attacker knows the value of p and knows a bunch of (eg. 10) values of ai and ci computed on the generator as following:

(a1 * x1 + b) mod p == c1

(a2 * x2 + b) mod p == c2

and so on. Values of x remain unknown to the attacker and are rather cryptographically random.

My question is: when the attacker has these pairs of known values is it possible for him to calculate the value of b? If yes, how?

What you're essentially computing here is a universal hash. Viewed this way, you have the guarantee that $$a_i \cdot x_i \pmod p$$ is distributed uniformly over the set $$\{0,1,2, ..., p-1\}$$ when $$a_i \neq 0$$. If the $$x_i$$'s are pseudorandom and independent (not sure if that's what you mean by "rather cryptographically random") then $$a_i \cdot x_i$$ will be pseudorandom over $$\{0,1,2, ..., p-1\}$$. You can then view this as a pseudorandom element of $$\mathbb{Z}_p$$ masking $$b$$. In other words, provided the $$x_i$$'s remain private, they should all (computationally) hide $$b$$. Moreover, if the $$a_i$$'s a public (known by the adversary), they add nothing in terms of security: $$x_i + b$$ is distributed identically to $$a_i \cdot x_i + b$$ when $$a_i \neq 0$$.
However, to formally prove this, you would need to show that if there exists an efficient distinguisher between $$a_ix_i + b$$ and a random element of $$\mathbb{Z}_p$$, then there also exists an efficient distinguisher for your RNG generating the $$x_i$$'s (a contradiction, assuming the RNG generating $$x_i$$'s is secure).