The RSA and Rabin encryption function are respectively defined as
E
N(
x) =
x
e mod
N and
E
N(
x) =
x
2 mod
N, where
N is a product of two large random primes
p, q and
e is relatively prime to
φ(
N). We present a much simpler and stronger proof of the result of
Alexi, Chor, Goldreich and
Schnorr [
ACGS88] that the following problems are equivalent by probabilistic polynomial time reductions: (1) given
E
N(
x) find
x; (2) given
E
N(
x) predict the least-significant bit of
x with success probability
, where
N has
n bits. The new proof consists of a more efficient algorithm for inverting the RSA/Rabin-function with the help of an oracle
that predicts the least-significant bit of
x. It yields provable security guarantees for RSA-message bits and for the RSA-random number generator for moduli
N of practical size.