2
$\begingroup$

According to ElGamal encryption, in order to encrypt a message I need to generate a shared secret s and after that I am to calculate c1 and c2 that are the final encrypted data. But what if my message is much longer than the bitness of the encryption system? I could split the message into many chunks and encrypt them separately.

  1. Would it be correct to use the same shared secret for all these chunks?
  2. Or I have to generate separate shared secrets for each chunk?

The first option would be preferable because it is much less expensive, but naively it looks less secure. Does this option have any vulnerability? Is there any research where I could read about it?

| improve this question | |
$\endgroup$
  • 3
    $\begingroup$ In practice, what we do when we need to encrypt a long message with a public key, we select a random symmetric key (which isn't that long), encrypt that with the public key system, and then encrypt the message with the symmetric key (using, say, AES or ChaCha20). Hence, the 'how do we split up a long message' just doesn't come up... $\endgroup$ – poncho Jun 30 at 15:06
2
$\begingroup$

As I mentioned in my comment, how you are proposing to use El Gamal has little to do with how we use it (or any public key encryption system) in practice. However, I can modify the question slightly in a way to make it relevant:

But what if have multiple messages I want to encrypt?

  1. Would it be correct to use the same shared secret for all these messages?
  2. Or I have to generate separate shared secrets for each message?

In your question, you were splitting up one message into several; however, someone could equally well want to encrypt several independent messages to the same public key.

Now, if we were to use the same shared secret, we'd give (for the messages $M_1, M_2, ,,., M_n$), we'd give the adversary the values $S \cdot M_1, S \cdot M_2, …, S \cdot M_n$).

Now, with encryption, we want to limit any information the attacker can obtain from the ciphertexts to what he already knows. Now, this is an issue with reusing the same shared secret; for example, if the attacker already happens to know (or guess) $M_1$ (or in the split-up message case, he already knows a part of the original message), we'd like him not to be able to leverage that to learn anything else. However, with knowledge of $M_1$, he could recover $S$; with that, he could recover the plaintexts of all the other messages (or in the split-case, the entire long message), and so he does learn far more than what he started with (which was knowledge of $M_1$).

Because of this (and other attacks that allow the adversary to recover $M_1 \cdot M_2^{-1}$, also more information than we'd like him to have), we really need an independent shared secret for each message.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the answer and the explanation. But what if an attacker does not know any of the original messages? Is it secure in this case or still there is a way to compute S somehow? $\endgroup$ – Fomalhaut Jun 30 at 20:26
  • $\begingroup$ @Fomalhaut: typically, it is wise to assume that the attacker does have some partial information (or, at least, plausible guesses). $\endgroup$ – poncho Jun 30 at 20:36
  • $\begingroup$ I understand it. But I still want to know the answer. Maybe there is a research about it. $\endgroup$ – Fomalhaut Jun 30 at 20:40

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.