Binary Elliptic Curves Point Doubling Formula - Calculate Lambda from P3

Harashta

5/16/24, 7:31 AM

As I am studying ordinary (non-supersingular) binary elliptic curves in the Guide to ECC book by Hankerson (Section 3.1, page 81), for point doubling, the equations presented in the book are:

$x_3 = \lambda^2 + \lambda + a = {x_1}^2 + \frac{b}{{x_1}^2}$

$y_3 = {x_1}^2 + (\lambda + 1) x_3 $

$\lambda = x_1 + y_1/x_1$

I have some questions to confirm my understanding, and I really appreciate elaboration on this:

To my understanding, $\lambda$ is a gradient. Then, if I have the information about the result of point doubling (i.e., $x_3, y_3$), can I calculate $\lambda$ as $\lambda = x_3 + y_3/x_3$ instead of $\lambda = x_1 + y_1/x_1$? Or isn't it possible, and I should use other equations (like point halving? But I can not find the formula in the book).
Unrelated to the above question, the value of $a$ and $b$ is always known, right? So for calculating $x_3$, I can use either $\lambda^2 + \lambda + a$ or ${x_1}^2 + \frac{b}{{x_1}^2}$ and it will always be correct. Is that true?

209

1 + 0

elliptic-curves

finite-field

elliptic-curve-generation

Score:5

Crypto

Daniel S

5/16/24, 9:12 AM

One can think of $\lambda$ as the (formal) gradient of the tangent to the curve at the point $(x_1,y_1)$, but this will not be the same as the gradient of the tangent to the curve at the point $(x_3,y_3)$. You should instead use the formulae for point halving (see pages 7-8 of this paper by Pornin for example).
Yes, that is correct. To see the equivalence note that by the curve equation $$y_1^2=x_1y_1+x_1^3+ax_1^2+b$$ so that $$\lambda^2=x_1^2+\frac{y_1^2}{x_1^2}=x_1^2+\frac{y_1}{x_1}+x_1+a+\frac b{x_1^2}$$ and $$\lambda^2+\lambda+a=\left(x_1^2+\frac{y_1}{x_1}+x_1+a+\frac b{x_1^2}\right)+\left(x_1+\frac{y_1}{x_1}\right)+a=x_1^2+\frac b{x_1^2}.$$

+ 4

Harashta

5/16/24, 9:22 AM

Thank you very much for your response! I will look into that. One question, just realized I have come across the paper previously, but I thought that the paper was not very "authoritative" because the equation for Point Doubling is slightly different (i.e., $y_3 = \lambda (x_1 + x_3) + x_3 + y_1$) than Hankerson's (see Page 7 about Point Addition (and point doubling)). It looks like a point addition equation to me. Would you say that the paper is a good reference to study binary elliptic curves?

Daniel S

5/16/24, 9:26 AM

I am happy to endorse the Pornin paper as an good reference for the study of binary elliptic curves. The different form of the addition equation again follows from straightforward identities.

Harashta

5/16/24, 9:27 AM

Then, does it mean I can use the above equation interchangeably with Hankerson's, right? Thank you very much for your explanation! I was afraid that the Point Doubling will have different characteristics so that I can't use $y_1$ for that.

fgrieu

5/16/24, 9:28 AM

@prairie99: I second the recommendation for the Pornin paper when the goal is efficiency and constant-timeness (that's independently of The Bear being our [user#28](https://crypto.stackexchange.com/users/28)). [update] The formulas page 7 should be OK (it's only later that the paper proposes a coordinate system that I think is new, and definitely leads to formulas different from the formulas for Cartesian coordinates).

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Binary Elliptic Curves Point Doubling Formula - Calculate Lambda from P3

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.