0
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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

Note that calling your construction an "RNG" is a bit of a misnomer, it's really a linear transformation of a (pseudo)random number or alternatively can be viewed as a masking of a secret (see additive secret sharing).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.