Welcome to the resource topic for
**1999/019**

**Title:**

Security of all RSA and Discrete Log Bits

**Authors:**
Johan Hastad, 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.

**ePrint:**
https://eprint.iacr.org/1999/019

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .