ed25519.go

     1  // Copyright 2016 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package ed25519 implements the Ed25519 signature algorithm. See
     6  // https://ed25519.cr.yp.to/.
     7  //
     8  // These functions are also compatible with the “Ed25519” function defined in
     9  // RFC 8032. However, unlike RFC 8032's formulation, this package's private key
    10  // representation includes a public key suffix to make multiple signing
    11  // operations with the same key more efficient. This package refers to the RFC
    12  // 8032 private key as the “seed”.
    13  //
    14  // Operations involving private keys are implemented using constant-time
    15  // algorithms.
    16  package ed25519
    17  
    18  import (
    19  	"bytes"
    20  	"crypto"
    21  	"crypto/internal/edwards25519"
    22  	cryptorand "crypto/rand"
    23  	"crypto/sha512"
    24  	"crypto/subtle"
    25  	"errors"
    26  	"io"
    27  	"strconv"
    28  )
    29  
    30  const (
    31  	// PublicKeySize is the size, in bytes, of public keys as used in this package.
    32  	PublicKeySize = 32
    33  	// PrivateKeySize is the size, in bytes, of private keys as used in this package.
    34  	PrivateKeySize = 64
    35  	// SignatureSize is the size, in bytes, of signatures generated and verified by this package.
    36  	SignatureSize = 64
    37  	// SeedSize is the size, in bytes, of private key seeds. These are the private key representations used by RFC 8032.
    38  	SeedSize = 32
    39  )
    40  
    41  // PublicKey is the type of Ed25519 public keys.
    42  type PublicKey []byte
    43  
    44  // Any methods implemented on PublicKey might need to also be implemented on
    45  // PrivateKey, as the latter embeds the former and will expose its methods.
    46  
    47  // Equal reports whether pub and x have the same value.
    48  func (pub PublicKey) Equal(x crypto.PublicKey) bool {
    49  	xx, ok := x.(PublicKey)
    50  	if !ok {
    51  		return false
    52  	}
    53  	return subtle.ConstantTimeCompare(pub, xx) == 1
    54  }
    55  
    56  // PrivateKey is the type of Ed25519 private keys. It implements [crypto.Signer].
    57  type PrivateKey []byte
    58  
    59  // Public returns the [PublicKey] corresponding to priv.
    60  func (priv PrivateKey) Public() crypto.PublicKey {
    61  	publicKey := make([]byte, PublicKeySize)
    62  	copy(publicKey, priv[32:])
    63  	return PublicKey(publicKey)
    64  }
    65  
    66  // Equal reports whether priv and x have the same value.
    67  func (priv PrivateKey) Equal(x crypto.PrivateKey) bool {
    68  	xx, ok := x.(PrivateKey)
    69  	if !ok {
    70  		return false
    71  	}
    72  	return subtle.ConstantTimeCompare(priv, xx) == 1
    73  }
    74  
    75  // Seed returns the private key seed corresponding to priv. It is provided for
    76  // interoperability with RFC 8032. RFC 8032's private keys correspond to seeds
    77  // in this package.
    78  func (priv PrivateKey) Seed() []byte {
    79  	return bytes.Clone(priv[:SeedSize])
    80  }
    81  
    82  // Sign signs the given message with priv. rand is ignored and can be nil.
    83  //
    84  // If opts.HashFunc() is [crypto.SHA512], the pre-hashed variant Ed25519ph is used
    85  // and message is expected to be a SHA-512 hash, otherwise opts.HashFunc() must
    86  // be [crypto.Hash](0) and the message must not be hashed, as Ed25519 performs two
    87  // passes over messages to be signed.
    88  //
    89  // A value of type [Options] can be used as opts, or crypto.Hash(0) or
    90  // crypto.SHA512 directly to select plain Ed25519 or Ed25519ph, respectively.
    91  func (priv PrivateKey) Sign(rand io.Reader, message []byte, opts crypto.SignerOpts) (signature []byte, err error) {
    92  	hash := opts.HashFunc()
    93  	context := ""
    94  	if opts, ok := opts.(*Options); ok {
    95  		context = opts.Context
    96  	}
    97  	switch {
    98  	case hash == crypto.SHA512: // Ed25519ph
    99  		if l := len(message); l != sha512.Size {
   100  			return nil, errors.New("ed25519: bad Ed25519ph message hash length: " + strconv.Itoa(l))
   101  		}
   102  		if l := len(context); l > 255 {
   103  			return nil, errors.New("ed25519: bad Ed25519ph context length: " + strconv.Itoa(l))
   104  		}
   105  		signature := make([]byte, SignatureSize)
   106  		sign(signature, priv, message, domPrefixPh, context)
   107  		return signature, nil
   108  	case hash == crypto.Hash(0) && context != "": // Ed25519ctx
   109  		if l := len(context); l > 255 {
   110  			return nil, errors.New("ed25519: bad Ed25519ctx context length: " + strconv.Itoa(l))
   111  		}
   112  		signature := make([]byte, SignatureSize)
   113  		sign(signature, priv, message, domPrefixCtx, context)
   114  		return signature, nil
   115  	case hash == crypto.Hash(0): // Ed25519
   116  		return Sign(priv, message), nil
   117  	default:
   118  		return nil, errors.New("ed25519: expected opts.HashFunc() zero (unhashed message, for standard Ed25519) or SHA-512 (for Ed25519ph)")
   119  	}
   120  }
   121  
   122  // Options can be used with [PrivateKey.Sign] or [VerifyWithOptions]
   123  // to select Ed25519 variants.
   124  type Options struct {
   125  	// Hash can be zero for regular Ed25519, or crypto.SHA512 for Ed25519ph.
   126  	Hash crypto.Hash
   127  
   128  	// Context, if not empty, selects Ed25519ctx or provides the context string
   129  	// for Ed25519ph. It can be at most 255 bytes in length.
   130  	Context string
   131  }
   132  
   133  // HashFunc returns o.Hash.
   134  func (o *Options) HashFunc() crypto.Hash { return o.Hash }
   135  
   136  // GenerateKey generates a public/private key pair using entropy from rand.
   137  // If rand is nil, [crypto/rand.Reader] will be used.
   138  //
   139  // The output of this function is deterministic, and equivalent to reading
   140  // [SeedSize] bytes from rand, and passing them to [NewKeyFromSeed].
   141  func GenerateKey(rand io.Reader) (PublicKey, PrivateKey, error) {
   142  	if rand == nil {
   143  		rand = cryptorand.Reader
   144  	}
   145  
   146  	seed := make([]byte, SeedSize)
   147  	if _, err := io.ReadFull(rand, seed); err != nil {
   148  		return nil, nil, err
   149  	}
   150  
   151  	privateKey := NewKeyFromSeed(seed)
   152  	publicKey := make([]byte, PublicKeySize)
   153  	copy(publicKey, privateKey[32:])
   154  
   155  	return publicKey, privateKey, nil
   156  }
   157  
   158  // NewKeyFromSeed calculates a private key from a seed. It will panic if
   159  // len(seed) is not [SeedSize]. This function is provided for interoperability
   160  // with RFC 8032. RFC 8032's private keys correspond to seeds in this
   161  // package.
   162  func NewKeyFromSeed(seed []byte) PrivateKey {
   163  	// Outline the function body so that the returned key can be stack-allocated.
   164  	privateKey := make([]byte, PrivateKeySize)
   165  	newKeyFromSeed(privateKey, seed)
   166  	return privateKey
   167  }
   168  
   169  func newKeyFromSeed(privateKey, seed []byte) {
   170  	if l := len(seed); l != SeedSize {
   171  		panic("ed25519: bad seed length: " + strconv.Itoa(l))
   172  	}
   173  
   174  	h := sha512.Sum512(seed)
   175  	s, err := edwards25519.NewScalar().SetBytesWithClamping(h[:32])
   176  	if err != nil {
   177  		panic("ed25519: internal error: setting scalar failed")
   178  	}
   179  	A := (&edwards25519.Point{}).ScalarBaseMult(s)
   180  
   181  	publicKey := A.Bytes()
   182  
   183  	copy(privateKey, seed)
   184  	copy(privateKey[32:], publicKey)
   185  }
   186  
   187  // Sign signs the message with privateKey and returns a signature. It will
   188  // panic if len(privateKey) is not [PrivateKeySize].
   189  func Sign(privateKey PrivateKey, message []byte) []byte {
   190  	// Outline the function body so that the returned signature can be
   191  	// stack-allocated.
   192  	signature := make([]byte, SignatureSize)
   193  	sign(signature, privateKey, message, domPrefixPure, "")
   194  	return signature
   195  }
   196  
   197  // Domain separation prefixes used to disambiguate Ed25519/Ed25519ph/Ed25519ctx.
   198  // See RFC 8032, Section 2 and Section 5.1.
   199  const (
   200  	// domPrefixPure is empty for pure Ed25519.
   201  	domPrefixPure = ""
   202  	// domPrefixPh is dom2(phflag=1) for Ed25519ph. It must be followed by the
   203  	// uint8-length prefixed context.
   204  	domPrefixPh = "SigEd25519 no Ed25519 collisions\x01"
   205  	// domPrefixCtx is dom2(phflag=0) for Ed25519ctx. It must be followed by the
   206  	// uint8-length prefixed context.
   207  	domPrefixCtx = "SigEd25519 no Ed25519 collisions\x00"
   208  )
   209  
   210  func sign(signature, privateKey, message []byte, domPrefix, context string) {
   211  	if l := len(privateKey); l != PrivateKeySize {
   212  		panic("ed25519: bad private key length: " + strconv.Itoa(l))
   213  	}
   214  	seed, publicKey := privateKey[:SeedSize], privateKey[SeedSize:]
   215  
   216  	h := sha512.Sum512(seed)
   217  	s, err := edwards25519.NewScalar().SetBytesWithClamping(h[:32])
   218  	if err != nil {
   219  		panic("ed25519: internal error: setting scalar failed")
   220  	}
   221  	prefix := h[32:]
   222  
   223  	mh := sha512.New()
   224  	if domPrefix != domPrefixPure {
   225  		mh.Write([]byte(domPrefix))
   226  		mh.Write([]byte{byte(len(context))})
   227  		mh.Write([]byte(context))
   228  	}
   229  	mh.Write(prefix)
   230  	mh.Write(message)
   231  	messageDigest := make([]byte, 0, sha512.Size)
   232  	messageDigest = mh.Sum(messageDigest)
   233  	r, err := edwards25519.NewScalar().SetUniformBytes(messageDigest)
   234  	if err != nil {
   235  		panic("ed25519: internal error: setting scalar failed")
   236  	}
   237  
   238  	R := (&edwards25519.Point{}).ScalarBaseMult(r)
   239  
   240  	kh := sha512.New()
   241  	if domPrefix != domPrefixPure {
   242  		kh.Write([]byte(domPrefix))
   243  		kh.Write([]byte{byte(len(context))})
   244  		kh.Write([]byte(context))
   245  	}
   246  	kh.Write(R.Bytes())
   247  	kh.Write(publicKey)
   248  	kh.Write(message)
   249  	hramDigest := make([]byte, 0, sha512.Size)
   250  	hramDigest = kh.Sum(hramDigest)
   251  	k, err := edwards25519.NewScalar().SetUniformBytes(hramDigest)
   252  	if err != nil {
   253  		panic("ed25519: internal error: setting scalar failed")
   254  	}
   255  
   256  	S := edwards25519.NewScalar().MultiplyAdd(k, s, r)
   257  
   258  	copy(signature[:32], R.Bytes())
   259  	copy(signature[32:], S.Bytes())
   260  }
   261  
   262  // Verify reports whether sig is a valid signature of message by publicKey. It
   263  // will panic if len(publicKey) is not [PublicKeySize].
   264  //
   265  // The inputs are not considered confidential, and may leak through timing side
   266  // channels, or if an attacker has control of part of the inputs.
   267  func Verify(publicKey PublicKey, message, sig []byte) bool {
   268  	return verify(publicKey, message, sig, domPrefixPure, "")
   269  }
   270  
   271  // VerifyWithOptions reports whether sig is a valid signature of message by
   272  // publicKey. A valid signature is indicated by returning a nil error. It will
   273  // panic if len(publicKey) is not [PublicKeySize].
   274  //
   275  // If opts.Hash is [crypto.SHA512], the pre-hashed variant Ed25519ph is used and
   276  // message is expected to be a SHA-512 hash, otherwise opts.Hash must be
   277  // [crypto.Hash](0) and the message must not be hashed, as Ed25519 performs two
   278  // passes over messages to be signed.
   279  //
   280  // The inputs are not considered confidential, and may leak through timing side
   281  // channels, or if an attacker has control of part of the inputs.
   282  func VerifyWithOptions(publicKey PublicKey, message, sig []byte, opts *Options) error {
   283  	switch {
   284  	case opts.Hash == crypto.SHA512: // Ed25519ph
   285  		if l := len(message); l != sha512.Size {
   286  			return errors.New("ed25519: bad Ed25519ph message hash length: " + strconv.Itoa(l))
   287  		}
   288  		if l := len(opts.Context); l > 255 {
   289  			return errors.New("ed25519: bad Ed25519ph context length: " + strconv.Itoa(l))
   290  		}
   291  		if !verify(publicKey, message, sig, domPrefixPh, opts.Context) {
   292  			return errors.New("ed25519: invalid signature")
   293  		}
   294  		return nil
   295  	case opts.Hash == crypto.Hash(0) && opts.Context != "": // Ed25519ctx
   296  		if l := len(opts.Context); l > 255 {
   297  			return errors.New("ed25519: bad Ed25519ctx context length: " + strconv.Itoa(l))
   298  		}
   299  		if !verify(publicKey, message, sig, domPrefixCtx, opts.Context) {
   300  			return errors.New("ed25519: invalid signature")
   301  		}
   302  		return nil
   303  	case opts.Hash == crypto.Hash(0): // Ed25519
   304  		if !verify(publicKey, message, sig, domPrefixPure, "") {
   305  			return errors.New("ed25519: invalid signature")
   306  		}
   307  		return nil
   308  	default:
   309  		return errors.New("ed25519: expected opts.Hash zero (unhashed message, for standard Ed25519) or SHA-512 (for Ed25519ph)")
   310  	}
   311  }
   312  
   313  func verify(publicKey PublicKey, message, sig []byte, domPrefix, context string) bool {
   314  	if l := len(publicKey); l != PublicKeySize {
   315  		panic("ed25519: bad public key length: " + strconv.Itoa(l))
   316  	}
   317  
   318  	if len(sig) != SignatureSize || sig[63]&224 != 0 {
   319  		return false
   320  	}
   321  
   322  	A, err := (&edwards25519.Point{}).SetBytes(publicKey)
   323  	if err != nil {
   324  		return false
   325  	}
   326  
   327  	kh := sha512.New()
   328  	if domPrefix != domPrefixPure {
   329  		kh.Write([]byte(domPrefix))
   330  		kh.Write([]byte{byte(len(context))})
   331  		kh.Write([]byte(context))
   332  	}
   333  	kh.Write(sig[:32])
   334  	kh.Write(publicKey)
   335  	kh.Write(message)
   336  	hramDigest := make([]byte, 0, sha512.Size)
   337  	hramDigest = kh.Sum(hramDigest)
   338  	k, err := edwards25519.NewScalar().SetUniformBytes(hramDigest)
   339  	if err != nil {
   340  		panic("ed25519: internal error: setting scalar failed")
   341  	}
   342  
   343  	S, err := edwards25519.NewScalar().SetCanonicalBytes(sig[32:])
   344  	if err != nil {
   345  		return false
   346  	}
   347  
   348  	// [S]B = R + [k]A --> [k](-A) + [S]B = R
   349  	minusA := (&edwards25519.Point{}).Negate(A)
   350  	R := (&edwards25519.Point{}).VarTimeDoubleScalarBaseMult(k, minusA, S)
   351  
   352  	return bytes.Equal(sig[:32], R.Bytes())
   353  }
   354
View as plain text