Twisted Edwards curves

This module provides a native additive-group parent for a twisted Edwards curve over a field. A twisted Edwards curve is given by

\[a x^2 + y^2 = 1 + d x^2 y^2.\]

The implementation is deliberately separate from EllipticCurve_generic. Sage’s EllipticCurve constructor represents elliptic curves by a Weierstrass model, whereas the Edwards model is particularly useful when the coordinate system and its complete addition law are part of the application (for example, Ed25519).

Only the complete twisted Edwards setting is accepted here: the base ring is a field of characteristic different from 2, a and d are nonzero and distinct, a is a square, and d is a nonsquare. Under these conditions the affine addition formulas are complete. The points exposed by this class are affine pairs (x, y).

This class models the curve group only. The Ed25519 protocol layer, including SHA-512 hashing, scalar pruning, little-endian encoding, the cofactor, and the particular base point, is available in sage.crypto.ed25519.

In the usual Ed25519 signature notation, r is the nonce scalar, R=[r]B is the resulting group point (normally transmitted in encoded form), h is the challenge hash reduced modulo the subgroup order, and s = r + h a (mod L) is the response. Thus R and r are not two spellings for the same object. A fault mask or a fault location in an implementation is not part of the Ed25519 standard; it must be inferred from the implementation or from the supplied faulty outputs.

EXAMPLES:

Sage

sage: from sage.schemes.elliptic_curves.ell_edwards import TwistedEdwardsCurve
sage: F = GF(19)
sage: C = TwistedEdwardsCurve(F, 1, 2)
sage: C
Twisted Edwards curve over Finite Field of size 19 (a=1, d=2)
sage: P = C(1, 0)
sage: O = C(0, 1)
sage: P + O == P
True
sage: 4*P == O
True

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.ell_edwards import TwistedEdwardsCurve
>>> F = GF(Integer(19))
>>> C = TwistedEdwardsCurve(F, Integer(1), Integer(2))
>>> C
Twisted Edwards curve over Finite Field of size 19 (a=1, d=2)
>>> P = C(Integer(1), Integer(0))
>>> O = C(Integer(0), Integer(1))
>>> P + O == P
True
>>> Integer(4)*P == O
True

Sage Live

from sage.schemes.elliptic_curves.ell_edwards import TwistedEdwardsCurve
F = GF(19)
C = TwistedEdwardsCurve(F, 1, 2)
C
P = C(1, 0)
O = C(0, 1)
P + O == P
4*P == O

The point operations use Sage’s ordinary additive-group operators. No separate scalar-multiplication routine is required:

Sage

sage: Q = C(0, -1)
sage: P + P == Q
True
sage: -(P + Q) == -P - Q
True
sage: points = [C(x, y) for x in F for y in F if C.is_on_curve(x, y)]
sage: all((P + Q) + R == P + (Q + R)
....:     for P in points for Q in points for R in points)
True

Python

>>> from sage.all import *
>>> Q = C(Integer(0), -Integer(1))
>>> P + P == Q
True
>>> -(P + Q) == -P - Q
True
>>> points = [C(x, y) for x in F for y in F if C.is_on_curve(x, y)]
>>> all((P + Q) + R == P + (Q + R)
...     for P in points for Q in points for R in points)
True

Sage Live

Q = C(0, -1)
P + P == Q
-(P + Q) == -P - Q
points = [C(x, y) for x in F for y in F if C.is_on_curve(x, y)]
all((P + Q) + R == P + (Q + R)
    for P in points for Q in points for R in points)

The curve can be converted to the Weierstrass curve used by Sage’s existing elliptic-curve algorithms. The conversion is birational, so the identity and the exceptional 2-torsion point are handled explicitly:

Sage

sage: E = C.to_elliptic_curve()
sage: C.from_elliptic_curve(P.to_elliptic_curve()) == P
True
sage: C.from_elliptic_curve(O.to_elliptic_curve()) == O
True
sage: C.from_elliptic_curve(Q.to_elliptic_curve()) == Q
True
sage: all(C.from_elliptic_curve(P.to_elliptic_curve()) == P for P in points)
True

Python

>>> from sage.all import *
>>> E = C.to_elliptic_curve()
>>> C.from_elliptic_curve(P.to_elliptic_curve()) == P
True
>>> C.from_elliptic_curve(O.to_elliptic_curve()) == O
True
>>> C.from_elliptic_curve(Q.to_elliptic_curve()) == Q
True
>>> all(C.from_elliptic_curve(P.to_elliptic_curve()) == P for P in points)
True

Sage Live

E = C.to_elliptic_curve()
C.from_elliptic_curve(P.to_elliptic_curve()) == P
C.from_elliptic_curve(O.to_elliptic_curve()) == O
C.from_elliptic_curve(Q.to_elliptic_curve()) == Q
all(C.from_elliptic_curve(P.to_elliptic_curve()) == P for P in points)

REFERENCES:

• [Edwards2007]

• [Hisil2008]

[Edwards2007]

H. M. Edwards, A normal form for elliptic curves, Bulletin of the American Mathematical Society 44 (2007), 393–422.

[Hisil2008]

H. Hisil, K. K.-H. Wong, G. Carter, and E. Dawson, Twisted Edwards Curves Revisited, ASIACRYPT 2008, Lecture Notes in Computer Science 5350, 326–343.

AUTHORS:

• SageMath developers (2026): initial native twisted Edwards group support

class sage.schemes.elliptic_curves.ell_edwards.TwistedEdwardsCurve(base_ring, a, d)

Bases: UniqueRepresentation, Parent

A complete twisted Edwards curve over a field.

INPUT:

• base_ring – a field of characteristic different from 2

• a, d – nonzero, distinct elements of base_ring such that a is a square and d is a nonsquare

OUTPUT:

The additive group of affine points satisfying

\[a x^2 + y^2 = 1 + d x^2 y^2.\]

The parameter restrictions are exactly those used by the complete twisted Edwards addition law. For Ed25519 over GF(2^255 - 19), use a=-1 and d=-121665/121666. The protocol-level Ed25519 encoding and signing operations are provided by sage.crypto.ed25519.

EXAMPLES:

Sage

sage: from sage.schemes.elliptic_curves.ell_edwards import TwistedEdwardsCurve
sage: C = TwistedEdwardsCurve(GF(19), 1, 2)
sage: C.a(), C.d()
(1, 2)
sage: C(0, 1).is_zero()
True
sage: C((0, -1))
(0 : 18)

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.ell_edwards import TwistedEdwardsCurve
>>> C = TwistedEdwardsCurve(GF(Integer(19)), Integer(1), Integer(2))
>>> C.a(), C.d()
(1, 2)
>>> C(Integer(0), Integer(1)).is_zero()
True
>>> C((Integer(0), -Integer(1)))
(0 : 18)

Sage Live

from sage.schemes.elliptic_curves.ell_edwards import TwistedEdwardsCurve
C = TwistedEdwardsCurve(GF(19), 1, 2)
C.a(), C.d()
C(0, 1).is_zero()
C((0, -1))

Invalid models and points are rejected:

Sage

sage: TwistedEdwardsCurve(ZZ, 1, 2)
Traceback (most recent call last):
...
TypeError: the base ring must be a field
sage: TwistedEdwardsCurve(GF(19), 1, 1)
Traceback (most recent call last):
...
ValueError: ``a`` and ``d`` must be distinct
sage: C(1, 1)
Traceback (most recent call last):
...
ValueError: the coordinates do not define a point on the curve

Python

>>> from sage.all import *
>>> TwistedEdwardsCurve(ZZ, Integer(1), Integer(2))
Traceback (most recent call last):
...
TypeError: the base ring must be a field
>>> TwistedEdwardsCurve(GF(Integer(19)), Integer(1), Integer(1))
Traceback (most recent call last):
...
ValueError: ``a`` and ``d`` must be distinct
>>> C(Integer(1), Integer(1))
Traceback (most recent call last):
...
ValueError: the coordinates do not define a point on the curve

Sage Live

TwistedEdwardsCurve(ZZ, 1, 2)
TwistedEdwardsCurve(GF(19), 1, 1)
C(1, 1)

Element

alias of TwistedEdwardsPoint

a()

Return the coefficient a.

d()

Return the coefficient d.

from_elliptic_curve(point)

Map a point on to_elliptic_curve() back to this curve.

is_on_curve(x, y=None)

Return whether the given affine coordinates satisfy the equation.

some_elements()

to_elliptic_curve()

Return the corresponding Weierstrass elliptic curve.

If delta = a-d, the returned curve is

\[Y^2 = X^3 + ABX^2 + B^2X,\]

with A=2(a+d)/delta and B=4/delta. Point conversion is provided by TwistedEdwardsPoint.to_elliptic_curve() and from_elliptic_curve().

zero()

Return the identity point (0, 1).

class sage.schemes.elliptic_curves.ell_edwards.TwistedEdwardsPoint(parent, coordinates, check=True)

Bases: AdditiveGroupElement

A point on a TwistedEdwardsCurve.

The point is stored in the affine chart as a pair (x, y). The parent validates the equation when check=True (the default).

coordinates()

Return the affine coordinates of this point.

curve()

Return the twisted Edwards curve containing this point.

to_elliptic_curve()

Map this point to Sage’s Weierstrass elliptic-curve model.

The map is obtained through the Montgomery model

\[Bv^2=u^3+Au^2+u,\]

where u=(1+y)/(1-y), v=u/x, A=2(a+d)/(a-d), and B=4/(a-d). The corresponding Weierstrass coordinates are (X,Y)=(Bu,B^2v).

The identity maps to the point at infinity. The point (0,-1) maps to (0,0).

x()

Return the first affine coordinate.

xy()

Return the affine coordinates of this point.

y()

Return the second affine coordinate.

Make live