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

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.