Need clarity on plotting the y cordinate from the x co-ordinate in Elliptic curve cryptography

edit

The source is hard to read, both mathematically and with a xpdf viewer, so let us restrict us to understand only the paragraph related to the questions (1) and (2) above. We are now on the page 1906 and the cook book tells us to initialize the elliptic curve $$ E_p(a,b)\ :\ y^2=x^3 +ax+b\ , $$ defined over the field $\mathbb F_p$ with $p$ elements. This field is GF(p) in sage. So in order to initialize this object in sage, for the special choice of the example at loc. cit., $p=751$, $a=-1$, $b=188$, we type (in the sage interpreter console):

sage: E = EllipticCurve( GF(751), [ -1, 188 ] )

sage: E
Elliptic Curve defined by y^2 = x^3 + 750*x + 188 over Finite Field of size 751

sage: E.order()
727

OK, i was too curious to see the "order of the curve", i.e. the number of points lying on it. So the order is this $n=727$, the source uses $n$, sometimes $N$ for this number.

In order to produce some confusion, the source wants to send the letter b as a message. (They could have taken some J or so... since the curve has parameters a, and b.) In the next second we want but to send the B instead. No problem, we are sending the $11$, convention, the letters A, B, C, ... are by convention converted to 10, 11, 12, ... . "Same information".

There is also some parameter, $k=20$. Setting this parameter as Step 5 makes it better. So the confusion on my side takes shape. (Why not set it once for all times at the beginning as parameter? Does this $k=20$ depend on something chosen in the previous steps?)

The cook book wants now to associate the $x$-value to the $B$ given by the "formula": $$ x = mk+1 \overset ?= 11\cdot 20+1\ .$$ With this occasion, we record the fact that the $11$ is in fact an $m$. Or at least ask ourselves, and accept it, since we cannot change the pdf. Starting with the natural number $221$ from above, we seek for the first $x$ in the sequence $221, 222, 223, 224, 225,\dots$ so that $(x,?)$ is a point on the given curve. Let us do this in sage:

sage: for x in [ 221..751 ]:
....:     if F(x^3 - x + 188).is_square():
....:         print x
....:         break
....:         
224

We take then this first occurence and associate the corresponding $?$ value. There are two of them, of course:

sage: sqrt( F(224)^3 - F(224) + F(188) )
248

Both sage and the source consider that $248$ is the better square root. (The value $-248=751-248=503$ is the other one.)

The source than claims:

6. Now the point (224,248) is point is encrypted and decrypted as a message.

And this is a good point to stop. I think, we can now decrypt the way things can / could be done in the setting of the article.

N.B. Please excuse the many personal comments. But it was really hard & frustrating to get the message from the article, after this, doing the job in sage took seconds. Best, the author would have written it by providing sage code...