0
$\begingroup$

I'm trying to work out a problem from a previous exam in Cryptography regarding elliptic curves. I can add points on an EC using the formulas given, but the suggested solution to this exam problem I cannot understand.

The EC is given by $E:Y^{2} = X^{3} + X + 46$ over $\mathbb{F}_{101}$, and I'm given three points, $P = (2,37)$, $Q = (54,2)$ and $R = (64,19)$ I'm supposed to show that $$6P + 2Q + R = \infty$$ $$2P + Q + 2R = \infty$$

$\infty$ being the identity or zero/neutral element of the corresponding group. I tried to compute the addition of the points to itself and see if some inverses turned up, but I might have made a mistake because I couldn't find such a property. The suggested solution however talks about doublings and addition, and the cost of these operations. I don't really understand how that plays a part, and nowhere in the solution do they compute anything so I'm really unsure how they arrive at the correct conclusion. Some help would be appreciated.

EDIT: Someone asked to see the suggested solution, but I couldn't figure out how to format it correctly, so I'll give a link to it. It's the answer to problem 3b). https://wiki.math.ntnu.no/_media/tma4160/losning2013.pdf

$\endgroup$
  • $\begingroup$ One would need the curve itself for the computation, I suppose? $\endgroup$ – Hagen von Eitzen Oct 4 '15 at 12:04
  • $\begingroup$ Oops, I'll make an edit $\endgroup$ – Auclair Oct 4 '15 at 12:04
  • $\begingroup$ It might help to know the curve :p. Anyway given that it shouldn't be too hard to show that $6P + 2Q = -R$ and $2P+2R = -Q$. $\endgroup$ – fretty Oct 4 '15 at 12:05
  • $\begingroup$ Can you give the "suggested solution"? As it is, I don't see any way to show it other than to just compute, which is probably not what is expected. (It is true, by the way.) $\endgroup$ – fkraiem Oct 4 '15 at 19:26
  • $\begingroup$ That's funny, the suggested solution doesn't even answer the question. It tells how to answer it in the most efficient manner (this is why they are talking about the cost of doubling, etc), but doesn't show the steps in answering. $\endgroup$ – mikeazo Oct 5 '15 at 12:53
1
$\begingroup$

I was disposed to solve your question but the point $R=(63,19)$ does not belong to the curve $E$ so have no sense neither, the addition with $R$ nor the duplication point $2R$.

If you edit your post, I could give an answer maybe. I wonder a related problem could be find the point $R=(x,y)$ in order to have your relations (not forgetting that $ nP $ is given by a polynomial formula of degree $ n ^ 2 $). It would be convenient, if you edit, say that your $\infty$ is assumed to be the zero of the corresponding group.

NOTE.- I hope, anyway, not to be wrong saying $R\notin E$

              **********************

ADDENDUM.-This question only requires calculations with formulas defining the law of the group $E$, calculations in the finite field $\mathbb F_{101}$ which may be somewhat laborious task. It seems to me that AT LEAST ONE OF THE TWO GIVEN RELATIONS IS WRONG! because calculating $-Q = 2 (P + R)$ and $2P = 3R$ (this last relation implicated by elimination of $Q$) not give me the correct verification in both cases. I give here the calculation of $2(P+Q)$ which results distinct of $-Q$. If I am wrong in this calculation (with some frequency it happens to me) I think what is important is to see clearly the way this kind of problems in the realm of elliptic curves is solved.

                              ********************************

Then $R=(64,19), P=(2,37), Q=(54,2)$, so $-Q=(54,-2)$ lie in the curve $E: Y^2=X^3+X+46$ and it is asked to verified the relations $$6P+2Q+R=0….(1)$$ and $$2P+Q+2R=0….(2)$$ I have to use the formulas defining the group $E: y^2=x^3+Ax+B$.

If $P_i=(x_i,y_i); i=1,2$ then $P_1+P_2=(x_3,y_3)$

with $$x_3=m^2-x_1-x_2$$ and $$y_3=m(x_1-x_3)-y_1$$ where $$m=\frac{y_2-y_1}{x_2-x_1}\text{ when}\space\space P_1\ne P_2$$ and $$m=\frac{3x_1+A}{2y_1}\text{ when}\space\space P_1=P_2$$.

                               ********************************  

We calculate in detail with

$\boxed{2P+Q+2R=0\iff –Q=2(P+R)}$

►$P+R=(x,y)=?$

$m=\frac{19-37}{64-2}=\frac{-9}{31}$ then $$x=(\frac{-9}{31})^2-64-2=\frac{81-66\cdot(31)^2}{(31)^2}=\frac{-63345}{961}=\frac{-(627\cdot101+18)}{9\cdot101+52}=\frac{-18}{52}=\frac{-9}{26}=-9\cdot35=-315=-12$$ $$y=(\frac{-9}{31})(2-(-12))-37=\frac{-9\cdot14-31\cdot37}{31}=\frac{-1273}{31}=\frac{-(12\cdot101+61)}{31}=\frac{-61}{31}=-61\cdot88=-61(-13)=793=7\cdot101+86=86=-15$$ Thus $P+R=(-12,-15)$

►$2(P+R)=2(-12,-15)=(x,y)=?$

$m=\frac{3(-12)+1}{2(-15)}=\frac{-35}{-30}=\frac76$ then $$x=(\frac76)^2-2(-12)=\frac{49+36\cdot24}{36}=\frac{913}{36}=913\cdot87=4(-14)=-56=45$$ $$y=\frac76(-12-45)-(-15)=\frac{7(-57)+6\cdot15}{6}=\frac{-309}{6}=-\frac{309}{6}=\frac{-6}{6}=-1$$ Thus $2(P+R)=(45,-1)\ne(54,-2)=-Q$ which would imply that the relation (2) is false (If none error in this calculation).

$\endgroup$
  • $\begingroup$ You are correct, $(63,19)$ doesn't lie on the curve, but $(64,19)$ does. I copied the wrong point, but for my own computations I've used the correct one. $\endgroup$ – Auclair Oct 4 '15 at 18:43

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.