edwards25519

Documentation

Index

• Variables
• func FeAdd(dst, a, b *FieldElement)
• func FeCMove(f, g *FieldElement, b int32)
• func FeCombine(h *FieldElement, h0, h1, h2, h3, h4, h5, h6, h7, h8, h9 int64)
• func FeCopy(dst, src *FieldElement)
• func FeFromBytes(dst *FieldElement, src *[32]byte)
• func FeInvert(out, z *FieldElement)
• func FeIsNegative(f *FieldElement) byte
• func FeIsNonZero(f *FieldElement) int32
• func FeMul(h, f, g *FieldElement)
• func FeNeg(h, f *FieldElement)
• func FeOne(fe *FieldElement)
• func FeSquare(h, f *FieldElement)
• func FeSquare2(h, f *FieldElement)
• func FeSub(dst, a, b *FieldElement)
• func FeToBytes(s *[32]byte, h *FieldElement)
• func FeZero(fe *FieldElement)
• func GeDoubleScalarMultVartime(r *ProjectiveGroupElement, a *[32]byte, A *ExtendedGroupElement, b *[32]byte)
• func GeScalarMultBase(h *ExtendedGroupElement, a *[32]byte)
• func PreComputedGroupElementCMove(t, u *PreComputedGroupElement, b int32)
• func ScMulAdd(s, a, b, c *[32]byte)
• func ScReduce(out *[32]byte, s *[64]byte)
• type CachedGroupElement
• type CompletedGroupElement
  • func (p *CompletedGroupElement) ToExtended(r *ExtendedGroupElement)
  • func (p *CompletedGroupElement) ToProjective(r *ProjectiveGroupElement)
• type ExtendedGroupElement
  • func (p *ExtendedGroupElement) Double(r *CompletedGroupElement)
  • func (p *ExtendedGroupElement) FromBytes(s *[32]byte) bool
  • func (p *ExtendedGroupElement) ToBytes(s *[32]byte)
  • func (p *ExtendedGroupElement) ToCached(r *CachedGroupElement)
  • func (p *ExtendedGroupElement) ToProjective(r *ProjectiveGroupElement)
  • func (p *ExtendedGroupElement) Zero()
• type FieldElement
• type PreComputedGroupElement
  • func (p *PreComputedGroupElement) Zero()
• type ProjectiveGroupElement
  • func (p *ProjectiveGroupElement) Double(r *CompletedGroupElement)
  • func (p *ProjectiveGroupElement) ToBytes(s *[32]byte)
  • func (p *ProjectiveGroupElement) Zero()

Variables

var A = FieldElement{
	486662, 0, 0, 0, 0, 0, 0, 0, 0, 0,
}

A is a constant in the Montgomery-form of curve25519.

var SqrtM1 = FieldElement{
	-32595792, -7943725, 9377950, 3500415, 12389472, -272473, -25146209, -2005654, 326686, 11406482,
}

SqrtM1 is the square-root of -1 in the field.

Functions

func FeAdd

func FeAdd(dst, a, b *FieldElement)

func FeCMove

func FeCMove(f, g *FieldElement, b int32)

Replace (f,g) with (g,g) if b == 1; replace (f,g) with (f,g) if b == 0.

Preconditions: b in {0,1}.

func FeCombine

func FeCombine(h *FieldElement, h0, h1, h2, h3, h4, h5, h6, h7, h8, h9 int64)

func FeCopy

func FeCopy(dst, src *FieldElement)

func FeFromBytes

func FeFromBytes(dst *FieldElement, src *[32]byte)

func FeInvert

func FeInvert(out, z *FieldElement)

func FeIsNegative

func FeIsNegative(f *FieldElement) byte

func FeIsNonZero

func FeIsNonZero(f *FieldElement) int32

func FeMul

func FeMul(h, f, g *FieldElement)

FeMul calculates h = f * g Can overlap h with f or g.

Preconditions:

|f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
|g| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.

Postconditions:

|h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.

Notes on implementation strategy:

Using schoolbook multiplication. Karatsuba would save a little in some cost models.

Most multiplications by 2 and 19 are 32-bit precomputations; cheaper than 64-bit postcomputations.

There is one remaining multiplication by 19 in the carry chain; one *19 precomputation can be merged into this, but the resulting data flow is considerably less clean.

There are 12 carries below. 10 of them are 2-way parallelizable and vectorizable. Can get away with 11 carries, but then data flow is much deeper.

With tighter constraints on inputs, can squeeze carries into int32.

func FeNeg

func FeNeg(h, f *FieldElement)

FeNeg sets h = -f

Preconditions:

|f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.

Postconditions:

|h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.

func FeOne

func FeOne(fe *FieldElement)

func FeSquare

func FeSquare(h, f *FieldElement)

FeSquare calculates h = f*f. Can overlap h with f.

Preconditions:

|f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.

Postconditions:

|h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.

func FeSquare2

func FeSquare2(h, f *FieldElement)

FeSquare2 sets h = 2 * f * f

Can overlap h with f.

Preconditions:

|f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.

Postconditions:

|h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.

See fe_mul.c for discussion of implementation strategy.

func FeSub

func FeSub(dst, a, b *FieldElement)

func FeToBytes

func FeToBytes(s *[32]byte, h *FieldElement)

FeToBytes marshals h to s. Preconditions:

|h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.

Write p=2^255-19; q=floor(h/p). Basic claim: q = floor(2^(-255)(h + 19 2^(-25)h9 + 2^(-1))).

Proof:

Have |h|<=p so |q|<=1 so |19^2 2^(-255) q|<1/4.
Also have |h-2^230 h9|<2^230 so |19 2^(-255)(h-2^230 h9)|<1/4.

Write y=2^(-1)-19^2 2^(-255)q-19 2^(-255)(h-2^230 h9).
Then 0<y<1.

Write r=h-pq.
Have 0<=r<=p-1=2^255-20.
Thus 0<=r+19(2^-255)r<r+19(2^-255)2^255<=2^255-1.

Write x=r+19(2^-255)r+y.
Then 0<x<2^255 so floor(2^(-255)x) = 0 so floor(q+2^(-255)x) = q.

Have q+2^(-255)x = 2^(-255)(h + 19 2^(-25) h9 + 2^(-1))
so floor(2^(-255)(h + 19 2^(-25) h9 + 2^(-1))) = q.

func FeZero

func FeZero(fe *FieldElement)

func GeDoubleScalarMultVartime

func GeDoubleScalarMultVartime(r *ProjectiveGroupElement, a *[32]byte, A *ExtendedGroupElement, b *[32]byte)

GeDoubleScalarMultVartime sets r = a*A + b*B where a = a[0]+256*a[1]+...+256^31 a[31]. and b = b[0]+256*b[1]+...+256^31 b[31]. B is the Ed25519 base point (x,4/5) with x positive.

func GeScalarMultBase

func GeScalarMultBase(h *ExtendedGroupElement, a *[32]byte)

GeScalarMultBase computes h = a*B, where

a = a[0]+256*a[1]+...+256^31 a[31]
B is the Ed25519 base point (x,4/5) with x positive.

Preconditions:

a[31] <= 127

func PreComputedGroupElementCMove

func PreComputedGroupElementCMove(t, u *PreComputedGroupElement, b int32)

func ScMulAdd

func ScMulAdd(s, a, b, c *[32]byte)

Input:

a[0]+256*a[1]+...+256^31*a[31] = a
b[0]+256*b[1]+...+256^31*b[31] = b
c[0]+256*c[1]+...+256^31*c[31] = c

Output:

s[0]+256*s[1]+...+256^31*s[31] = (ab+c) mod l
where l = 2^252 + 27742317777372353535851937790883648493.

func ScReduce

func ScReduce(out *[32]byte, s *[64]byte)

Input:

s[0]+256*s[1]+...+256^63*s[63] = s

Output:

s[0]+256*s[1]+...+256^31*s[31] = s mod l
where l = 2^252 + 27742317777372353535851937790883648493.

Types

type CachedGroupElement

type CachedGroupElement struct {
	Z, T2d FieldElement
	// contains filtered or unexported fields
}

type CompletedGroupElement

type CompletedGroupElement struct {
	X, Y, Z, T FieldElement
}

func (*CompletedGroupElement) ToExtended

func (p *CompletedGroupElement) ToExtended(r *ExtendedGroupElement)

func (*CompletedGroupElement) ToProjective

func (p *CompletedGroupElement) ToProjective(r *ProjectiveGroupElement)

type ExtendedGroupElement

type ExtendedGroupElement struct {
	X, Y, Z, T FieldElement
}

func (*ExtendedGroupElement) Double

func (p *ExtendedGroupElement) Double(r *CompletedGroupElement)

func (*ExtendedGroupElement) FromBytes

func (p *ExtendedGroupElement) FromBytes(s *[32]byte) bool

func (*ExtendedGroupElement) ToBytes

func (p *ExtendedGroupElement) ToBytes(s *[32]byte)

func (*ExtendedGroupElement) ToCached

func (p *ExtendedGroupElement) ToCached(r *CachedGroupElement)

func (*ExtendedGroupElement) ToProjective

func (p *ExtendedGroupElement) ToProjective(r *ProjectiveGroupElement)

func (*ExtendedGroupElement) Zero

func (p *ExtendedGroupElement) Zero()

type FieldElement

type FieldElement [10]int32

FieldElement represents an element of the field GF(2^255 - 19). An element t, entries t[0]...t[9], represents the integer t[0]+2^26 t[1]+2^51 t[2]+2^77 t[3]+2^102 t[4]+...+2^230 t[9]. Bounds on each t[i] vary depending on context.

type PreComputedGroupElement

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

func (*PreComputedGroupElement) Zero

func (p *PreComputedGroupElement) Zero()

type ProjectiveGroupElement

type ProjectiveGroupElement struct {
	X, Y, Z FieldElement
}

func (*ProjectiveGroupElement) Double

func (p *ProjectiveGroupElement) Double(r *CompletedGroupElement)

func (*ProjectiveGroupElement) ToBytes

func (p *ProjectiveGroupElement) ToBytes(s *[32]byte)

func (*ProjectiveGroupElement) Zero

func (p *ProjectiveGroupElement) Zero()