Ask Your Question

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

asked 2015-11-04 12:54:28 +0200

abejo gravatar image

I'm just new to elliptic curve cryptography. I have been working on RSA for quite some time. Moreover I'm not from a mathematical background. The whole concept looks very complex. So tell me my understanding is correct or not. I was looking at sample implementation at In the pdf given there, the curve equation is y^2=x^3+ax+b,the domain parameters are p(751),a(-1),b(188),n(727). I want to encode a letter 'b' and it is first encoded as 11. Now x=mk+1 ie 11*20+1=221 cannot solve it for a y such that y^2= x^3 + ax+ b mod p.
So go for x=mk+2 , x=222 , no y exists. x=mk+3, x=223, no y exists. x=mk+4 so x=224 can solve it for y and y=248

1)Can somebody explain how exactly x=224 solves the equation for y?

2)On what basis mk+1 is taken? Is there any standard formula for choosing the y co-ordinate?

edit retag flag offensive close merge delete


How exactly is this related to sagemath?

If it is not related to sagemath perhaps a better site for your question would be here.

fidbc gravatar imagefidbc ( 2015-11-04 23:18:19 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2017-06-13 23:35:24 +0200

dan_fulea gravatar image

updated 2017-06-13 23:39:39 +0200

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()

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

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

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...

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2015-11-04 12:54:28 +0200

Seen: 450 times

Last updated: Jun 13 '17