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