edwards25519

package
v0.0.0-...-98bfee9 Latest Latest
Warning

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

Go to latest
Published: Mar 28, 2016 License: Apache-2.0 Imports: 1 Imported by: 0

Documentation

Overview

Package edwards25519 implements operations in GF(2**255-19) and on an Edwards curve that is isomorphic to curve25519. See http://ed25519.cr.yp.to/.

Index

Constants

This section is empty.

Variables

View Source
var A = FieldElement{
	486662, 0, 0, 0, 0, 0, 0, 0, 0, 0,
}
View Source
var BasePointOrder = [32]byte{237, 211, 245, 92, 26, 99, 18, 88, 214, 156, 247, 162, 222, 249, 222, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16}

BasePointOrder is the number of points in the subgroup generated by the base point.

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

Functions

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.

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 (*ExtendedGroupElement) FromBytes

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

func (*ExtendedGroupElement) FromBytesBaseGroup

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

FromBytesBaseGroup unmarshals an elliptic curve point returns true iff the point point is in the order l subgroup generated by the base point. This implementation is based on https://www.iacr.org/archive/pkc2003/25670211/25670211.pdf Definition 1. Validation of an elliptic curve public key P ensures that P is a point of order BasePointOrder in E.

func (*ExtendedGroupElement) FromParityAndY

func (p *ExtendedGroupElement) FromParityAndY(bit byte, y *FieldElement) 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 (*ProjectiveGroupElement) ToBytes

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

func (*ProjectiveGroupElement) ToExtended

func (p *ProjectiveGroupElement) ToExtended(s *ExtendedGroupElement)

func (*ProjectiveGroupElement) Zero

func (p *ProjectiveGroupElement) Zero()

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL