Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
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
add comment

1 Answer

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.

share|improve this answer
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
Hi thomas, can you share with us more details of that attack. –  pratibha Dec 18 '12 at 9:37
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.