# mapping point on elliptic curve

good evening guys, let us suppose that elliptic curve is given by the following equation

$$y^2=x^3-x+1 \pmod {127}$$ on the following table message $$9$$ is converted to the point on curve

if i insert directly into equation , we will get

$$9^3-9+1=721$$ and $$721$$ mod $$127$$ gives me 86, so how 91 is given? what is relation between $$91$$ and $$9$$ ? please help me

• You may want to note that there is no $y$ such that $y^2=86\bmod 127$ and as such there's no point with $x=9$ on the curve. Presumably what was done here is that 9 was taken, shifted by 1 decimal digit to the left and then 0,1,2,... was tried for the least significant digit until an x value was found that actually yields a point on the curve.
– SEJPM
Oct 31 '18 at 19:55
• Oct 31 '18 at 20:07
• @SEJPM could you elaborate a bit more please, how it is done? Oct 31 '18 at 20:08
• They claim that they use encoding from Mapping an Arbitrary Message to an Elliptic Curve when Defined over GF(2^n ). There are many encodings there. Better to ask the author. Oct 31 '18 at 20:29

After having read the "paper", which is probably just a "publication" the relevant student had to tick off, I'm pretty sure that a standard probabilistic encoding of messages to curve points was used, which is usually attributed to Koblitz. Written algorithmically:

1. Pick a message $$m$$ of 1 decimal digit length.
2. Set $$i\gets 0$$
3. Construct $$x=m\cdot 10+i$$. If $$i\geq 10$$ return with an error, this has probability around $$2^{-10}$$.
4. Compute $$y=\sqrt{x^3+ax+b}\bmod p$$ where $$\sqrt\cdot$$ is a modular square root, ie $$(\sqrt x\cdot \sqrt x)\bmod p=x$$. If no such $$y$$ exists, set $$i\gets i+1$$ and go to 3.
5. return $$(x,y)$$

Decoding a curve point can then be achieved by finding the decimal representation and cutting the last digit off.

• Note that this can easily be extended beyond "1 decimal digit" and to use bits / bytes instead of decimal digits and to allow error probabilities of around $2^{-256}$ by sacrificing one byte of message space.
– SEJPM
Oct 31 '18 at 20:36
• I just found that 10 works and saw your post :) Oct 31 '18 at 20:37