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