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