# 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. – Maarten Bodewes Dec 10 '19 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? – Ilmari Karonen Dec 11 '19 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. – Maarten Bodewes Dec 11 '19 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$$ and so you have roughly a $$1/2$$ chance of any given $$x'$$ working and given that you try $$2^\ell$$ values, you have a chance of $$2^{-\ell}$$ of none of them 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. – Maeher Dec 11 '19 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. – Maarten Bodewes Dec 17 '19 at 20:26

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".