9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Dec 17 '17 at 13:24
8
$\begingroup$

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

$\endgroup$
0
$\begingroup$

A key reason I see for the use of RSA hybrid encryption, and as far as I know this is the only way to achieve what I'm about to describe, is efficient sharing of large messages with multiple recipients.

Given a large message $M$, a random key $k$, and $p_x$ the public key for recipient $x$, one can share $Enc_k(M)$ in a public space where all recipients can access it and separately distribute $p_1(k), p_2(k), ..., p_n(k)$ to each of your $n$ intended recipients.

With IES the symmetric encryption key is different for each recipient, so you end up sending $n$ ephemeral public keys and $n$ different encrypted versions of $M$. So in cases where encrypting and distributing $n$ copies of $M$ is time-consuming or otherwise impractical, being able to encrypt once and then distribute the same key to each of your recipients is extremely valuable.

I think this explains why it would be desirable in the context of PGP, where one could imagine sending a large email attachment to a considerable number of users—having to re-encrypt the attachment for each user would be cumbersome. Using IES in this context would remove this efficiency while not adding any additional security.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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