## Predicting nonlinear pseudorandom number generators

HTML articles powered by AMS MathViewer

- by Simon R. Blackburn, Domingo Gomez-Perez, Jaime Gutierrez and Igor E. Shparlinski PDF
- Math. Comp.
**74**(2005), 1471-1494 Request permission

## Abstract:

Let $p$ be a prime and let $a$ and $b$ be elements of the finite field $\mathbb {F}_p$ of $p$ elements. The inversive congruential generator (ICG) is a sequence $(u_n)$ of pseudorandom numbers defined by the relation $u_{n+1} \equiv a u_n^{-1} + b \bmod p$. We show that if sufficiently many of the most significant bits of several consecutive values $u_n$ of the ICG are given, one can recover the initial value $u_0$ (even in the case where the coefficients $a$ and $b$ are not known). We also obtain similar results for the quadratic congruential generator (QCG), $v_{n+1} \equiv f(v_n) \bmod p$, where $f \in \mathbb {F}_p[X]$. This suggests that for cryptographic applications ICG and QCG should be used with great care. Our results are somewhat similar to those known for the linear congruential generator (LCG), $x_{n+1} \equiv a x_n + b \bmod p$, but they apply only to much longer bit strings. We also estimate limits of some heuristic approaches, which still remain much weaker than those known for LCG.## References

- M. Ajtai, R. Kumar and D. Sivakumar, ‘A sieve algorithm for the shortest lattice vector problem’,
*Proc. 33rd ACM Symp. on Theory of Comput.*, ACM, 2001, 601–610. - P. H. T. Beelen and J. M. Doumen,
*Pseudorandom sequences from elliptic curves*, Finite fields with applications to coding theory, cryptography and related areas (Oaxaca, 2001) Springer, Berlin, 2002, pp. 37–52. MR**1995326** - S. R. Blackburn, D. Gomez-Perez, J. Gutierrez and I. E. Shparlinski, ‘Predicting the inversive generator’,
*Proc. 9th IMA Intern. Conf on Cryptography and Coding*, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin,**2898**(2003), 264–275. - S. R. Blackburn, D. Gomez-Perez, J. Gutierrez and I. E. Shparlinski, ‘Reconstructing noisy polynomial evaluation in residue rings’, J. of Algorithms (to appear).
- Dan Boneh, Shai Halevi, and Nick Howgrave-Graham,
*The modular inversion hidden number problem*, Advances in cryptology—ASIACRYPT 2001 (Gold Coast), Lecture Notes in Comput. Sci., vol. 2248, Springer, Berlin, 2001, pp. 36–51. MR**1934514**, DOI 10.1007/3-540-45682-1_{3} - Joan Boyar,
*Inferring sequences produced by pseudo-random number generators*, J. Assoc. Comput. Mach.**36**(1989), no. 1, 129–141. MR**1072416**, DOI 10.1145/58562.59305 - Joan Boyar,
*Inferring sequences produced by a linear congruential generator missing low-order bits*, J. Cryptology**1**(1989), no. 3, 177–184. MR**1007218**, DOI 10.1007/BF02252875 - Gustavus J. Simmons (ed.),
*Contemporary cryptology*, IEEE Press, New York, 1992. The science of information integrity. MR**1205128** - Wun Seng Chou,
*The period lengths of inversive pseudorandom vector generations*, Finite Fields Appl.**1**(1995), no. 1, 126–132. MR**1334630**, DOI 10.1006/ffta.1995.1009 - Don Coppersmith,
*Small solutions to polynomial equations, and low exponent RSA vulnerabilities*, J. Cryptology**10**(1997), no. 4, 233–260. MR**1476612**, DOI 10.1007/s001459900030 - Don Coppersmith,
*Finding small solutions to small degree polynomials*, Cryptography and lattices (Providence, RI, 2001) Lecture Notes in Comput. Sci., vol. 2146, Springer, Berlin, 2001, pp. 20–31. MR**1903884**, DOI 10.1007/3-540-44670-2_{3} - Mary Flahive and Harald Niederreiter,
*On inversive congruential generators for pseudorandom numbers*, Finite fields, coding theory, and advances in communications and computing (Las Vegas, NV, 1991) Lecture Notes in Pure and Appl. Math., vol. 141, Dekker, New York, 1993, pp. 75–80. MR**1199823** - Alan M. Frieze, Johan Håstad, Ravi Kannan, Jeffrey C. Lagarias, and Adi Shamir,
*Reconstructing truncated integer variables satisfying linear congruences*, SIAM J. Comput.**17**(1988), no. 2, 262–280. Special issue on cryptography. MR**935340**, DOI 10.1137/0217016 - Guang Gong, Thomas A. Berson, and Douglas R. Stinson,
*Elliptic curve pseudorandom sequence generators*, Selected areas in cryptography (Kingston, ON, 1999) Lecture Notes in Comput. Sci., vol. 1758, Springer, Berlin, 2000, pp. 34–48. MR**1767726**, DOI 10.1007/3-540-46513-8_{3} - Martin Grötschel, László Lovász, and Alexander Schrijver,
*Geometric algorithms and combinatorial optimization*, 2nd ed., Algorithms and Combinatorics, vol. 2, Springer-Verlag, Berlin, 1993. MR**1261419**, DOI 10.1007/978-3-642-78240-4 - J. Gutierrez, I. E. Shparlinski and A. Winterhof, ‘On the linear and nonlinear complexity profile of nonlinear pseudorandom number generators’,
*IEEE Trans. on Information Theory*,**49**(2003), 60–64. - F. Hess and I. E. Shparlinski, ‘On the linear complexity and multidimensional distribution of congruential generators over elliptic curves’,
*Designs, Codes and Cryptography*(to appear). - Nicholas Howgrave-Graham,
*Finding small roots of univariate modular equations revisited*, Cryptography and coding (Cirencester, 1997) Lecture Notes in Comput. Sci., vol. 1355, Springer, Berlin, 1997, pp. 131–142. MR**1660500**, DOI 10.1007/BFb0024458 - Antoine Joux and Jacques Stern,
*Lattice reduction: a toolbox for the cryptanalyst*, J. Cryptology**11**(1998), no. 3, 161–185. MR**1633944**, DOI 10.1007/s001459900042 - Ravi Kannan,
*Algorithmic geometry of numbers*, Annual review of computer science, Vol. 2, Annual Reviews, Palo Alto, CA, 1987, pp. 231–267. MR**921497** - Ravi Kannan,
*Minkowski’s convex body theorem and integer programming*, Math. Oper. Res.**12**(1987), no. 3, 415–440. MR**906415**, DOI 10.1287/moor.12.3.415 - Donald E. Knuth,
*Deciphering a linear congruential encryption*, IEEE Trans. Inform. Theory**31**(1985), no. 1, 49–52. MR**786369**, DOI 10.1109/TIT.1985.1056997 - V. S. Konjagin,
*The number of solutions of congruences of the $n$th degree with one unknown*, Mat. Sb. (N.S.)**109(151)**(1979), no. 2, 171–187, 327 (Russian). MR**542556** - Hugo Krawczyk,
*How to predict congruential generators*, J. Algorithms**13**(1992), no. 4, 527–545. MR**1187200**, DOI 10.1016/0196-6774(92)90054-G - J. C. Lagarias,
*Pseudorandom number generators in cryptography and number theory*, Cryptology and computational number theory (Boulder, CO, 1989) Proc. Sympos. Appl. Math., vol. 42, Amer. Math. Soc., Providence, RI, 1990, pp. 115–143. MR**1095554**, DOI 10.1090/psapm/042/1095554 - A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász,
*Factoring polynomials with rational coefficients*, Math. Ann.**261**(1982), no. 4, 515–534. MR**682664**, DOI 10.1007/BF01457454 - D. Micciancio and S. Goldwasser,
*Complexity of lattice problems*, Kluwer Acad. Publ., 2002. - Phong Q. Nguyen and Jacques Stern,
*Lattice reduction in cryptology: an update*, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 85–112. MR**1850600**, DOI 10.1007/10722028_{4} - Phong Q. Nguyen and Jacques Stern,
*The two faces of lattices in cryptology*, Cryptography and lattices (Providence, RI, 2001) Lecture Notes in Comput. Sci., vol. 2146, Springer, Berlin, 2001, pp. 146–180. MR**1903893**, DOI 10.1007/3-540-44670-2_{1}2 - Harald Niederreiter,
*New developments in uniform pseudorandom number and vector generation*, Monte Carlo and quasi-Monte Carlo methods in scientific computing (Las Vegas, NV, 1994) Lect. Notes Stat., vol. 106, Springer, New York, 1995, pp. 87–120. MR**1445782**, DOI 10.1007/978-1-4612-2552-2_{5} - H. Niederreiter, ‘Design and analysis of nonlinear pseudorandom number generators’,
*Monte Carlo Simulation*, A.A. Balkema Publishers, Rotterdam, 2001, 3–9. - Harald Niederreiter and Igor E. Shparlinski,
*Recent advances in the theory of nonlinear pseudorandom number generators*, Monte Carlo and quasi-Monte Carlo methods, 2000 (Hong Kong), Springer, Berlin, 2002, pp. 86–102. MR**1958848** - H. Niederreiter and I. E. Shparlinski, ‘Dynamical systems generated by rational functions’,
*Proc. the 15th Symp. on Appl. Algebra, Algebraic Algorithms, and Error-Correcting Codes*, Lect. Notes in Comp. Sci., vol. 2643, Springer-Verlag, Berlin, 2003, 6–17. - V. Shoup, ‘Number theory
**C++**library (NTL)’, version 5.3.1, available at http://www.shoup.net/ntl/.

## Additional Information

**Simon R. Blackburn**- Affiliation: Department of Mathematics, Royal Holloway, University of London, Egham, Surrey, TW20 0EX, United Kingdom
- Email: s.blackburn@rhul.ac.uk
**Domingo Gomez-Perez**- Affiliation: Faculty of Science, University of Cantabria, E-39071 Santander, Spain
- Email: gomezd@unican.es
**Jaime Gutierrez**- Affiliation: Faculty of Science, University of Cantabria, E-39071 Santander, Spain
- Email: jaime.gutierrez@unican.es
**Igor E. Shparlinski**- Affiliation: Department of Computing, Macquarie University, Sydney, NSW 2109, Australia
- MR Author ID: 192194
- Email: igor@comp.mq.edu.au
- Received by editor(s): August 14, 2003
- Received by editor(s) in revised form: February 6, 2004
- Published electronically: July 27, 2004
- © Copyright 2004 American Mathematical Society
- Journal: Math. Comp.
**74**(2005), 1471-1494 - MSC (2000): Primary 11H06, 11K45, 11T71, 94A60
- DOI: https://doi.org/10.1090/S0025-5718-04-01698-9
- MathSciNet review: 2137013