ed25519.go

     1  // Copyright 2024 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
     6  
     7  import (
     8  	"bytes"
     9  	"crypto/internal/fips140"
    10  	"crypto/internal/fips140/drbg"
    11  	"crypto/internal/fips140/edwards25519"
    12  	"crypto/internal/fips140/sha512"
    13  	"errors"
    14  	"strconv"
    15  )
    16  
    17  // See https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/ for the
    18  // components of the keys and the moving parts of the algorithm.
    19  
    20  const (
    21  	seedSize       = 32
    22  	publicKeySize  = 32
    23  	privateKeySize = seedSize + publicKeySize
    24  	signatureSize  = 64
    25  	sha512Size     = 64
    26  )
    27  
    28  type PrivateKey struct {
    29  	seed   [seedSize]byte
    30  	pub    [publicKeySize]byte
    31  	s      edwards25519.Scalar
    32  	prefix [sha512Size / 2]byte
    33  }
    34  
    35  func (priv *PrivateKey) Bytes() []byte {
    36  	k := make([]byte, 0, privateKeySize)
    37  	k = append(k, priv.seed[:]...)
    38  	k = append(k, priv.pub[:]...)
    39  	return k
    40  }
    41  
    42  func (priv *PrivateKey) Seed() []byte {
    43  	seed := priv.seed
    44  	return seed[:]
    45  }
    46  
    47  func (priv *PrivateKey) PublicKey() []byte {
    48  	pub := priv.pub
    49  	return pub[:]
    50  }
    51  
    52  type PublicKey struct {
    53  	a      edwards25519.Point
    54  	aBytes [32]byte
    55  }
    56  
    57  func (pub *PublicKey) Bytes() []byte {
    58  	a := pub.aBytes
    59  	return a[:]
    60  }
    61  
    62  // GenerateKey generates a new Ed25519 private key pair.
    63  func GenerateKey() (*PrivateKey, error) {
    64  	priv := &PrivateKey{}
    65  	return generateKey(priv)
    66  }
    67  
    68  func generateKey(priv *PrivateKey) (*PrivateKey, error) {
    69  	fips140.RecordApproved()
    70  	drbg.Read(priv.seed[:])
    71  	precomputePrivateKey(priv)
    72  	if err := fipsPCT(priv); err != nil {
    73  		// This clearly can't happen, but FIPS 140-3 requires that we check.
    74  		panic(err)
    75  	}
    76  	return priv, nil
    77  }
    78  
    79  func NewPrivateKeyFromSeed(seed []byte) (*PrivateKey, error) {
    80  	priv := &PrivateKey{}
    81  	return newPrivateKeyFromSeed(priv, seed)
    82  }
    83  
    84  func newPrivateKeyFromSeed(priv *PrivateKey, seed []byte) (*PrivateKey, error) {
    85  	fips140.RecordApproved()
    86  	if l := len(seed); l != seedSize {
    87  		return nil, errors.New("ed25519: bad seed length: " + strconv.Itoa(l))
    88  	}
    89  	copy(priv.seed[:], seed)
    90  	precomputePrivateKey(priv)
    91  	if err := fipsPCT(priv); err != nil {
    92  		// This clearly can't happen, but FIPS 140-3 requires that we check.
    93  		panic(err)
    94  	}
    95  	return priv, nil
    96  }
    97  
    98  func precomputePrivateKey(priv *PrivateKey) {
    99  	hs := sha512.New()
   100  	hs.Write(priv.seed[:])
   101  	h := hs.Sum(make([]byte, 0, sha512Size))
   102  
   103  	s, err := priv.s.SetBytesWithClamping(h[:32])
   104  	if err != nil {
   105  		panic("ed25519: internal error: setting scalar failed")
   106  	}
   107  	A := (&edwards25519.Point{}).ScalarBaseMult(s)
   108  	copy(priv.pub[:], A.Bytes())
   109  
   110  	copy(priv.prefix[:], h[32:])
   111  }
   112  
   113  func NewPrivateKey(priv []byte) (*PrivateKey, error) {
   114  	p := &PrivateKey{}
   115  	return newPrivateKey(p, priv)
   116  }
   117  
   118  func newPrivateKey(priv *PrivateKey, privBytes []byte) (*PrivateKey, error) {
   119  	fips140.RecordApproved()
   120  	if l := len(privBytes); l != privateKeySize {
   121  		return nil, errors.New("ed25519: bad private key length: " + strconv.Itoa(l))
   122  	}
   123  
   124  	copy(priv.seed[:], privBytes[:32])
   125  
   126  	hs := sha512.New()
   127  	hs.Write(priv.seed[:])
   128  	h := hs.Sum(make([]byte, 0, sha512Size))
   129  
   130  	if _, err := priv.s.SetBytesWithClamping(h[:32]); err != nil {
   131  		panic("ed25519: internal error: setting scalar failed")
   132  	}
   133  	// Note that we are not decompressing the public key point here,
   134  	// because it takes > 20% of the time of a signature generation.
   135  	// Signing doesn't use it as a point anyway.
   136  	copy(priv.pub[:], privBytes[32:])
   137  
   138  	copy(priv.prefix[:], h[32:])
   139  
   140  	if err := fipsPCT(priv); err != nil {
   141  		// This can happen if the application messed with the private key
   142  		// encoding, and the public key doesn't match the seed anymore.
   143  		return nil, err
   144  	}
   145  
   146  	return priv, nil
   147  }
   148  
   149  func NewPublicKey(pub []byte) (*PublicKey, error) {
   150  	p := &PublicKey{}
   151  	return newPublicKey(p, pub)
   152  }
   153  
   154  func newPublicKey(pub *PublicKey, pubBytes []byte) (*PublicKey, error) {
   155  	if l := len(pubBytes); l != publicKeySize {
   156  		return nil, errors.New("ed25519: bad public key length: " + strconv.Itoa(l))
   157  	}
   158  	// SetBytes checks that the point is on the curve.
   159  	if _, err := pub.a.SetBytes(pubBytes); err != nil {
   160  		return nil, errors.New("ed25519: bad public key")
   161  	}
   162  	copy(pub.aBytes[:], pubBytes)
   163  	return pub, nil
   164  }
   165  
   166  // Domain separation prefixes used to disambiguate Ed25519/Ed25519ph/Ed25519ctx.
   167  // See RFC 8032, Section 2 and Section 5.1.
   168  const (
   169  	// domPrefixPure is empty for pure Ed25519.
   170  	domPrefixPure = ""
   171  	// domPrefixPh is dom2(phflag=1) for Ed25519ph. It must be followed by the
   172  	// uint8-length prefixed context.
   173  	domPrefixPh = "SigEd25519 no Ed25519 collisions\x01"
   174  	// domPrefixCtx is dom2(phflag=0) for Ed25519ctx. It must be followed by the
   175  	// uint8-length prefixed context.
   176  	domPrefixCtx = "SigEd25519 no Ed25519 collisions\x00"
   177  )
   178  
   179  func Sign(priv *PrivateKey, message []byte) []byte {
   180  	// Outline the function body so that the returned signature can be
   181  	// stack-allocated.
   182  	signature := make([]byte, signatureSize)
   183  	return sign(signature, priv, message)
   184  }
   185  
   186  func sign(signature []byte, priv *PrivateKey, message []byte) []byte {
   187  	fipsSelfTest()
   188  	fips140.RecordApproved()
   189  	return signWithDom(signature, priv, message, domPrefixPure, "")
   190  }
   191  
   192  func SignPH(priv *PrivateKey, message []byte, context string) ([]byte, error) {
   193  	// Outline the function body so that the returned signature can be
   194  	// stack-allocated.
   195  	signature := make([]byte, signatureSize)
   196  	return signPH(signature, priv, message, context)
   197  }
   198  
   199  func signPH(signature []byte, priv *PrivateKey, message []byte, context string) ([]byte, error) {
   200  	fipsSelfTest()
   201  	fips140.RecordApproved()
   202  	if l := len(message); l != sha512Size {
   203  		return nil, errors.New("ed25519: bad Ed25519ph message hash length: " + strconv.Itoa(l))
   204  	}
   205  	if l := len(context); l > 255 {
   206  		return nil, errors.New("ed25519: bad Ed25519ph context length: " + strconv.Itoa(l))
   207  	}
   208  	return signWithDom(signature, priv, message, domPrefixPh, context), nil
   209  }
   210  
   211  func SignCtx(priv *PrivateKey, message []byte, context string) ([]byte, error) {
   212  	// Outline the function body so that the returned signature can be
   213  	// stack-allocated.
   214  	signature := make([]byte, signatureSize)
   215  	return signCtx(signature, priv, message, context)
   216  }
   217  
   218  func signCtx(signature []byte, priv *PrivateKey, message []byte, context string) ([]byte, error) {
   219  	fipsSelfTest()
   220  	// FIPS 186-5 specifies Ed25519 and Ed25519ph (with context), but not Ed25519ctx.
   221  	fips140.RecordNonApproved()
   222  	// Note that per RFC 8032, Section 5.1, the context SHOULD NOT be empty.
   223  	if l := len(context); l > 255 {
   224  		return nil, errors.New("ed25519: bad Ed25519ctx context length: " + strconv.Itoa(l))
   225  	}
   226  	return signWithDom(signature, priv, message, domPrefixCtx, context), nil
   227  }
   228  
   229  func signWithDom(signature []byte, priv *PrivateKey, message []byte, domPrefix, context string) []byte {
   230  	mh := sha512.New()
   231  	if domPrefix != domPrefixPure {
   232  		mh.Write([]byte(domPrefix))
   233  		mh.Write([]byte{byte(len(context))})
   234  		mh.Write([]byte(context))
   235  	}
   236  	mh.Write(priv.prefix[:])
   237  	mh.Write(message)
   238  	messageDigest := make([]byte, 0, sha512Size)
   239  	messageDigest = mh.Sum(messageDigest)
   240  	r, err := edwards25519.NewScalar().SetUniformBytes(messageDigest)
   241  	if err != nil {
   242  		panic("ed25519: internal error: setting scalar failed")
   243  	}
   244  
   245  	R := (&edwards25519.Point{}).ScalarBaseMult(r)
   246  
   247  	kh := sha512.New()
   248  	if domPrefix != domPrefixPure {
   249  		kh.Write([]byte(domPrefix))
   250  		kh.Write([]byte{byte(len(context))})
   251  		kh.Write([]byte(context))
   252  	}
   253  	kh.Write(R.Bytes())
   254  	kh.Write(priv.pub[:])
   255  	kh.Write(message)
   256  	hramDigest := make([]byte, 0, sha512Size)
   257  	hramDigest = kh.Sum(hramDigest)
   258  	k, err := edwards25519.NewScalar().SetUniformBytes(hramDigest)
   259  	if err != nil {
   260  		panic("ed25519: internal error: setting scalar failed")
   261  	}
   262  
   263  	S := edwards25519.NewScalar().MultiplyAdd(k, &priv.s, r)
   264  
   265  	copy(signature[:32], R.Bytes())
   266  	copy(signature[32:], S.Bytes())
   267  
   268  	return signature
   269  }
   270  
   271  func Verify(pub *PublicKey, message, sig []byte) error {
   272  	return verify(pub, message, sig)
   273  }
   274  
   275  func verify(pub *PublicKey, message, sig []byte) error {
   276  	fipsSelfTest()
   277  	fips140.RecordApproved()
   278  	return verifyWithDom(pub, message, sig, domPrefixPure, "")
   279  }
   280  
   281  func VerifyPH(pub *PublicKey, message []byte, sig []byte, context string) error {
   282  	fipsSelfTest()
   283  	fips140.RecordApproved()
   284  	if l := len(message); l != sha512Size {
   285  		return errors.New("ed25519: bad Ed25519ph message hash length: " + strconv.Itoa(l))
   286  	}
   287  	if l := len(context); l > 255 {
   288  		return errors.New("ed25519: bad Ed25519ph context length: " + strconv.Itoa(l))
   289  	}
   290  	return verifyWithDom(pub, message, sig, domPrefixPh, context)
   291  }
   292  
   293  func VerifyCtx(pub *PublicKey, message []byte, sig []byte, context string) error {
   294  	fipsSelfTest()
   295  	// FIPS 186-5 specifies Ed25519 and Ed25519ph (with context), but not Ed25519ctx.
   296  	fips140.RecordNonApproved()
   297  	if l := len(context); l > 255 {
   298  		return errors.New("ed25519: bad Ed25519ctx context length: " + strconv.Itoa(l))
   299  	}
   300  	return verifyWithDom(pub, message, sig, domPrefixCtx, context)
   301  }
   302  
   303  func verifyWithDom(pub *PublicKey, message, sig []byte, domPrefix, context string) error {
   304  	if l := len(sig); l != signatureSize {
   305  		return errors.New("ed25519: bad signature length: " + strconv.Itoa(l))
   306  	}
   307  
   308  	if sig[63]&224 != 0 {
   309  		return errors.New("ed25519: invalid signature")
   310  	}
   311  
   312  	kh := sha512.New()
   313  	if domPrefix != domPrefixPure {
   314  		kh.Write([]byte(domPrefix))
   315  		kh.Write([]byte{byte(len(context))})
   316  		kh.Write([]byte(context))
   317  	}
   318  	kh.Write(sig[:32])
   319  	kh.Write(pub.aBytes[:])
   320  	kh.Write(message)
   321  	hramDigest := make([]byte, 0, sha512Size)
   322  	hramDigest = kh.Sum(hramDigest)
   323  	k, err := edwards25519.NewScalar().SetUniformBytes(hramDigest)
   324  	if err != nil {
   325  		panic("ed25519: internal error: setting scalar failed")
   326  	}
   327  
   328  	S, err := edwards25519.NewScalar().SetCanonicalBytes(sig[32:])
   329  	if err != nil {
   330  		return errors.New("ed25519: invalid signature")
   331  	}
   332  
   333  	// [S]B = R + [k]A --> [k](-A) + [S]B = R
   334  	minusA := (&edwards25519.Point{}).Negate(&pub.a)
   335  	R := (&edwards25519.Point{}).VarTimeDoubleScalarBaseMult(k, minusA, S)
   336  
   337  	if !bytes.Equal(sig[:32], R.Bytes()) {
   338  		return errors.New("ed25519: invalid signature")
   339  	}
   340  	return nil
   341  }
   342
View as plain text