edwards25519

func ExtendedGroupElementCMove ¶

func ExtendedGroupElementCMove(t, u *ExtendedGroupElement, b int32)

func ExtendedGroupElementCopy ¶

func ExtendedGroupElementCopy(t, u *ExtendedGroupElement)

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 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 GeAdd ¶

func GeAdd(r, a, b *ExtendedGroupElement)

GeAdd sets r = a+b. r may overlaop with a and b.

func GeDouble ¶

func GeDouble(r, p *ExtendedGroupElement)

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 GeScalarMult ¶

func GeScalarMult(r *ExtendedGroupElement, a *[32]byte, A *ExtendedGroupElement)

GeScalarMult sets r = a*A where a = a[0]+256*a[1]+...+256^31 a[31].

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 ScNeg ¶

func ScNeg(r, s *[32]byte)

Input:

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

Output:

s[0]+256*s[1]+...+256^31*s[31] = l - s
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.