64
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ RSA is a primitive. It needs to be assembled into a system to be useful. The short answer -- pick any encryption system that is known to be secure, uses the RSA primitives, and that provides the characteristics you want (for example, supporting long blocks of plaintext). Length is not the only reason the RSA primitives are generally unsuitable for direct use. $\endgroup$ – David Schwartz Aug 23 '11 at 11:24
  • $\begingroup$ Unfortunately owing to my insufficient explanation, an earlier post of mine is unavailable to you. You can find however in Example 3 in the Appendix in s13.zetaboards.com/Crypto/topic/7234475/1 an encryption of a plaintext of arbitrary length in the sense of the common block encryption, i.e. exactly what you asked. $\endgroup$ – Mok-Kong Shen Dec 28 '15 at 17:21
60
$\begingroup$

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$.)

$\endgroup$
  • $\begingroup$ My old blog entry on the subject has some sample code (in C#) @ pages.infinit.net/ctech/20031101-0151.html $\endgroup$ – poupou Sep 7 '11 at 22:57
  • $\begingroup$ @samoz really informative and exactly what I was looking for thanks. $\endgroup$ – Prix Dec 5 '16 at 9:54
38
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Could you indicate why you would need CBC over ECB when using a PKCS#1 compatible padding scheme? The padding scheme should already contain at least 8 bytes of random data, so wouldn't that act as a per-block IV? Note: I'm only considering confidentiality here of course. $\endgroup$ – Maarten Bodewes Mar 2 '13 at 16:50
  • 1
    $\begingroup$ True ... "can" be done but don't. Use symmetric encryption (e.g., AES512) of payload using a strong PRNG based secret-key and then encrypt the secret-key using 2048 bit RSA public key. It is fast, efficient, can handle (virtually) any size payload and is no more complex than the less effective method described herein. $\endgroup$ – Darrell Teague Mar 11 '16 at 20:47
6
$\begingroup$

[...] 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.

$\endgroup$
  • $\begingroup$ While I do agree that the proposed situation is non-standard, simply saying to use AES I believe is incorrect, since it assumes you can securely distribute keys. Also, what do you mean it exposes weaknesses in the ciphers themselves? $\endgroup$ – samoz Jul 16 '13 at 13:43
  • $\begingroup$ In the hybrid approach described as the first answer, there is no key-exchange. The client generates a secret-key using a strong PRNG, uses a symmetric algorithm (like AES) to encrypt the payload, then encrypts the secret-key using the public RSA key. $\endgroup$ – Darrell Teague Mar 11 '16 at 20:49
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ There is no need for "secure distribution of symmetric keys". The public key of the RSA pair is, well, "public". That is the only information disseminated. Only the receiver who has the private-key component (which is NOT exchanged) can then decrypt the RSA encrypted secret-key used to (AES) encrypt the payload. $\endgroup$ – Darrell Teague Mar 11 '16 at 20:52

protected by e-sushi Oct 28 '16 at 18:48

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.