# How to create an EC point from a plaintext message for encryption

It seems that ElGamal encryption is also possible for Elliptic Curve cryptography. However, that requires the user to convert the message to a point on the curve. What strategies are there to derive a point from a plaintext message? Is it simply generating an X value that just the message converting to a number and finding the Y coordinate for that X value?

• This has come up a few times now, so I might as well ask myself. I did some interesting techniques myself using a derivation from OAEP, but that was rather protocol specific. Dec 10, 2019 at 23:09
• What use case(s) do you have in mind for this? In particular, can you think of something for which a KEM approach (generate random curve point and encrypt it, use hash of point as symmetric key to encrypt message) wouldn't work? Dec 11, 2019 at 16:41
• @IlmariKaronen I don't. The question to encrypt / decrypt without involving symmetric cryptography (i.e. a hybrid cryptosystem) has come up a few times, and this question often seems to be left hanging, so I thought it was a good idea to ask separately. If I'd need something like KEM, I'd use ECIES - both can be used to establish a key after all. Dec 11, 2019 at 17:12

The standard approach for this goes as follows, which I think is usually attributed to this paper by Koblitz:

Suppose you have a curve over an $$k$$-bit prime field. Also suppose you want to encode a fixed-length $$k-1-\ell$$ bit message - the one bit is subtracted to not having to mess with non-power-of-two field sizes. Then iteratively execute the following:

1. Compute $$x=m\mathbin\|0^\ell$$
2. Compute $$x'=x^3+ax+b\bmod q$$ for the curve's parameters $$(a,b)$$ and the field prime $$q$$.
3. If $$x'$$ is a quadratic residue, compute $$y=\sqrt x\bmod q$$ and return $$(x,y)$$ else increment the last $$\ell$$-bit of $$x$$ by 1 and try steps 2 and 3 again. If these fail $$2^{\ell}$$ times abort with "non-encodable"

Decoding simply ignores the $$y$$-coordinate and strips away the last $$\ell$$ bits of the received point.

This should work because the set of quadratic residues modulo a prime has size roughly $$q/2$$. Therefore, you have roughly a $$1/2$$ chance of any given $$x'$$ working. Given that you try $$2^\ell$$ values, you have roughly $$2^{-2^{\ell}}$$ chance of none working.

• Interestingly an encryption scheme using this encoding procedure would no longer be complete according to standard definitions. Because even if we allow for non-perfect completeness, the probability of decryption errors is only taken over the randomness of the encryption process, but not the sampling of the message. Dec 11, 2019 at 19:01
• I'm still accepting this answer although users should be beware of the comment above and that additional step may have to be taken for it to be considered secure. Unless @Maeher tells me it cannot be made secure, of course. Dec 17, 2019 at 20:26
• Note that this method will produce a point on the curve, but if the curve has a cofactor then this is not guaranteed to produce a point in the correct subgroup. For many applications, this will not be an issue. However it is something to be aware of if ElGamal EC points are being manipulated in more complex ways. Dec 30, 2021 at 15:10

There is also a variant of Koblitz's approach *

Let the message units $$m$$ be integers $$0, let $$\kappa$$ be large enough integer so that we are satisfied with error probability $$2^{-\kappa}$$, when we try to embed plaintexts $$m$$. In practice it is around $$30\leq \kappa \leq 50$$.

Now take $$\kappa =30$$ with an elliptic curve $$E:y^2 = x^3+ ax +b$$ over $$\mathbb{F}_q$$ with $$q=p^r$$ with $$p$$ is a prime.

• Embedding: Given a message number $$m$$ compute the following values for $$x$$ for embedding the message $$m$$:

$$x = \{m\cdot \kappa +j, \ \ j=0,1,\ldots \} = \{30m,\ 30m+1,\ 30m+2,\ \ldots\}$$ until we found $$x^3+ ax +b$$ is a square modulo $$p$$ and this gives as the point $$(x,\sqrt{x^3+ax+b})$$ on the elliptic curve.

• To convert a point $$(x,y)$$ on $$E$$ back to original message number $$m$$, compute $$m= \lfloor x/30 \rfloor$$

$$x^3+ax+b$$ is a square approximately half of all $$x$$, i.e. 50%. Therefore with only around $$2^{-\kappa}$$ probability that this method will fail to embed a message to a point on $$E$$ over $$\mathbb{F}_q$$. In that case, choose another $$\kappa$$.

Example

Let $$E$$ be $$y^2 = x^3+ 3x$$, $$m=2174$$ and $$p=4177$$. Now calculate the series $$x = \{30\cdot 2174,\ 30\cdot 2174 +1,\ 30\cdot 2174+2,\ \ldots\}$$ until $$x^3+3x$$ is a square modulo $$4177$$. It is square when $$j=15$$

\begin{align} x & =30 \cdot 2174 + 15 \\ & = 65235 \\ x^3+3x &= (30 \cdot 2174 + 15)^3 +3( 30 \cdot 2174 + 15)\\ & = 277614407048580 \\ & \equiv 1444 \bmod 4177\\ & \equiv 38^2. \end{align}

Therefore the message $$m=2174$$ is embedded to the point $$(x,\sqrt{x^3+ax+b}) = (65235,38)$$

To convert the message point $$(65235,38)$$ on $$E$$ back to the original message $$m$$ compute $$m=\lfloor 65235/30\rfloor = \lfloor 2174.5 \rfloor = 2174$$

* This answer is based on the book of Song Y. Yan "Computational Number Theory and Modern Cryptography".

Notes:

1. This answer was given for ECC-ElGamal encryption where $$M+[r]P$$ is calculated. It is possible that $$M$$ is encoded into a short group if the curve group is not a prime group, i.e. we have a cofactor >1. This is not a problem in the case of pure ECC-ElGamal encryption.

2. The $$\kappa$$ must be agreed on both sides for proper converting a point to the original message.

3. Instead of ECC-ElGamal encryption use Elliptic Curve Integrated Encryption Scheme (ECIES)

4. If you use this encoding other than pure ElGamal encryption, make sure that small-subgroup doesn't introduce insecurity.

• As noted for the other answer, this method is not guaranteed to produce a point in the correct subgroup if the curve has a cofactor (but it probably will not matter, depending on how you use the point later). Dec 30, 2021 at 15:23
• @knaccc I don't see that this makes a problem for ECC-ElGamal. Both Q and A was for this. Am I missing a point? Dec 30, 2021 at 15:53
• It depends what you do with the points later. If it's just simple addition and subtraction to encrypt/decrypt, then that'll work. But there are more complex things that can be done with the ElGamal points, such as proving two ciphertexts are encryptions of the same message. Subgroup attacks could be possible when you do certain complex things. For example, the DEDIS library considered this important enough to do the subgroup check github.com/dedis/kyber/blob/…. It's just something to be aware of. Dec 30, 2021 at 16:15
• @knaccc I've added some notes to make sure that no one uses it blindly. Thanks. Dec 30, 2021 at 16:34
• Btw it's not necessarily a small subgroup attack that's the problem, it's also being in the wrong large subgroup that can be an attack vector. It was a such a problem that caused a vulnerability in the Monero codebase, which is why I'm particularly sensitive to sanitizing EC points. Dec 30, 2021 at 16:37