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
 24package ed448
 25
 26import (
 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
 41const (
 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
 54const (
 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.
 61type 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.
 74type SchemeID uint
 75
 76const (
 77	ED448 SchemeID = iota
 78	ED448Ph
 79)
 80
 81// PublicKey is the type of Ed448 public keys.
 82type PublicKey []byte
 83
 84// Equal reports whether pub and x have the same value.
 85func (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.
 91type PrivateKey []byte
 92
 93// Equal reports whether priv and x have the same value.
 94func (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.
100func (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.
109func (priv PrivateKey) Seed() []byte {
110	seed := make([]byte, SeedSize)
111	copy(seed, priv[:SeedSize])
112	return seed
113}
114
115func (priv PrivateKey) Scheme() sign.Scheme { return sch }
116
117func (pub PublicKey) Scheme() sign.Scheme { return sch }
118
119func (priv PrivateKey) MarshalBinary() (data []byte, err error) {
120	privateKey := make(PrivateKey, PrivateKeySize)
121	copy(privateKey, priv)
122	return privateKey, nil
123}
124
125func (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.
139func (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.
164func 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.
185func NewKeyFromSeed(seed []byte) PrivateKey {
186	privateKey := make([]byte, PrivateKeySize)
187	newKeyFromSeed(privateKey, seed)
188	return privateKey
189}
190
191func 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
207func signAll(signature []byte, privateKey PrivateKey, message, ctx []byte, preHash bool) {
208	if len(ctx) > ContextMaxSize {
209		panic(fmt.Errorf("ed448: bad context length: %v", 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.
277func 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.
288func 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
294func 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.
348func 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.
370func 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.
380func VerifyPh(public PublicKey, message, signature []byte, ctx string) bool {
381	return verify(public, message, signature, []byte(ctx), true)
382}
383
384func 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.
392func 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
401func 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}