RSA reconstructing private key knowing MSBs

PREMISE: This question is purely theoretical because usually an attacker will not know private exponent d and can't compare it with obtained MSB bytes.

Suppose an RSA 1024 bit signature.

An attacker through a key exposure obtain the half most significant bytes of the private exponent d.

Can the attacker reconstruct the LSBs of d without bruteforce the LSB part? Can he make it in a reasonable amount of time?

There are best way to do it?

• I found related attacks, one where $d<n^{1/4}$ and one where the attacker knows the $n^{1/4}$ least significant bits. But I don't know an attack that applies to your problem. – CodesInChaos Oct 23 '15 at 16:04
• Please have a loook at this eprint paper: (eprint: RSA private key reconstruction from random bits using SAT solvers) [eprint.iacr.org/2013/026.pdf] but public exponent is three. – thepacker Oct 23 '15 at 18:55
• There is another Paper of Boneh, Durfee and Frankel Exposing an RSA Private key Given a Small Fraction of its Bits – thepacker Oct 23 '15 at 19:16
• Another related paper, here. – otus Oct 24 '15 at 7:14

I do not believe that there is any reasonably efficient way to reconstruct the lsbits; if there were, then a good fraction of the RSA keys out there could be efficiently factored (!).

Here's why: a lot of RSA keys have a modulus $n = pq$, where $p$ and $q$ are primes of equal size. Then, let us assume a small $e$ (it needs to be relatively prime to $p-1$ and $q-1$; we could use the $e$ in the public key, or pick our own and hope we're lucky). Then, the relationship between $d$ and $e$ is:

$$de \equiv 1 \pmod{lcm(p-1, q-1)}$$

which we can rearrange into

$$d = (k(n - p - q + 1)/\gcd(p-1, q-1) + 1) / e$$

where $k$ is some unknown integer that turns out to be within the range $(0, e)$. If we're interested in only the msbits of $d$, we can simplify this to:

$$d \approx (k (n + \epsilon) / (e \cdot \gcd(p-1, q-1)$$

Where $\epsilon < 5\sqrt{n}$. We can guess $k$ and the contibutions of $\epsilon$ on $n$, and $\gcd(p-1, q-1)$ is likely to be a small even value; going through the possibilities, that gives us reasonable guesses for the msbit's of $d$; if one is correct, then we could use the assumed method to reconstruct the lsbit's, and then immediately factor.

• Just to understand what i have studied in my classroom during these days i generated a 1024 key and suppose that i can access only to e and n where e is 3. I successfully guess the 64 msbytes of the private exponent d using k < e (very easy for choosed public exponent e). From your answer i don't get why \epsilon must be exactly \epsilon < 5\sqrt{n}? Understand the contribution of \epsilon and \gcd(p-1, q-1) how can help me to write a method to recover lsbit's? I don't get completely this part that is the part that i ask. As always thanks for your help. – Seed3Key Oct 23 '15 at 18:00
• @Seed3Key: "how can help me to write a method to recover lsbit's?"; actually, the point I was attempting to make is that I don't believe that there is an efficient method (or, rather if there is, it would be a significant breakthrough that would allow us to factor a good fraction of the RSA keys out there) – poncho Oct 23 '15 at 18:29