6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – CodesInChaos Oct 23 '15 at 16:04
  • 1
    $\begingroup$ 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. $\endgroup$ – thepacker Oct 23 '15 at 18:55
  • 2
    $\begingroup$ There is another Paper of Boneh, Durfee and Frankel Exposing an RSA Private key Given a Small Fraction of its Bits $\endgroup$ – thepacker Oct 23 '15 at 19:16
  • 1
    $\begingroup$ Another related paper, here. $\endgroup$ – otus Oct 24 '15 at 7:14
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Seed3Key Oct 23 '15 at 18:00
  • 3
    $\begingroup$ @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) $\endgroup$ – poncho Oct 23 '15 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.