Encrypted data length is very large with RSA

Question

I want that encrypted data have the same length as my original text, because I must respect the constraint of length. I am using BouncyCastle.

Here's my code to generate the keys pair:

KeyPairGenerator keyGen = KeyPairGenerator.getInstance("RSA");
keyGen.initialize(512);
KeyPair keypair = keyGen.genKeyPair();
PublicKey pub = keypair.getPublic();
byte[] pubs = pub.getEncoded();

And here's my code to encrypt:

Cipher cipher = Cipher.getInstance("RSA/ECB/PKCS1PADDING");
PublicKey pk = KeyFactory.getInstance("RSA").generatePublic(new X509EncodedKeySpec(pubs));
cipher.init(Cipher.ENCRYPT_MODE, pk);
byte[] cipherBytes = cipher.doFinal(plainArray);

The encoded data is very large, what can I do to make as small as original data ?

Answer 1

If you can keep the key secret, you can use a symmetric cryptosystem like AES. If used in CFB mode, it can be adapted to any bit length. I.e. #bits input & output is identical.

RSA and ElGamal -- the main public-key cryptosystems-- can be broken in a matter of hours even at 512 bits as you are selecting. 1024 - 4096 bits is normal. Less than 512 bits is worthless unless your opponent is limited to using 1990s hardware. :-)

Answer 2

The nature of RSA is such that you use exponentiation in encryption and decryption.

Basically, for public key e and private key d, you take a message m and then you get a compressed message equal to c=m^e and mod it by n. Then you decrypt with m=c^d and again mod it by n (mod means take the remainder).

If you think about it, a message to the power of something results in a larger number. Because you do a mod n, you end up with a number that is at most n-1. n is the key length.

So basically, whatever message you take, you encrypt to something as large as n. The message has to be less than n.

But the message has to be turned into an integer using a padding scheme (so you can do the exponentiation). This padding scheme may require less than n bits. And so, you end up with larger files than the size of the data being encrypted. Also, the last chunk may be less than n bits, but will encrypt into size n.

Answer 3

Nothing, at least not regarding the RSA. RSA requires a certain amount of padding to be secure, and as the data will be seen as random data by any compression method, you cannot compress it either.

Of course, you should not directly encrypt data directly using RSA, you should encrypt a random session/data key instead. But even then, you will have the encrypted session key as overhead.

You can remove some bits for the asymmetric encrypted data/key by using Elliptic Curve Cryptography (the output of which is double the key size minimum, but key sizes are much smaller to achieve the same level of security). EC cryptography is not for the meek though, it has lots of complexity.

512 bit RSA is considered insecure by the way. Use 1024 as minimum or keep to the ECRYPT II or NIST recommendations listed at http://www.keylength.com/ .