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?

Answer 1

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. The preconditions to using Coppersmith's method are:

1. $f_p(x)=0 \pmod p$ at the point we want to evaluate (i.e., for the middle bits).
2. $f_p(x)$ is monic (i.e., the leading coefficient of $f$ is 1).

First, let's start writing $p$ in terms of $x$. Let $MID(p)$ represent the middle bits of $p$. So $p = MSB(p) + MID(p) · 2^{n/8} + LSB(p)$**. Now let's rewrite this as a function of $x$. Let $g_p(x) = MSB(p) + x · 2^{n/8} + LSB(p)$. We have to make this function monic. To do this, we can multiply $g_p(x)$ by $(2^{n/8})^{-1} \mod N$. We can't do it $\mod p$ since we don't know how to compute inverses $\mod p$ as $p$ is unknown. Ok, so let's rewrite our functions,

$$ f_p(x) =g_p(x)(2^{n/8})^{-1} \mod N = x + MSB(p)\cdot (2^{n/8})^{-1} + x + LSB(p) (2^{n/8})^{-1} $$

Now all that's left before computing Coppersmith's method is to check that $f_p(MID(p))=0 \mod p$.

$$ f(x)=MID(p)+MSB(p)(2^{n/8})^{-1}+LSB(p)(2^{n/8})^{-1}=p(2^{n/8})^{-1} $$

Note that this can be rewritten as: $pC$, and any number multiplied by $p$ in $\mod p$ is $0 \mod p$ i.e., $pC = 0 \mod 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.

** I left the notation in terms of MSB(p) to be consistent with the first author for this answer, but I think showing that the preconditions for applying that Coppersmith hold is easier when we think of the MSB(p) as the bit values shifted by some $2^{n/k}$ where $k$ is some constant. This notation can be seen in referring to the middle bits $MID(p) \cdot (2^{n/8})$.

Answer 2

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.