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