# How to securely map messages to points on an elliptic curve

I'm implementing a demonstration hybrid cryptosystem in Python (FinCrypt, I know the name is bad) and I'm migrating over from my Weierstrass curve implementation, which was based off of this, to one based on Edward's curves from here.

However, I'm at a loss when it comes to mapping a message onto an element of the elliptic curve, and I noticed that the implementation I'm currently using doesn't require the message to be mapped, at least to my knowledge.

I was wondering three things:

1. Do I have to map a message, or is it possible to do something like I've already got going with Edward's curves
2. Is my current implementation of the ElGamal part insecure because it doesn't map messages and instead takes an integer?
3. If I do have to implement a mapping for security, how would you reccomend I map message values to points, and how should I figure out the maximum message size based on my curve?

If I do have to implement a mapping for security, how would you reccomend I map message values to points, and how should I figure out the maximum message size based on my curve?

The default strategy for encoding an integer message as curve point is to define a value $$k$$ smaller than $$\log_2 p$$ (with $$p$$ being the field prime), such that for every valid message length $$m$$, $$m+k< \log_2 p$$ holds. You would then encode the message as the $$m$$ high bits of the x coordinate and start counting up on the $$k$$ low bits until you reach an $$x$$ that has an $$y$$ on the curve (which you find using the curve equation). This usually has probability $$2^{-k}$$ of failing to encode a message. For decoding you simply throw away the $$k$$ low bits and take the rest as your message.

Is my current implementation of the ElGamal part insecure because it doesn't map messages and instead takes an integer?

Yes, the scheme as given is insecure because you can easily distinguish an encryption of $$1$$ from an encryption of $$2^{1024}$$ because the former will be about as long as the curve's prime and the latter will be more than 1024-bit long, which formally breaks the IND-CPA security of the scheme.

Note that in order to use proper ElGamal you need to encode your message as a curve point $$M$$ and then compute $$c_1=[k]\beta+M, c_2=[k]G$$ all as operations on the curve. Also note that I'm fairly confident that simply replacing the unbounded integer addition with integer addition $$\bmod p$$ will not yield security either because curve point coordinates are not uniformly chosen integers (for starters because some $$x$$ values simply do not occur).

Do I have to map a message, or is it possible to do something like I've already got going with Edward's curves

I see no reason to make any changes to your code, because currently it doesn't actually use ElGamal (see above). If you were to use proper ElGamal, the same strategy that worked for Weierstrass should also work for Edwards (see the first part).

• What is expected of the program in the cases where the number cannot be mapped? – ThePlasmaRailgun Oct 9 '18 at 19:28
• @ThePlasmaRailgun It should reject the message with an error. – SEJPM Oct 9 '18 at 21:04
• How would I do it in a production cryptosystem, where a seemingly random inability to encrypt a message would be unacceptable? Or is the chance just low enough that you wouldn't need to worry. – ThePlasmaRailgun Oct 9 '18 at 22:29
• I'm using the E-521 curve and would like to encrypt in at least 64 byte blocks, if that helps you figure out the probabilities – ThePlasmaRailgun Oct 9 '18 at 22:30
• @ThePlasmaRailgun that would give you about 8-9 bits to play with for the encoding, thus giving you a probability of $2^{-8}$ of failure, which is not good. Note that there is no known deterministic encoding of messages into elliptic curve points, so you always have to deal with these probabilities. Of course you could just dedicate about 8 bytes to the encoding which would give you $2^{-64}$ which should be good enough. Also you probably shouldn't be using this to begin with, but rather something like ECIES. – SEJPM Oct 10 '18 at 7:55

using a kobltiz method we convert a message into an elliptic curve point

• Welcome to crypto.stackexchange - The system has auto-flagged this answer as low-quality due to it's length and content. Can you please elaborate and explain? – Ella Rose Mar 14 '19 at 20:27