Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
1  
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? –  poncho Feb 7 at 14:30
    
You're right, thanks for the point! –  samoz Feb 7 at 14:36
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
1  
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. –  CodesInChaos Feb 7 at 15:13
    
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. –  CodesInChaos Feb 7 at 17:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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