1
$\begingroup$

I need to compute ecc multiplication with this values : $ P=(1,3)\space ; \space k=2 \space ; \space a=24 \space ; \space b= 13 \space ;\space p=29 $ which means $y^{2}=x^{3}+24x+13 \space$. as far as I know in such situation one should compute values using this formula :

$ \lambda= \frac{3x^{2}+a}{2y} $

$ x_r=\lambda^2 - 2x $

$ y_r=\lambda(x-x_r) - y $

when I calculate equation I end up $R=(18.25 , 6.375)$ where true answer of this shoud be $R=(11,10)$ (this site proves it : http://www.christelbach.com/eccalculator.aspx). please help me to find my calculation mistake.

note : just if you are interested I'm using this matlab code :

   temp=(3*(x1^2)+a)/(2*y1);
   x3=mod(temp^2-x1-x2,n);
   y3=mod((x1-x3)*temp-y1,n);
$\endgroup$
3
$\begingroup$

For adding, subtracting, and multiplying modulo 29, you can just do the operation in the integers and take it modulo 29 (as you're already doing). To find $a/b$, however, you need to use the extended Euclidean algorithm to find the inverse of $b$ modulo 29, then compute $a \cdot b^{-1}$. This StackOverflow post has pseudocode for the extended Euclidean algorithm. Your mistake is trying to use ordinary division to compute temp.

Multiply $3x^2 + a$ by the inverse of $2y$ to compute temp in your code and you should be good, at least if your goal is to multiply $P$ by 2. If you want to add distinct points, you need to compute $\lambda$ with a different formula, but the rest is the same; if you want to multiply by something other than 2, you should implement something akin to exponentiation by squaring.

$\endgroup$
1
$\begingroup$

The duplication formula for elliptic curves $y^2=x^3+Ax+B$ (over a field $K$ with $char(K)\not=2\ $) is $$x(2P)=\frac{x^4-2Ax^2-8Bx+A^2}{4y^2}$$ Setting $x=1,y=3$ you get $x(2P)=\frac{19}{36}.$ You have to compute the previous fraction in the finite field $GF(29).$ This is computed as $19\cdot 36^{-1}\pmod {29} = 11.$

Further you can copy-paste the following (sage)-code in sagecell

p=29
E=EllipticCurve(GF(p),[0,0,0,24,13])
E;
P=E(1,3)
2*P
$\endgroup$

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.