Security of all RSA and Discrete Log Bits

Johan Hastad; Mats Naslund

Paper 1999/019

Security of all RSA and Discrete Log Bits

Johan Hastad and Mats Naslund

Abstract

We study the security of individual bits in an RSA encrypted message E_N(x). We show that given E_N(x), predicting any single bit in x with only a non-negligible advantage over the trivial guessing strategy, is (through a polynomial time reduction) as hard as breaking RSA. Moreover, we prove that blocks of O(log log N) bits of x are computationally indistinguishable from random bits. The results carry over to the Rabin encryption scheme. Considering the discrete exponentiation function, g^x modulo p, with probability 1-o(1) over random choices of the prime p, the analog results are demonstrated. Finally, we prove that the bits of ax+b modulo p give hard core predicates for any one-way function f.

Metadata

Available format(s): PS
Publication info: Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Keywords: public key encryption RSA discrete log bit security hard core.
Contact author(s): mats naslund @ era-t ericsson se
History: 1999-08-27: received
Short URL: https://ia.cr/1999/019
License: CC BY

BibTeX

@misc{cryptoeprint:1999/019,
      author = {Johan Hastad and Mats Naslund},
      title = {Security of all RSA and Discrete Log Bits},
      howpublished = {Cryptology ePrint Archive, Paper 1999/019},
      year = {1999},
      note = {\url{https://eprint.iacr.org/1999/019}},
      url = {https://eprint.iacr.org/1999/019}
}