Problem on Elliptic Curve Point Doubling

Question

Given an elliptical curve e.g. from “Understanding Cryptography” by Parr & Pelzl §9.2 Example 9.5:

$y^2 = x^3 + 2x + 2~~~~ mod~17$

And given a primitive $P = (5, 1)$, the book indicates:

We compute now all the "powers" of P.

They then provide a table:

$2P = (5, 1) + (5, 1) = (6, 3)$

$3P = 2P + P = (10, 6)$

$...$

$18P = (5, 16)$

Unfortunately it is not apparent to me what action they are performing with the addition ($+$), or what they mean by "powers". What operation is being performed to go from $(5, 1) + (5, 1)$ to $(6, 3)$, and so on?

The obvious operation (i.e. what Wolfram alpha does) of $(5, 1) + (5, 1) = (5 + 5, 1 + 1)$ yields $(10, 2)$. There are a plethora of other possible combinations of operations that one could try, but I'd just be guessing.

Generally, given the secret, ordinarily labeled $d$, how ought one calculate $dP = P + P~ +~ ... ~+~ P$?

(This presumably computes the public key $X$ & $Y$ points, from $d$ and the $Gx$ and $Gy$ parameters)

While it is a rather core operation, and likely quite basic, I have found no illustrative examples and at-best convoluted implementations. I'll keep looking, but I thought that a good answer might be a useful for the next person searching.

Edit

This exact example also appears and is discussed at: https://math.stackexchange.com/questions/430836

Answer 1

The point addition $P+Q$ and doubling $2P = P +P $ in Elliptic Curves $E$ are not just x,y coordinates in the Euclidean Plane that you can add the coordinates. One can find the rules in Wikipedia;

Point addition: With 2 distinct points, P and Q, addition is defined as the negation of the point resulting from the intersection of the curve, E, and the straight line defined by the points P and Q, giving the point, R.

Point doubling: Where the points P and Q, are coincident (at the same coordinates), addition is similar, except that there is no well-defined straight line through P and Q, so the operation is closed using limiting case, the tangent to the curve, E, at P and Q.

---

Given the Elliptic curve $E:y^2= x^3+a x + b$ and a point $P=(x_p,y_p)$ on the curve, the doubling $R=2P = P + P$ can be calculated by:

\begin{align} \lambda &= \frac{3 x_p^2 + a }{2 y_p}\\ x_r &= \lambda^2 -2 x_p\\ y_r &= \lambda(x_p-x_r) - y_p \end{align}

The curve is defined in modular arithmetic $\pmod{17}$, therefore convert $1/2$ into $2^{-1} \equiv 9 \bmod 17$ and find the inverse by extended GCD algorithm.

$\lambda = (3\cdot 5^2 +2)\cdot 9) \equiv 13 \bmod 17$

$x_r = \lambda^2 - 2 x_p = (13^2 -10 ) \equiv 6 \bmod 17 $

$x_y = \lambda(x_p - x_r)-y_p = 13 \cdot ( 1 - 6) - 1 \equiv 3 \bmod 17$

$$(5,1) + (5,1) = (6,3)$$

Answer 2

I give a python program to clarify the above answer.

Given the Elliptic curve $E:y^2= x^3+2 x + 2 \pmod {17} , \#E=19$ and a primitive point $P=(x_p,y_p)=(5,1)$ on the curve. We calculate the $nP$

# -*- coding:UTF-8

# Extended Euclidean algorithm
def extended_gcd(aa, bb):
   lastremainder, remainder = abs(aa), abs(bb)
   x, lastx, y, lasty = 0, 1, 1, 0
   while remainder:
       lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
       x, lastx = lastx - quotient*x, x
       y, lasty = lasty - quotient*y, y
   return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

# calculate `modular inverse`
def modinv(a, m):
   g, x, y = extended_gcd(a, m)
   if g != 1:
       raise ValueError
   return x % m

# define the curve E: y^2 = x^3 + 2x + 2 (mod 17)  #E=19
p = 17
a = 2
b = 2
# the primitive point (x1,y1)=(5,1)
x1 = x2 =5
y1 = y2 = 1
print str(1)+"P:\t", (x1, y1)
for i in range(2, 19):
   s = 0
   if (x1 == x2):
       # indentical point
       s = ((3 * (x1 ** 2) + a) * modinv(2 * y1, p))%p
   else:
       # different points
       s = ((y2 - y1) * modinv(x2 - x1, p))%p
   # calculate i.P
   x3 = (s ** 2 - x1 - x2) % p
   y3 = (s*(x1 - x3) - y1) % p
   print str(i) + "P:\t", (x3,y3)
   (x2, y2) = (x3, y3)

Run this program, we can get the result:

1P:     (5, 1)
2P:     (6, 3)
3P:     (10, 6)
4P:     (3, 1)
5P:     (9, 16)
6P:     (16, 13)
7P:     (0, 6)
8P:     (13, 7)
9P:     (7, 6)
10P:    (7, 11)
11P:    (13, 10)
12P:    (0, 11)
13P:    (16, 4)
14P:    (9, 1)
15P:    (3, 16)
16P:    (10, 11)
17P:    (6, 14)
18P:    (5, 16)