Geodesic
On properties of the Klimov--Shamir generator of pseudorandom numbers
Diskretnaya Matematika, Tome 23 (2011) no. 1, pp. 51-71.

Voir la notice de l'article provenant de la source Math-Net.Ru

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$. 
@article{DM_2011_23_1_a4,
     author = {S. V. Rykov},
     title = {On properties of the {Klimov--Shamir} generator of pseudorandom numbers},
     journal = {Diskretnaya Matematika},
     pages = {51--71},
     publisher = {mathdoc},
     volume = {23},
     number = {1},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2011_23_1_a4/}
}
TY  - JOUR
AU  - S. V. Rykov
TI  - On properties of the Klimov--Shamir generator of pseudorandom numbers
JO  - Diskretnaya Matematika
PY  - 2011
SP  - 51
EP  - 71
VL  - 23
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2011_23_1_a4/
LA  - ru
ID  - DM_2011_23_1_a4
ER  - 
%0 Journal Article
%A S. V. Rykov
%T On properties of the Klimov--Shamir generator of pseudorandom numbers
%J Diskretnaya Matematika
%D 2011
%P 51-71
%V 23
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2011_23_1_a4/
%G ru
%F DM_2011_23_1_a4
S. V. Rykov. On properties of the Klimov--Shamir generator of pseudorandom numbers. Diskretnaya Matematika, Tome 23 (2011) no. 1, pp. 51-71. http://geodesic.mathdoc.fr/item/DM_2011_23_1_a4/

[1] Anashin V. S., “Ravnomerno raspredelennye posledovatelnosti tselykh $p$-adicheskikh chisel”, Matematicheskie zametki, 55:2 (1994), 3–46 | MR | Zbl

[2] Anashin V. S., “Uniformly distributed sequences over $p$-adic integers”, Proc. Intern. Conf. “Number theoretic and algebraic methods in computer science”, eds. van der Poorten A. J., Shparlinsky I., Zimmer H. G., World Scientific, Singapore, 1995, 1–18 | MR | Zbl

[3] Anashin V. S., “Uniformly distributed sequences in computer algebra, or how to construct program generators of random numbers”, J. Math. Sci., 89:4 (1998), 1355–1390 | DOI | MR | Zbl

[4] Anashin V. S., “Ravnomerno raspredelennye posledovatelnosti tselykh $p$-adicheskikh chisel”, Diskretnaya matematika, 14:4 (2002), 3–64 | MR | Zbl

[5] Anashin V. S., “Ergodic transformations in the space of $p$-adic integers”, AIP Conf. Proc., 826 (2006), 3–24 | DOI | MR | Zbl

[6] Anashin V. S., Khrennikov A. Yu., Applied algebraic dynamics, de Gruyter, Berlin, 2009 | MR | Zbl

[7] Bénony V., Recher F., Wegrzynowski E., Fontaine C., “Cryptanalysis of a particular case of Klimov–Shamir Pseudo-Random Generator”, Lect. Notes Computer Sci., 3486, 2004, 313–322

[8] Eichenauer-Herrmann`J., “Quadratic congruential pseudorandom numbers: Distribution of triples”, J. Comput. Appl. Math., 62 (1995), 239–253 | DOI | MR | Zbl

[9] Eichenauer-Herrmann J., “Quadratic congruential pseudorandom numbers: Distribution of lagged pairs”, J. Comput. Appl. Math., 79 (1997), 75–85 | DOI | MR | Zbl

[10] Emmerich F., “Equidistribution properties of quadratic congruential pseudorandom numbers”, J. Comput. Appl. Math., 79 (1997), 207–214 | DOI | MR | Zbl

[11] Klimov A., Applications of T-functions in cryptography, PhD Thesis, Dept. Appl. Math. Computer Sci., Weizmann Institute of Science, Rehovot, 2005

[12] Klimov A., Shamir A., “A new class of invertible mappings”, Lect. Notes Comput. Sci., 2523, 2002, 470–483 | Zbl

[13] Klimov A., Shamir A., “Cryptographic applications of T-functions”, Lect. Notes Comput. Sci., 3006, 2003, 248–261 | MR

[14] Klimov A., Shamir A., “New cryptographic primitives based on multiword T-functions”, Lect. Notes Comput. Sci., 3017, 2004, 1–15 | Zbl

[15] Klimov A., Shamir A., “New applications of T-functions in block ciphers and hash functions”, Lect. Notes Comput. Sci., 3557, 2005, 18–31 | Zbl

[16] Molland H., Helleseth T., “A linear weakness in the Klimov–Shamir T-function”, Proc. ISIT' 2005, IEEE, 2005, 1106–1110

[17] Molland H., Helleseth T., “Linear properties in T-functions”, IEEE Trans. Inform. Theory, 52:11 (2006), 5151–5157 | DOI | MR

[18] Wang J.-S., Qi W.-F., “Linear equation on polynomial single cycle T-functions”, Lect. Notes Comput. Sci., 4990, 2008, 256–270 | MR | Zbl