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