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