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