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

enter image description here

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

  • $\begingroup$ 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. $\endgroup$
    – SEJPM
    Oct 31 '18 at 19:55
  • $\begingroup$ iacis.org/iis/2017/2_iis_2017_103-112.pdf it is here $\endgroup$ Oct 31 '18 at 20:07
  • $\begingroup$ @SEJPM could you elaborate a bit more please, how it is done? $\endgroup$ Oct 31 '18 at 20:08
  • $\begingroup$ 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. $\endgroup$
    – kelalaka
    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.

  • $\begingroup$ 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. $\endgroup$
    – SEJPM
    Oct 31 '18 at 20:36
  • $\begingroup$ I just found that 10 works and saw your post :) $\endgroup$
    – kelalaka
    Oct 31 '18 at 20:37

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.