How can I use asymmetric encryption, such as RSA, to encrypt an arbitrary length of plaintext?

Question

RSA is not designed to be used on long blocks of plaintext like a block cipher, but I need to use it to send a large (encrypted) message.

How can I do this?

Answer 1

The solution to this problem is to use hybrid encryption. Namely, this involves using RSA to asymmetrically encrypt a symmetric key.

Randomly generate a symmetric encryption (say AES) key and encrypt the plaintext message with it. Then, encrypt the symmetric key with RSA. Transmit both the symmetrically encrypted text as well as the asymmetrically encrypted symmetric key.

The receiver can then decrypt the RSA block, which will yield the symmetric key, allowing the symmetrically encrypted text to be decrypted.

This can be shown more formally as the following. Let $M$ be the plaintext, $K_{AES}$ be the randomly chosen AES key, and $K_{Pu}$ be the receiver's public RSA key you already have.

$$ C_1 = E_{AES}(M, K_{AES}) $$ $$ C_2 = E_{RSA}(K_{AES}, K_{Pu}) $$

Then, send both $C_1$ and $C_2$.

Let $K_{Pr}$ be the receiver's private RSA key. The receiver can then recover $M$ as

$$ K_{AES} = D_{RSA}(C_2, K_{Pr}) $$ $$ M = D_{AES}(C_1, K_{AES}) $$

(To allow streaming decryption or large messages, you would usually send $C_2$ first and then (the much larger) $C_1$.)

Answer 2

Theoretically you can do encryption of long messages with RSA, in the same way that you can encrypt a long message with a block cipher. This requires an appropriate chaining mode, e.g. CBC: each plaintext "block" is first XORed with (part of) the encrypted previous block.

With RSA and proper padding, there is a per-block size overhead. Namely, with the "v1.5" padding described in PKCS#1, and a 1024-bit RSA key, each RSA invocation can encrypt a message up to 117 bytes, and results in a 128-byte value. Hence, in order to apply CBC chaining, you would have to "extract" a part of the previous 128-byte value of the appropriate size. Things can become subtle, security-wise, at that point, because CBC relies on encrypted blocks being good at "randomizing" data, and nothing proves that the 128 bytes will look sufficiently random from the outside (actually, there are good reasons why the first bytes will not be random enough).

(If you do not use a proper padding, then you already have bigger problems. RSA without its padding is no longer RSA, and, more importantly, is no longer secure.)

Nobody in their right frame of mind does such RSA-with-CBC encryption. Among the reasons are:

• the construction has not received sufficient scrutiny to be deemed secure;
• the size overhead implies that the encrypted message will be about 9.4% longer than the plaintext message;
• RSA encryption is not very fast (a modern CPU would still succeed in encrypting, say, 2 MBytes worth of data per second that way).

This last reason is the most often quoted, but, in my opinion, the least compelling of the three.

In practice, everybody uses RSA encryption as a key exchange mechanism, to be used with a fast, secure symmetric encryption system, as @samoz describes. This has been much more analyzed (hence it is believed to be a secure way of doing things), it enlarges data by only a fixed amount (a few hundred bytes at most, even if encrypting gigabytes), and is much faster, too.

Answer 3

[...] but I need to use it to send a large message.

The short answer to this is "no you don't" unless it's for some silly class assignment or something. As @Samoz's answer indicates, there are ways asymmetric encryption can be forced into being a streaming cipher, but the disadvantages are deal-killing.

In particular,

• it's not standard and is going to be an idiosyncratic scheme only you use,
• using asymmetric encryption exposes weaknesses in the ciphers themselves,
• it forces you to manage very large numbers of very large keys.

By comparison, well-known streaming ciphers, like AES, are computationally efficient, require much smaller keys and fewer of them, are more robust under operator mistakes, and are standard.

Basically, one of the mistakes slightly less egregious than involvement in a land war in Asia is trying to do tricky things with existing encryption algorithms.

Answer 4

The question already assumed secure distribution of symmetric keys, i.e. use RSA. The implicit assumption in "how do I use RSA" is "(asymmetric) key distribution is already taken care of". So you simply send the RSA encrypted key with the AES cyphertext. I use an xml file that has the RSA key ID, encrypted AES key, file hash, and potentially other metadata (if it is ok to send in clear), then transmit the file pair.