ed448.go

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

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