ed25519.go

Documentation: github.com/cloudflare/circl/sign/ed25519

     1  // Package ed25519 implements Ed25519 signature scheme as described in RFC-8032.
     2  //
     3  // This package provides optimized implementations of the three signature
     4  // variants and maintaining closer compatibility with crypto/ed25519.
     5  //
     6  //	| Scheme Name | Sign Function     | Verification  | Context           |
     7  //	|-------------|-------------------|---------------|-------------------|
     8  //	| Ed25519     | Sign              | Verify        | None              |
     9  //	| Ed25519Ph   | SignPh            | VerifyPh      | Yes, can be empty |
    10  //	| Ed25519Ctx  | SignWithCtx       | VerifyWithCtx | Yes, non-empty    |
    11  //	| All above   | (PrivateKey).Sign | VerifyAny     | As above          |
    12  //
    13  // Specific functions for sign and verify are defined. A generic signing
    14  // function for all schemes is available through the crypto.Signer interface,
    15  // which is implemented by the PrivateKey type. A correspond all-in-one
    16  // verification method is provided by the VerifyAny function.
    17  //
    18  // Signing with Ed25519Ph or Ed25519Ctx requires a context string for domain
    19  // separation. This parameter is passed using a SignerOptions struct defined
    20  // in this package. While Ed25519Ph accepts an empty context, Ed25519Ctx
    21  // enforces non-empty context strings.
    22  //
    23  // # Compatibility with crypto.ed25519
    24  //
    25  // These functions are compatible with the “Ed25519” function defined in
    26  // RFC-8032. However, unlike RFC 8032's formulation, this package's private
    27  // key representation includes a public key suffix to make multiple signing
    28  // operations with the same key more efficient. This package refers to the
    29  // RFC-8032 private key as the “seed”.
    30  //
    31  // References
    32  //
    33  //   - RFC-8032: https://rfc-editor.org/rfc/rfc8032.txt
    34  //   - Ed25519: https://ed25519.cr.yp.to/
    35  //   - EdDSA: High-speed high-security signatures. https://doi.org/10.1007/s13389-012-0027-1
    36  package ed25519
    37  
    38  import (
    39  	"bytes"
    40  	"crypto"
    41  	cryptoRand "crypto/rand"
    42  	"crypto/sha512"
    43  	"crypto/subtle"
    44  	"errors"
    45  	"fmt"
    46  	"io"
    47  	"strconv"
    48  
    49  	"github.com/cloudflare/circl/sign"
    50  )
    51  
    52  const (
    53  	// ContextMaxSize is the maximum length (in bytes) allowed for context.
    54  	ContextMaxSize = 255
    55  	// PublicKeySize is the size, in bytes, of public keys as used in this package.
    56  	PublicKeySize = 32
    57  	// PrivateKeySize is the size, in bytes, of private keys as used in this package.
    58  	PrivateKeySize = 64
    59  	// SignatureSize is the size, in bytes, of signatures generated and verified by this package.
    60  	SignatureSize = 64
    61  	// SeedSize is the size, in bytes, of private key seeds. These are the private key representations used by RFC 8032.
    62  	SeedSize = 32
    63  )
    64  
    65  const (
    66  	paramB = 256 / 8 // Size of keys in bytes.
    67  )
    68  
    69  // SignerOptions implements crypto.SignerOpts and augments with parameters
    70  // that are specific to the Ed25519 signature schemes.
    71  type SignerOptions struct {
    72  	// Hash must be crypto.Hash(0) for Ed25519/Ed25519ctx, or crypto.SHA512
    73  	// for Ed25519ph.
    74  	crypto.Hash
    75  
    76  	// Context is an optional domain separation string for Ed25519ph and a
    77  	// must for Ed25519ctx. Its length must be less or equal than 255 bytes.
    78  	Context string
    79  
    80  	// Scheme is an identifier for choosing a signature scheme. The zero value
    81  	// is ED25519.
    82  	Scheme SchemeID
    83  }
    84  
    85  // SchemeID is an identifier for each signature scheme.
    86  type SchemeID uint
    87  
    88  const (
    89  	ED25519 SchemeID = iota
    90  	ED25519Ph
    91  	ED25519Ctx
    92  )
    93  
    94  // PrivateKey is the type of Ed25519 private keys. It implements crypto.Signer.
    95  type PrivateKey []byte
    96  
    97  // Equal reports whether priv and x have the same value.
    98  func (priv PrivateKey) Equal(x crypto.PrivateKey) bool {
    99  	xx, ok := x.(PrivateKey)
   100  	return ok && subtle.ConstantTimeCompare(priv, xx) == 1
   101  }
   102  
   103  // Public returns the PublicKey corresponding to priv.
   104  func (priv PrivateKey) Public() crypto.PublicKey {
   105  	publicKey := make(PublicKey, PublicKeySize)
   106  	copy(publicKey, priv[SeedSize:])
   107  	return publicKey
   108  }
   109  
   110  // Seed returns the private key seed corresponding to priv. It is provided for
   111  // interoperability with RFC 8032. RFC 8032's private keys correspond to seeds
   112  // in this package.
   113  func (priv PrivateKey) Seed() []byte {
   114  	seed := make([]byte, SeedSize)
   115  	copy(seed, priv[:SeedSize])
   116  	return seed
   117  }
   118  
   119  func (priv PrivateKey) Scheme() sign.Scheme { return sch }
   120  
   121  func (pub PublicKey) Scheme() sign.Scheme { return sch }
   122  
   123  func (priv PrivateKey) MarshalBinary() (data []byte, err error) {
   124  	privateKey := make(PrivateKey, PrivateKeySize)
   125  	copy(privateKey, priv)
   126  	return privateKey, nil
   127  }
   128  
   129  func (pub PublicKey) MarshalBinary() (data []byte, err error) {
   130  	publicKey := make(PublicKey, PublicKeySize)
   131  	copy(publicKey, pub)
   132  	return publicKey, nil
   133  }
   134  
   135  // Equal reports whether pub and x have the same value.
   136  func (pub PublicKey) Equal(x crypto.PublicKey) bool {
   137  	xx, ok := x.(PublicKey)
   138  	return ok && bytes.Equal(pub, xx)
   139  }
   140  
   141  // Sign creates a signature of a message with priv key.
   142  // This function is compatible with crypto.ed25519 and also supports the
   143  // three signature variants defined in RFC-8032, namely Ed25519 (or pure
   144  // EdDSA), Ed25519Ph, and Ed25519Ctx.
   145  // The opts.HashFunc() must return zero to specify either Ed25519 or Ed25519Ctx
   146  // variant. This can be achieved by passing crypto.Hash(0) as the value for
   147  // opts.
   148  // The opts.HashFunc() must return SHA512 to specify the Ed25519Ph variant.
   149  // This can be achieved by passing crypto.SHA512 as the value for opts.
   150  // Use a SignerOptions struct (defined in this package) to pass a context
   151  // string for signing.
   152  func (priv PrivateKey) Sign(
   153  	rand io.Reader,
   154  	message []byte,
   155  	opts crypto.SignerOpts,
   156  ) (signature []byte, err error) {
   157  	var ctx string
   158  	var scheme SchemeID
   159  	if o, ok := opts.(SignerOptions); ok {
   160  		ctx = o.Context
   161  		scheme = o.Scheme
   162  	}
   163  
   164  	switch true {
   165  	case scheme == ED25519 && opts.HashFunc() == crypto.Hash(0):
   166  		return Sign(priv, message), nil
   167  	case scheme == ED25519Ph && opts.HashFunc() == crypto.SHA512:
   168  		return SignPh(priv, message, ctx), nil
   169  	case scheme == ED25519Ctx && opts.HashFunc() == crypto.Hash(0) && len(ctx) > 0:
   170  		return SignWithCtx(priv, message, ctx), nil
   171  	default:
   172  		return nil, errors.New("ed25519: bad hash algorithm")
   173  	}
   174  }
   175  
   176  // GenerateKey generates a public/private key pair using entropy from rand.
   177  // If rand is nil, crypto/rand.Reader will be used.
   178  func GenerateKey(rand io.Reader) (PublicKey, PrivateKey, error) {
   179  	if rand == nil {
   180  		rand = cryptoRand.Reader
   181  	}
   182  
   183  	seed := make([]byte, SeedSize)
   184  	if _, err := io.ReadFull(rand, seed); err != nil {
   185  		return nil, nil, err
   186  	}
   187  
   188  	privateKey := NewKeyFromSeed(seed)
   189  	publicKey := make(PublicKey, PublicKeySize)
   190  	copy(publicKey, privateKey[SeedSize:])
   191  
   192  	return publicKey, privateKey, nil
   193  }
   194  
   195  // NewKeyFromSeed calculates a private key from a seed. It will panic if
   196  // len(seed) is not SeedSize. This function is provided for interoperability
   197  // with RFC 8032. RFC 8032's private keys correspond to seeds in this
   198  // package.
   199  func NewKeyFromSeed(seed []byte) PrivateKey {
   200  	privateKey := make(PrivateKey, PrivateKeySize)
   201  	newKeyFromSeed(privateKey, seed)
   202  	return privateKey
   203  }
   204  
   205  func newKeyFromSeed(privateKey, seed []byte) {
   206  	if l := len(seed); l != SeedSize {
   207  		panic("ed25519: bad seed length: " + strconv.Itoa(l))
   208  	}
   209  	var P pointR1
   210  	k := sha512.Sum512(seed)
   211  	clamp(k[:])
   212  	reduceModOrder(k[:paramB], false)
   213  	P.fixedMult(k[:paramB])
   214  	copy(privateKey[:SeedSize], seed)
   215  	_ = P.ToBytes(privateKey[SeedSize:])
   216  }
   217  
   218  func signAll(signature []byte, privateKey PrivateKey, message, ctx []byte, preHash bool) {
   219  	if l := len(privateKey); l != PrivateKeySize {
   220  		panic("ed25519: bad private key length: " + strconv.Itoa(l))
   221  	}
   222  
   223  	H := sha512.New()
   224  	var PHM []byte
   225  
   226  	if preHash {
   227  		_, _ = H.Write(message)
   228  		PHM = H.Sum(nil)
   229  		H.Reset()
   230  	} else {
   231  		PHM = message
   232  	}
   233  
   234  	// 1.  Hash the 32-byte private key using SHA-512.
   235  	_, _ = H.Write(privateKey[:SeedSize])
   236  	h := H.Sum(nil)
   237  	clamp(h[:])
   238  	prefix, s := h[paramB:], h[:paramB]
   239  
   240  	// 2.  Compute SHA-512(dom2(F, C) || prefix || PH(M))
   241  	H.Reset()
   242  
   243  	writeDom(H, ctx, preHash)
   244  
   245  	_, _ = H.Write(prefix)
   246  	_, _ = H.Write(PHM)
   247  	r := H.Sum(nil)
   248  	reduceModOrder(r[:], true)
   249  
   250  	// 3.  Compute the point [r]B.
   251  	var P pointR1
   252  	P.fixedMult(r[:paramB])
   253  	R := (&[paramB]byte{})[:]
   254  	if err := P.ToBytes(R); err != nil {
   255  		panic(err)
   256  	}
   257  
   258  	// 4.  Compute SHA512(dom2(F, C) || R || A || PH(M)).
   259  	H.Reset()
   260  
   261  	writeDom(H, ctx, preHash)
   262  
   263  	_, _ = H.Write(R)
   264  	_, _ = H.Write(privateKey[SeedSize:])
   265  	_, _ = H.Write(PHM)
   266  	hRAM := H.Sum(nil)
   267  
   268  	reduceModOrder(hRAM[:], true)
   269  
   270  	// 5.  Compute S = (r + k * s) mod order.
   271  	S := (&[paramB]byte{})[:]
   272  	calculateS(S, r[:paramB], hRAM[:paramB], s)
   273  
   274  	// 6.  The signature is the concatenation of R and S.
   275  	copy(signature[:paramB], R[:])
   276  	copy(signature[paramB:], S[:])
   277  }
   278  
   279  // Sign signs the message with privateKey and returns a signature.
   280  // This function supports the signature variant defined in RFC-8032: Ed25519,
   281  // also known as the pure version of EdDSA.
   282  // It will panic if len(privateKey) is not PrivateKeySize.
   283  func Sign(privateKey PrivateKey, message []byte) []byte {
   284  	signature := make([]byte, SignatureSize)
   285  	signAll(signature, privateKey, message, []byte(""), false)
   286  	return signature
   287  }
   288  
   289  // SignPh creates a signature of a message with private key and context.
   290  // This function supports the signature variant defined in RFC-8032: Ed25519ph,
   291  // meaning it internally hashes the message using SHA-512, and optionally
   292  // accepts a context string.
   293  // It will panic if len(privateKey) is not PrivateKeySize.
   294  // Context could be passed to this function, which length should be no more than
   295  // ContextMaxSize=255. It can be empty.
   296  func SignPh(privateKey PrivateKey, message []byte, ctx string) []byte {
   297  	if len(ctx) > ContextMaxSize {
   298  		panic(fmt.Errorf("ed25519: bad context length: %v", len(ctx)))
   299  	}
   300  
   301  	signature := make([]byte, SignatureSize)
   302  	signAll(signature, privateKey, message, []byte(ctx), true)
   303  	return signature
   304  }
   305  
   306  // SignWithCtx creates a signature of a message with private key and context.
   307  // This function supports the signature variant defined in RFC-8032: Ed25519ctx,
   308  // meaning it accepts a non-empty context string.
   309  // It will panic if len(privateKey) is not PrivateKeySize.
   310  // Context must be passed to this function, which length should be no more than
   311  // ContextMaxSize=255 and cannot be empty.
   312  func SignWithCtx(privateKey PrivateKey, message []byte, ctx string) []byte {
   313  	if len(ctx) == 0 || len(ctx) > ContextMaxSize {
   314  		panic(fmt.Errorf("ed25519: bad context length: %v > %v", len(ctx), ContextMaxSize))
   315  	}
   316  
   317  	signature := make([]byte, SignatureSize)
   318  	signAll(signature, privateKey, message, []byte(ctx), false)
   319  	return signature
   320  }
   321  
   322  func verify(public PublicKey, message, signature, ctx []byte, preHash bool) bool {
   323  	if len(public) != PublicKeySize ||
   324  		len(signature) != SignatureSize ||
   325  		!isLessThanOrder(signature[paramB:]) {
   326  		return false
   327  	}
   328  
   329  	var P pointR1
   330  	if ok := P.FromBytes(public); !ok {
   331  		return false
   332  	}
   333  
   334  	H := sha512.New()
   335  	var PHM []byte
   336  
   337  	if preHash {
   338  		_, _ = H.Write(message)
   339  		PHM = H.Sum(nil)
   340  		H.Reset()
   341  	} else {
   342  		PHM = message
   343  	}
   344  
   345  	R := signature[:paramB]
   346  
   347  	writeDom(H, ctx, preHash)
   348  
   349  	_, _ = H.Write(R)
   350  	_, _ = H.Write(public)
   351  	_, _ = H.Write(PHM)
   352  	hRAM := H.Sum(nil)
   353  	reduceModOrder(hRAM[:], true)
   354  
   355  	var Q pointR1
   356  	encR := (&[paramB]byte{})[:]
   357  	P.neg()
   358  	Q.doubleMult(&P, signature[paramB:], hRAM[:paramB])
   359  	_ = Q.ToBytes(encR)
   360  	return bytes.Equal(R, encR)
   361  }
   362  
   363  // VerifyAny returns true if the signature is valid. Failure cases are invalid
   364  // signature, or when the public key cannot be decoded.
   365  // This function supports all the three signature variants defined in RFC-8032,
   366  // namely Ed25519 (or pure EdDSA), Ed25519Ph, and Ed25519Ctx.
   367  // The opts.HashFunc() must return zero to specify either Ed25519 or Ed25519Ctx
   368  // variant. This can be achieved by passing crypto.Hash(0) as the value for opts.
   369  // The opts.HashFunc() must return SHA512 to specify the Ed25519Ph variant.
   370  // This can be achieved by passing crypto.SHA512 as the value for opts.
   371  // Use a SignerOptions struct to pass a context string for signing.
   372  func VerifyAny(public PublicKey, message, signature []byte, opts crypto.SignerOpts) bool {
   373  	var ctx string
   374  	var scheme SchemeID
   375  	if o, ok := opts.(SignerOptions); ok {
   376  		ctx = o.Context
   377  		scheme = o.Scheme
   378  	}
   379  
   380  	switch true {
   381  	case scheme == ED25519 && opts.HashFunc() == crypto.Hash(0):
   382  		return Verify(public, message, signature)
   383  	case scheme == ED25519Ph && opts.HashFunc() == crypto.SHA512:
   384  		return VerifyPh(public, message, signature, ctx)
   385  	case scheme == ED25519Ctx && opts.HashFunc() == crypto.Hash(0) && len(ctx) > 0:
   386  		return VerifyWithCtx(public, message, signature, ctx)
   387  	default:
   388  		return false
   389  	}
   390  }
   391  
   392  // Verify returns true if the signature is valid. Failure cases are invalid
   393  // signature, or when the public key cannot be decoded.
   394  // This function supports the signature variant defined in RFC-8032: Ed25519,
   395  // also known as the pure version of EdDSA.
   396  func Verify(public PublicKey, message, signature []byte) bool {
   397  	return verify(public, message, signature, []byte(""), false)
   398  }
   399  
   400  // VerifyPh returns true if the signature is valid. Failure cases are invalid
   401  // signature, or when the public key cannot be decoded.
   402  // This function supports the signature variant defined in RFC-8032: Ed25519ph,
   403  // meaning it internally hashes the message using SHA-512.
   404  // Context could be passed to this function, which length should be no more than
   405  // 255. It can be empty.
   406  func VerifyPh(public PublicKey, message, signature []byte, ctx string) bool {
   407  	return verify(public, message, signature, []byte(ctx), true)
   408  }
   409  
   410  // VerifyWithCtx returns true if the signature is valid. Failure cases are invalid
   411  // signature, or when the public key cannot be decoded, or when context is
   412  // not provided.
   413  // This function supports the signature variant defined in RFC-8032: Ed25519ctx,
   414  // meaning it does not handle prehashed messages. Non-empty context string must be
   415  // provided, and must not be more than 255 of length.
   416  func VerifyWithCtx(public PublicKey, message, signature []byte, ctx string) bool {
   417  	if len(ctx) == 0 || len(ctx) > ContextMaxSize {
   418  		return false
   419  	}
   420  
   421  	return verify(public, message, signature, []byte(ctx), false)
   422  }
   423  
   424  func clamp(k []byte) {
   425  	k[0] &= 248
   426  	k[paramB-1] = (k[paramB-1] & 127) | 64
   427  }
   428  
   429  // isLessThanOrder returns true if 0 <= x < order.
   430  func isLessThanOrder(x []byte) bool {
   431  	i := len(order) - 1
   432  	for i > 0 && x[i] == order[i] {
   433  		i--
   434  	}
   435  	return x[i] < order[i]
   436  }
   437  
   438  func writeDom(h io.Writer, ctx []byte, preHash bool) {
   439  	dom2 := "SigEd25519 no Ed25519 collisions"
   440  
   441  	if len(ctx) > 0 {
   442  		_, _ = h.Write([]byte(dom2))
   443  		if preHash {
   444  			_, _ = h.Write([]byte{byte(0x01), byte(len(ctx))})
   445  		} else {
   446  			_, _ = h.Write([]byte{byte(0x00), byte(len(ctx))})
   447  		}
   448  		_, _ = h.Write(ctx)
   449  	} else if preHash {
   450  		_, _ = h.Write([]byte(dom2))
   451  		_, _ = h.Write([]byte{0x01, 0x00})
   452  	}
   453  }
   454
View as plain text