Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 message.

How can I do this?

share|improve this question
    
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. –  David Schwartz Aug 23 '11 at 11:24

3 Answers 3

up vote 25 down vote accepted

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

share|improve this answer
    
My old blog entry on the subject has some sample code (in C#) @ pages.infinit.net/ctech/20031101-0151.html –  poupou Sep 7 '11 at 22:57

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.

share|improve this answer
1  
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. –  owlstead Mar 2 '13 at 16:50

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

share|improve this answer
    
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? –  samoz Jul 16 '13 at 13:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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