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
3  
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

2 Answers 2

Yes, what you have is enough to recover p in both cases.

In the first case you just need to write the proper equation to be then solved thanks to Coppersmith method to find small roots of univariate polynomial. As explained by Alexander May in pages 40 and 41 of his thesis what you ask is always doable if the unknown bits are consecutive (and you have at least $\frac{n}{4}$ known bits).

You just need to write the correct polynomial and let Coppersmith's method find the solution, in this case it's $f_p(x) = x · 2^{n/8} + MSB(p) + LSB(p)$

I successfully tested a solution for the problem you described using sage, the solution is available here.

In the second case, as poncho pointed out, it is trivial to recover the $LSB(p)$ knowing the $LSB(q)$, just note that: $LSB(p) = N * LSB(q)^{-1}\bmod{2^{n/8}} $

In case your unknown bits of p are not consecutive, then it's not so easy and you probably will need more bits: see this paper by Herrmann and May that basically states that $log(2)n \approx 0.7n $ bits of $p$ are always enough to solve the equation but the complexity is exponential in the number of different not consecutive unknown bit blocks.

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

Your Answer

 
discard

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.