7
$\begingroup$

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?

$\endgroup$
3
  • $\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
    Commented Dec 10, 2019 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$ Commented Dec 11, 2019 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
    Commented Dec 11, 2019 at 17:12

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\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
    Commented Dec 11, 2019 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
    Commented Dec 17, 2019 at 20:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – knaccc
    Commented Dec 30, 2021 at 15:10
6
$\begingroup$

There is also a variant of Koblitz's approach *

Let the message units $m$ be integers $0<m<M$, and let $\kappa$ be a 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 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 properly 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, ensure that small-subgroup doesn't introduce insecurity.

$\endgroup$
7
  • $\begingroup$ 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). $\endgroup$
    – knaccc
    Commented Dec 30, 2021 at 15:23
  • $\begingroup$ @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? $\endgroup$
    – kelalaka
    Commented Dec 30, 2021 at 15:53
  • $\begingroup$ 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. $\endgroup$
    – knaccc
    Commented Dec 30, 2021 at 16:15
  • 1
    $\begingroup$ @knaccc I've added some notes to make sure that no one uses it blindly. Thanks. $\endgroup$
    – kelalaka
    Commented Dec 30, 2021 at 16:34
  • $\begingroup$ 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. $\endgroup$
    – knaccc
    Commented Dec 30, 2021 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.