2
$\begingroup$

In one of my assignments I need to solve the problem below:

For a Montgomery curve $3y^2 = x^3+x^2+x$ over ${\mathbb{F}}_{11}$ and point $P = (9,8)$, compute the $x$ coordinate of $3P$ using the Montgomery ladder.

I just need a hint to get an idea and not the whole answer. if anyone with some useful links would also be appreciable. As I tried to search google for this but was not able to get any idea.


Is it that I need to find it as $3P = 2P + P $ because I found one question about scalar multiplication here. but then I think it is not the correct way to use the Montgomery ladder.

$\endgroup$
  • $\begingroup$ Do you know what the Montgomery ladder algorithm is? $\endgroup$ – poncho Jan 16 '16 at 1:57
  • $\begingroup$ Yes I have read about it and I know that we double when we have bit 1 and we add if bit 0. But I am not able to apply here. Or otherwise I haven't that much knowledge about it. $\endgroup$ – TechJ Jan 16 '16 at 1:59
  • 3
    $\begingroup$ See en.wikipedia.org/wiki/… $\endgroup$ – poncho Jan 16 '16 at 4:58
3
$\begingroup$

The Montgomery Curve is introduced by Peter L. Montgomery for speeding up the Pollard and Elliptic Curve Methods of integer factorization. Montgomery Curves are in the form $By^2=x^3+Ax^2+x$ and it is also represented as $M_{A,B}$.

Addition and Doubling Formulas of Montgomery Curves

Given Montgomery Curve $By^2=x^3+Ax^2+x$ and the point $P_1 = (x_1,x_1)$ and $P_2 = (x_2,x_2)$ than the addition and doubling, $P_3 = (x_3,x_3) = P_1+P_2$ as follows

  • Addition formula in Affine Coordinates: $(P1 \neq \pm P2)$

\begin{align} \alpha & = (y_2 − y_1)/(x_2 − x_1)\\ x_3 & = B \alpha^2 − A − x_1 − x_2\\ y_3 & = \alpha (x_1 − x_3) − y_1 \end{align}

  • Doubling formula in Affine Coordinates: $(P1 = P2)$

\begin{align} \alpha & = (3x_1^2 + 2 A x_1 + 1)/(2 B y_1)\\ x_3 & = B\alpha^2 − A − 2x_1\\ y_3 & = \alpha (x_1 − x_3) − y_1 \end{align}

As usual, these are calculated from the geometrical meaning of addition.

Montgomery Ladder

The Montgomery Ladder is an algorithm to calculate $[x]P$ for a given scalar $x$ and a point $P$.

Represent $x$ in binary $x= x_0 + 2x_1 + 2^2x_2 + \cdots + 2^mx_m $ and let $m= \lfloor \log_2 x \rfloor$.

  R0 = 0
  R1 = P
  for i from m downto 0 do
     if xi = 0 then
        R1 = point_add(R0, R1)
        R0 = point_double(R0)
     else
        R0 = point_add(R0, R1)
        R1 = point_double(R1)
  return R0

Calculation

Now, $x=3 = 1 + 2\cdot 1$, i.e. $x_0=1$ and $x_1 =1$

$m= \lfloor \log_2 3 \rfloor = 1$. Therefore, we visit the loop twice.

since $x_i =1$ we will be always in the else case, or simply we run the below.

  1. R0 = 0
  2. R1 = P
  3. R0 = point_add(R0, R1)
  4. R1 = point_double(R1)
  5. R0 = point_add(R0, R1)
  6. R1 = point_double(R1)
  7. return R0
  1. $R_0 = \mathcal{O}$
  2. $R_1 = P$
  3. $R_0 = \mathcal{O} + P = P$
  4. $R_1 = P + P = [2]P$
  5. $R_0 = [2]P+P = [3]P$
  6. $R_1 = [2]P+[2]P = [4]P$
  7. return $R_0 = [3]P$

The given Montgomery Curve $3y^2=x^3+x^2+x$ than it is $M_{1,3}$ so $A=1,B=3$ and $P=(9,8)$

$[2]P = (1,10)$ by the below simple sage math point doubling.

k.<a> = GF(11, modulus="primitive")
k.modulus()
A = k(1)
B = k(3)
x1 = k(9)
y1 = k(8)
alpha  =  (3*x1^2 + 2 *A * x1 + 1)/(2 * B * y1)
x3 = B * alpha^2 - A - 2 * x1
y3 = alpha *(x1 - x3) - y1
print x3
print y3

$[3]P = [2]P+P = (5,2)$ by the below simple sage math point addtion.

k.<a> = GF(11)
A = k(1)
B = k(3)
x1 = k(9)
y1 = k(8)
x2 = k(1)
y2 = k(10)
alpha = (y2 - y1)/(x2 - x1)
x3  = B * alpha^2 - A - x1 - x2
y3  = alpha * (x1 - x3) - y1
print x3
print y3

Notes :

| improve this answer | |
$\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.