# How to secure Elliptic Curve ElGamal encryption against known plaintext attacks?

If I have an encoding function $$f(x)$$ that maps a message $$m$$ to a point $$P$$ on a suitable Elliptic Curve $$E$$ . If I have the public key $$Q$$ of my recepient then I can encrypt the message as follows:

Choosing a random number $$k < n -1$$ where $$n$$ is the order of the curve E .

Calculating $$C = [k] G$$ where $$G$$ is the generator point of the curve E

Calculating $$R = [k]Q$$ where $$Q$$ is the recipient's public key

Now the message is encrypted by adding $$P$$ to $$R$$ to get $$C_e$$ $$( = R + P)$$ which is sent along with $$C$$ to the recepient.

DECRYPTION:

Now for the recepient to decrypt my message they compute $$R = [privatekey] C$$ (where $$C = [k]G$$) and simply subtract $$R$$ from $$C_e$$ to get the encoded point $$P$$ back which is then decoded by an inverse function $$f^{-1}(x)$$ to recover $$m$$. Now , two problems arise : If the attacker knows the plaintext (suppose if I follow a particular format of data while sending messages ) he could encode his guessed plaintext and subtract it from $$C_e$$ to recover $$R$$ back ! . If I used that same $$R$$ to encrypt further "blocks" of my message then the security of the later parts of my message has been breached!

I realize that doing something like a scalar multiplication over and over again for every block of data, would be a huge drawback in efficiency and speed.

Is there any way to compute a different $$R$$ for every block of data, without using much resources and that too quickly ?

Does reusing the same $$R$$ for another message break security ?

NOTE: This question is for educational purposes only. It's for the sake of expanding my knowledge on Crypto.

• $R=[privatekey]C$ are you sure about this equality? $R = [k\cdot pivatekey]G$ – kelalaka Feb 9 at 14:27
• @kelalaka Yes $R = [privatekey] C$ where $C = [k] G$ – Vivekanand V Feb 9 at 15:38
• Well, you can of course random pad the message using e.g. OAEP, but the problem with EC is that there will be very little message space left - if any. – Maarten Bodewes Feb 10 at 2:52
• What you're describing is not ElGamal. ElGamal does not reuse randomness. As always, the correct solution to the original problem of encrypting long messages using something like ElGamal is ECIES. – Maeher Feb 10 at 8:07
• @VivekanandV ElGamal does not operate on "blocks". The message space of ElGamal defined over group $\mathbb{G}$ is $\mathbb{G}$. You are encrypting several distinct messages. To do so, by definition, ElGamal uses independently uniformly distributed random values. Reusing randomness makes the scheme completely insecure. – Maeher Feb 10 at 9:21

Is there any way to compute a different $$R$$ for every block of data, without using much resources and that too quickly ?

There's no common way. Standard practice is hybrid encryption per ECIES.

In a nutshell, ECIES is the same as EC-ElGamal with regard to $$E$$, $$G$$, $$\text{privatekey}$$, $$Q$$, $$k$$, $$C$$, $$R$$, but the shared secret $$R$$ is used (after a key derivation step) as the key to a symmetric authenticated cipher that conveys the message $$m$$. This removes the burden of mapping $$m$$ to a point on the curve, which severely limits the size of $$m$$, and typically is iterative thus has the potential to leak information about $$m$$ by side channels.

Does reusing the same $$R$$ for another message break security (in EC-ElGamal)?

Yes. Assume $$m_0$$ and $$m_1$$ mapped to $$P_0$$ and $$P_1$$ are encrypted with the same $$R$$, into $$C_0$$ and $$C_1$$. It holds $$C_0=R+P_0$$ and $$C_1=R+P_1$$, therefore $$P_1=P_0-C_0+C_1$$. Thus $$m_1$$ can be found from $$m_0$$ and ciphertext. With $$R$$ fixed, the cipher is insecure under known-plaintext attack.

• Even if the attacker has no knowledge of a plaintext $$m_0$$, s/he does learn something about the plaintext. In particular she can tell if $$m_0=m_1$$, since that's equivalent to $$C_0=C_1$$. This qualifies as a break, since the objective of encryption is to prevent adversaries from learning anything about plaintext (except its length). As an example, this allows to distinguish between a routine Have a quiet nightshift Joe ($$m_0=m_1$$) from an exceptional Launch missile to target A ($$m_0\ne m_1$$).
• Doubling $$R$$ at each message would be extremely insecure. It would hold $$P_j+P_j-P_{j+1}=C_j+C_j-C_{j+1}$$, and that allows to decipher any message sent encrypted twice, as $$P_j=P_{j+1}=C_j+C_j-C_{j+1}$$.
• If the attacker has no knowledge of plaintext, is there any other way to break this cipher ? To prevent a known plain text attack does doubling $R$ for every next message give this cipher any immunity against it? – Vivekanand V Feb 11 at 9:16
• Thankyou for your elaborate and easy to understand answer, I thought about all the vulnerabilities that you illustrated. I think the only way to make this secure is to use a random "one time" $R$, and also an encoding function that adds unpredictability to the message based on some secret key. So considering drawbacks, ECIES would be much quicker, faster and secure. – Vivekanand V Feb 11 at 17:19