Author: Le Chaud LapinLe Chaud Lapin
Date: May 19, 2008 22:27
Hi All,
A day I have dreaded for a long time has finally arrived. I must
recognized the insufficient performance of RSA encryption. It is the
only bottle-neck in moderately large software system that I am
building.
For example, making n 512 bits, e=17, d = e^-1(mod phi), and p q both
on order of 256 bits, on a typical PC, performance is on the order of
50,000-100,000 mod-exp's per second, if e is used. If d is used,
however, the performance is on the order of a few hundred operations
per second.
Given that my system does not follow the typical model assumed by, for
example, web servers running SSL, I need to maxmize end-to-end
throughput. Choosing a low exponent, might not necessarily help.
O(n) for encryption using standard big-number algorithms [binary-
method-multiply-with-reduce] is quadratic, so it would seem that if
there were a way to carefully choose both e and d to limit their
collective sizes (to reasonable extent), both sides of pipe,
encryption, decryption, would be "slow", but overall throughput would
be increased.
|