All elliptic curves can be written in Weierstrass form

y² = x³ + ax + b

with a few exceptions [1].

Montgomery elliptic curves have the form

B y² = x³ + A x² + x

and twisted Edwards curves have the form

a x² + y² = 1 + d x² y²

Every Montgomery curve has a twisted Edwards form, and vice versa, but not all curves have a Montgomery or twisted Edwards form.

Converting coefficients

Here is Python code for converting coefficients between the various forms. See [2].

def Montgomery_to_Twisted_Edwards(B, A, p):
    # By^2 = x^3 + Ax^2 + x
    a = ((A + 2)*pow(B, -1, p)) % p
    d = ((A - 2)*pow(B, -1, p)) % p          
    return a, d

def Twisted_Edwards_to_Montgomery(a, d, p):
    # ax^2 + y^2 = 1 + d x^2 y^2
    x = pow(a - d, -1, p)
    B = (4*x) % p
    A = (2*(a + d)*x) % p
    return B, A

def Montgomery_to_Weierstrass(B, A, p):
    # By^2 = x^3 + Ax^2 + x
    a = (B**2 * (1 - A**2*pow(3, -1, p))) % p
    b = (B**3 * (2*A**3 - 9*A) * pow(27, -1, p)) % p
    return a, b

Tiny Jubjub curve

The code below confirms that the forms of the Tiny Jubjub curve (TJJ) given in the previous post are consistent.

# Twisted Edwards definition
a, d, p = 3, 8, 13

B, A = Twisted_Edwards_to_Montgomery(a, d, p)
assert(B == 7)
assert(A == 6)

wa, b = Montgomery_to_Weierstrass(B, A)
assert(wa == 8)
assert(b == 8)

Baby Jubjub

I was looking up the Baby Jubjub curve and found incompatible definitions. All agreed that the field is integers modulo the prime

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

and that the Montgomery form of the curve is

y² = x³ + 168698 x² + x

But the sources differed in the twisted Edwards form of the curve. The code above shows that a correct twisted Edwards form is the one given in [2]:

168700 x² + y² = 1 + 168696 x² y²

Now it is possible to find multiple Edwards forms for a given Montgomery form, so an alternate form is not necessarily wrong. But when I converted both to Weierstrass form and computed the j-invariant, the results were different, and so the curves were not equivalent.

Related posts

[1] All elliptic curves can be written in Weierstrass form as long as the underlying field does not have characteristic 2 or 3. Cryptography is primarily interest in fields whose characteristic is a gargantuan prime, not 2 or 3.

[2] Marta Bellés-Muñoz, Barry Whitehat, Jordi Baylina, Vanesa Daza, and Jose Luis Muñoz-Tapia. Twisted edwards elliptic curves for zero-knowledge circuits. Mathematics, 9(23), 2021.

The post Weierstrass, Montgomery, and Edwards elliptic curve forms first appeared on John D. Cook.

Previous Post