0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Point Doubling $\endgroup$ – kelalaka Nov 30 '18 at 21:18
  • $\begingroup$ @kelalaka Ahhhh, yes, that makes sense. $\endgroup$ – Brian M. Hunt Nov 30 '18 at 21:21
  • $\begingroup$ This question has been answered, but it might give some visibility to the next passers-along to keep this around, but I'm fine with it being deleted if that's preferred here. $\endgroup$ – Brian M. Hunt Nov 30 '18 at 21:47
  • $\begingroup$ post your calculation as an answer? $\endgroup$ – kelalaka Nov 30 '18 at 21:49
  • $\begingroup$ @kelalaka The best answer is probably a link to the math question that is virtually identical. Unfortunately trivial answers are turned into comments 😀 . $\endgroup$ – Brian M. Hunt Nov 30 '18 at 21:54
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ The tricky part was the modular inverse i.e. 2^-1 = 9. $\endgroup$ – Brian M. Hunt Nov 30 '18 at 22:21
  • 1
    $\begingroup$ Because it's a Galois field, Fermat's Little Theorem can be used instead of extended GCD. $\endgroup$ – Brian M. Hunt Dec 1 '18 at 13:41

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.