When/why is RSA (hybrid) encryption used rather than alternatives?

Question

I've read that RSA is not meant for encrypting large plaintext because:
(Are these also true for other public-key encryptions like ElGamal?)

• It is slow.
• Padding makes the ciphertext blocks much longer.
• No one uses RSA that way; so its security is not scrutinized.

Instead, a hybrid scheme is used, e.g., samoz's answer at How can I use asymmetric encryption, such as RSA, to encrypt an arbitrary length of plaintext?

And apparently, that is also encryption in PGP works:

• Select a random symmetric key.
• Encrypt plaintext with this symmetric key.
• Encrypt the symmetric key using the receiver's public key.
• (optionally) Sign (the hash of) the ciphertext plaintext.
• Send symmetric ciphertext, the encrypted symmetric key, and (optionally) the signature.

This scheme has the same problem that I asked about here Why use Diffie-Hellman key exchange over RSA (or any public-key encryption)?, i.e., encrypting a ''unilateral'' symmetric key with the receiver's public key.

So why not use Integrated Encryption Scheme? This scheme uses the receiver's public key to create a Diffie-Hellman symmetric key. With this, I don't see how public-key encryption would ever need to be used at all. For example, TLS only uses RSA signature (or DSA) to sign key exchange, not RSA encryption. This makes me wonder when and/or why one would use public-key encryption at all.

Answer 1

The Integrated Encryption Scheme offers no qualitative advantage (in term of cryptographic service offered) compared to hybrid encryption using RSA. In particular, neither provides Forward Secrecy: if the private key of the recipient leaks, past cyphertexts can be deciphered. All there is to do is apply the decryption algorithm.

This contrasts with Diffie-Hellman key exchange followed by symmetric encryption with the session key, which can provide Forward Secrecy because the seeds used to generate the session key are never available to an adversary.

Asymmetric encryption protocols allowing forward secrecy (like authenticated DH combined with symmetric encryption) tend to require two-way communication (I know no exception), and thus are not universally usable. Public key encryption schemes (like IES/ECIES, and RSA combined with symmetric encryption for large messages) are the only common option for one-way communication, including email and enciphered backup (communication from past to future, thus one-way, from a cryptographer's perspective).

---

The rest of this answer compares advantages of the two encryption schemes discussed in the question.

The main advantages of RSA (with hybrid encryption, for all except very small messages) are that

• it was first there;
• it allows for very significantly more efficient asymmetric encryption (not decryption); this is an important feature in some applications where messages are of moderate size, and the enciphering party has limited computing power, or decryption seldom occurs.

The main advantage of IES is that it allows to perform asymmetric encryption based on the difficulty of solving a problem related to the Discrete Logarithm in a finite group (when RSA relies on solving a problem related to factoring). In turn, this allows:

• more efficient decryption, because smaller exponents are involved;
• and when using a finite group based on an Elliptic Curve, that is ECIES:
  • yet more efficient decryption because elementary operations can involve smaller values for conjectured equivalent security;
  • slightly smaller cryptograms when compared to straight hybrid encryption (this advantage all but disappears, except for very small messages, when we take the mildly unusual step of embedding part of the message into the RSA cryptogram).

Per request: such embedding could be as follows. Assume a 3072-bit (384-byte) public RSA modulus, and some 256-bit (32-byte) hash function $H()$. RSAES-OAEP of PKCS#1v2 allows to encipher any message $M$ from 0 to 318 bytes into a 384-byte cryptogram, by

• padding $M$ into $\widetilde M$
  
  where
  • seed is a fresh random value as wide as a hash;
  • lHash is the hash of some public constant;
  • PS is filler bytes with value zero;
  • the Mask Generating Function is some PRF, usually built from the hash.
• then applying the raw RSA public-key transformation $\widetilde M\to C=\widetilde M^e\bmod N$.

This is reversible by applying the raw RSA private-key transformation $C\to \widetilde M=C^d\bmod N$, followed by un-padding.

For $M$ above 318 bytes, we can encipher the message portion past that limit using AES-256 in CTR mode, using the 32-byte seed as key (the IV can be all-zero, or the low 128-bit of $C$). The overhead for encryption is 66 bytes (2 hashes plus 2 bytes), comparable to that of ECIES with affine coordinates on a 256-bit curve (64-byte).

Note: this simplified scheme does NOT provide message integrity; breaks the security argument of RSAES-OAEP by reusing seed; and for that reason is not easily implementable on top of usual RSAES-OAEP APIs, which tend to give no access to seed.