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$.