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 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 &lt; 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.