Paper 1999/019

Security of all RSA and Discrete Log Bits

Johan Hastad and Mats Naslund


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.

Available format(s)
Publication info
Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
public key encryptionRSAdiscrete logbit securityhard core.
Contact author(s)
mats naslund @ era-t ericsson se
1999-08-27: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.