# 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
• – dato datuashvili Oct 31 '18 at 20:07
• @SEJPM could you elaborate a bit more please, how it is done? – dato datuashvili 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. – kelalaka Oct 31 '18 at 20:29

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)$$
• 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