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

View as plain text