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?

  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Dec 10 '19 at 23:09
  • $\begingroup$ 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? $\endgroup$ Dec 11 '19 at 16:41
  • $\begingroup$ @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. $\endgroup$
    – 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.

  • 2
    $\begingroup$ 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. $\endgroup$
    – Maeher
    Dec 11 '19 at 19:01
  • $\begingroup$ 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. $\endgroup$
    – 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<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$.


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


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.