3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ $R=[privatekey]C$ are you sure about this equality? $R = [k\cdot pivatekey]G$ $\endgroup$ – kelalaka Feb 9 at 14:27
  • $\begingroup$ @kelalaka Yes $ R = [privatekey] C $ where $ C = [k] G $ $\endgroup$ – Vivekanand V Feb 9 at 15:38
  • 1
    $\begingroup$ 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. $\endgroup$ – Maarten Bodewes Feb 10 at 2:52
  • 1
    $\begingroup$ 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. $\endgroup$ – Maeher Feb 10 at 8:07
  • 1
    $\begingroup$ @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. $\endgroup$ – Maeher Feb 10 at 9:21
1
$\begingroup$

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.

Additions per comment:

  • 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}$.
| improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Vivekanand V Feb 11 at 9:16
  • 1
    $\begingroup$ 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. $\endgroup$ – Vivekanand V Feb 11 at 17:19

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.