1
$\begingroup$

I want to represent a Montgomery Curve (curve25519) in Weierstrass form as a personal exercise.

After doing some math and referencing the conversion equation at http://en.wikipedia.org/wiki/Montgomery_curve, several of my terms contain decimals, which I believe is incorrect. Namely,

(3-A^2) / (3*B^2)

is a decimal, when A = 486662 and B = 1 and doing it directly.

Note that (3-A^2) is negative, so I added the modulus to it to make it positive, which then enables the division by 3 properly as shown here, b

Are there restrictions on which Montgomery curves can be converted to Weierstrass curves?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Wouldn't you do those conversion equations within the field, and not in the reals? That is, do the addition, subtraction and multiplication modulo the prime, and division by computing the modular inverse? $\endgroup$
    – poncho
    Feb 7, 2014 at 14:30

1 Answer 1

Reset to default
2
$\begingroup$

My comment already gave you the answer; I'm submitting an official answer to give you something to upvote :-)

An elliptic curve is defined within a field; in the case of curve25519, it is defined within the field $GF(2^{255}-19)$; this is a prime field, because $2^{255}-19$ is prime.

So, when we get to the conversion formulas such as $\frac{3 - A^2}{3\cdot B^2}$, this formula is done within the field the curve is defined in.

Because this is a prime field, addition and multiplication can be implemented by addition and multiplication modulo $2^{255}-19$. However, division is trickier; it's typically done by computing the modular inverse of the divisor.

As for your question:

Are there restrictions on which Montgomery curves can be converted to Weierstrass curves?

No, there are no restrictions; all Elliptic curves are isomorphic to some curve in Weierstrass form. The Wikipedia page you gave gives an explicit mapping from a Montogomery curve into Weierstrauss form.

The one glitch is converting the Curve25519 generator, which is defined as $x=9$; they omit the y-coordinate, and hence corresponds to two elliptic curve points (as there are two different solutions on the curve equation with $x=9$). This translates into two different points on the Weierstrass curve (which share the $x$ coordinate as well); you can either say that the conversion is that translated $x$ coordinate, or arbitrarily pick one of the valid $y$ coordinates.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I don't thinks answers the question fully. I'd also expect answers to "Does such a formula exist for all montgomery curves? Does it work for all points on those curves?" since those are restrictions on which curves can be converted. $\endgroup$
    – CodesInChaos
    Feb 7, 2014 at 15:13
  • $\begingroup$ Concerning the two points with x=9 issue: The Ed25519 paper fixes a point with both x and y coordinates, which when converted to Curve25519 has x=9. I'd choose that point instead of arbitrarily picking one. $\endgroup$
    – CodesInChaos
    Feb 7, 2014 at 17:47
  • $\begingroup$ Another relevant point to this answer is that after remapping to Weierstrass form, the x=9 coordinate must also be remapped with the same change of variables. $\endgroup$
    – samoz
    May 8, 2014 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.