RSA encryption algorithms

[Dratino]

I wrote a program to generate pairs of RSA keys the other day in Python, but it seems incredibly inefficient (it usually takes about 2-3 seconds to generate a 512-bit key, and 6-10 seconds to generate a 1024-bit key).

However, it's not so much the keypair generation that I'm worried about, but the time it takes to encrypt a message. Even using an "exponentiation by squaring" algorithm, it takes my laptop about 0.054 seconds to encrypt a 1024-bit message. Is there something I'm doing wrong, or do I just have a really crummy laptop? (Or, does RSA really just take that long to encrypt stuff. It could be the case that I'm worried about nothing.)

[Insectoid]

If you look on the RSA website, you'll find that "With the typical modular exponentiation algorithms used to implement the RSA algorithm, public key operations take O(k^2) steps, private key operations take O(k^3) steps, and key generation takes O(k^4) steps, where k is the number of bits in the modulus."

I dunno how big your modulus is, but O(K^4) gets very slow, very quickly.

[Brightguy]

Dratino @ Wed Nov 09, 2011 10:28 am wrote:

Even using an "exponentiation by squaring" algorithm, it takes my laptop about 0.054 seconds to encrypt a 1024-bit message.

This might just be the python overhead. But encryption should be the fastest RSA operation, assuming you take your public key exponent to be O(1). If you use fast multiplication, you can encrypt messages in nearly linear time.