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 schnorr 7 8 import ( 9 "fmt" 10 11 "github.com/decred/dcrd/crypto/blake256" 12 "github.com/decred/dcrd/dcrec/secp256k1/v4" 13 ) 14 15 const ( 16 // SignatureSize is the size of an encoded Schnorr signature. 17 SignatureSize = 64 18 19 // scalarSize is the size of an encoded big endian scalar. 20 scalarSize = 32 21 ) 22 23 var ( 24 // rfc6979ExtraDataV0 is the extra data to feed to RFC6979 when generating 25 // the deterministic nonce for the EC-Schnorr-DCRv0 scheme. This ensures 26 // the same nonce is not generated for the same message and key as for other 27 // signing algorithms such as ECDSA. 28 // 29 // It is equal to BLAKE-256([]byte("EC-Schnorr-DCRv0")). 30 rfc6979ExtraDataV0 = [32]byte{ 31 0x0b, 0x75, 0xf9, 0x7b, 0x60, 0xe8, 0xa5, 0x76, 32 0x28, 0x76, 0xc0, 0x04, 0x82, 0x9e, 0xe9, 0xb9, 33 0x26, 0xfa, 0x6f, 0x0d, 0x2e, 0xea, 0xec, 0x3a, 34 0x4f, 0xd1, 0x44, 0x6a, 0x76, 0x83, 0x31, 0xcb, 35 } 36 ) 37 38 // Signature is a type representing a Schnorr signature. 39 type Signature struct { 40 r secp256k1.FieldVal 41 s secp256k1.ModNScalar 42 } 43 44 // NewSignature instantiates a new signature given some r and s values. 45 func NewSignature(r *secp256k1.FieldVal, s *secp256k1.ModNScalar) *Signature { 46 var sig Signature 47 sig.r.Set(r).Normalize() 48 sig.s.Set(s) 49 return &sig 50 } 51 52 // Serialize returns the Schnorr signature in the more strict format. 53 // 54 // The signatures are encoded as: 55 // 56 // sig[0:32] x coordinate of the point R, encoded as a big-endian uint256 57 // sig[32:64] s, encoded also as big-endian uint256 58 func (sig Signature) Serialize() []byte { 59 // Total length of returned signature is the length of r and s. 60 var b [SignatureSize]byte 61 sig.r.PutBytesUnchecked(b[0:32]) 62 sig.s.PutBytesUnchecked(b[32:64]) 63 return b[:] 64 } 65 66 // ParseSignature parses a signature according to the EC-Schnorr-DCRv0 67 // specification and enforces the following additional restrictions specific to 68 // secp256k1: 69 // 70 // - The r component must be in the valid range for secp256k1 field elements 71 // - The s component must be in the valid range for secp256k1 scalars 72 func ParseSignature(sig []byte) (*Signature, error) { 73 // The signature must be the correct length. 74 sigLen := len(sig) 75 if sigLen < SignatureSize { 76 str := fmt.Sprintf("malformed signature: too short: %d < %d", sigLen, 77 SignatureSize) 78 return nil, signatureError(ErrSigTooShort, str) 79 } 80 if sigLen > SignatureSize { 81 str := fmt.Sprintf("malformed signature: too long: %d > %d", sigLen, 82 SignatureSize) 83 return nil, signatureError(ErrSigTooLong, str) 84 } 85 86 // The signature is validly encoded at this point, however, enforce 87 // additional restrictions to ensure r is in the range [0, p-1], and s is in 88 // the range [0, n-1] since valid Schnorr signatures are required to be in 89 // that range per spec. 90 var r secp256k1.FieldVal 91 if overflow := r.SetByteSlice(sig[0:32]); overflow { 92 str := "invalid signature: r >= field prime" 93 return nil, signatureError(ErrSigRTooBig, str) 94 } 95 var s secp256k1.ModNScalar 96 if overflow := s.SetByteSlice(sig[32:64]); overflow { 97 str := "invalid signature: s >= group order" 98 return nil, signatureError(ErrSigSTooBig, str) 99 } 100 101 // Return the signature. 102 return NewSignature(&r, &s), nil 103 } 104 105 // IsEqual compares this Signature instance to the one passed, returning true 106 // if both Signatures are equivalent. A signature is equivalent to another, if 107 // they both have the same scalar value for R and S. 108 func (sig Signature) IsEqual(otherSig *Signature) bool { 109 return sig.r.Equals(&otherSig.r) && sig.s.Equals(&otherSig.s) 110 } 111 112 // schnorrVerify attempt to verify the signature for the provided hash and 113 // secp256k1 public key and either returns nil if successful or a specific error 114 // indicating why it failed if not successful. 115 // 116 // This differs from the exported Verify method in that it returns a specific 117 // error to support better testing while the exported method simply returns a 118 // bool indicating success or failure. 119 func schnorrVerify(sig *Signature, hash []byte, pubKey *secp256k1.PublicKey) error { 120 // The algorithm for producing a EC-Schnorr-DCRv0 signature is described in 121 // README.md and is reproduced here for reference: 122 // 123 // 124 // 1. Fail if m is not 32 bytes 125 // 2. Fail if Q is not a point on the curve 126 // 3. Fail if r >= p 127 // 4. Fail if s >= n 128 // 5. e = BLAKE-256(r || m) (Ensure r is padded to 32 bytes) 129 // 6. Fail if e >= n 130 // 7. R = s*G + e*Q 131 // 8. Fail if R is the point at infinity 132 // 9. Fail if R.y is odd 133 // 10. Verified if R.x == r 134 135 // Step 1. 136 // 137 // Fail if m is not 32 bytes 138 if len(hash) != scalarSize { 139 str := fmt.Sprintf("wrong size for message (got %v, want %v)", 140 len(hash), scalarSize) 141 return signatureError(ErrInvalidHashLen, str) 142 } 143 144 // Step 2. 145 // 146 // Fail if Q is not a point on the curve 147 if !pubKey.IsOnCurve() { 148 str := "pubkey point is not on curve" 149 return signatureError(ErrPubKeyNotOnCurve, str) 150 } 151 152 // Step 3. 153 // 154 // Fail if r >= p 155 // 156 // Note this is already handled by the fact r is a field element. 157 158 // Step 4. 159 // 160 // Fail if s >= n 161 // 162 // Note this is already handled by the fact s is a mod n scalar. 163 164 // Step 5. 165 // 166 // e = BLAKE-256(r || m) (Ensure r is padded to 32 bytes) 167 var commitmentInput [scalarSize * 2]byte 168 sig.r.PutBytesUnchecked(commitmentInput[0:scalarSize]) 169 copy(commitmentInput[scalarSize:], hash[:]) 170 commitment := blake256.Sum256(commitmentInput[:]) 171 172 // Step 6. 173 // 174 // Fail if e >= n 175 var e secp256k1.ModNScalar 176 if overflow := e.SetBytes(&commitment); overflow != 0 { 177 str := "hash of (R || m) too big" 178 return signatureError(ErrSchnorrHashValue, str) 179 } 180 181 // Step 7. 182 // 183 // R = s*G + e*Q 184 var Q, R, sG, eQ secp256k1.JacobianPoint 185 pubKey.AsJacobian(&Q) 186 secp256k1.ScalarBaseMultNonConst(&sig.s, &sG) 187 secp256k1.ScalarMultNonConst(&e, &Q, &eQ) 188 secp256k1.AddNonConst(&sG, &eQ, &R) 189 190 // Step 8. 191 // 192 // Fail if R is the point at infinity 193 if (R.X.IsZero() && R.Y.IsZero()) || R.Z.IsZero() { 194 str := "calculated R point is the point at infinity" 195 return signatureError(ErrSigRNotOnCurve, str) 196 } 197 198 // Step 9. 199 // 200 // Fail if R.y is odd 201 // 202 // Note that R must be in affine coordinates for this check. 203 R.ToAffine() 204 if R.Y.IsOdd() { 205 str := "calculated R y-value is odd" 206 return signatureError(ErrSigRYIsOdd, str) 207 } 208 209 // Step 10. 210 // 211 // Verified if R.x == r 212 // 213 // Note that R must be in affine coordinates for this check. 214 if !sig.r.Equals(&R.X) { 215 str := "calculated R point was not given R" 216 return signatureError(ErrUnequalRValues, str) 217 } 218 219 return nil 220 } 221 222 // Verify returns whether or not the signature is valid for the provided hash 223 // and secp256k1 public key. 224 func (sig *Signature) Verify(hash []byte, pubKey *secp256k1.PublicKey) bool { 225 return schnorrVerify(sig, hash, pubKey) == nil 226 } 227 228 // zeroArray zeroes the memory of a scalar array. 229 func zeroArray(a *[scalarSize]byte) { 230 for i := 0; i < scalarSize; i++ { 231 a[i] = 0x00 232 } 233 } 234 235 // schnorrSign generates an EC-Schnorr-DCRv0 signature over the secp256k1 curve 236 // for the provided hash (which should be the result of hashing a larger 237 // message) using the given nonce and private key. The produced signature is 238 // deterministic (same message, nonce, and key yield the same signature) and 239 // canonical. 240 // 241 // WARNING: The hash MUST be 32 bytes and both the nonce and private keys must 242 // NOT be 0. Since this is an internal use function, these preconditions MUST 243 // be satisified by the caller. 244 func schnorrSign(privKey, nonce *secp256k1.ModNScalar, hash []byte) (*Signature, error) { 245 // The algorithm for producing a EC-Schnorr-DCRv0 signature is described in 246 // README.md and is reproduced here for reference: 247 // 248 // G = curve generator 249 // n = curve order 250 // d = private key 251 // m = message 252 // r, s = signature 253 // 254 // 1. Fail if m is not 32 bytes 255 // 2. Fail if d = 0 or d >= n 256 // 3. Use RFC6979 to generate a deterministic nonce k in [1, n-1] 257 // parameterized by the private key, message being signed, extra data 258 // that identifies the scheme, and an iteration count 259 // 4. R = kG 260 // 5. Negate nonce k if R.y is odd (R.y is the y coordinate of the point R) 261 // 6. r = R.x (R.x is the x coordinate of the point R) 262 // 7. e = BLAKE-256(r || m) (Ensure r is padded to 32 bytes) 263 // 8. Repeat from step 3 (with iteration + 1) if e >= n 264 // 9. s = k - e*d mod n 265 // 10. Return (r, s) 266 267 // NOTE: Steps 1-3 are performed by the caller. 268 // 269 // Step 4. 270 // 271 // R = kG 272 var R secp256k1.JacobianPoint 273 k := *nonce 274 secp256k1.ScalarBaseMultNonConst(&k, &R) 275 276 // Step 5. 277 // 278 // Negate nonce k if R.y is odd (R.y is the y coordinate of the point R) 279 // 280 // Note that R must be in affine coordinates for this check. 281 R.ToAffine() 282 if R.Y.IsOdd() { 283 k.Negate() 284 } 285 286 // Step 6. 287 // 288 // r = R.x (R.x is the x coordinate of the point R) 289 r := &R.X 290 291 // Step 7. 292 // 293 // e = BLAKE-256(r || m) (Ensure r is padded to 32 bytes) 294 var commitmentInput [scalarSize * 2]byte 295 r.PutBytesUnchecked(commitmentInput[0:scalarSize]) 296 copy(commitmentInput[scalarSize:], hash[:]) 297 commitment := blake256.Sum256(commitmentInput[:]) 298 299 // Step 8. 300 // 301 // Repeat from step 1 (with iteration + 1) if e >= N 302 var e secp256k1.ModNScalar 303 if overflow := e.SetBytes(&commitment); overflow != 0 { 304 k.Zero() 305 str := "hash of (R || m) too big" 306 return nil, signatureError(ErrSchnorrHashValue, str) 307 } 308 309 // Step 9. 310 // 311 // s = k - e*d mod n 312 s := new(secp256k1.ModNScalar).Mul2(&e, privKey).Negate().Add(&k) 313 k.Zero() 314 315 // Step 10. 316 // 317 // Return (r, s) 318 return NewSignature(r, s), nil 319 } 320 321 // Sign generates an EC-Schnorr-DCRv0 signature over the secp256k1 curve for the 322 // provided hash (which should be the result of hashing a larger message) using 323 // the given private key. The produced signature is deterministic (same message 324 // and same key yield the same signature) and canonical. 325 // 326 // Note that the current signing implementation has a few remaining variable 327 // time aspects which make use of the private key and the generated nonce, which 328 // can expose the signer to constant time attacks. As a result, this function 329 // should not be used in situations where there is the possibility of someone 330 // having EM field/cache/etc access. 331 func Sign(privKey *secp256k1.PrivateKey, hash []byte) (*Signature, error) { 332 // The algorithm for producing a EC-Schnorr-DCRv0 signature is described in 333 // README.md and is reproduced here for reference: 334 // 335 // G = curve generator 336 // n = curve order 337 // d = private key 338 // m = message 339 // r, s = signature 340 // 341 // 1. Fail if m is not 32 bytes 342 // 2. Fail if d = 0 or d >= n 343 // 3. Use RFC6979 to generate a deterministic nonce k in [1, n-1] 344 // parameterized by the private key, message being signed, extra data 345 // that identifies the scheme, and an iteration count 346 // 4. R = kG 347 // 5. Negate nonce k if R.y is odd (R.y is the y coordinate of the point R) 348 // 6. r = R.x (R.x is the x coordinate of the point R) 349 // 7. e = BLAKE-256(r || m) (Ensure r is padded to 32 bytes) 350 // 8. Repeat from step 3 (with iteration + 1) if e >= n 351 // 9. s = k - e*d mod n 352 // 10. Return (r, s) 353 354 // Step 1. 355 // 356 // Fail if m is not 32 bytes 357 if len(hash) != scalarSize { 358 str := fmt.Sprintf("wrong size for message hash (got %v, want %v)", 359 len(hash), scalarSize) 360 return nil, signatureError(ErrInvalidHashLen, str) 361 } 362 363 // Step 2. 364 // 365 // Fail if d = 0 or d >= n 366 privKeyScalar := &privKey.Key 367 if privKeyScalar.IsZero() { 368 str := "private key is zero" 369 return nil, signatureError(ErrPrivateKeyIsZero, str) 370 } 371 372 var privKeyBytes [scalarSize]byte 373 privKeyScalar.PutBytes(&privKeyBytes) 374 defer zeroArray(&privKeyBytes) 375 for iteration := uint32(0); ; iteration++ { 376 // Step 3. 377 // 378 // Use RFC6979 to generate a deterministic nonce k in [1, n-1] 379 // parameterized by the private key, message being signed, extra data 380 // that identifies the scheme, and an iteration count 381 k := secp256k1.NonceRFC6979(privKeyBytes[:], hash, rfc6979ExtraDataV0[:], 382 nil, iteration) 383 384 // Steps 4-10. 385 sig, err := schnorrSign(privKeyScalar, k, hash) 386 k.Zero() 387 if err != nil { 388 // Try again with a new nonce. 389 continue 390 } 391 392 return sig, nil 393 } 394 } 395