Remote Access Mathematics of Computation
Green Open Access

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
DOI: https://doi.org/10.1090/S0025-5718-00-01274-6
Published electronically: June 12, 2000
MathSciNet review: 1813147
Full-text PDF

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 pseudo-random number generator', SIAM J. Comp., 15 (1986), 364-383. MR 87k:65007
  • 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. T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, Elsevier, Amsterdam, 1998. MR 99h:94045
  • 8. M. Drmota and R.F. Tichy, Sequences, Discrepancies and Applications, Springer-Verlag, Berlin, 1997. MR 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. R. Impagliazzo and M. Naor, `Efficient cryptographic schemes provably as secure as subset sum', J. Cryptology, 9 (1996), 199-216. MR 97k:94030
  • 15. J. C. Lagarias, `Pseudorandom number generators in cryptography and number theory', Proc. Symp. in Appl. Math., Amer. Math. Soc., Providence, RI, 42 (1990), 115-143. MR 92f:11109
  • 16. M. Luby, Pseudorandomness and Cryptographic Applications, Princeton Univ. Press, Princeton, 1996. MR 97b:94024
  • 17. A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Cryptography, CRC Press, Boca Raton, FL, 1996. MR 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. D. R. Stinson, Cryptography: Theory and Practice, CRC Press, Boca Raton, FL, 1995. MR 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: https://doi.org/10.1090/S0025-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

American Mathematical Society