1 // Copyright (c) 2013-2022 The btcsuite developers
2 3 package schnorr
4 5 import (
6 "fmt"
7 8 "crypto/ec"
9 "crypto/ec/chainhash"
10 "crypto/ec/secp256k1"
11 )
12 13 const (
14 // SignatureSize is the size of an encoded Schnorr signature.
15 SignatureSize = 64
16 // scalarSize is the size of an encoded big endian scalar.
17 scalarSize = 32
18 )
19 20 func _rfc6979ExtraDataV0() [32]uint8 {
21 return [32]uint8{
22 0xa3, 0xeb, 0x4c, 0x18, 0x2f, 0xae, 0x7e, 0xf4,
23 0xe8, 0x10, 0xc6, 0xee, 0x13, 0xb0, 0xe9, 0x26,
24 0x68, 0x6d, 0x71, 0xe8, 0x7f, 0x39, 0x4f, 0x79,
25 0x9c, 0x00, 0xa5, 0x21, 0x03, 0xcb, 0x4e, 0x17,
26 }
27 }
28 29 // Signature is a type representing a Schnorr signature.
30 type Signature struct {
31 r btcec.FieldVal
32 s btcec.ModNScalar
33 }
34 35 // NewSignature instantiates a new signature given some r and s values.
36 func NewSignature(r *btcec.FieldVal, s *btcec.ModNScalar) *Signature {
37 var sig Signature
38 sig.r.Set(r).Normalize()
39 sig.s.Set(s)
40 return &sig
41 }
42 43 // Serialize returns the Schnorr signature in a stricter format.
44 //
45 // The signatures are encoded as
46 //
47 // sig[0:32]
48 // x coordinate of the point R, encoded as a big-endian uint256
49 // sig[32:64]
50 // s, encoded also as big-endian uint256
51 func (sig Signature) Serialize() []byte {
52 // Total length of returned signature is the length of r and s.
53 var b [SignatureSize]byte
54 sig.r.PutBytesUnchecked(b[0:32])
55 sig.s.PutBytesUnchecked(b[32:64])
56 return b[:]
57 }
58 59 // ParseSignature parses a signature according to the BIP-340 specification and
60 // enforces the following additional restrictions specific to secp256k1:
61 //
62 // - The r component must be in the valid range for secp256k1 field elements
63 //
64 // - The s component must be in the valid range for secp256k1 scalars
65 func ParseSignature(sig []byte) (*Signature, error) {
66 // The signature must be the correct length.
67 sigLen := len(sig)
68 if sigLen < SignatureSize {
69 str := fmt.Sprintf(
70 "malformed signature: too short: %d < %d", sigLen,
71 SignatureSize,
72 )
73 return nil, signatureError(ErrSigTooShort, str)
74 }
75 if sigLen > SignatureSize {
76 str := fmt.Sprintf(
77 "malformed signature: too long: %d > %d", sigLen,
78 SignatureSize,
79 )
80 return nil, signatureError(ErrSigTooLong, str)
81 }
82 // The signature is validly encoded at this point, however, enforce
83 // additional restrictions to ensure r is in the range [0, p-1], and s is in
84 // the range [0, n-1] since valid Schnorr signatures are required to be in
85 // that range per spec.
86 var r btcec.FieldVal
87 if overflow := r.SetByteSlice(sig[0:32]); overflow {
88 str := "invalid signature: r >= field prime"
89 return nil, signatureError(ErrSigRTooBig, str)
90 }
91 var s btcec.ModNScalar
92 s.SetByteSlice(sig[32:64])
93 // Return the signature.
94 return NewSignature(&r, &s), nil
95 }
96 97 // IsEqual compares this Signature instance to the one passed, returning true if
98 // both Signatures are equivalent. A signature is equivalent to another if they
99 // both have the same scalar value for R and S.
100 func (sig Signature) IsEqual(otherSig *Signature) bool {
101 return sig.r.Equals(&otherSig.r) && sig.s.Equals(&otherSig.s)
102 }
103 104 // schnorrVerify attempt to verify the signature for the provided hash and
105 // secp256k1 public key and either returns nil if successful or a specific error
106 // indicating why it failed if not successful.
107 //
108 // This differs from the exported Verify method in that it returns a specific
109 // error to support better testing, while the exported method simply returns a
110 // bool indicating success or failure.
111 func schnorrVerify(sig *Signature, hash []byte, pubKeyBytes []byte) error {
112 // The algorithm for producing a BIP-340 signature is described in
113 // README.md and is reproduced here for reference:
114 //
115 // 1. Fail if m is not 32 bytes
116 // 2. P = lift_x(int(pk)).
117 // 3. r = int(sig[0:32]); fail is r >= p.
118 // 4. s = int(sig[32:64]); fail if s >= n.
119 // 5. e = int(tagged_hash("BIP0340/challenge", bytes(r) || bytes(P) || M)) mod n.
120 // 6. R = s*G - e*P
121 // 7. Fail if is_infinite(R)
122 // 8. Fail if not hash_even_y(R)
123 // 9. Fail is x(R) != r.
124 // 10. Return success iff not failure occured before reachign this
125 // point.
126 127 // // Step 1.
128 // //
129 // // Fail if m is not 32 bytes
130 // if len(hash) != scalarSize {
131 // str := fmt.Sprintf("wrong size for message (got %v, want %v)",
132 // len(hash), scalarSize)
133 // return signatureError(schnorr.ErrInvalidHashLen, str)
134 // }
135 136 // Step 2.
137 //
138 // P = lift_x(int(pk))
139 //
140 // Fail if P is not a point on the curve
141 pubKey, err := ParsePubKey(pubKeyBytes)
142 if err != nil {
143 return err
144 }
145 if !pubKey.IsOnCurve() {
146 str := "pubkey point is not on curve"
147 return signatureError(ErrPubKeyNotOnCurve, str)
148 }
149 // Step 3.
150 //
151 // Fail if r >= p
152 //
153 // Note this is already handled by the fact r is a field element.
154 //
155 // Step 4.
156 //
157 // Fail if s >= n
158 //
159 // Note this is already handled by the fact s is a mod n scalar.
160 //
161 // Step 5.
162 //
163 // e = int(tagged_hash("BIP0340/challenge", bytes(r) || bytes(P) || M)) mod n.
164 var rBytes [32]byte
165 sig.r.PutBytesUnchecked(rBytes[:])
166 pBytes := SerializePubKey(pubKey)
167 commitment := chainhash.TaggedHash(
168 chainhash.TagBIP0340Challenge, rBytes[:], pBytes, hash,
169 )
170 var e btcec.ModNScalar
171 e.SetBytes((*[32]byte)(commitment))
172 // Negate e here so we can use AddNonConst below to subtract the s*G
173 // point from e*P.
174 e.Negate()
175 // Step 6.
176 //
177 // R = s*G - e*P
178 var P, R, sG, eP btcec.JacobianPoint
179 pubKey.AsJacobian(&P)
180 btcec.ScalarBaseMultNonConst(&sig.s, &sG)
181 btcec.ScalarMultNonConst(&e, &P, &eP)
182 btcec.AddNonConst(&sG, &eP, &R)
183 // Step 7.
184 //
185 // Fail if R is the point at infinity
186 if (R.X.IsZero() && R.Y.IsZero()) || R.Z.IsZero() {
187 str := "calculated R point is the point at infinity"
188 return signatureError(ErrSigRNotOnCurve, str)
189 }
190 // Step 8.
191 //
192 // Fail if R.y is odd
193 //
194 // Note that R must be in affine coordinates for this check.
195 R.ToAffine()
196 if R.Y.IsOdd() {
197 str := "calculated R y-value is odd"
198 return signatureError(ErrSigRYIsOdd, str)
199 }
200 // Step 9.
201 //
202 // Verified if R.x == r
203 //
204 // Note that R must be in affine coordinates for this check.
205 if !sig.r.Equals(&R.X) {
206 str := "calculated R point was not given R"
207 return signatureError(ErrUnequalRValues, str)
208 }
209 // Step 10.
210 //
211 // Return success iff not failure occured before reachign this
212 return nil
213 }
214 215 // Verify returns whether or not the signature is valid for the provided hash
216 // and secp256k1 public key.
217 func (sig *Signature) Verify(hash []byte, pubKey *btcec.PublicKey) bool {
218 pubkeyBytes := SerializePubKey(pubKey)
219 return schnorrVerify(sig, hash, pubkeyBytes) == nil
220 }
221 222 // zeroArray zeroes the memory of a scalar array.
223 func zeroArray(a *[scalarSize]byte) {
224 for i := 0; i < scalarSize; i++ {
225 a[i] = 0x00
226 }
227 }
228 229 // schnorrSign generates an BIP-340 signature over the secp256k1 curve for the
230 // provided hash (which should be the result of hashing a larger message) using
231 // the given nonce and secret key. The produced signature is deterministic (the
232 // same message, nonce, and key yield the same signature) and canonical.
233 //
234 // WARNING: The hash MUST be 32 bytes, and both the nonce and secret keys must
235 // NOT be 0. Since this is an internal use function, these preconditions MUST be
236 // satisified by the caller.
237 func schnorrSign(
238 privKey, nonce *btcec.ModNScalar, pubKey *btcec.PublicKey,
239 hash []byte, opts *signOptions,
240 ) (*Signature, error) {
241 242 // The algorithm for producing a BIP-340 signature is described in
243 // README.md and is reproduced here for reference:
244 //
245 // G = curve generator
246 // n = curve order
247 // d = secret key
248 // m = message
249 // a = input randmoness
250 // r, s = signature
251 //
252 // 1. d' = int(d)
253 // 2. Fail if m is not 32 bytes
254 // 3. Fail if d = 0 or d >= n
255 // 4. P = d'*G
256 // 5. Negate d if P.y is odd
257 // 6. t = bytes(d) xor tagged_hash("BIP0340/aux", t || bytes(P) || m)
258 // 7. rand = tagged_hash("BIP0340/nonce", a)
259 // 8. k' = int(rand) mod n
260 // 9. Fail if k' = 0
261 // 10. R = 'k*G
262 // 11. Negate k if R.y id odd
263 // 12. e = tagged_hash("BIP0340/challenge", bytes(R) || bytes(P) || m) mod n
264 // 13. sig = bytes(R) || bytes((k + e*d)) mod n
265 // 14. If Verify(bytes(P), m, sig) fails, abort.
266 // 15. return sig.
267 //
268 // Note that the set of functional options passed in may modify the
269 // above algorithm. Namely if CustomNonce is used, then steps 6-8 are
270 // replaced with a process that generates the nonce using rfc6979. If
271 // FastSign is passed, then we skip set 14.
272 273 // NOTE: Steps 1-9 are performed by the caller.
274 275 //
276 // Step 10.
277 //
278 // R = kG
279 var R btcec.JacobianPoint
280 k := *nonce
281 btcec.ScalarBaseMultNonConst(&k, &R)
282 // Step 11.
283 //
284 // Negate nonce k if R.y is odd (R.y is the y coordinate of the point R)
285 //
286 // Note that R must be in affine coordinates for this check.
287 R.ToAffine()
288 if R.Y.IsOdd() {
289 k.Negate()
290 }
291 // Step 12.
292 //
293 // e = tagged_hash("BIP0340/challenge", bytes(R) || bytes(P) || m) mod n
294 var rBytes [32]byte
295 r := &R.X
296 r.PutBytesUnchecked(rBytes[:])
297 pBytes := SerializePubKey(pubKey)
298 commitment := chainhash.TaggedHash(
299 chainhash.TagBIP0340Challenge, rBytes[:], pBytes, hash,
300 )
301 var e btcec.ModNScalar
302 if overflow := e.SetBytes((*[32]byte)(commitment)); overflow != 0 {
303 k.Zero()
304 str := "hash of (r || P || m) too big"
305 return nil, signatureError(ErrSchnorrHashValue, str)
306 }
307 // Step 13.
308 //
309 // s = k + e*d mod n
310 var sVal btcec.ModNScalar
311 s := sVal.Mul2(&e, privKey).Add(&k)
312 k.Zero()
313 sig := NewSignature(r, s)
314 // Step 14.
315 //
316 // If Verify(bytes(P), m, sig) fails, abort.
317 if !opts.fastSign {
318 if err := schnorrVerify(sig, hash, pBytes); err != nil {
319 return nil, err
320 }
321 }
322 // Step 15.
323 //
324 // Return (r, s)
325 return sig, nil
326 }
327 328 // SignOption is a functional option argument that allows callers to modify the
329 // way we generate BIP-340 schnorr signatures.
330 type SignOption func(*signOptions)
331 332 // signOptions houses the set of functional options that can be used to modify
333 // the method used to generate the BIP-340 signature.
334 type signOptions struct {
335 // fastSign determines if we'll skip the check at the end of the routine
336 // where we attempt to verify the produced signature.
337 fastSign bool
338 // authNonce allows the user to pass in their own nonce information, which
339 // is useful for schemes like mu-sig.
340 authNonce *[32]byte
341 }
342 343 // defaultSignOptions returns the default set of signing operations.
344 func defaultSignOptions() *signOptions { return &signOptions{} }
345 346 // FastSign forces signing to skip the extra verification step at the end.
347 // Peformance sensitive applications may opt to use this option to speed up the
348 // signing operation.
349 func FastSign() SignOption {
350 return func(o *signOptions) { o.fastSign = true }
351 }
352 353 // CustomNonce allows users to pass in a custom set of auxData that's used as
354 // input randomness to generate the nonce used during signing. Users may want
355 // to specify this custom value when using multi-signatures schemes such as
356 // Mu-Sig2. If this option isn't set, then rfc6979 will be used to generate the
357 // nonce material.
358 func CustomNonce(auxData [32]byte) SignOption {
359 return func(o *signOptions) { o.authNonce = &auxData }
360 }
361 362 // Sign generates an BIP-340 signature over the secp256k1 curve for the provided
363 // hash (which should be the result of hashing a larger message) using the given
364 // secret key. The produced signature is deterministic (the same message and the
365 // same key yield the same signature) and canonical.
366 //
367 // Note that the current signing implementation has a few remaining variable
368 // time aspects which make use of the secret key and the generated nonce, which
369 // can expose the signer to constant time attacks. As a result, this function
370 // should not be used in situations where there is the possibility of someone
371 // having EM field/cache/etc access.
372 func Sign(
373 privKey *btcec.SecretKey, hash []byte,
374 signOpts ...SignOption,
375 ) (*Signature, error) {
376 // First, parse the set of optional signing options.
377 opts := defaultSignOptions()
378 for _, option := range signOpts {
379 option(opts)
380 }
381 // The algorithm for producing a BIP-340 signature is described in README.md
382 // and is reproduced here for reference:
383 //
384 // G = curve generator
385 // n = curve order
386 // d = secret key
387 // m = message
388 // a = input randmoness
389 // r, s = signature
390 //
391 // 1. d' = int(d)
392 // 2. Fail if m is not 32 bytes
393 // 3. Fail if d = 0 or d >= n
394 // 4. P = d'*G
395 // 5. Negate d if P.y is odd
396 // 6. t = bytes(d) xor tagged_hash("BIP0340/aux", t || bytes(P) || m)
397 // 7. rand = tagged_hash("BIP0340/nonce", a)
398 // 8. k' = int(rand) mod n
399 // 9. Fail if k' = 0
400 // 10. R = 'k*G
401 // 11. Negate k if R.y id odd
402 // 12. e = tagged_hash("BIP0340/challenge", bytes(R) || bytes(P) || mod) mod n
403 // 13. sig = bytes(R) || bytes((k + e*d)) mod n
404 // 14. If Verify(bytes(P), m, sig) fails, abort.
405 // 15. return sig.
406 //
407 // Note that the set of functional options passed in may modify the above
408 // algorithm. Namely if CustomNonce is used, then steps 6-8 are replaced
409 // with a process that generates the nonce using rfc6979. If FastSign is
410 // passed, then we skip set 14.
411 //
412 // Step 1.
413 //
414 // d' = int(d)
415 var privKeyScalar btcec.ModNScalar
416 privKeyScalar.Set(&privKey.Key)
417 418 // Step 2.
419 //
420 // Fail if m is not 32 bytes
421 // if len(hash) != scalarSize {
422 // str := fmt.Sprintf("wrong size for message hash (got %v, want %v)",
423 // len(hash), scalarSize)
424 // return nil, signatureError(schnorr.ErrInvalidHashLen, str)
425 // }
426 //
427 // Step 3.
428 //
429 // Fail if d = 0 or d >= n
430 if privKeyScalar.IsZero() {
431 str := "secret key is zero"
432 return nil, signatureError(ErrSecretKeyIsZero, str)
433 }
434 // Step 4.
435 //
436 // P = 'd*G
437 pub := privKey.PubKey()
438 // Step 5.
439 //
440 // Negate d if P.y is odd.
441 pubKeyBytes := pub.SerializeCompressed()
442 if pubKeyBytes[0] == secp256k1.PubKeyFormatCompressedOdd {
443 privKeyScalar.Negate()
444 }
445 // At this point, we check to see if a CustomNonce has been passed in, and
446 // if so, then we'll deviate from the main routine here by generating the
447 // nonce value as specified by BIP-0340.
448 if opts.authNonce != nil {
449 // Step 6.
450 //
451 // t = bytes(d) xor tagged_hash("BIP0340/aux", a)
452 privBytes := privKeyScalar.Bytes()
453 t := chainhash.TaggedHash(
454 chainhash.TagBIP0340Aux, (*opts.authNonce)[:],
455 )
456 for i := 0; i < len(t); i++ {
457 t[i] ^= privBytes[i]
458 }
459 // Step 7.
460 //
461 // rand = tagged_hash("BIP0340/nonce", t || bytes(P) || m)
462 //
463 // We snip off the first byte of the serialized pubkey, as we only need
464 // the x coordinate and not the market byte.
465 rand := chainhash.TaggedHash(
466 chainhash.TagBIP0340Nonce, t[:], pubKeyBytes[1:], hash,
467 )
468 // Step 8.
469 //
470 // k'= int(rand) mod n
471 var kPrime btcec.ModNScalar
472 kPrime.SetBytes((*[32]byte)(rand))
473 // Step 9.
474 //
475 // Fail if k' = 0
476 if kPrime.IsZero() {
477 str := fmt.Sprintf("generated nonce is zero")
478 return nil, signatureError(ErrSchnorrHashValue, str)
479 }
480 sig, err := schnorrSign(&privKeyScalar, &kPrime, pub, hash, opts)
481 kPrime.Zero()
482 if err != nil {
483 return nil, err
484 }
485 return sig, nil
486 }
487 var privKeyBytes [scalarSize]byte
488 privKeyScalar.PutBytes(&privKeyBytes)
489 defer zeroArray(&privKeyBytes)
490 for iteration := uint32(0); ; iteration++ {
491 var k *secp256k1.ModNScalar
492 // Step 6-9.
493 //
494 // Use RFC6979 to generate a deterministic nonce k in [1, n-1]
495 // parameterized by the secret key, message being signed, extra data
496 // that identifies the scheme, and an iteration count
497 extraData := _rfc6979ExtraDataV0()
498 k = btcec.NonceRFC6979(
499 privKeyBytes[:], hash, extraData[:], nil, iteration,
500 )
501 // Steps 10-15.
502 sig, err := schnorrSign(&privKeyScalar, k, pub, hash, opts)
503 k.Zero()
504 if err != nil {
505 // Try again with a new nonce.
506 continue
507 }
508 return sig, nil
509 }
510 }
511