Proof that padded RSA is CPA-secure I'm referring to page 383 of J. Katz and Y. Lindell's Introduction to Modern Cryptography.  The book presents a padded RSA: 


${\bf Key Generation:}$ same as Textbook RSA (given security parameter $1^n$, generate public key ($N,e$), secret key ($N,d$), such that $N = pq, ed \equiv 1 \mod{(p-1)(q-1)}$)
${\bf Encryption:}$ given public key ($N,e$), and message $m$ of length $l(n) \leq 2n - 2$, choose random bit string $r$ of length $2n - l(n) - 1$, and interpret the padded message $r||m$ (where $||$ is concatenation) as an element of $(\mathbb{Z}/N\mathbb{Z})^*$.  Output the ciphertext $c := (r||m)^e \mod{N}$.
${\bf Decryption:}$ given secret key ($N,d$), and cipertext $c$, compute $m' := c^d \mod{N}$, and ouput the $l(n)$ low-order bits of $m'$


The book claims that if $l(n) = O(\log{N})$, then the padded cryptosystem is CPA-secure.  Unfortunately, it states that the full proof is beyond the scope of the book.  Where can I find the full proof of the CPA-security of this version of padded RSA?
This result is proven in the following research papers:


Johan Hastad, Mats Naslund.  The Security of all RSA and Discrete Log Bits.  Journal of the ACM, Oct 2003, pp.1--45.
W. Alexi, B. Chor, O. Goldrech, C. Schnorr.  RSA and Rabin functions: Certain parts are as hard as the whole.  SIAM Journal on Computing, vol 17 no 2, pp.194--209.


They show that if you can predict the least significant bit (or the $O(\log \log N)$ least significant bits), then you can break RSA.  See also the citations in that article for similar results.



I can give you a taste for why this might be true, by sketching how to prove a much weaker version: if you have a way to compute the least significant bit of $x$ from the RSA encryption $E(x)$, then I can break RSA.

Let me start with a warmup.  Suppose you have a black box that, given a ciphertext $E(x)$, can answer the yes-or-no question ``is $x$ in the range $[0, N/2)$?''.  Suppose your black box is perfect: it always gives the right answer.  Let me show you how I can use your black box to break RSA.

Notation: Here $E(x)$ denotes the RSA encryption of message $x$, i.e.,
$E(x) = x^e \bmod N$.  Notice that there is no padding and no randomization in my definition of $E(\cdot)$.  Also note that RSA is homomorphic, so $E(2x) = 2^e E(x) \bmod N$.  In other words, given $E(x)$, I can derive $E(2x)$ even without knowing $x$.  I will use the notation $[a,b)$ to represent the set of integers $a,a+1,a+2,\ldots,b-1$.

Now let's solve the warmup problem.  We are given $E(x)$, and we want to find $x$.  Basically, we're going to use binary search.


First, we query your black box with $E(x)$ to learn whether $x$ is in the range $[0,N/2)$ or in the range $[N/2,N)$.  Suppose we learn that $x$ was in the range $[0,N/2)$.
Next, we query your black box with $E(2x)$.  This tells us whether $2x$ is in the range $[0,N/2)$ or in $[N/2,N)$, which in turn tells us whether $x$ is in the range $[0,N/4)$ or in $[N/4,N/2)$.  Suppose we learn that $x$ is in the range $[N/4,N/2)$.
Next, we query your black box with $E(4x)$.  This tells us whether $4x \bmod N$ is in the range $[0,N/2)$ or in $[N/2,N)$.  Note that $4x \bmod N = 4x-N$ (given what we know about the range $x$ is in).  So, we know whether $4x-N$ is in the range $[0,N/2)$ or in $[N/2,N)$, which in turn tells us whether $x$ is in the range $[N/4,3N/8)$ or in $[3N/8,N/2)$.
Keep going like this, until $x$ is completely known.


This requires $O(\lg N)$ queries to your black box. If your black box always gives the correct answer, then at the end we learn the exact value of $x$.

In other words, if you have a black box like that, then given any RSA ciphertext $E(x)$, I can derive $x$: which is a total break of RSA.  (Conversely, if we assume RSA is secure, then such a black box is impossible to build.)

The warmup above might start to give you some idea of what it might look like to try to prove the stronger result.


For instance, suppose you don't have a black box that answers the question "is $x$ in the range $[0,N/2)$?", but you do have a green box that answers the question "is the least significant bit of $x$ one?".

Well, given a green box, we can build a black box.  Given $E(x)$, we query the green box on $E(2x) = 2^e E(x) \bmod N$; if it answers "yes", then $x$ is in the range $[0,N/2)$, otherwise $x$ is in the range $[N/2,N)$.  So, the green box's answer to $E(2x)$ reveals how the black box should respond to the query $E(x)$.

Therefore, if you have a green box that can compute the least significant bit, you can break RSA (by constructing a black box and applying the binary search method as above).  Conversely, if we think RSA is secure, then there should be no way to build a green box like this.
As another example of a generalization, suppose your black box doesn't always give the right answer; it answers correctly with probability $1/2 + \epsilon$, and incorrectly with probability $1/2 - \epsilon$, for some $\epsilon&gt;0$.  Then we have an instance of a game of 20 questions, where we have only a noisy view of our answer.  It turns out there are algorithmic ways to deal with this noise, though it does take a lot of difficult technical work.  For the details, see the papers mentioned above.