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 "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 935 // Step 4. 936 // 937 // y = +sqrt(r^3 + 7) (mod P) 938 // Fail if y does not exist. 939 // y = -y if needed to match pubkey recovery code oddness bit 940 // 941 // The signature must be invalid if the calculation fails because the X 942 // coord originally came from a random point on the curve which means there 943 // must be a Y coord that satisfies the equation for a valid signature. 944 oddY := pubKeyRecoveryCode&pubKeyRecoveryCodeOddnessBit != 0 945 var y secp256k1.FieldVal 946 if valid := secp256k1.DecompressY(&fieldR, oddY, &y); !valid { 947 str := "invalid signature: not for a valid curve point" 948 return nil, false, signatureError(ErrPointNotOnCurve, str) 949 } 950 951 // Step 5. 952 // 953 // X = (r, y) 954 var X secp256k1.JacobianPoint 955 X.X.Set(fieldR.Normalize()) 956 X.Y.Set(y.Normalize()) 957 X.Z.SetInt(1) 958 959 // Step 6. 960 // 961 // e = H(m) mod N 962 var e secp256k1.ModNScalar 963 e.SetByteSlice(hash) 964 965 // Step 7. 966 // 967 // w = r^-1 mod N 968 w := new(secp256k1.ModNScalar).InverseValNonConst(&r) 969 970 // Step 8. 971 // 972 // u1 = -(e * w) mod N 973 // u2 = s * w mod N 974 u1 := new(secp256k1.ModNScalar).Mul2(&e, w).Negate() 975 u2 := new(secp256k1.ModNScalar).Mul2(&s, w) 976 977 // Step 9. 978 // 979 // Q = u1G + u2X 980 var Q, u1G, u2X secp256k1.JacobianPoint 981 secp256k1.ScalarBaseMultNonConst(u1, &u1G) 982 secp256k1.ScalarMultNonConst(u2, &X, &u2X) 983 secp256k1.AddNonConst(&u1G, &u2X, &Q) 984 985 // Step 10. 986 // 987 // Fail if Q is the point at infinity. 988 // 989 // Either the signature or the pubkey recovery code must be invalid if the 990 // recovered pubkey is the point at infinity. 991 if (Q.X.IsZero() && Q.Y.IsZero()) || Q.Z.IsZero() { 992 str := "invalid signature: recovered pubkey is the point at infinity" 993 return nil, false, signatureError(ErrPointNotOnCurve, str) 994 } 995 996 // Notice that the public key is in affine coordinates. 997 Q.ToAffine() 998 pubKey := secp256k1.NewPublicKey(&Q.X, &Q.Y) 999 return pubKey, wasCompressed, nil 1000 } 1001