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