1
$\begingroup$

In many source codes that implement ECDH, there is a function that multiplies the base point of that curve with a constant. This function usually takes as arguments the constant and just one coordinate of the point. All formulas for multiplying a point on an elliptic curve with a constant involves both coordinates of that point. Can anybody explains how those functions do their job?

For example https://github.com/WireGuard/WireGuard/blob/master/src/crypto/zinc/curve25519/curve25519-fiat32.c

The function curve25519_generic multiplies the base point of curve25519 with the scalar. A point on curve25519 has both coordinates on 32 bytes but the function takes just the x as an argument.

$\endgroup$
4
$\begingroup$

The Montgomery Powering Ladder for computing the scalar product of a point P on an elliptic curve (or in every other abelian group) only needs the x-coordinate of P.

It is used widely since it is believed to be secure against side channel attacks, which is not true in all cases-- for example, see this.

For further details concerning the Montgomery Powering Ladder, see the subsection "Montgomery's ladder technique" in this article

To compute $d\cdot P, P\in E(K)$ we have the following formulas which are used in MPL:

Let $P_{1}, P_{2}, P_{3}, P'_{3} \in E(K): y^{2} = x^{3} + Ax + B$

$P_{3} = P_{1} + P_{2}$

$P'_{3} = P_{1} - P_{2} = \left(x'_{3}, y'_{3}\right)$

$x_{3} = \dfrac{2\left(x_{1} + x_{2}\right)\left(x_{1}x_{2} + A\right) + 4B}{\left(x_{1} - x_{2}\right)^{2}} - x'_{3}$

As you see, the y-coordinate of P is not needed in this computation.

I hope my answer satisfies your need!

$\endgroup$
  • $\begingroup$ Can you point me to the source of these formulas? Thx $\endgroup$ – mip Jul 22 at 14:53
  • 1
    $\begingroup$ These formulars are out of the paper 'Improved Elliptic Curve Multiplication Methods Resistant against Side Channel Attacks' by Tetsuya Izu, Bodo Möller and Tsuyoshi Takagi. link.springer.com/chapter/10.1007/3-540-36231-2_24 $\endgroup$ – Dr. Ministic Jul 22 at 19:27

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.