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 ¶
- Variables
- func CachedGroupElementCMove(t, u *CachedGroupElement, b int32)
- 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 FeDivPowM1(out, u, v *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 GeDoubleScalarMultPrecompVartime(r *ProjectiveGroupElement, a *[32]byte, A *ExtendedGroupElement, b *[32]byte, ...)
- func GeDoubleScalarMultVartime(r *ProjectiveGroupElement, a *[32]byte, A *ExtendedGroupElement, b *[32]byte)
- func GeMul8(r *CompletedGroupElement, t *ProjectiveGroupElement)
- func GePrecompute(r *[8]CachedGroupElement, s *ExtendedGroupElement)
- func GeScalarMult(r *ProjectiveGroupElement, a *[32]byte, A *ExtendedGroupElement)
- func GeScalarMultBase(h *ExtendedGroupElement, a *[32]byte)
- func PreComputedGroupElementCMove(t, u *PreComputedGroupElement, b int32)
- func ScAdd(s, a, b *[32]byte)
- func ScIsZero(s *[32]byte) bool
- func ScMulAdd(s, a, b, c *[32]byte)
- func ScMulSub(s, a, b, c *[32]byte)
- func ScReduce(out *[32]byte, s *[64]byte)
- func ScReduce32(s *[32]byte)
- func ScSub(s, a, b *[32]byte)
- func ScValid(s *[32]byte) bool
- type CachedGroupElement
- type CompletedGroupElement
- 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
- type ProjectiveGroupElement
Constants ¶
This section is empty.
Variables ¶
var A = FieldElement{
486662, 0, 0, 0, 0, 0, 0, 0, 0, 0,
}
var FeFffb1 = FieldElement{-31702527, -2466483, -26106795, -12203692, -12169197, -321052, 14850977, -10296299, -16929438, -407568} /* sqrt(-2 * A * (A + 2)) */
var FeFffb2 = FieldElement{8166131, -6741800, -17040804, 3154616, 21461005, 1466302, -30876704, -6368709, 10503587, -13363080} /* sqrt(2 * A * (A + 2)) */
var FeFffb3 = FieldElement{-13620103, 14639558, 4532995, 7679154, 16815101, -15883539, -22863840, -14813421, 13716513, -6477756} /* sqrt(-sqrt(-1) * A * (A + 2)) */
var FeFffb4 = FieldElement{-21786234, -12173074, 21573800, 4524538, -4645904, 16204591, 8012863, -8444712, 3212926, 6885324} /* sqrt(sqrt(-1) * A * (A + 2)) */
var FeMa = FieldElement{-486662, 0, 0, 0, 0, 0, 0, 0, 0, 0} /* -A */
var FeMa2 = FieldElement{-12721188, -3529, 0, 0, 0, 0, 0, 0, 0, 0} /* -A^2 */
var FeSqrtM1 = FieldElement{-32595792, -7943725, 9377950, 3500415, 12389472, -272473, -25146209, -2005654, 326686, 11406482} /* sqrt(-1) */
var SqrtM1 = FieldElement{
-32595792, -7943725, 9377950, 3500415, 12389472, -272473, -25146209, -2005654, 326686, 11406482,
}
Functions ¶
func CachedGroupElementCMove ¶
func CachedGroupElementCMove(t, u *CachedGroupElement, b int32)
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 FeDivPowM1 ¶
func FeDivPowM1(out, u, v *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 GeDoubleScalarMultPrecompVartime ¶
func GeDoubleScalarMultPrecompVartime(r *ProjectiveGroupElement, a *[32]byte, A *ExtendedGroupElement, b *[32]byte, Bi *[8]CachedGroupElement)
sets r = a*A + b*B where Bi is the [8]CachedGroupElement consisting of B,3B,5B,7B,9B,11B,13B,15B
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 GePrecompute ¶
func GePrecompute(r *[8]CachedGroupElement, s *ExtendedGroupElement)
caches s into an array of CachedGroupElements for scalar multiplication later
func GeScalarMult ¶
func GeScalarMult(r *ProjectiveGroupElement, a *[32]byte, A *ExtendedGroupElement)
GeScalarMult computes h = a*A, where
a = a[0]+256*a[1]+...+256^31 a[31] A is a point on the curve
Preconditions:
a[31] <= 127
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 ScMulSub ¶
func ScMulSub(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] = (c-ab) mod l where l = 2^252 + 27742317777372353535851937790883648493.
func ScReduce ¶
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.
func ScReduce32 ¶
func ScReduce32(s *[32]byte)
Types ¶
type CachedGroupElement ¶
type CachedGroupElement struct {
Z, T2d FieldElement
// contains filtered or unexported fields
}
func (*CachedGroupElement) Zero ¶
func (c *CachedGroupElement) Zero()
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) FromBytes ¶
func (p *ProjectiveGroupElement) FromBytes(s *[32]byte)
func (*ProjectiveGroupElement) ToBytes ¶
func (p *ProjectiveGroupElement) ToBytes(s *[32]byte)
func (*ProjectiveGroupElement) Zero ¶
func (p *ProjectiveGroupElement) Zero()