edwards25519

package module
v0.0.0-...-0a9ae29 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 23, 2025 License: BSD-3-Clause Imports: 6 Imported by: 12

README

filippo.io/edwards25519

import "filippo.io/edwards25519"

This library implements the edwards25519 elliptic curve, exposing the necessary APIs to build a wide array of higher-level primitives. Read the docs at pkg.go.dev/filippo.io/edwards25519.

The package tracks the upstream standard library package crypto/internal/fips140/edwards25519 and extends it with additional functionality.

The code is originally derived from Adam Langley's internal implementation in the Go standard library, and includes George Tankersley's performance improvements. It was then further developed by Henry de Valence for use in ristretto255, and was finally merged back into the Go standard library as of Go 1.17.

Most users don't need this package, and should instead use crypto/ed25519 for signatures, crypto/ecdh for Diffie-Hellman, or github.com/gtank/ristretto255 for prime order group logic. However, for anyone currently using a fork of the internal edwards25519 package or of github.com/agl/edwards25519, this package should be a safer, faster, and more powerful alternative.

Since this package is meant to curb proliferation of edwards25519 implementations in the Go ecosystem, it welcomes requests for new APIs or reviewable performance improvements.

Documentation

Overview

Package edwards25519 implements group logic for the twisted Edwards curve 

-x^2 + y^2 = 1 + -(121665/121666)*x^2*y^2

This is better known as the Edwards curve equivalent to Curve25519, and is the curve used by the Ed25519 signature scheme.

Most users don't need this package, and should instead use crypto/ed25519 for signatures, crypto/ecdh for Diffie-Hellman, or github.com/gtank/ristretto255 for prime order group logic.

However, developers who do need to interact with low-level edwards25519 operations can use this package, which is an extended version of crypto/internal/fips140/edwards25519 from the standard library repackaged as an importable module.

Index

Constants

This section is empty.

Variables

View Source 
var EightTorsion = [8]*Point{
	pointFromElements(
		feFromLimbs(0, 0, 0, 0, 0),
		feFromLimbs(1, 0, 0, 0, 0),
		feFromLimbs(1, 0, 0, 0, 0),
		feFromLimbs(0, 0, 0, 0, 0),
	),
	pointFromElements(
		feFromLimbs(
			358744748052810,
			1691584618240980,
			977650209285361,
			1429865912637724,
			560044844278676,
		),
		feFromLimbs(
			84926274344903,
			473620666599931,
			365590438845504,
			1028470286882429,
			2146499180330972,
		),
		feFromLimbs(1, 0, 0, 0, 0),
		feFromLimbs(
			1448326834587521,
			1857896831960481,
			1093722731865333,
			1677408490711241,
			1915505153018406,
		),
	),
	pointFromElements(
		feFromLimbs(
			533094393274173,
			2016890930128738,
			18285341111199,
			134597186663265,
			1486323764102114,
		),
		feFromLimbs(0, 0, 0, 0, 0),
		feFromLimbs(1, 0, 0, 0, 0),
		feFromLimbs(0, 0, 0, 0, 0),
	),
	pointFromElements(
		feFromLimbs(
			358744748052810,
			1691584618240980,
			977650209285361,
			1429865912637724,
			560044844278676,
		),
		feFromLimbs(
			2166873539340326,
			1778179147085316,
			1886209374839743,
			1223329526802818,
			105300633354275,
		),
		feFromLimbs(1, 0, 0, 0, 0),
		feFromLimbs(
			803472979097708,
			393902981724766,
			1158077081819914,
			574391322974006,
			336294660666841,
		),
	),
	pointFromElements(
		feFromLimbs(0, 0, 0, 0, 0),
		feFromLimbs(
			2251799813685228,
			2251799813685247,
			2251799813685247,
			2251799813685247,
			2251799813685247,
		),
		feFromLimbs(1, 0, 0, 0, 0),
		feFromLimbs(0, 0, 0, 0, 0),
	),
	pointFromElements(
		feFromLimbs(
			1893055065632419,
			560215195444267,
			1274149604399886,
			821933901047523,
			1691754969406571,
		),
		feFromLimbs(
			2166873539340326,
			1778179147085316,
			1886209374839743,
			1223329526802818,
			105300633354275,
		),
		feFromLimbs(1, 0, 0, 0, 0),
		feFromLimbs(
			1448326834587521,
			1857896831960481,
			1093722731865333,
			1677408490711241,
			1915505153018406,
		),
	),
	pointFromElements(
		feFromLimbs(
			1718705420411056,
			234908883556509,
			2233514472574048,
			2117202627021982,
			765476049583133,
		),
		feFromLimbs(0, 0, 0, 0, 0),
		feFromLimbs(1, 0, 0, 0, 0),
		feFromLimbs(0, 0, 0, 0, 0),
	),
	pointFromElements(
		feFromLimbs(
			1893055065632419,
			560215195444267,
			1274149604399886,
			821933901047523,
			1691754969406571,
		),
		feFromLimbs(
			84926274344903,
			473620666599931,
			365590438845504,
			1028470286882429,
			2146499180330972,
		),
		feFromLimbs(1, 0, 0, 0, 0),
		feFromLimbs(
			803472979097708,
			393902981724766,
			1158077081819914,
			574391322974006,
			336294660666841,
		),
	),
}

EightTorsion The 8-torsion subgroup E[8].

In the case of Curve25519, it is cyclic; the i-th element of the array is [i]P, where P is a point of order 8 generating E[8].

Thus E[4] is the points indexed by `0,2,4,6`, and E[2] is the points indexed by `0,4`.

See https://github.com/dalek-cryptography/curve25519-dalek/blob/015707ab4eb137fb7dc8e65730770a4378f87b2f/curve25519-dalek/src/backend/serial/u64/constants.rs#L188-L339

Functions

func BatchBytes 

func BatchBytes(points []*Point, out [][32]byte)

func BatchBytesMontgomery 

func BatchBytesMontgomery(points []*Point, out [][32]byte)

Types

type Point 

type Point struct {
	// contains filtered or unexported fields
}

Point represents a point on the edwards25519 curve.

This type works similarly to math/big.Int, and all arguments and receivers are allowed to alias.

The zero value is NOT valid, and it may be used only as a receiver.

func NewGeneratorPoint 

func NewGeneratorPoint() *Point

NewGeneratorPoint returns a new Point set to the canonical generator.

func NewIdentityPoint 

func NewIdentityPoint() *Point

NewIdentityPoint returns a new Point set to the identity.

func (*Point) Add 

func (v *Point) Add(p, q *Point) *Point

Add sets v = p + q, and returns v.

func (*Point) Bytes 

func (v *Point) Bytes() []byte

Bytes returns the canonical 32-byte encoding of v, according to RFC 8032, Section 5.1.2.

func (*Point) BytesMontgomery 

func (v *Point) BytesMontgomery() []byte

BytesMontgomery converts v to a point on the birationally-equivalent Curve25519 Montgomery curve, and returns its canonical 32 bytes encoding according to RFC 7748.

Note that BytesMontgomery only encodes the u-coordinate, so v and -v encode to the same value. If v is the identity point, BytesMontgomery returns 32 zero bytes, analogously to the X25519 function.

The lack of an inverse operation (such as SetMontgomeryBytes) is deliberate: while every valid edwards25519 point has a unique u-coordinate Montgomery encoding, X25519 accepts inputs on the quadratic twist, which don't correspond to any edwards25519 point, and every other X25519 input corresponds to two edwards25519 points.

func (*Point) Double 

func (v *Point) Double(p *Point) *Point

Double sets v = p + p, and returns v.

func (*Point) Equal 

func (v *Point) Equal(u *Point) int

Equal returns 1 if v is equivalent to u, and 0 otherwise.

func (*Point) ExtendedCoordinates 

func (v *Point) ExtendedCoordinates() (X, Y, Z, T *field.Element)

ExtendedCoordinates returns v in extended coordinates (X:Y:Z:T) where x = X/Z, y = Y/Z, and xy = T/Z as in https://eprint.iacr.org/2008/522.

func (*Point) IsSmallOrder 

func (v *Point) IsSmallOrder() bool

IsSmallOrder Determine if this point is of small order. true if it is in the torsion subgroup E[8]; false if it is not in the torsion subgroup E[8];

See https://github.com/FiloSottile/edwards25519/issues/34

func (*Point) IsTorsionFree 

func (v *Point) IsTorsionFree() bool

IsTorsionFree Determine if this point is “torsion-free”, i.e., is contained in the prime-order subgroup. true if it has zero torsion component and is in the prime-order subgroup; false if it has a nonzero torsion component and is not in the prime-order subgroup.

See https://github.com/FiloSottile/edwards25519/issues/33

func (*Point) IsTorsionFreeVarTime 

func (v *Point) IsTorsionFreeVarTime() bool

IsTorsionFreeVarTime Determine if this point is “torsion-free”, i.e., is contained in the prime-order subgroup. true if it has zero torsion component and is in the prime-order subgroup; false if it has a nonzero torsion component and is not in the prime-order subgroup.

Implies IsSmallOrder == false Implies point is on the curve due to decoding checks

See https://github.com/FiloSottile/edwards25519/issues/33

Ported from https://github.com/kayabaNerve/fcmp-plus-plus/blob/94744c5324e869a9483bbbd93a864e108304bf76/crypto/divisors/src/tests/torsion_check.rs#L44-L203 Ported from https://github.com/pornin/crrl/blob/main/src/ed25519.rs Based on https://eprint.iacr.org/2022/1164.pdf

func (*Point) MultByCofactor 

func (v *Point) MultByCofactor(p *Point) *Point

MultByCofactor sets v = 8 * p, and returns v.

func (*Point) MultByPrimeOrder 

func (v *Point) MultByPrimeOrder(p *Point) *Point

MultByPrimeOrder sets v = l * p, where l is the order of the scalar field, and returns v. If and only if p is the identity or a point on the prime-order subgroup, v will be set to the identity. This can be used to check if p has a low-order component.

func (*Point) MultiScalarMult 

func (v *Point) MultiScalarMult(scalars []*Scalar, points []*Point) *Point

MultiScalarMult sets v = sum(scalars[i] * points[i]), and returns v.

Execution time depends only on the lengths of the two slices, which must match.

func (*Point) Negate 

func (v *Point) Negate(p *Point) *Point

Negate sets v = -p, and returns v.

func (*Point) ScalarBaseMult 

func (v *Point) ScalarBaseMult(x *Scalar) *Point

ScalarBaseMult sets v = x * B, where B is the canonical generator, and returns v.

The scalar multiplication is done in constant time.

func (*Point) ScalarMult 

func (v *Point) ScalarMult(x *Scalar, q *Point) *Point

ScalarMult sets v = x * q, and returns v.

The scalar multiplication is done in constant time.

func (*Point) ScalarMultPrecomputed 

func (v *Point) ScalarMultPrecomputed(x *Scalar, table *PrecomputedTable) *Point

ScalarMultPrecomputed sets v = x * q (via table), and returns v.

The scalar multiplication is done in constant time.

func (*Point) ScalarMultSlow 

func (v *Point) ScalarMultSlow(x *Scalar, q *Point) *Point

ScalarMultSlow sets v = x * q, and returns v. It doesn't precompute a large table, so it is considerably slower, but requires less memory.

The scalar multiplication is done in constant time.

func (*Point) Select 

func (v *Point) Select(a, b *Point, cond int) *Point

Select sets v to a if cond == 1 and to b if cond == 0.

func (*Point) Set 

func (v *Point) Set(u *Point) *Point

Set sets v = u, and returns v.

func (*Point) SetBytes 

func (v *Point) SetBytes(x []byte) (*Point, error)

SetBytes sets v = x, where x is a 32-byte encoding of v. If x does not represent a valid point on the curve, SetBytes returns nil and an error and the receiver is unchanged. Otherwise, SetBytes returns v.

Note that SetBytes accepts all non-canonical encodings of valid points. That is, it follows decoding rules that match most implementations in the ecosystem rather than RFC 8032.

func (*Point) SetCanonicalBytesVarTime 

func (v *Point) SetCanonicalBytesVarTime(x []byte) (*Point, error)

SetCanonicalBytesVarTime sets v = x, where x is a 32-byte encoding of v. If x does not represent a valid point on the curve, SetBytesVarTime returns nil and an error and the receiver is unchanged. Otherwise, SetBytesVarTime returns v.

Note that SetCanonicalBytesVarTime does not accept all non-canonical encodings of valid points.

Variable time

func (*Point) SetExtendedCoordinates 

func (v *Point) SetExtendedCoordinates(X, Y, Z, T *field.Element) (*Point, error)

SetExtendedCoordinates sets v = (X:Y:Z:T) in extended coordinates where x = X/Z, y = Y/Z, and xy = T/Z as in https://eprint.iacr.org/2008/522.

If the coordinates are invalid or don't represent a valid point on the curve, SetExtendedCoordinates returns nil and an error and the receiver is unchanged. Otherwise, SetExtendedCoordinates returns v.

func (*Point) Subtract 

func (v *Point) Subtract(p, q *Point) *Point

Subtract sets v = p - q, and returns v.

func (*Point) VarTimeDoubleScalarBaseMult 

func (v *Point) VarTimeDoubleScalarBaseMult(a *Scalar, A *Point, b *Scalar) *Point

VarTimeDoubleScalarBaseMult sets v = a * A + b * B, where B is the canonical generator, and returns v.

Execution time depends on the inputs.

func (*Point) VarTimeDoubleScalarBaseMultPrecomputed 

func (v *Point) VarTimeDoubleScalarBaseMultPrecomputed(a *Scalar, aTable *PrecomputedTable, b *Scalar) *Point

VarTimeDoubleScalarBaseMultPrecomputed sets v = a * A + b * B, where B is the canonical generator, and returns v. Execution time depends on the inputs.

func (*Point) VarTimeDoubleScalarMult 

func (v *Point) VarTimeDoubleScalarMult(a *Scalar, A *Point, b *Scalar, B *Point) *Point

VarTimeDoubleScalarMult sets v = a * A + b * B, and returns v.

Execution time depends on the inputs.

func (*Point) VarTimeDoubleScalarMultPrecomputed 

func (v *Point) VarTimeDoubleScalarMultPrecomputed(a *Scalar, aTable *PrecomputedTable, b *Scalar, bTable *PrecomputedTable) *Point

VarTimeDoubleScalarMultPrecomputed sets v = a * A + b * B, and returns v. Execution time depends on the inputs.

func (*Point) VarTimeMultiScalarMult 

func (v *Point) VarTimeMultiScalarMult(scalars []*Scalar, points []*Point) *Point

VarTimeMultiScalarMult sets v = sum(scalars[i] * points[i]), and returns v.

Execution time depends on the inputs.

func (*Point) VarTimeMultiScalarMultPippenger 

func (v *Point) VarTimeMultiScalarMultPippenger(scalars []*Scalar, points []*Point) *Point

VarTimeMultiScalarMultPippenger sets v = sum(scalars[i] * points[i]), and returns v. Implements a version of Pippenger's algorithm.

The algorithm works as follows:

Let `n` be a number of point-scalar pairs. Let `w` be a window of bits (6..8, chosen based on `n`, see cost factor).

  1. Prepare `2^(w-1) - 1` buckets with indices `[1..2^(w-1))` initialized with identity points. Bucket 0 is not needed as it would contain points multiplied by 0.
  2. Convert scalars to a radix-`2^w` representation with signed digits in `[-2^w/2, 2^w/2]`. Note: only the last digit may equal `2^w/2`.
  3. Starting with the last window, for each point `i=[0..n)` add it to a bucket indexed by the point's scalar's value in the window.
  4. Once all points in a window are sorted into buckets, add buckets by multiplying each by their index. Efficient way of doing it is to start with the last bucket and compute two sums: intermediate sum from the last to the first, and the full sum made of all intermediate sums.
  5. Shift the resulting sum of buckets by `w` bits by using `w` doublings.
  6. Add to the return value.
  7. Repeat the loop.

Approximate cost w/o wNAF optimizations (A = addition, D = doubling):

```ascii cost = (n*A + 2*(2^w/2)*A + w*D + A)*256/w 

      |          |       |     |   |
      |          |       |     |   looping over 256/w windows
      |          |       |     adding to the result
sorting points   |       shifting the sum by w bits (to the next window, starting from last window)
one by one       |
into buckets     adding/subtracting all buckets
                 multiplied by their indexes
                 using a sum of intermediate sums

```

For large `n`, dominant factor is (n*256/w) additions. However, if `w` is too big and `n` is not too big, then `(2^w/2)*A` could dominate. Therefore, the optimal choice of `w` grows slowly as `n` grows.

This algorithm is adapted from section 4 of <https://eprint.iacr.org/2012/549.pdf>.

func (*Point) VarTimeScalarBaseMult 

func (v *Point) VarTimeScalarBaseMult(x *Scalar) *Point

VarTimeScalarBaseMult sets v = x * B, where B is the canonical generator, and returns v. Execution time depends on the inputs.

func (*Point) VarTimeScalarMult 

func (v *Point) VarTimeScalarMult(x *Scalar, q *Point) *Point

VarTimeScalarMult sets v = x * q, and returns v., and returns v. Execution time depends on the inputs.

func (*Point) VarTimeScalarMultPrecomputed 

func (v *Point) VarTimeScalarMultPrecomputed(x *Scalar, table *PrecomputedTable) *Point

VarTimeScalarMultPrecomputed sets v = x * q, and returns v. Execution time depends on the inputs.

type PrecomputedTable 

type PrecomputedTable [32]affineLookupTable

func PointTablePrecompute 

func PointTablePrecompute(q *Point) *PrecomputedTable

type Scalar 

type Scalar struct {
	// contains filtered or unexported fields
}

A Scalar is an integer modulo 

l = 2^252 + 27742317777372353535851937790883648493

which is the prime order of the edwards25519 group.

This type works similarly to math/big.Int, and all arguments and receivers are allowed to alias.

The zero value is a valid zero element.

func NewScalar 

func NewScalar() *Scalar

NewScalar returns a new zero Scalar.

func (*Scalar) Add 

func (s *Scalar) Add(x, y *Scalar) *Scalar

Add sets s = x + y mod l, and returns s.

func (*Scalar) Bytes 

func (s *Scalar) Bytes() []byte

Bytes returns the canonical 32-byte little-endian encoding of s.

func (*Scalar) Equal 

func (s *Scalar) Equal(t *Scalar) int

Equal returns 1 if s and t are equal, and 0 otherwise.

func (*Scalar) Invert 

func (s *Scalar) Invert(t *Scalar) *Scalar

Invert sets s to the inverse of a nonzero scalar v, and returns s.

If t is zero, Invert returns zero.

func (*Scalar) Multiply 

func (s *Scalar) Multiply(x, y *Scalar) *Scalar

Multiply sets s = x * y mod l, and returns s.

func (*Scalar) MultiplyAdd 

func (s *Scalar) MultiplyAdd(x, y, z *Scalar) *Scalar

MultiplyAdd sets s = x * y + z mod l, and returns s. It is equivalent to using Multiply and then Add.

func (*Scalar) Negate 

func (s *Scalar) Negate(x *Scalar) *Scalar

Negate sets s = -x mod l, and returns s.

func (*Scalar) One 

func (s *Scalar) One() *Scalar

func (*Scalar) Select 

func (s *Scalar) Select(a, b *Scalar, cond int) *Scalar

Select sets v to a if cond == 1, and to b if cond == 0.

func (*Scalar) Set 

func (s *Scalar) Set(x *Scalar) *Scalar

Set sets s = x, and returns s.

func (*Scalar) SetBytesWithClamping 

func (s *Scalar) SetBytesWithClamping(x []byte) (*Scalar, error)

SetBytesWithClamping applies the buffer pruning described in RFC 8032, Section 5.1.5 (also known as clamping) and sets s to the result. The input must be 32 bytes, and it is not modified. If x is not of the right length, SetBytesWithClamping returns nil and an error, and the receiver is unchanged.

Note that since Scalar values are always reduced modulo the prime order of the curve, the resulting value will not preserve any of the cofactor-clearing properties that clamping is meant to provide. It will however work as expected as long as it is applied to points on the prime order subgroup, like in Ed25519. In fact, it is lost to history why RFC 8032 adopted the irrelevant RFC 7748 clamping, but it is now required for compatibility.

func (*Scalar) SetCanonicalBytes 

func (s *Scalar) SetCanonicalBytes(x []byte) (*Scalar, error)

SetCanonicalBytes sets s = x, where x is a 32-byte little-endian encoding of s, and returns s. If x is not a canonical encoding of s, SetCanonicalBytes returns nil and an error, and the receiver is unchanged.

func (*Scalar) SetUniformBytes 

func (s *Scalar) SetUniformBytes(x []byte) (*Scalar, error)

SetUniformBytes sets s = x mod l, where x is a 64-byte little-endian integer. If x is not of the right length, SetUniformBytes returns nil and an error, and the receiver is unchanged.

SetUniformBytes can be used to set s to a uniformly distributed value given 64 uniformly distributed random bytes.

func (*Scalar) Subtract 

func (s *Scalar) Subtract(x, y *Scalar) *Scalar

Subtract sets s = x - y mod l, and returns s.

func (*Scalar) Zero 

func (s *Scalar) Zero() *Scalar

Source Files

View all Source files

Directories

Path Synopsis
Package field implements fast arithmetic modulo 2^255-19.
 Package field implements fast arithmetic modulo 2^255-19.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.