1 // Copyright (c) 2013-2014 The btcsuite developers
2 // Copyright (c) 2015-2022 The Decred developers
3 // Use of this source code is governed by an ISC
4 // license that can be found in the LICENSE file.
5 6 package ecdsa
7 8 import (
9 "fmt"
10 11 "smesh.lol/pkg/nostr/ec/secp256k1"
12 )
13 14 // References:
15 // [GECC]: Guide to Elliptic Curve Cryptography (Hankerson, Menezes, Vanstone)
16 //
17 // [ISO/IEC 8825-1]: Information technology — ASN.1 encoding rules:
18 // Specification of Basic Encoding Rules (BER), Canonical Encoding Rules
19 // (CER) and Distinguished Encoding Rules (DER)
20 //
21 // [SEC1]: Elliptic Curve Cryptography (May 31, 2009, Version 2.0)
22 // https://www.secg.org/sec1-v2.pdf
23 24 var (
25 // zero32 is an array of 32 bytes used for the purposes of zeroing and is
26 // defined here to avoid extra allocations.
27 zero32 = [32]byte{}
28 // orderAsFieldVal is the order of the secp256k1 curve group stored as a
29 // field value. It is provided here to avoid the need to create it multiple
30 // times.
31 orderAsFieldVal = func() secp256k1.FieldVal {
32 var f secp256k1.FieldVal
33 f.SetByteSlice(secp256k1.Params().N.Bytes())
34 return f
35 }()
36 )
37 38 const (
39 // asn1SequenceID is the ASN.1 identifier for a sequence and is used when
40 // parsing and serializing signatures encoded with the Distinguished
41 // Encoding Rules (DER) format per section 10 of [ISO/IEC 8825-1].
42 asn1SequenceID = 0x30
43 // asn1IntegerID is the ASN.1 identifier for an integer and is used when
44 // parsing and serializing signatures encoded with the Distinguished
45 // Encoding Rules (DER) format per section 10 of [ISO/IEC 8825-1].
46 asn1IntegerID = 0x02
47 )
48 49 // Signature is a type representing an ECDSA signature.
50 type Signature struct {
51 r secp256k1.ModNScalar
52 s secp256k1.ModNScalar
53 }
54 55 // NewSignature instantiates a new signature given some r and s values.
56 func NewSignature(r, s *secp256k1.ModNScalar) *Signature {
57 return &Signature{*r, *s}
58 }
59 60 // Serialize returns the ECDSA signature in the Distinguished Encoding Rules
61 // (DER) format per section 10 of [ISO/IEC 8825-1] and such that the S component
62 // of the signature is less than or equal to the half order of the group.
63 //
64 // Note that the serialized bytes returned do not include the appended hash type
65 // used in Decred signature scripts.
66 func (sig *Signature) Serialize() []byte {
67 // The format of a DER encoded signature is as follows:
68 //
69 // 0x30 <total length> 0x02 <length of R> <R> 0x02 <length of S> <S>
70 // - 0x30 is the ASN.1 identifier for a sequence.
71 // - Total length is 1 byte and specifies length of all remaining data.
72 // - 0x02 is the ASN.1 identifier that specifies an integer follows.
73 // - Length of R is 1 byte and specifies how many bytes R occupies.
74 // - R is the arbitrary length big-endian encoded number which
75 // represents the R value of the signature. DER encoding dictates
76 // that the value must be encoded using the minimum possible number
77 // of bytes. This implies the first byte can only be null if the
78 // highest bit of the next byte is set in order to prevent it from
79 // being interpreted as a negative number.
80 // - 0x02 is once again the ASN.1 integer identifier.
81 // - Length of S is 1 byte and specifies how many bytes S occupies.
82 // - S is the arbitrary length big-endian encoded number which
83 // represents the S value of the signature. The encoding rules are
84 // identical as those for R.
85 86 // Ensure the S component of the signature is less than or equal to the half
87 // order of the group because both S and its negation are valid signatures
88 // modulo the order, so this forces a consistent choice to reduce signature
89 // malleability.
90 sigS := (&secp256k1.ModNScalar{}).Set(&sig.s)
91 if sigS.IsOverHalfOrder() {
92 sigS.Negate()
93 }
94 95 // Serialize the R and S components of the signature into their fixed
96 // 32-byte big-endian encoding. Note that the extra leading zero byte is
97 // used to ensure it is canonical per DER and will be stripped if needed
98 // below.
99 var rBuf, sBuf [33]byte
100 sig.r.PutBytesUnchecked(rBuf[1:33])
101 sigS.PutBytesUnchecked(sBuf[1:33])
102 // Ensure the encoded bytes for the R and S components are canonical per DER
103 // by trimming all leading zero bytes so long as the next byte does not have
104 // the high bit set and it's not the final byte.
105 canonR, canonS := rBuf[:], sBuf[:]
106 for len(canonR) > 1 && canonR[0] == 0x00 && canonR[1]&0x80 == 0 {
107 canonR = canonR[1:]
108 }
109 for len(canonS) > 1 && canonS[0] == 0x00 && canonS[1]&0x80 == 0 {
110 canonS = canonS[1:]
111 }
112 // Total length of returned signature is 1 byte for each magic and length
113 // (6 total), plus lengths of R and S.
114 totalLen := 6 + len(canonR) + len(canonS)
115 b := []byte{:0:totalLen}
116 b = append(b, asn1SequenceID)
117 b = append(b, byte(totalLen-2))
118 b = append(b, asn1IntegerID)
119 b = append(b, byte(len(canonR)))
120 b = append(b, canonR...)
121 b = append(b, asn1IntegerID)
122 b = append(b, byte(len(canonS)))
123 b = append(b, canonS...)
124 return b
125 }
126 127 // zeroArray32 zeroes the provided 32-byte buffer.
128 func zeroArray32(b *[32]byte) {
129 copy(b[:], zero32[:])
130 }
131 132 // fieldToModNScalar converts a field value to scalar modulo the group order and
133 // returns the scalar along with either 1 if it was reduced (aka it overflowed)
134 // or 0 otherwise.
135 //
136 // Note that a bool is not used here because it is not possible in Go to convert
137 // from a bool to numeric value in constant time and many constant-time
138 // operations require a numeric value.
139 func fieldToModNScalar(v *secp256k1.FieldVal) (secp256k1.ModNScalar, uint32) {
140 var buf [32]byte
141 v.PutBytes(&buf)
142 var s secp256k1.ModNScalar
143 overflow := s.SetBytes(&buf)
144 zeroArray32(&buf)
145 return s, overflow
146 }
147 148 // modNScalarToField converts a scalar modulo the group order to a field value.
149 func modNScalarToField(v *secp256k1.ModNScalar) secp256k1.FieldVal {
150 var buf [32]byte
151 v.PutBytes(&buf)
152 var fv secp256k1.FieldVal
153 fv.SetBytes(&buf)
154 return fv
155 }
156 157 // Verify returns whether the signature is valid for the provided hash
158 // and secp256k1 public key.
159 func (sig *Signature) Verify(hash []byte, pubKey *secp256k1.PublicKey) bool {
160 // The algorithm for verifying an ECDSA signature is given as algorithm 4.30
161 // in [GECC].
162 //
163 // The following is a paraphrased version for reference:
164 //
165 // G = curve generator
166 // N = curve order
167 // Q = public key
168 // m = message
169 // R, S = signature
170 //
171 // 1. Fail if R and S are not in [1, N-1]
172 // 2. e = H(m)
173 // 3. w = S^-1 mod N
174 // 4. u1 = e * w mod N
175 // u2 = R * w mod N
176 // 5. X = u1G + u2Q
177 // 6. Fail if X is the point at infinity
178 // 7. x = X.x mod N (X.x is the x coordinate of X)
179 // 8. Verified if x == R
180 //
181 // However, since all group operations are done internally in Jacobian
182 // projective space, the algorithm is modified slightly here in order to
183 // avoid an expensive inversion back into affine coordinates at step 7.
184 // Credits to Greg Maxwell for originally suggesting this optimization.
185 //
186 // Ordinarily, step 7 involves converting the x coordinate to affine by
187 // calculating x = x / z^2 (mod P) and then calculating the remainder as
188 // x = x (mod N). Then step 8 compares it to R.
189 //
190 // Note that since R is the x coordinate mod N from a random point that was
191 // originally mod P, and the cofactor of the secp256k1 curve is 1, there are
192 // only two possible x coordinates that the original random point could have
193 // been to produce R: x, where x < N, and x+N, where x+N < P.
194 //
195 // This implies that the signature is valid if either:
196 // a) R == X.x / X.z^2 (mod P)
197 // => R * X.z^2 == X.x (mod P)
198 // --or--
199 // b) R + N < P && R + N == X.x / X.z^2 (mod P)
200 // => R + N < P && (R + N) * X.z^2 == X.x (mod P)
201 //
202 // Therefore the following modified algorithm is used:
203 //
204 // 1. Fail if R and S are not in [1, N-1]
205 // 2. e = H(m)
206 // 3. w = S^-1 mod N
207 // 4. u1 = e * w mod N
208 // u2 = R * w mod N
209 // 5. X = u1G + u2Q
210 // 6. Fail if X is the point at infinity
211 // 7. z = (X.z)^2 mod P (X.z is the z coordinate of X)
212 // 8. Verified if R * z == X.x (mod P)
213 // 9. Fail if R + N >= P
214 // 10. Verified if (R + N) * z == X.x (mod P)
215 //
216 // Step 1.
217 //
218 // Fail if R and S are not in [1, N-1].
219 if sig.r.IsZero() || sig.s.IsZero() {
220 return false
221 }
222 // Step 2.
223 //
224 // e = H(m)
225 var e secp256k1.ModNScalar
226 e.SetByteSlice(hash)
227 // Step 3.
228 //
229 // w = S^-1 mod N
230 w := (&secp256k1.ModNScalar{}).InverseValNonConst(&sig.s)
231 // Step 4.
232 //
233 // u1 = e * w mod N
234 // u2 = R * w mod N
235 u1 := (&secp256k1.ModNScalar{}).Mul2(&e, w)
236 u2 := (&secp256k1.ModNScalar{}).Mul2(&sig.r, w)
237 // Step 5.
238 //
239 // X = u1G + u2Q
240 var X, Q, u1G, u2Q secp256k1.JacobianPoint
241 pubKey.AsJacobian(&Q)
242 secp256k1.ScalarBaseMultNonConst(u1, &u1G)
243 secp256k1.ScalarMultNonConst(u2, &Q, &u2Q)
244 secp256k1.AddNonConst(&u1G, &u2Q, &X)
245 // Step 6.
246 //
247 // Fail if X is the point at infinity
248 if (X.X.IsZero() && X.Y.IsZero()) || X.Z.IsZero() {
249 return false
250 }
251 // Step 7.
252 //
253 // z = (X.z)^2 mod P (X.z is the z coordinate of X)
254 z := (&secp256k1.FieldVal{}).SquareVal(&X.Z)
255 // Step 8.
256 //
257 // Verified if R * z == X.x (mod P)
258 sigRModP := modNScalarToField(&sig.r)
259 result := (&secp256k1.FieldVal{}).Mul2(&sigRModP, z).Normalize()
260 if result.Equals(&X.X) {
261 return true
262 }
263 // Step 9.
264 //
265 // Fail if R + N >= P
266 if sigRModP.IsGtOrEqPrimeMinusOrder() {
267 return false
268 }
269 // Step 10.
270 //
271 // Verified if (R + N) * z == X.x (mod P)
272 sigRModP.Add(&orderAsFieldVal)
273 result.Mul2(&sigRModP, z).Normalize()
274 return result.Equals(&X.X)
275 }
276 277 // IsEqual compares this Signature instance to the one passed, returning true if
278 // both Signatures are equivalent. A signature is equivalent to another, if
279 // they both have the same scalar value for R and S.
280 func (sig *Signature) IsEqual(otherSig *Signature) bool {
281 return sig.r.Equals(&otherSig.r) && sig.s.Equals(&otherSig.s)
282 }
283 284 // ParseDERSignature parses a signature in the Distinguished Encoding Rules
285 // (DER) format per section 10 of [ISO/IEC 8825-1] and enforces the following
286 // additional restrictions specific to secp256k1:
287 //
288 // - The R and S values must be in the valid range for secp256k1 scalars:
289 // - Negative values are rejected
290 // - Zero is rejected
291 // - Values greater than or equal to the secp256k1 group order are rejected
292 func ParseDERSignature(sig []byte) (*Signature, error) {
293 // The format of a DER encoded signature for secp256k1 is as follows:
294 //
295 // 0x30 <total length> 0x02 <length of R> <R> 0x02 <length of S> <S>
296 // - 0x30 is the ASN.1 identifier for a sequence
297 // - Total length is 1 byte and specifies length of all remaining data
298 // - 0x02 is the ASN.1 identifier that specifies an integer follows
299 // - Length of R is 1 byte and specifies how many bytes R occupies
300 // - R is the arbitrary length big-endian encoded number which
301 // represents the R value of the signature. DER encoding dictates
302 // that the value must be encoded using the minimum possible number
303 // of bytes. This implies the first byte can only be null if the
304 // highest bit of the next byte is set in order to prevent it from
305 // being interpreted as a negative number.
306 // - 0x02 is once again the ASN.1 integer identifier
307 // - Length of S is 1 byte and specifies how many bytes S occupies
308 // - S is the arbitrary length big-endian encoded number which
309 // represents the S value of the signature. The encoding rules are
310 // identical as those for R.
311 //
312 // NOTE: The DER specification supports specifying lengths that can occupy
313 // more than 1 byte, however, since this is specific to secp256k1
314 // signatures, all lengths will be a single byte.
315 const (
316 // minSigLen is the minimum length of a DER encoded signature and is
317 // when both R and S are 1 byte each.
318 //
319 // 0x30 + <1-byte> + 0x02 + 0x01 + <byte> + 0x2 + 0x01 + <byte>
320 minSigLen = 8
321 // maxSigLen is the maximum length of a DER encoded signature and is
322 // when both R and S are 33 bytes each. It is 33 bytes because a
323 // 256-bit integer requires 32 bytes and an additional leading null byte
324 // might be required if the high bit is set in the value.
325 //
326 // 0x30 + <1-byte> + 0x02 + 0x21 + <33 bytes> + 0x2 + 0x21 + <33 bytes>
327 maxSigLen = 72
328 // sequenceOffset is the byte offset within the signature of the
329 // expected ASN.1 sequence identifier.
330 sequenceOffset = 0
331 // dataLenOffset is the byte offset within the signature of the expected
332 // total length of all remaining data in the signature.
333 dataLenOffset = 1
334 // rTypeOffset is the byte offset within the signature of the ASN.1
335 // identifier for R and is expected to indicate an ASN.1 integer.
336 rTypeOffset = 2
337 // rLenOffset is the byte offset within the signature of the length of
338 // R.
339 rLenOffset = 3
340 // rOffset is the byte offset within the signature of R.
341 rOffset = 4
342 )
343 // The signature must adhere to the minimum and maximum allowed length.
344 sigLen := len(sig)
345 if sigLen < minSigLen {
346 str := fmt.Sprintf(
347 "malformed signature: too short: %d < %d", sigLen,
348 minSigLen,
349 )
350 return nil, signatureError(ErrSigTooShort, str)
351 }
352 if sigLen > maxSigLen {
353 str := fmt.Sprintf(
354 "malformed signature: too long: %d > %d", sigLen,
355 maxSigLen,
356 )
357 return nil, signatureError(ErrSigTooLong, str)
358 }
359 // The signature must start with the ASN.1 sequence identifier.
360 if sig[sequenceOffset] != asn1SequenceID {
361 str := fmt.Sprintf(
362 "malformed signature: format has wrong type: %#x",
363 sig[sequenceOffset],
364 )
365 return nil, signatureError(ErrSigInvalidSeqID, str)
366 }
367 // The signature must indicate the correct amount of data for all elements
368 // related to R and S.
369 if int(sig[dataLenOffset]) != sigLen-2 {
370 str := fmt.Sprintf(
371 "malformed signature: bad length: %d != %d",
372 sig[dataLenOffset], sigLen-2,
373 )
374 return nil, signatureError(ErrSigInvalidDataLen, str)
375 }
376 // Calculate the offsets of the elements related to S and ensure S is inside
377 // the signature.
378 //
379 // rLen specifies the length of the big-endian encoded number which
380 // represents the R value of the signature.
381 //
382 // sTypeOffset is the offset of the ASN.1 identifier for S and, like its R
383 // counterpart, is expected to indicate an ASN.1 integer.
384 //
385 // sLenOffset and sOffset are the byte offsets within the signature of the
386 // length of S and S itself, respectively.
387 rLen := int(sig[rLenOffset])
388 sTypeOffset := rOffset + rLen
389 sLenOffset := sTypeOffset + 1
390 if sTypeOffset >= sigLen {
391 str := "malformed signature: S type indicator missing"
392 return nil, signatureError(ErrSigMissingSTypeID, str)
393 }
394 if sLenOffset >= sigLen {
395 str := "malformed signature: S length missing"
396 return nil, signatureError(ErrSigMissingSLen, str)
397 }
398 // The lengths of R and S must match the overall length of the signature.
399 //
400 // sLen specifies the length of the big-endian encoded number which
401 // represents the S value of the signature.
402 sOffset := sLenOffset + 1
403 sLen := int(sig[sLenOffset])
404 if sOffset+sLen != sigLen {
405 str := "malformed signature: invalid S length"
406 return nil, signatureError(ErrSigInvalidSLen, str)
407 }
408 // R elements must be ASN.1 integers.
409 if sig[rTypeOffset] != asn1IntegerID {
410 str := fmt.Sprintf(
411 "malformed signature: R integer marker: %#x != %#x",
412 sig[rTypeOffset], asn1IntegerID,
413 )
414 return nil, signatureError(ErrSigInvalidRIntID, str)
415 }
416 // Zero-length integers are not allowed for R.
417 if rLen == 0 {
418 str := "malformed signature: R length is zero"
419 return nil, signatureError(ErrSigZeroRLen, str)
420 }
421 // R must not be negative.
422 if sig[rOffset]&0x80 != 0 {
423 str := "malformed signature: R is negative"
424 return nil, signatureError(ErrSigNegativeR, str)
425 }
426 // Null bytes at the start of R are not allowed, unless R would otherwise be
427 // interpreted as a negative number.
428 if rLen > 1 && sig[rOffset] == 0x00 && sig[rOffset+1]&0x80 == 0 {
429 str := "malformed signature: R value has too much padding"
430 return nil, signatureError(ErrSigTooMuchRPadding, str)
431 }
432 // S elements must be ASN.1 integers.
433 if sig[sTypeOffset] != asn1IntegerID {
434 str := fmt.Sprintf(
435 "malformed signature: S integer marker: %#x != %#x",
436 sig[sTypeOffset], asn1IntegerID,
437 )
438 return nil, signatureError(ErrSigInvalidSIntID, str)
439 }
440 // Zero-length integers are not allowed for S.
441 if sLen == 0 {
442 str := "malformed signature: S length is zero"
443 return nil, signatureError(ErrSigZeroSLen, str)
444 }
445 // S must not be negative.
446 if sig[sOffset]&0x80 != 0 {
447 str := "malformed signature: S is negative"
448 return nil, signatureError(ErrSigNegativeS, str)
449 }
450 // Null bytes at the start of S are not allowed, unless S would otherwise be
451 // interpreted as a negative number.
452 if sLen > 1 && sig[sOffset] == 0x00 && sig[sOffset+1]&0x80 == 0 {
453 str := "malformed signature: S value has too much padding"
454 return nil, signatureError(ErrSigTooMuchSPadding, str)
455 }
456 // The signature is validly encoded per DER at this point, however, enforce
457 // additional restrictions to ensure R and S are in the range [1, N-1] since
458 // valid ECDSA signatures are required to be in that range per spec.
459 //
460 // Also note that while the overflow checks are required to make use of the
461 // specialized mod N scalar type, rejecting zero here is not strictly
462 // required because it is also checked when verifying the signature, but
463 // there really isn't a good reason not to fail early here on signatures
464 // that do not conform to the ECDSA spec.
465 //
466 // Strip leading zeroes from R.
467 rBytes := sig[rOffset : rOffset+rLen]
468 for len(rBytes) > 0 && rBytes[0] == 0x00 {
469 rBytes = rBytes[1:]
470 }
471 // R must be in the range [1, N-1]. Notice the check for the maximum number
472 // of bytes is required because SetByteSlice truncates as noted in its
473 // comment so it could otherwise fail to detect the overflow.
474 var r secp256k1.ModNScalar
475 if len(rBytes) > 32 {
476 str := "invalid signature: R is larger than 256 bits"
477 return nil, signatureError(ErrSigRTooBig, str)
478 }
479 if overflow := r.SetByteSlice(rBytes); overflow {
480 str := "invalid signature: R >= group order"
481 return nil, signatureError(ErrSigRTooBig, str)
482 }
483 if r.IsZero() {
484 str := "invalid signature: R is 0"
485 return nil, signatureError(ErrSigRIsZero, str)
486 }
487 // Strip leading zeroes from S.
488 sBytes := sig[sOffset : sOffset+sLen]
489 for len(sBytes) > 0 && sBytes[0] == 0x00 {
490 sBytes = sBytes[1:]
491 }
492 // S must be in the range [1, N-1]. Notice the check for the maximum number
493 // of bytes is required because SetByteSlice truncates as noted in its
494 // comment so it could otherwise fail to detect the overflow.
495 var s secp256k1.ModNScalar
496 if len(sBytes) > 32 {
497 str := "invalid signature: S is larger than 256 bits"
498 return nil, signatureError(ErrSigSTooBig, str)
499 }
500 if overflow := s.SetByteSlice(sBytes); overflow {
501 str := "invalid signature: S >= group order"
502 return nil, signatureError(ErrSigSTooBig, str)
503 }
504 if s.IsZero() {
505 str := "invalid signature: S is 0"
506 return nil, signatureError(ErrSigSIsZero, str)
507 }
508 // Create and return the signature.
509 return NewSignature(&r, &s), nil
510 }
511 512 // sign generates an ECDSA signature over the secp256k1 curve for the provided
513 // hash (which should be the result of hashing a larger message) using the given
514 // nonce and secret key and returns it along with an additional public key
515 // recovery code and success indicator. Upon success, the produced signature is
516 // deterministic (same message, nonce, and key yield the same signature) and
517 // canonical in accordance with BIP0062.
518 //
519 // Note that signRFC6979 makes use of this function as it is the primary ECDSA
520 // signing logic. It differs in that it accepts a nonce to use when signing and
521 // may not successfully produce a valid signature for the given nonce. It is
522 // primarily separated for testing purposes.
523 func sign(secKey, nonce *secp256k1.ModNScalar, hash []byte) (
524 *Signature, byte,
525 bool,
526 ) {
527 // The algorithm for producing an ECDSA signature is given as algorithm 4.29
528 // in [GECC].
529 //
530 // The following is a paraphrased version for reference:
531 //
532 // G = curve generator
533 // N = curve order
534 // d = secret key
535 // m = message
536 // r, s = signature
537 //
538 // 1. Select random nonce k in [1, N-1]
539 // 2. Compute kG
540 // 3. r = kG.x mod N (kG.x is the x coordinate of the point kG)
541 // Repeat from step 1 if r = 0
542 // 4. e = H(m)
543 // 5. s = k^-1(e + dr) mod N
544 // Repeat from step 1 if s = 0
545 // 6. Return (r,s)
546 //
547 // This is slightly modified here to conform to RFC6979 and BIP 62 as
548 // follows:
549 //
550 // A. Instead of selecting a random nonce in step 1, use RFC6979 to generate
551 // a deterministic nonce in [1, N-1] parameterized by the secret key,
552 // message being signed, and an iteration count for the repeat cases
553 // B. Negate s calculated in step 5 if it is > N/2
554 // This is done because both s and its negation are valid signatures
555 // modulo the curve order N, so it forces a consistent choice to reduce
556 // signature malleability
557 //
558 // NOTE: Step 1 is performed by the caller.
559 //
560 // Step 2.
561 //
562 // Compute kG
563 //
564 // Note that the point must be in affine coordinates.
565 k := nonce
566 var kG secp256k1.JacobianPoint
567 secp256k1.ScalarBaseMultNonConst(k, &kG)
568 kG.ToAffine()
569 // Step 3.
570 //
571 // r = kG.x mod N
572 // Repeat from step 1 if r = 0
573 r, overflow := fieldToModNScalar(&kG.X)
574 if r.IsZero() {
575 return nil, 0, false
576 }
577 // Since the secp256k1 curve has a cofactor of 1, when recovering a
578 // public key from an ECDSA signature over it, there are four possible
579 // candidates corresponding to the following cases:
580 //
581 // 1) The X coord of the random point is < N and its Y coord even
582 // 2) The X coord of the random point is < N and its Y coord is odd
583 // 3) The X coord of the random point is >= N and its Y coord is even
584 // 4) The X coord of the random point is >= N and its Y coord is odd
585 //
586 // Rather than forcing the recovery procedure to check all possible
587 // cases, this creates a recovery code that uniquely identifies which of
588 // the cases apply by making use of 2 bits. Bit 0 identifies the
589 // oddness case and Bit 1 identifies the overflow case (aka when the X
590 // coord >= N).
591 //
592 // It is also worth noting that making use of Hasse's theorem shows
593 // there are around log_2((p-n)/p) ~= -127.65 ~= 1 in 2^127 points where
594 // the X coordinate is >= N. It is not possible to calculate these
595 // points since that would require breaking the ECDLP, but, in practice
596 // this strongly implies with extremely high probability that there are
597 // only a few actual points for which this case is true.
598 pubKeyRecoveryCode := byte(overflow<<1) | byte(kG.Y.IsOddBit())
599 // Step 4.
600 //
601 // e = H(m)
602 //
603 // Note that this actually sets e = H(m) mod N which is correct since
604 // it is only used in step 5 which itself is mod N.
605 var e secp256k1.ModNScalar
606 e.SetByteSlice(hash)
607 // Step 5 with modification B.
608 //
609 // s = k^-1(e + dr) mod N
610 // Repeat from step 1 if s = 0
611 // s = -s if s > N/2
612 kinv := (&secp256k1.ModNScalar{}).InverseValNonConst(k)
613 s := (&secp256k1.ModNScalar{}).Mul2(secKey, &r).Add(&e).Mul(kinv)
614 if s.IsZero() {
615 return nil, 0, false
616 }
617 if s.IsOverHalfOrder() {
618 s.Negate()
619 // Negating s corresponds to the random point that would have been
620 // generated by -k (mod N), which necessarily has the opposite
621 // oddness since N is prime, thus flip the pubkey recovery code
622 // oddness bit accordingly.
623 pubKeyRecoveryCode ^= 0x01
624 }
625 // Step 6.
626 //
627 // Return (r,s)
628 return NewSignature(&r, s), pubKeyRecoveryCode, true
629 }
630 631 // signRFC6979 generates a deterministic ECDSA signature according to RFC 6979
632 // and BIP0062 and returns it along with an additional public key recovery code
633 // for efficiently recovering the public key from the signature.
634 func signRFC6979(secKey *secp256k1.SecretKey, hash []byte) (
635 *Signature,
636 byte,
637 ) {
638 // The algorithm for producing an ECDSA signature is given as algorithm 4.29
639 // in [GECC].
640 //
641 // The following is a paraphrased version for reference:
642 //
643 // G = curve generator
644 // N = curve order
645 // d = secret key
646 // m = message
647 // r, s = signature
648 //
649 // 1. Select random nonce k in [1, N-1]
650 // 2. Compute kG
651 // 3. r = kG.x mod N (kG.x is the x coordinate of the point kG)
652 // Repeat from step 1 if r = 0
653 // 4. e = H(m)
654 // 5. s = k^-1(e + dr) mod N
655 // Repeat from step 1 if s = 0
656 // 6. Return (r,s)
657 //
658 // This is slightly modified here to conform to RFC6979 and BIP 62 as
659 // follows:
660 //
661 // A. Instead of selecting a random nonce in step 1, use RFC6979 to generate
662 // a deterministic nonce in [1, N-1] parameterized by the secret key,
663 // message being signed, and an iteration count for the repeat cases
664 // B. Negate s calculated in step 5 if it is > N/2
665 // This is done because both s and its negation are valid signatures
666 // modulo the curve order N, so it forces a consistent choice to reduce
667 // signature malleability
668 secKeyScalar := &secKey.Key
669 var secKeyBytes [32]byte
670 secKeyScalar.PutBytes(&secKeyBytes)
671 defer zeroArray32(&secKeyBytes)
672 for iteration := uint32(0); ; iteration++ {
673 // Step 1 with modification A.
674 //
675 // Generate a deterministic nonce in [1, N-1] parameterized by the
676 // secret key, message being signed, and iteration count.
677 k := secp256k1.NonceRFC6979(secKeyBytes[:], hash, nil, nil, iteration)
678 // Steps 2-6.
679 sig, pubKeyRecoveryCode, success := sign(secKeyScalar, k, hash)
680 k.Zero()
681 if !success {
682 continue
683 }
684 return sig, pubKeyRecoveryCode
685 }
686 }
687 688 // Sign generates an ECDSA signature over the secp256k1 curve for the provided
689 // hash (which should be the result of hashing a larger message) using the given
690 // secret key. The produced signature is deterministic (same message and same
691 // key yield the same signature) and canonical in accordance with RFC6979 and
692 // BIP0062.
693 func Sign(key *secp256k1.SecretKey, hash []byte) *Signature {
694 signature, _ := signRFC6979(key, hash)
695 return signature
696 }
697 698 const (
699 // compactSigSize is the size of a compact signature. It consists of a
700 // compact signature recovery code byte followed by the R and S components
701 // serialized as 32-byte big-endian values. 1+32*2 = 65.
702 // for the R and S components. 1+32+32=65.
703 compactSigSize = 65
704 // compactSigMagicOffset is a value used when creating the compact signature
705 // recovery code inherited from Bitcoin and has no meaning, but has been
706 // retained for compatibility. For historical purposes, it was originally
707 // picked to avoid a binary representation that would allow compact
708 // signatures to be mistaken for other components.
709 compactSigMagicOffset = 27
710 // compactSigCompPubKey is a value used when creating the compact signature
711 // recovery code to indicate the original public key was compressed.
712 compactSigCompPubKey = 4
713 // pubKeyRecoveryCodeOddnessBit specifies the bit that indicates the oddess
714 // of the Y coordinate of the random point calculated when creating a
715 // signature.
716 pubKeyRecoveryCodeOddnessBit = 1 << 0
717 // pubKeyRecoveryCodeOverflowBit specifies the bit that indicates the X
718 // coordinate of the random point calculated when creating a signature was
719 // >= N, where N is the order of the group.
720 pubKeyRecoveryCodeOverflowBit = 1 << 1
721 )
722 723 // SignCompact produces a compact ECDSA signature over the secp256k1 curve for
724 // the provided hash (which should be the result of hashing a larger message)
725 // using the given secret key. The isCompressedKey parameter specifies if the
726 // produced signature should reference a compressed public key or not.
727 //
728 // Compact signature format:
729 // <1-byte compact sig recovery code><32-byte R><32-byte S>
730 //
731 // The compact sig recovery code is the value 27 + public key recovery code + 4
732 // if the compact signature was created with a compressed public key.
733 func SignCompact(
734 key *secp256k1.SecretKey, hash []byte,
735 isCompressedKey bool,
736 ) []byte {
737 // Create the signature and associated pubkey recovery code and calculate
738 // the compact signature recovery code.
739 sig, pubKeyRecoveryCode := signRFC6979(key, hash)
740 compactSigRecoveryCode := compactSigMagicOffset + pubKeyRecoveryCode
741 if isCompressedKey {
742 compactSigRecoveryCode += compactSigCompPubKey
743 }
744 // Output <compactSigRecoveryCode><32-byte R><32-byte S>.
745 var b [compactSigSize]byte
746 b[0] = compactSigRecoveryCode
747 sig.r.PutBytesUnchecked(b[1:33])
748 sig.s.PutBytesUnchecked(b[33:65])
749 return b[:]
750 }
751 752 // RecoverCompact attempts to recover the secp256k1 public key from the provided
753 // compact signature and message hash. It first verifies the signature, and, if
754 // the signature matches then the recovered public key will be returned as well
755 // as a boolean indicating whether or not the original key was compressed.
756 func RecoverCompact(signature, hash []byte) (
757 *secp256k1.PublicKey, bool, error,
758 ) {
759 // The following is very loosely based on the information and algorithm that
760 // describes recovering a public key from and ECDSA signature in section
761 // 4.1.6 of [SEC1].
762 //
763 // Given the following parameters:
764 //
765 // G = curve generator
766 // N = group order
767 // P = field prime
768 // Q = public key
769 // m = message
770 // e = hash of the message
771 // r, s = signature
772 // X = random point used when creating signature whose x coordinate is r
773 //
774 // The equation to recover a public key candidate from an ECDSA signature
775 // is:
776 // Q = r^-1(sX - eG).
777 //
778 // This can be verified by plugging it in for Q in the sig verification
779 // equation:
780 // X = s^-1(eG + rQ) (mod N)
781 // => s^-1(eG + r(r^-1(sX - eG))) (mod N)
782 // => s^-1(eG + sX - eG) (mod N)
783 // => s^-1(sX) (mod N)
784 // => X (mod N)
785 //
786 // However, note that since r is the x coordinate mod N from a random point
787 // that was originally mod P, and the cofactor of the secp256k1 curve is 1,
788 // there are four possible points that the original random point could have
789 // been to produce r: (r,y), (r,-y), (r+N,y), and (r+N,-y). At least 2 of
790 // those points will successfully verify, and all 4 will successfully verify
791 // when the original x coordinate was in the range [N+1, P-1], but in any
792 // case, only one of them corresponds to the original secret key used.
793 //
794 // The method described by section 4.1.6 of [SEC1] to determine which one is
795 // the correct one involves calculating each possibility as a candidate
796 // public key and comparing the candidate to the authentic public key. It
797 // also hints that it is possible to generate the signature in a such a
798 // way that only one of the candidate public keys is viable.
799 //
800 // A more efficient approach that is specific to the secp256k1 curve is used
801 // here instead which is to produce a "pubkey recovery code" when signing
802 // that uniquely identifies which of the 4 possibilities is correct for the
803 // original random point and using that to recover the pubkey directly as
804 // follows:
805 //
806 // 1. Fail if r and s are not in [1, N-1]
807 // 2. Convert r to integer mod P
808 // 3. If pubkey recovery code overflow bit is set:
809 // 3.1 Fail if r + N >= P
810 // 3.2 r = r + N (mod P)
811 // 4. y = +sqrt(r^3 + 7) (mod P)
812 // 4.1 Fail if y does not exist
813 // 4.2 y = -y if needed to match pubkey recovery code oddness bit
814 // 5. X = (r, y)
815 // 6. e = H(m) mod N
816 // 7. w = r^-1 mod N
817 // 8. u1 = -(e * w) mod N
818 // u2 = s * w mod N
819 // 9. Q = u1G + u2X
820 // 10. Fail if Q is the point at infinity
821 //
822 // A compact signature consists of a recovery byte followed by the R and
823 // S components serialized as 32-byte big-endian values.
824 if len(signature) != compactSigSize {
825 str := fmt.Sprintf(
826 "malformed signature: wrong size: %d != %d",
827 len(signature), compactSigSize,
828 )
829 return nil, false, signatureError(ErrSigInvalidLen, str)
830 }
831 // Parse and validate the compact signature recovery code.
832 const (
833 minValidCode = compactSigMagicOffset
834 maxValidCode = compactSigMagicOffset + compactSigCompPubKey + 3
835 )
836 sigRecoveryCode := signature[0]
837 if sigRecoveryCode < minValidCode || sigRecoveryCode > maxValidCode {
838 str := fmt.Sprintf(
839 "invalid signature: public key recovery code %d is "+
840 "not in the valid range [%d, %d]", sigRecoveryCode,
841 minValidCode,
842 maxValidCode,
843 )
844 return nil, false, signatureError(ErrSigInvalidRecoveryCode, str)
845 }
846 sigRecoveryCode -= compactSigMagicOffset
847 wasCompressed := sigRecoveryCode&compactSigCompPubKey != 0
848 pubKeyRecoveryCode := sigRecoveryCode & 3
849 // Step 1.
850 //
851 // Parse and validate the R and S signature components.
852 //
853 // Fail if r and s are not in [1, N-1].
854 var r, s secp256k1.ModNScalar
855 if overflow := r.SetByteSlice(signature[1:33]); overflow {
856 str := "invalid signature: R >= group order"
857 return nil, false, signatureError(ErrSigRTooBig, str)
858 }
859 if r.IsZero() {
860 str := "invalid signature: R is 0"
861 return nil, false, signatureError(ErrSigRIsZero, str)
862 }
863 if overflow := s.SetByteSlice(signature[33:]); overflow {
864 str := "invalid signature: S >= group order"
865 return nil, false, signatureError(ErrSigSTooBig, str)
866 }
867 if s.IsZero() {
868 str := "invalid signature: S is 0"
869 return nil, false, signatureError(ErrSigSIsZero, str)
870 }
871 // Step 2.
872 //
873 // Convert r to integer mod P.
874 fieldR := modNScalarToField(&r)
875 // Step 3.
876 //
877 // If pubkey recovery code overflow bit is set:
878 if pubKeyRecoveryCode&pubKeyRecoveryCodeOverflowBit != 0 {
879 // Step 3.1.
880 //
881 // Fail if r + N >= P
882 //
883 // Either the signature or the recovery code must be invalid if the
884 // recovery code overflow bit is set and adding N to the R component
885 // would exceed the field prime since R originally came from the X
886 // coordinate of a random point on the curve.
887 if fieldR.IsGtOrEqPrimeMinusOrder() {
888 str := "invalid signature: signature R + N >= P"
889 return nil, false, signatureError(ErrSigOverflowsPrime, str)
890 }
891 // Step 3.2.
892 //
893 // r = r + N (mod P)
894 fieldR.Add(&orderAsFieldVal)
895 }
896 // Step 4.
897 //
898 // y = +sqrt(r^3 + 7) (mod P)
899 // Fail if y does not exist.
900 // y = -y if needed to match pubkey recovery code oddness bit
901 //
902 // The signature must be invalid if the calculation fails because the X
903 // coord originally came from a random point on the curve which means there
904 // must be a Y coord that satisfies the equation for a valid signature.
905 oddY := pubKeyRecoveryCode&pubKeyRecoveryCodeOddnessBit != 0
906 var y secp256k1.FieldVal
907 if valid := secp256k1.DecompressY(&fieldR, oddY, &y); !valid {
908 str := "invalid signature: not for a valid curve point"
909 return nil, false, signatureError(ErrPointNotOnCurve, str)
910 }
911 // Step 5.
912 //
913 // X = (r, y)
914 var X secp256k1.JacobianPoint
915 X.X.Set(fieldR.Normalize())
916 X.Y.Set(y.Normalize())
917 X.Z.SetInt(1)
918 // Step 6.
919 //
920 // e = H(m) mod N
921 var e secp256k1.ModNScalar
922 e.SetByteSlice(hash)
923 // Step 7.
924 //
925 // w = r^-1 mod N
926 w := (&secp256k1.ModNScalar{}).InverseValNonConst(&r)
927 // Step 8.
928 //
929 // u1 = -(e * w) mod N
930 // u2 = s * w mod N
931 u1 := (&secp256k1.ModNScalar{}).Mul2(&e, w).Negate()
932 u2 := (&secp256k1.ModNScalar{}).Mul2(&s, w)
933 // Step 9.
934 //
935 // Q = u1G + u2X
936 var Q, u1G, u2X secp256k1.JacobianPoint
937 secp256k1.ScalarBaseMultNonConst(u1, &u1G)
938 secp256k1.ScalarMultNonConst(u2, &X, &u2X)
939 secp256k1.AddNonConst(&u1G, &u2X, &Q)
940 // Step 10.
941 //
942 // Fail if Q is the point at infinity.
943 //
944 // Either the signature or the pubkey recovery code must be invalid if the
945 // recovered pubkey is the point at infinity.
946 if (Q.X.IsZero() && Q.Y.IsZero()) || Q.Z.IsZero() {
947 str := "invalid signature: recovered pubkey is the point at infinity"
948 return nil, false, signatureError(ErrPointNotOnCurve, str)
949 }
950 // Notice that the public key is in affine coordinates.
951 Q.ToAffine()
952 pubKey := secp256k1.NewPublicKey(&Q.X, &Q.Y)
953 return pubKey, wasCompressed, nil
954 }
955