Attacks on the RSA Cryptosystem

Question

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?

Peter.

Answer 1

when you try to reconstruct p or q given bits from side channel attacks, the complexity is exponential to number of bits unknown. suppose you dont 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.