1. You can try larger key, though I don't think it's a good idea.

Exponetiation algorithms are O(n**2) at best, possibly O(n**3). That

means, in the ideal case, that when you have 10x larger key, you'd

need 100x more multiplications.

2. You can split the longer key into blocks, and encrypt them alone.

If it is fast enough for you, then you're done.

3. If it is too slow, use the above mentioned combination of RSA&AES.

The tradeoff is slow RSA speed vs time of AES initialisation. In case

of relatively small number of blocks, AES might be slower.

4. For RSA+AES, I'd have a look at PKCS#1, either at the original

padding or OAEP. The original padding is really simple to implement,

and it'll save you some wheel reinventing. The newer one, OAEP, is

more complicated, but has some nice additional properties. You can use

standard pkcs tools to generate/test your data in this case as an

additional benefit.

5. For RSA only, I'd use some padding scheme as well, possibly based on PKCS.

I'd include block number somewhere to prevent reordering. You need to

make sure that the block doesn't produces a number larger than modulo

(in PKCS this is achived by adding 00 00 or 01 00 bytes in front of

the data).

6. You can try ElGamal [1] that allows you to precompute most of the

things berforehand, so it might be possible to use large keys. Even if

you choose the "random" parameters small enough, you might be able to

trade some security for some speed.

[1] http://en.wikipedia.org/wiki/ElGamal_encryption

HTH.

J.

## ···

On 8/28/06, snacktime <snacktime@gmail.com> wrote:

Without going into too much detail, I've run into a roadblock using

rsa. I need to encrypt data that is larger than the key size. Right

now I am generating a random key, encrypting the data with it using

AES, then encrypting the key with rsa. Works, but I'd rather keep it

simpler if there is another asymmetric cipher I could use in place of

rsa. At most the data to be encrypted would be 10 times the key size.

Any ideas?

Chris