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

Question

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?

Answer 1

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.

Answer 2

There is also a variant of Koblitz's approach ^*

Let the message units $m$ be integers $0<m<M$, 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.