7
$\begingroup$

I am confused about the distinction between RSA and ECC (Elliptic curve) when it comes to encryption and would appreciate it if someone could confirm if my understanding is correct.

When encrypting a large file using RSA, you:

  1. Generate a random symmetric key
  2. Encrypt the file using the symmetric key (AES for example)
  3. Then you encrypt the symmetric key using the receiver's public key
  4. You send the encrypted file + encrypted symmetric key
  5. The receiver takes the encrypted symmetric key and decrypts it using his own private key
  6. Then the receiver decrypts the file using the decrypted symmetric key

But if I understand correctly, encrypting using ECC is completely different, especially the order:

  1. Instead of generating a random symmetric key, you "derive" it using ECDH (using sender's private key and receiver's public key)
  2. Then you encrypt the file using the derived symmetric key (AES)
  3. You hand this over to the receiver
  4. The receiver derives the same shared key using ECDH (same logic as step 1)
  5. The receiver decrypts the decrypted file using AES

Basically, there is no such thing as "asymmetric encryption" in ECIES. There is only symmetric encryption using AES, but it works like asymmetric encryption because the shared key is generated using asymmetric cryptography.

Questions

1. Is this correct?

Am I understanding this correctly? Is there no way to create a "single encrypted file" that gets shared with everyone (instead you have to generate a distinct encrypted file for each receiver)

2. Higher guarantee that only the receiver can open?

If you're effectively generating a different version for each user, does this mean ECIES (while it's more wasteful in terms of data generated and stored) has a higher guarantee of ONLY the receiver being able to open the message? Because in the case of RSA + AES there's only one encrypted file, if the session key gets leaked anyone can decrypt it, whereas in ECIES if a receiver wants to leak a message, he needs to leak his private key. Is this correct?

3. How to efficiently broadcast to multiple parties?

If this is the case, how would I implement 1-to-N broadcast encryption of a single message efficiently?

For example, let's say I want to send a single 1GB file to 1000 people. Everybody gets the same file.

  1. RSA+AES: Using RSA + AES I can encrypt the file once and only generate N different encrypted keys. Let's say the encrypted file is 2GB and each encrypted key is 1KB. This means I end up with 2GB + 1000*1KB of data to transmit.
  2. ECIES: But when using ECIES, I must generate N unique encrypted files, which means 2GB * 1000 = 2TB of data to transmit.

If my understanding is correct, this ECIES approach does not scale as well as RSA+AES. Am I misunderstanding something? How would one implement a broadcast encrypted messaging for ECIES?

$\endgroup$
7
$\begingroup$
  1. Is this correct?

The principles are right, but a number of details are missing. Among these:

  • For RSA
    • "Encrypt the file" can't be with AES only, since that's a 128-bit block cipher, and it would be insecure past 16 bytes. There is an operating mode involved, and likely it involves generation of an Initialization Vector. It's a good idea to use authenticated encryption (though in the context it won't provide authentication, since we are dealing with public-key encryption, and anybody can encipher anything). Also there's padding.
    • "Encrypt the symmetric key using the receiver's public key" is not textbook RSA applied to the symmetric key. Some padding mode (like RSAES-OAEP of PKCS#1v2.2) is used, or (like in RSA-KEM) the symmetric key used to encrypt the file is derived by some Key Derivation Function from the a wider key, itself encrypted by transformation from bytestring to integer, textbook RSA encryption, and transformation from integer to bytestring.
  • For ECIES
    • At each use, the first step is that a random ephemeral secret integer $k$ is generated by the sender, $R\gets k\,G$ is computed and made part of the cryptogram, so that the Diffie-Hellman (or is it ElGamal) shared key $k\,Q_V=d_V\,R$ gets used only once, and can be recovered by the receiver [which private/public key pair is $(d_V,Q_V)$ with $Q_V=d_V\,G$ ].
    • In the key derivation step, a Key Derivation Function derives two symmetric keys from the shared secret.
    • In the encryption step, one of these keys is used for encryption, yielding the ciphertext, and in the missing "tagging operation" step, the other key is used to make a Message Authentication Code of the ciphertext (and possible other info). Otherwise said, authenticated encryption using encrypt-then-MAC is mandated by ECIES, when authenticated encryption is only good practice with RSA, and the way to achieve it unspecified.

  1. Higher guarantee that only the receiver can open?

No. In both cases, only the receiver can decipher, as long as the underlying crypto stands secure.

The added insurance ECIES gives comes from the mandated use of authenticated encryption. Informally, it can't happen that the message is partially altered by an attacker, or that a decryption made by the receiver of an altered message is abused into allowing an attacker decipher a genuine message. In any case, the message is not authenticated, for there is no sender public/private key pair involved.


  1. How to efficiently broadcast to multiple parties?

That's an issue for ECIES, and RSA when using RSA-KEM: since the symmetric key is derived by the asymmetric cryptography, it can't be identical for multiple recipients.

The solution is to draw a random symmetric authenticated-encryption key (e.g. for AES-GCM) used for the bulk of the file, as in RSA with RSAES-OAEP; and encipher that key to multiple recipients using ECIES, or RSA-KEM plus some cipher. In the case of RSA-KEM, it's still a good idea to use authenticated encryption for the encryption of the key, in order to not require resistance to related-key attack from the cipher used for the bulk of the file.

$\endgroup$
  • $\begingroup$ Thank you. While reading your solution I just got an idea but not sure if this is what you meant or is a different approach. Would it be possible to: 1. Encrypt a file with AES session key; 2. ECIES encrypt the AES session key for each receiver (This is significantly smaller than directly doing ECIES on the file itself); 3. For each receiver, send the same AES encrypted file + ECIES encrypted AES session key; Would this model achieve the goal? $\endgroup$ – Vlad Dec 3 '20 at 7:53
  • $\begingroup$ @Vlad: yes, this is also what my last paragraph suggests. It tried to clarify that. $\endgroup$ – fgrieu Dec 3 '20 at 7:53
  • $\begingroup$ Thank you, one last thing I'm still confused about (Question 2). Using the example right above, if I encrypted a file with one AES session key and individually encrypted the session key with N different receiver pubkeys, it is true that only the owners of the private keys can decrypt the encrypted session key. But if someone leaks the AES session key AFTER decryption, then anyone who has access to the session key can decrypt the file WITHOUT even needing the receiver private keys, no? $\endgroup$ – Vlad Dec 3 '20 at 8:05
  • $\begingroup$ @Vlad: True, if intermediary keys leak, it becomes possible to decipher the bulk of the file without a receiver private key. But as far as I can tell this always applies: RSAES-OAEP to encipher the bulk-encryption key, RSA-KEM or ECIES to generate or encrypt the bulk-encryption key. $\endgroup$ – fgrieu Dec 3 '20 at 8:11
  • 1
    $\begingroup$ I meant (full) ephemeral key pair $k, R$ (I didn't say fully ephemeral encryption scheme, of course). In the description I missed the $R$. Note that the shared secret depends on the key pair of the receiver in this case, so you need an extra step if you want to have a data key shared between recipients. That's kind of hidden because I think that the description is too short... $\endgroup$ – Maarten Bodewes Dec 3 '20 at 10:03

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.