Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

On the uniformity of distribution of the RSA pairs


Author: Igor E. Shparlinski
Journal: Math. Comp. 70 (2001), 801-808
MSC (2000): Primary 11T71, 94A60; Secondary 11K38, 11T23
Published electronically: June 12, 2000
MathSciNet review: 1813147
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract:

Let $m= pl$ be a product of two distinct primes $p$ and $l$. We show that for almost all exponents $e$ with $\operatorname{gcd} (e, \varphi(m))= 1$the RSA pairs $(x, x^e)$ are uniformly distributed modulo $m$when $x$ runs through

$\bullet$
the group of units $\mathbb{Z}_m^*$ modulo $m$ (that is, as in the classical RSA scheme);

$\bullet$
the set of $k$-products $x = a_{i_1}\cdots a_{i_k}$, $ 1 \le i_1 < \cdots < i_k \le n$, where $a_1, \cdots, a_n \in \mathbb{Z}_m^*$ are selected at random (that is, as in the recently introduced RSA scheme with precomputation).
These results are based on some new bounds of exponential sums.


References [Enhancements On Off] (What's this?)

  • 1. M. Ajtai, `Generating hard instances of lattice problems', Electronic Colloq. on Comp. Compl., Univ. of Trier, TR96-007 (1996), 1-29. CMP 97:06
  • 2. W. Banks, F. Griffin, D. Lieman and I. E. Shparlinski, `Non-linear complexity of the Naor-Reingold pseudo-random function', Proc. the 2nd Intern. Conf. on Information Security and Cryptology, Seoul, 1999, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, (to appear).
  • 3. L. Blum, M. Blum, and M. Shub, A simple unpredictable pseudorandom number generator, SIAM J. Comput. 15 (1986), no. 2, 364–383. MR 837589 (87k:65007), http://dx.doi.org/10.1137/0215025
  • 4. V. Boyko, M. Peinado and R. Venkatesan, `Speeding up discrete log and factoring based schemes via precomputations', Proc. of Eurocrypt'98, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1403 (1998), 221-234.
  • 5. R. Canetti, J. B. Friedlander, S. Konyagin, M. Larsen, D. Lieman and I. E. Shparlinski, `On the statistical properties of Diffie-Hellman distributions', Israel J. Math., (to appear).
  • 6. R. Canetti, J. B. Friedlander and I. E. Shparlinski, `On certain exponential sums and the distribution of Diffie-Hellman triples', J. London Math. Soc., (1999), 799-812. CMP 99:17
  • 7. Thomas W. Cusick, Cunsheng Ding, and Ari Renvall, Stream ciphers and number theory, North-Holland Mathematical Library, vol. 55, North-Holland Publishing Co., Amsterdam, 1998. MR 1634586 (99h:94045)
  • 8. Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456 (98j:11057)
  • 9. J. B. Friedlander, D. Lieman and I. E. Shparlinski, `On the distribution of the RSA generator', Proc. Intern. Conf. on Sequences and Their Applications (SETA'98), Singapore, Springer-Verlag, London, 1999, 205-212.
  • 10. J. B. Friedlander, C. Pomerance and I. E. Shparlinski, `Period of the power generator and small values of Carmichael's function', Math. Comp., (to appear).
  • 11. J. B. Friedlander and I. E. Shparlinski, `On the distribution of the power generator', Math. Comp., (to appear).
  • 12. F. Griffin and I. E. Shparlinski, `On the linear complexity of the Naor-Reingold pseudo-random function', Proc. 2nd Intern. Conf. on Information and Communication Security, Sydney, 1999, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1726 (1999), 301-308.
  • 13. F. Griffin and I. E. Shparlinski, `On the linear complexity profile of the power generator', Trans. IEEE Inform. Theory (to appear).
  • 14. Russell Impagliazzo and Moni Naor, Efficient cryptographic schemes provably as secure as subset sum, J. Cryptology 9 (1996), no. 4, 199–216. MR 1426279 (97k:94030), http://dx.doi.org/10.1007/s001459900012
  • 15. 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 (92f:11109), http://dx.doi.org/10.1090/psapm/042/1095554
  • 16. Michael Luby, Pseudorandomness and cryptographic applications, Princeton Computer Science Notes, Princeton University Press, Princeton, NJ, 1996. MR 1373652 (97b:94024)
  • 17. Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of applied cryptography, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1997. With a foreword by Ronald L. Rivest. MR 1412797 (99g:94015)
  • 18. M. Naor and O. Reingold, `Number-theoretic constructions of efficient pseudo-random functions', Proc. 38th IEEE Symp. on Foundations of Comp. Sci., 1997, 458-467.
  • 19. M. Naor and O. Reingold, `Synthesizers and their application to the parallel construction of pseudo-random functions', J. Comp. and Sys. Sci., 58 (1999), 336-375. CMP 99:15
  • 20. P. Nguyen, I. E. Shparlinski and J. Stern, `Distribution of modular sums and the security of the server aided exponentiation', Preprint, 2000, 1-16.
  • 21. P. Nguyen and J. Stern, `The hardness of the hidden subset sum problem and its cryptographic implications', Proc. CRYPTO'99, Santa Barbara, 1999, Springer-Verlag, Berlin, 1666 (1999), 31-46.
  • 22. I. E. Shparlinski, `On the uniformity of distribution of the Naor-Reingold pseudo-random number function', Finite Fields and Their Appl. (to appear).
  • 23. I. E. Shparlinski, `On the Naor-Reingold pseudo-random number generator from elliptic curves', Appl. Algebra in Engin., Commun. and Computing (to appear).
  • 24. I. E. Shparlinski, `On the linear complexity of the power generator', Designs, Codes and Cryptography, (to appear).
  • 25. I. E. Shparlinski and J. H. Silverman, `Linear complexity of the Naor-Reingold pseudo-random number function from elliptic curves', Preprint, 1999, 1-14.
  • 26. Douglas R. Stinson, Cryptography, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1995. Theory and practice. MR 1327060 (96k:94015)
  • 27. I. M. Vinogradov, Elements of Number Theory, Dover Publ., NY, 1954. MR 19:933e

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11T71, 94A60, 11K38, 11T23

Retrieve articles in all journals with MSC (2000): 11T71, 94A60, 11K38, 11T23


Additional Information

Igor E. Shparlinski
Affiliation: Department of Computing, Macquarie University, Sydney, New South Wales 2109, Australia
Email: igor@ics.mq.edu.au

DOI: http://dx.doi.org/10.1090/S0025-5718-00-01274-6
PII: S 0025-5718(00)01274-6
Keywords: RSA cryptosystem, uniform distribution, precomputation, exponential sums
Received by editor(s): June 22, 1999
Published electronically: June 12, 2000
Article copyright: © Copyright 2000 American Mathematical Society