6
$\begingroup$

There is a subtle difference between the 2 implementations for a Montgomery curve defined from the 2 following links

https://hyperelliptic.org/EFD/g1p/auto-montgom-xz.html

      A = X2+Z2
      AA = A^2
      B = X2-Z2
      BB = B^2
      E = AA-BB
      C = X3+Z3
      D = X3-Z3
      DA = D*A
      CB = C*B
      X5 = (DA+CB)^2
      Z5 = X1*(DA-CB)^2
      X4 = AA*BB
      Z4 = E*(BB+a24*E)

https://tools.ietf.org/html/rfc7748

       A = x_2 + z_2
       AA = A^2
       B = x_2 - z_2
       BB = B^2
       E = AA - BB
       C = x_3 + z_3
       D = x_3 - z_3
       DA = D * A
       CB = C * B
       x_3 = (DA + CB)^2
       z_3 = x_1 * (DA - CB)^2
       x_2 = AA * BB
       z_2 = E * (AA + a24 * E)

This AA / BB change on the last line does affect the result of a point multiplication with same input parameters.

Is there a reason for that difference ?

$\endgroup$
  • $\begingroup$ It looks to be a typo in RFC. When BB is used (as in EFD and original P.L. Montgomery paper), the test vectors can be reproduced. Submitted a review comment to RFC. Errare humanum est. How many existing implementations will fail to inter-operate ? $\endgroup$ – Pierre Mar 11 at 19:47
6
$\begingroup$

This is not a bug: it arises from different choice of sign in the definition of a24 := (a ± 2)/4; the RFC uses - while the EFD uses +.

RFC, following the Curve25519 paper:

The constant a24 is (486662 - 2) / 4 = 121665 for curve25519/X25519 and (156326 - 2) / 4 = 39081 for curve448/X448.

EFD, following Montgomery's paper (paywall-free):

Assumptions: 4*a24=a+2.

This apparent discrepancy was raised by Paul Lambert on the CFRG mailing list during discussion on the draft. It doesn't really matter which one you choose, as long as you're consistent about it!

$\endgroup$
  • $\begingroup$ Thanks for the explanation. I didn't spot the little difference on a24 definition between the RFC and the EFD. $\endgroup$ – Pierre Mar 11 at 22:09
5
$\begingroup$

This is not a typo; it is a difference in how the Montgomery doubling formula was derived between the original paper and the curve25519 paper. Both are correct.

To double a point on a Montgomery curve $$ y^2 = x^3 + Ax^2 + x\,, $$ one has the identity relating the doubled point $(x_3, \cdot)$ and the source point $(x_1, \cdot)$: $$ x_3 4x_1(x_1^2 + Ax_1 + 1) = (x_1^2 - 1)^2\,. $$ The doubled point $x_3$ can thus be computed as the fraction $$ \frac{(x_1^2 - 1)^2}{4x_1(x_1^2 + Ax_1 + 1)}\,. $$ But to minimize the operation number, and obtain several common subexpressions, we can write $(x_1^2 - 1)^2$ as $(x_1+1)^2(x_1-1)^2$, $4x_1$ as $(x_1 + 1)^2 - (x_1 - 1)^2$, and $x_1^2 + Ax_1 + 1$ as either $(x_1-1)^2 + ((A+2)/4)4x_1$ or $(x_1+1)^2 + ((A-2)/4)4x_1$. It is this latter somewhat arbitrary choice that results in there being two almost identical Montgomery doubling formulas.

$\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.