Is Wiener's attack on RSA extendable to larger keys with low hamming weight?

Question

Using small private exponents with RSA improves performance.

However, it has been shown (Wiener, 1990) that if $\log d \leq \frac14 \log N$, the private exponent $d$ can be reconstructed from the public key $(N,e)$.

Smart, Inc. uses special private keys designed such that they are:

• Larger than the minimum bound recommended by Wiener, and
• Still very efficient because of their low Hamming weight

Are such keys safe to use? How could one reconstruct the private keys from the public?

I did some research and think that Wiener's attack might be on the right track.

Answer 1

First, you have a typo in your question. Wiener's attack works if $\log(d) < 0.25 \log(N)$. This is not the best possible attack. "Boneh and Durfee" improved the result to $\log(d) < 0.292 \log(N)$.

I'm not aware of any better result, but that does not mean such results do not exist. In particular, it is quite unclear whether it would help an attacker to know that the Hamming weight of the private key is small.

Generally, it is very risky to use these corner cutting techniques. There are countless proposals for speeding up RSA by generating the private key in a particular way that already.

A good overview over the topic is Alexander May's thesis. This thesis is a few years old, but does nicely show what kind of attacks are possible, and more importantly how complex this subject is.

I would recommend not to use any RSA implemenation that tries to optimize performance by fiddling with the secret key.

Answer 2

Wiener's result (doi, announced in proceedings of crypto 1989) has been improved several times, and it is hard to tell how big the private exponent must be to be safe from further progress.

Also, the proposed technique, assuming $d>n^{1/3}$, requires a minimum of ${1\over3}\cdot\log_2(n)$ modular multiplications for the sparsest $d$ conceivable (a power of two), compared to say ${7\over6} \cdot\log_2(n)$ for classical RSA using sliding window exponentiation.

Thus, when not using the Chinese Remainder Theorem, the technique allows a speedup of a factor of $7\over2$ at best, which is less than the factor of nearly 4 allowed by the CRT; and when combining the technique with the CRT, one of the saving in the CRT (halving the size of the exponents) vanishes, thus the speedup is by a factor like $7\over4$ compared to classical RSA with CRT. That's not a huge speedup.

This shows the technique is risky, for a moderate speedup of the private key function (and a huge slowdown of the public key function compared to low-public-exponent RSA). If that kind of speed compromise is desirable, likely ECDSA is a better choice.

But this leaves the question unanswered.

Answer 3

The other answers explain why you shouldn't take shortcuts like this and why it won't provide much of a speedup anyway. As for an actual attack, here's an obvious one: brute force.

With the parameters you gave, there are only $\binom{309}{3} = 4869634$ possible values for d, which is small enough to easily check every value.

Answer 4

If the private exponent $d$ has very low Hamming weight, it will be easy to break the scheme.

Suppose that $d$ has weight $w$, and is $m$ bits wide. @Antimony already explained how to break it in $m \choose w$ time. I'll show how to break it even faster, using a birthday-style technique. My algorithm takes about $2.5 \sqrt{w} {m/2 \choose w/2}$ time, which is quite a bit faster. For instance, if $d$ is a 1024-bit exponent with Hamming weight 10, then @Antimony's method will take about $2^{78}$ steps of computation, whereas my method will take about $2^{41}$ steps of computation.

Start by writing $d=d'+d''$, where $d'$ has its low $m/2$ bits all zero, and $d''$ has its high $m/2$ bits all zero. We'll hope that both $d'$ and $d''$ have Hamming weight $w/2$ (this happens with probability about ${w \choose w/2}/2^w$, which is fairly large; I'll describe later how to remove this requirement).

Pick a random value $x$, and let $y=x^e$. Note that $$y^d = x.$$ It follows that $$y^{d'} = x/y^{d''}.$$ My algorithm will iterative over all possible values of $d'$, and store the corresponding value of $y^{d'}$ in a hash table. Then, it will iterate over all possible values of $d''$, and look up $x/y^{d''}$ in the hash table. If it finds a match in the hashtable, then it has found both $d$ and $d''$, and thus recovered the private exponent $d=d'+d''$.

The running time is $m/2 \choose w/2$ steps to populate the hashtable, and another $m/2 \choose w/2$ steps to look up entries, for a total running time of $2 {m/2 \choose w/2}$.

What's the success probability? This succeeds if half of the 1-bits of $d$ fall in its high $m/2$ bits, and half fall in the low $m/2$ bits. This happens with probability ${w \choose w/2}/2^w$, so this algorithm succeeds in recovering $d$ with probability about ${w \choose w/2}/2^w$. Using Stirling's formula, the success probability is about $1/\sqrt{\pi w/2}$.

What if the algorithm doesn't succeed? Well, then we try it again, but with a different way of splitting the $m$ bit positions into two sets. Above, I described it as a split with one set containing the high $m/2$ bits and the other set containing the low $m/2$ bits. However, we can generalize the algorithm and apply it, given any way of partitioning the $m$ bit positions into two sets, each of size $m/2$. Each such partition has about a $1/\sqrt{\pi w/2}$ probability of revealing $d$, so we can repeatedly try many random partitions, and after about $\sqrt{\pi w/2}$ trials, we expect to find one that reveals $d$. Thus, the total running time is $2 \sqrt{\pi w/2} {m/2 \choose w/2} \approx 2.5 \sqrt{w} {m/2 \choose w/2}$.