|
This article is cited in 1 scientific paper (total in 1 paper)
On properties of the Klimov–Shamir generator of pseudorandom numbers
S. V. Rykov
Abstract:
The pseudorandom number generator (PRNG) based on the transformation
$$
F_c(x)=x+(x^2\vee c)\pmod{2^n}
$$
was suggested by Klimov and Shamir in 2002. The function $F_c(x)$ is transitive modulo $2^n$ if and only if either $c\equiv5\pmod8$ or $c\equiv7\pmod8$.
We consider properties of the distribution of the pairs $(x_i, F_c(x_i))$ for various $c\in\mathbf Z/2^n\mathbf Z$ and demonstrate that their statistical properties are unsatisfactory, most notably for $c\geq2^{n/3}$.
We show that in the case $n=32$, at most 9 distinct pairs $(x_i, F_c(x_i))$ are needed to find the value of $c$ with probability $P\geq0,999$.
Received: 16.04.2010
Citation:
S. V. Rykov, “On properties of the Klimov–Shamir generator of pseudorandom numbers”, Diskr. Mat., 23:1 (2011), 51–71; Discrete Math. Appl., 21:2 (2011), 179–202
Linking options:
https://www.mathnet.ru/eng/dm1130https://doi.org/10.4213/dm1130 https://www.mathnet.ru/eng/dm/v23/i1/p51
|
|