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: %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.
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