Return to Answer

Wiener's result 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.

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.

Wiener's result 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 $\lceil log_2(n)/3\rceil$ 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.

Wiener's result 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.

Wiener's result 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 $\lceil log_2(n)/3\rceil$ 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-exponent RSA). If that kind of speed compromise is desirable, likely ECDSA is a better choice.

But this leaves the question unanswered.

Wiener's result 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 $\lceil log_2(n)/3\rceil$ 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.