# Attacks on the RSA Cryptosystem

I was reading some articles about attacks on RSA system and I wonder about some generalization of the following theorem.

Theorem (Coppersmith).

Let $N=pq$ be an $n$-bit RSA modulus, where $p<q<2p$. Then given the $\frac{n}{4}$ least significant bits of $p$ (that is $\approx$ half of LSB of $p$) or the $\frac{n}{4}$ most significant bits of $p$ (that is $\approx$ half of MSB of $p$), one can efficiently factor $N$.

I wonder what is going on, if we know for example $\frac{n}{8}$ MSB of $p$ and $\frac{n}{8}$ LSB of $p$.

Second idea, what is going on, if we know for example $\frac{n}{8}$ MSB of $p$ and $\frac{n}{8}$ LSB of $q$.

Is it enough for factoring $N$ in effective way? Or maybe with some other numbers instead of pair $(\frac{n}{8}, \frac{n}{8})$ (of course assuming, that both numbers are greater than $0$ and less than $\frac{n}{4}$)? Was there some research in this field?

-
Note that the two ideas are actually identical; if we know the $k$ LSbits of p, we can immediately deduce the $k$ LSBits of q. –  poncho Dec 10 '12 at 5:02
Take a look at the homepage of Alexander May, he published a lot about this topic. –  j.p. Dec 10 '12 at 11:04

When you try to reconstruct $p$ or $q$ given bits from side channel attacks, the complexity is exponential to the number of bits unknown.
Suppose you don't know $k$ bits of $p$, then for each combination of $0$ and $1$ for each unknown bit, you are going to try the answer as factor.
So, complexity is $O(2^k)$.
As $k$ increases, runtime increases exponentially.
This doesn't answer the question. There is, in fact, a specialized attack which allows one to factor N faster than testing all the missing bits when you have enough bits of $p$. –  Thomas Dec 18 '12 at 8:12