3
$\begingroup$

Can anyone answer me, if I can embed a message when I convert it to ASCII value to points on Elliptic curve $E(Fp)$ , by multiplied the ASCII value with a base point B?

For example, I have $E(F_{31}): y^2=x^3+x+3 \bmod 31$, a base point $B=(1,6)$ and the order of the the elliptic curve is $N= 41.$

To convert the text "Hello" to ASCII values we get $\{72,101,108,108,111\}$ and embedding them to get points lie on $E(F_{31})$ by following:

$72 B=72 (1,6)=(26,11)$ and so on.

Is that true to do that??

$\endgroup$
3
$\begingroup$

Can anyone answer me, if I can embed a message when I convert it to ASCII value to points on Elliptic curve $E(Fp)$ , by multiplied the ASCII value with a base point B?

This is probably a rather more extensive answer than what you were looking for; however here it goes:

There are a number of reasons why we might need to convert a 'value' to a curve point, that is, define a function $F(x)$ that takes a value $x$, and maps it to a point on $E(\mathbb{F}_p)$; there are also a number of ways to do so. Which one is best depends on the requirements that the use case demands. Some on the requirements to consider:

  • Does it need to be invertable? That is, if you're given a point $F(x)$, do you need to be able to recover $x$ (or, do you need that the problem of recovering $x$ to be difficult)? Some use cases need it to be invertable, others don't care.

  • Do you need to obscure the relationship between two mapped points? That is, if someone knows $x, y$, is it a problem if they can deduce the discrete log of $F(y)$ to the base $F(x)$; that is, if that can find the value $n$ s.t. $n \cdot F(y) = F(x)$? For some use cases, it is critical that this be a hard problem; for others, it isn't important.

  • How important is side channel resistance? If someone can listen into the computer evaluating $F(x)$ (e.g. by monitoring the timing), how important is that they not be able to get information on $x$? Again, for some use cases, this is critical.

Within those three requirements, there are three obvious strategies to implement $F(x)$:

  • Use simple point multiplication, which is your original idea, define $F(x) = x \cdot G$, for the curve generator point $G$. This is moderately efficient (using code you probably have lying around anyways) and (depending on your point multiplication routine) potentially side channel resistant; however it obviously makes the discrete log problem fairly easy. And, it is potentially invertable with some work if the range of possible $x$'s are small - if we know that $0 < x < n$, this we can recover $x$ with $O(\sqrt{n})$ steps.

  • Use a 'hunt and peck' approach, as suggested by Koblitz. You map the $x$ value into a potential $x$ coordinate, and then search for near-by values for which is the $x$ coordinate of an actual point (and then pick the $y$ coordinate somehow). This can obviously be made either invertible or noninvertible as required, and it disguises any relationship between mapped points. On the other hand, this isn't that efficient, and side channel resistance can be tricky (at least, I've seen people get it wrong).

  • Use a Hash2Curve algorithm, such as one found here. These algorithms are quite efficient, and they obscure any relationship between mapped points. On the downside, these algorithms are noninvertible, and the algorithms that can be used depend on the actual curve (generally, the value of $p$).

One last note: you appear to be asking how to embed messages in points so to use ECElGamal. In practice, we never use ECElGamal; it is rather more practical to use ECIES, where we use the Elliptic Curve to share a point that only the encryptor and decryptor know, and use that point to derive a symmetric key that encryptions the actual message. This solves the problem, without any need to map the message to a point.

| improve this answer | |
$\endgroup$

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.