ed25519

package
v0.0.0-...-729ab49 Latest Latest
Warning

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

 Go to latest Published: Feb 24, 2020 License: MIT Imports: 8 Imported by: 0

README

Edwards25519 Elliptic Curve

This is the standard edwards25519 curve definition.

Introduction

A drop-in replacement for golang/crypto/ed25519 (godoc, github) with additional functionality.

Motivation

In order to verify the validity of a given signature, the validator should posses the public key of the signer. It can be sent along with the message and its signature, which means that the overall data being sent includes 256 bits of the public key. Our function allows to extract the public key from the signature (and the message), thus the public key may not be sent, resulting in a smaller transferred data. Note: there's a computational cost for extracting the public key, so one should consider the trade-off between computations and data size.

Curve equation

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

Note:

  • curve is in two dimensions (nothing fancy, like all the curves is high school)
  • curve is mirrored below y axis due to y^2 part of the equation (not a polynomial)

Base point: G

The base point is a specific point on the curve. It is used as a basis for further calculations. It is an arbitrary choice by the curve authors, just to standardize the scheme.

Note that it is enough to specify the y value and the sign of the x value. That's because the specific x can be calculated from the curve equation.

G = (x, 4/5)  # take the point with the positive x

# The hex representation of the base point
5866666666666666666666666666666666666666666666666666666666666666

Prime order of the base point: l

l = 2^252 + 27742317777372353535851937790883648493
# => 7237005577332262213973186563042994240857116359379907606001950938285454250989

The l is a prime number specified by the curve authors.

In practice this is the private key's strength.

Total number of points on the curve¶

The total number of points on the curve is also a prime number:

q = 2^255 - 19

In practice not all points are "useful" and so the private key strength is limited to l describe above.

API

Sign2

Sign2 signs the message with privateKey and returns a signature. The signature may be verified using Verify2(), if the signer's public key is known. The signature returned by this method can be used together with the message to extract the public key using ExtractPublicKey() It will panic if len(privateKey) is not PrivateKeySize.

func Sign2(privateKey PrivateKey, message []byte) []byte
ExtractPublicKey

ExtractPublicKey extracts the signer's public key given a message and its signature. It will panic if len(sig) is not SignatureSize.

func ExtractPublicKey(message, sig []byte) PublicKey
Verify2

Verify2 verifies a signature created with Sign2(), assuming the verifier possesses the public key.

func Verify2(publicKey PublicKey, message, sig []byte) bool

Building

go build

Testing

go test ./... -v

Benchmarking

go test -bench=.
go test -bench . github.com/spacemeshos/ed25519/internal/edwards25519

Documentation

Overview

Package ed25519 implements the Ed25519 signature algorithm. See https://ed25519.cr.yp.to/.

These functions are also compatible with the “Ed25519” function defined in RFC 8032. However, unlike RFC 8032's formulation, this package's private key representation includes a public key suffix to make multiple signing operations with the same key more efficient. This package refers to the RFC 8032 private key as the “seed”.

Beginning with Go 1.13, the functionality of this package was moved to the standard library as crypto/ed25519. This package only acts as a compatibility wrapper.

Index

Constants

View Source 
const (
	// PublicKeySize is the size, in bytes, of public keys as used in this package.
	PublicKeySize = 32
	// PrivateKeySize is the size, in bytes, of private keys as used in this package.
	PrivateKeySize = 64
	// SignatureSize is the size, in bytes, of signatures generated and verified by this package.
	SignatureSize = 64
	// SeedSize is the size, in bytes, of private key seeds. These are the private key representations used by RFC 8032.
	SeedSize = 32
)

Variables

View Source 
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 GeScalarMultVartime 

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

GeScalarMultVartime sets r = a*A where a = a[0]+256*a[1]+...+256^31 a[31]. and A is a point on the curve

func GenerateKey 

func GenerateKey(rand io.Reader) (PublicKey, PrivateKey, error)

GenerateKey generates a public/private key pair using entropy from rand. If rand is nil, crypto/rand.Reader will be used.

func InvertModL 

func InvertModL(out, z *[32]byte)

InvertModL computes z mod l and puts the result into out

func InvertModL_old 

func InvertModL_old(out, z *[32]byte)

func PreComputedGroupElementCMove 

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

func ScMinimal 

func ScMinimal(scalar *[32]byte) bool

ScMinimal returns true if the given scalar is less than the order of the curve.

func ScMul 

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

The scalars are GF(2^252 + 27742317777372353535851937790883648493). Input: 

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

Output: 

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

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.

func Sign 

func Sign(privateKey PrivateKey, message []byte) []byte

Sign signs the message with privateKey and returns a signature. It will panic if len(privateKey) is not PrivateKeySize.

func Sign2 

func Sign2(privateKey PrivateKey, message []byte) []byte

Sign2 signs the message with privateKey and returns a signature. The signature may be verified using VerifyEx(), if the signer's public key is known. The signature returned by this method can be used together with the message to extract the public key using ExtractPublicKey() It will panic if len(privateKey) is not PrivateKeySize.

func Verify 

func Verify(publicKey PublicKey, message, sig []byte) bool

Verify reports whether sig is a valid signature of message by publicKey. It will panic if len(publicKey) is not PublicKeySize.

func Verify2 

func Verify2(publicKey PublicKey, message, sig []byte) bool

Verify2 verifies a signature created with Sign2(), assuming the verifier possesses the public key.

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 Curve 

type Curve struct {
}

Curve represents the Ed25519 group. There are no parameters and no initialization is required because it supports only this one specific curve.

func (*Curve) PointLen 

func (c *Curve) PointLen() int

PointLen returns 32, the size in bytes of an encoded Point on the Ed25519 curve.

func (*Curve) ScalarLen 

func (c *Curve) ScalarLen() int

ScalarLen returns 32, the size in bytes of an encoded Scalar for the Ed25519 curve.

func (*Curve) String 

func (c *Curve) String() string

Return the name of the curve, "Ed25519".

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 PreComputedGroupElement 

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

func (*PreComputedGroupElement) Zero 

func (p *PreComputedGroupElement) Zero()

type PrivateKey 

type PrivateKey = ed25519.PrivateKey

PrivateKey is the type of Ed25519 private keys. It implements crypto.Signer.

This type is an alias for crypto/ed25519's PrivateKey type. See the crypto/ed25519 package for the methods on this type.

func NewDerivedKeyFromSeed 

func NewDerivedKeyFromSeed(seed []byte, index uint64, salt []byte) PrivateKey

NewDerivedKeyFromSeed calculates a private key from a 32 bytes random seed, an integer index and salt

func NewKeyFromSeed 

func NewKeyFromSeed(seed []byte) PrivateKey

NewKeyFromSeed calculates a private key from a seed. It will panic if len(seed) is not SeedSize. This function is provided for interoperability with RFC 8032. RFC 8032's private keys correspond to seeds in this package.

type ProjectiveGroupElement 

type ProjectiveGroupElement struct {
	X, Y, Z fieldElement
}

func (*ProjectiveGroupElement) Double 

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

func (*ProjectiveGroupElement) ProjBytesExt 

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

func (*ProjectiveGroupElement) ToBytes 

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

func (*ProjectiveGroupElement) ToExtended 

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

func (*ProjectiveGroupElement) Zero 

func (p *ProjectiveGroupElement) Zero()

type PublicKey 

type PublicKey = ed25519.PublicKey

PublicKey is the type of Ed25519 public keys.

This type is an alias for crypto/ed25519's PublicKey type. See the crypto/ed25519 package for the methods on this type.

func ExtractPublicKey 

func ExtractPublicKey(message, sig []byte) (PublicKey, error)

ExtractPublicKey extracts the signer's public key given a message and its signature. Note that signature must be created using Sign2() and NOT using Sign(). It will panic if len(sig) is not SignatureSize.

Source Files

View all Source files

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.