Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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 < 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.
