ecdsa.go raw
1 package p256k1
2
3 import (
4 "errors"
5 "unsafe"
6 )
7
8 // ECDSASignature represents an ECDSA signature
9 type ECDSASignature struct {
10 r, s Scalar
11 }
12
13 // ECDSASign creates an ECDSA signature for a message hash using a private key
14 func ECDSASign(sig *ECDSASignature, msghash32 []byte, seckey []byte) error {
15 if len(msghash32) != 32 {
16 return errors.New("message hash must be 32 bytes")
17 }
18 if len(seckey) != 32 {
19 return errors.New("private key must be 32 bytes")
20 }
21
22 // Parse secret key
23 var sec Scalar
24 if !sec.setB32Seckey(seckey) {
25 return errors.New("invalid private key")
26 }
27
28 // Parse message hash
29 var msg Scalar
30 msg.setB32(msghash32)
31
32 // Generate nonce using RFC6979
33 var nonceKey [64]byte
34 copy(nonceKey[:32], msghash32)
35 copy(nonceKey[32:], seckey)
36
37 rng := NewRFC6979HMACSHA256(nonceKey[:])
38 memclear(unsafe.Pointer(&nonceKey[0]), 64)
39
40 var nonceBytes [32]byte
41 rng.Generate(nonceBytes[:])
42
43 // Parse nonce
44 var nonce Scalar
45 if !nonce.setB32Seckey(nonceBytes[:]) {
46 // Retry with new nonce
47 rng.Generate(nonceBytes[:])
48 if !nonce.setB32Seckey(nonceBytes[:]) {
49 rng.Finalize()
50 rng.Clear()
51 return errors.New("nonce generation failed")
52 }
53 }
54 memclear(unsafe.Pointer(&nonceBytes[0]), 32)
55 rng.Finalize()
56 rng.Clear()
57
58 // Compute R = nonce * G
59 var rp GroupElementJacobian
60 EcmultGen(&rp, &nonce)
61
62 // Convert to affine
63 var r GroupElementAffine
64 r.setGEJ(&rp)
65 r.x.normalize()
66 r.y.normalize()
67
68 // Extract r = X(R) mod n
69 var rBytes [32]byte
70 r.x.getB32(rBytes[:])
71
72 sig.r.setB32(rBytes[:])
73 if sig.r.isZero() {
74 return errors.New("signature r is zero")
75 }
76
77 // Compute s = nonce^-1 * (msg + r * sec) mod n
78 var n Scalar
79 n.mul(&sig.r, &sec)
80 n.add(&n, &msg)
81
82 var nonceInv Scalar
83 nonceInv.inverse(&nonce)
84 sig.s.mul(&nonceInv, &n)
85
86 // Normalize to low-S
87 if sig.s.isHigh() {
88 sig.s.condNegate(1)
89 }
90
91 if sig.s.isZero() {
92 return errors.New("signature s is zero")
93 }
94
95 // Clear sensitive data
96 sec.clear()
97 msg.clear()
98 nonce.clear()
99 n.clear()
100 nonceInv.clear()
101 rp.clear()
102 r.clear()
103
104 return nil
105 }
106
107 // ECDSAVerify verifies an ECDSA signature against a message hash and public key
108 func ECDSAVerify(sig *ECDSASignature, msghash32 []byte, pubkey *PublicKey) bool {
109 if len(msghash32) != 32 {
110 return false
111 }
112
113 // Check signature components are non-zero
114 if sig.r.isZero() || sig.s.isZero() {
115 return false
116 }
117
118 // Reject high-S signatures (Bitcoin consensus rule BIP-146)
119 if sig.s.isHigh() {
120 return false
121 }
122
123 // Parse message hash
124 var msg Scalar
125 msg.setB32(msghash32)
126
127 // Load public key
128 var pubkeyPoint GroupElementAffine
129 pubkeyPoint.fromBytes(pubkey.data[:])
130 if pubkeyPoint.isInfinity() {
131 return false
132 }
133
134 // Compute s^-1 mod n
135 var sInv Scalar
136 sInv.inverse(&sig.s)
137
138 // Compute u1 = msg * s^-1 mod n
139 var u1 Scalar
140 u1.mul(&msg, &sInv)
141
142 // Compute u2 = r * s^-1 mod n
143 var u2 Scalar
144 u2.mul(&sig.r, &sInv)
145
146 // Compute R = u1*G + u2*P using combined Strauss algorithm
147 // This shares doublings between both multiplications for better performance
148 var pubkeyJac GroupElementJacobian
149 pubkeyJac.setGE(&pubkeyPoint)
150
151 var R GroupElementJacobian
152 EcmultCombined(&R, &pubkeyJac, &u2, &u1)
153
154 if R.isInfinity() {
155 return false
156 }
157
158 // Convert R to affine
159 var RAff GroupElementAffine
160 RAff.setGEJ(&R)
161 RAff.x.normalize()
162
163 // Extract X(R) mod n
164 var rBytes [32]byte
165 RAff.x.getB32(rBytes[:])
166
167 var computedR Scalar
168 computedR.setB32(rBytes[:])
169
170 // Compare r with X(R) mod n
171 return sig.r.equal(&computedR)
172 }
173
174 // ECDSASignatureCompact represents a compact 64-byte signature (r || s)
175 type ECDSASignatureCompact [64]byte
176
177 // ToCompact converts an ECDSA signature to compact format
178 func (sig *ECDSASignature) ToCompact() *ECDSASignatureCompact {
179 var compact ECDSASignatureCompact
180 sig.r.getB32(compact[:32])
181 sig.s.getB32(compact[32:])
182 return &compact
183 }
184
185 // FromCompact converts a compact signature to ECDSA signature format
186 func (sig *ECDSASignature) FromCompact(compact *ECDSASignatureCompact) error {
187 sig.r.setB32(compact[:32])
188 sig.s.setB32(compact[32:64])
189
190 if sig.r.isZero() || sig.s.isZero() {
191 return errors.New("invalid signature: r or s is zero")
192 }
193
194 return nil
195 }
196
197 // VerifyCompact verifies a compact signature
198 func ECDSAVerifyCompact(compact *ECDSASignatureCompact, msghash32 []byte, pubkey *PublicKey) bool {
199 var sig ECDSASignature
200 if err := sig.FromCompact(compact); err != nil {
201 return false
202 }
203 return ECDSAVerify(&sig, msghash32, pubkey)
204 }
205
206 // SignCompact creates a compact signature
207 func ECDSASignCompact(compact *ECDSASignatureCompact, msghash32 []byte, seckey []byte) error {
208 var sig ECDSASignature
209 if err := ECDSASign(&sig, msghash32, seckey); err != nil {
210 return err
211 }
212 *compact = *sig.ToCompact()
213 return nil
214 }
215
216 // SerializeDER serializes the signature in DER format
217 func (sig *ECDSASignature) SerializeDER() []byte {
218 var rBytes, sBytes [32]byte
219 sig.r.getB32(rBytes[:])
220 sig.s.getB32(sBytes[:])
221
222 // Remove leading zeros and add 0x00 prefix if high bit set
223 rStart := 0
224 for rStart < 31 && rBytes[rStart] == 0 {
225 rStart++
226 }
227 sStart := 0
228 for sStart < 31 && sBytes[sStart] == 0 {
229 sStart++
230 }
231
232 rLen := 32 - rStart
233 sLen := 32 - sStart
234
235 // Add 0x00 prefix if high bit is set (to keep number positive)
236 rPad := 0
237 if rBytes[rStart]&0x80 != 0 {
238 rPad = 1
239 }
240 sPad := 0
241 if sBytes[sStart]&0x80 != 0 {
242 sPad = 1
243 }
244
245 // DER format: 0x30 [total-len] 0x02 [r-len] [r] 0x02 [s-len] [s]
246 totalLen := 2 + rLen + rPad + 2 + sLen + sPad
247 der := make([]byte, 2+totalLen)
248
249 der[0] = 0x30
250 der[1] = byte(totalLen)
251
252 pos := 2
253 der[pos] = 0x02
254 der[pos+1] = byte(rLen + rPad)
255 pos += 2
256 if rPad == 1 {
257 der[pos] = 0x00
258 pos++
259 }
260 copy(der[pos:], rBytes[rStart:])
261 pos += rLen
262
263 der[pos] = 0x02
264 der[pos+1] = byte(sLen + sPad)
265 pos += 2
266 if sPad == 1 {
267 der[pos] = 0x00
268 pos++
269 }
270 copy(der[pos:], sBytes[sStart:])
271
272 return der
273 }
274
275 // ParseDER parses a DER-encoded signature
276 func (sig *ECDSASignature) ParseDER(der []byte) error {
277 if len(der) < 8 {
278 return errors.New("DER signature too short")
279 }
280 if der[0] != 0x30 {
281 return errors.New("invalid DER signature: expected 0x30")
282 }
283
284 totalLen := int(der[1])
285 if len(der) < 2+totalLen {
286 return errors.New("DER signature length mismatch")
287 }
288
289 pos := 2
290
291 // Parse R
292 if der[pos] != 0x02 {
293 return errors.New("invalid DER signature: expected 0x02 for R")
294 }
295 rLen := int(der[pos+1])
296 pos += 2
297 if pos+rLen > len(der) {
298 return errors.New("DER signature: R length overflow")
299 }
300
301 rBytes := der[pos : pos+rLen]
302 pos += rLen
303
304 // Skip leading zero if present
305 if len(rBytes) > 0 && rBytes[0] == 0x00 {
306 rBytes = rBytes[1:]
307 }
308 if len(rBytes) > 32 {
309 return errors.New("DER signature: R too large")
310 }
311
312 // Parse S
313 if pos >= len(der) || der[pos] != 0x02 {
314 return errors.New("invalid DER signature: expected 0x02 for S")
315 }
316 sLen := int(der[pos+1])
317 pos += 2
318 if pos+sLen > len(der) {
319 return errors.New("DER signature: S length overflow")
320 }
321
322 sBytes := der[pos : pos+sLen]
323
324 // Skip leading zero if present
325 if len(sBytes) > 0 && sBytes[0] == 0x00 {
326 sBytes = sBytes[1:]
327 }
328 if len(sBytes) > 32 {
329 return errors.New("DER signature: S too large")
330 }
331
332 // Pad to 32 bytes and set
333 var rPadded, sPadded [32]byte
334 copy(rPadded[32-len(rBytes):], rBytes)
335 copy(sPadded[32-len(sBytes):], sBytes)
336
337 sig.r.setB32(rPadded[:])
338 sig.s.setB32(sPadded[:])
339
340 if sig.r.isZero() || sig.s.isZero() {
341 return errors.New("invalid signature: r or s is zero")
342 }
343
344 return nil
345 }
346
347 // ECDSASignDER signs and returns a DER-encoded signature
348 func ECDSASignDER(msghash32 []byte, seckey []byte) ([]byte, error) {
349 var sig ECDSASignature
350 if err := ECDSASign(&sig, msghash32, seckey); err != nil {
351 return nil, err
352 }
353 return sig.SerializeDER(), nil
354 }
355
356 // ECDSAVerifyDER verifies a DER-encoded signature
357 func ECDSAVerifyDER(sigDER []byte, msghash32 []byte, pubkey *PublicKey) bool {
358 var sig ECDSASignature
359 if err := sig.ParseDER(sigDER); err != nil {
360 return false
361 }
362 return ECDSAVerify(&sig, msghash32, pubkey)
363 }
364
365 // GetR returns the R component of the signature
366 func (sig *ECDSASignature) GetR() []byte {
367 var r [32]byte
368 sig.r.getB32(r[:])
369 return r[:]
370 }
371
372 // GetS returns the S component of the signature
373 func (sig *ECDSASignature) GetS() []byte {
374 var s [32]byte
375 sig.s.getB32(s[:])
376 return s[:]
377 }
378
379 // IsLowS returns true if the S value is in the lower half of the curve order
380 func (sig *ECDSASignature) IsLowS() bool {
381 return !sig.s.isHigh()
382 }
383
384 // NormalizeLowS ensures the S value is in the lower half of the curve order
385 // This is required by Bitcoin's consensus rules (BIP-66/BIP-146)
386 func (sig *ECDSASignature) NormalizeLowS() {
387 if sig.s.isHigh() {
388 sig.s.condNegate(1)
389 }
390 }
391
392 // ECDSARecoverableSignature represents an ECDSA signature with recovery information
393 type ECDSARecoverableSignature struct {
394 r, s Scalar
395 recid int // Recovery ID (0-3)
396 }
397
398 // ECDSASignRecoverable creates an ECDSA signature with recovery ID
399 func ECDSASignRecoverable(sig *ECDSARecoverableSignature, msghash32 []byte, seckey []byte) error {
400 if len(msghash32) != 32 {
401 return errors.New("message hash must be 32 bytes")
402 }
403 if len(seckey) != 32 {
404 return errors.New("private key must be 32 bytes")
405 }
406
407 // Parse secret key
408 var sec Scalar
409 if !sec.setB32Seckey(seckey) {
410 return errors.New("invalid private key")
411 }
412
413 // Parse message hash
414 var msg Scalar
415 msg.setB32(msghash32)
416
417 // Generate nonce using RFC6979
418 var nonceKey [64]byte
419 copy(nonceKey[:32], msghash32)
420 copy(nonceKey[32:], seckey)
421
422 rng := NewRFC6979HMACSHA256(nonceKey[:])
423 memclear(unsafe.Pointer(&nonceKey[0]), 64)
424
425 var nonceBytes [32]byte
426 rng.Generate(nonceBytes[:])
427
428 // Parse nonce
429 var nonce Scalar
430 if !nonce.setB32Seckey(nonceBytes[:]) {
431 rng.Generate(nonceBytes[:])
432 if !nonce.setB32Seckey(nonceBytes[:]) {
433 rng.Finalize()
434 rng.Clear()
435 return errors.New("nonce generation failed")
436 }
437 }
438 memclear(unsafe.Pointer(&nonceBytes[0]), 32)
439 rng.Finalize()
440 rng.Clear()
441
442 // Compute R = nonce * G
443 var rp GroupElementJacobian
444 EcmultGen(&rp, &nonce)
445
446 // Convert to affine
447 var r GroupElementAffine
448 r.setGEJ(&rp)
449 r.x.normalize()
450 r.y.normalize()
451
452 // Determine recovery ID based on Y coordinate parity and overflow
453 sig.recid = 0
454 if r.y.isOdd() {
455 sig.recid |= 1
456 }
457
458 // Extract r = X(R) mod n
459 var rBytes [32]byte
460 r.x.getB32(rBytes[:])
461
462 sig.r.setB32(rBytes[:])
463
464 // Note: For secp256k1, the case where X(R) >= n is extremely rare (probability ~2^-128)
465 // We don't set bit 1 of recid here since the probability is negligible
466
467 if sig.r.isZero() {
468 return errors.New("signature r is zero")
469 }
470
471 // Compute s = nonce^-1 * (msg + r * sec) mod n
472 var n Scalar
473 n.mul(&sig.r, &sec)
474 n.add(&n, &msg)
475
476 var nonceInv Scalar
477 nonceInv.inverse(&nonce)
478 sig.s.mul(&nonceInv, &n)
479
480 // Normalize to low-S (flip recid bit 0 if we negate)
481 if sig.s.isHigh() {
482 sig.s.condNegate(1)
483 sig.recid ^= 1
484 }
485
486 if sig.s.isZero() {
487 return errors.New("signature s is zero")
488 }
489
490 // Clear sensitive data
491 sec.clear()
492 msg.clear()
493 nonce.clear()
494 n.clear()
495 nonceInv.clear()
496 rp.clear()
497 r.clear()
498
499 return nil
500 }
501
502 // ToCompact returns the 64-byte compact signature and recovery ID
503 func (sig *ECDSARecoverableSignature) ToCompact() ([]byte, int) {
504 compact := make([]byte, 64)
505 sig.r.getB32(compact[:32])
506 sig.s.getB32(compact[32:])
507 return compact, sig.recid
508 }
509
510 // FromCompact parses a compact signature with recovery ID
511 func (sig *ECDSARecoverableSignature) FromCompact(compact []byte, recid int) error {
512 if len(compact) != 64 {
513 return errors.New("compact signature must be 64 bytes")
514 }
515 if recid < 0 || recid > 3 {
516 return errors.New("recovery ID must be 0-3")
517 }
518
519 sig.r.setB32(compact[:32])
520 sig.s.setB32(compact[32:])
521 sig.recid = recid
522
523 if sig.r.isZero() || sig.s.isZero() {
524 return errors.New("invalid signature: r or s is zero")
525 }
526
527 return nil
528 }
529
530 // ECDSARecover recovers the public key from an ECDSA signature
531 func ECDSARecover(pubkey *PublicKey, sig *ECDSARecoverableSignature, msghash32 []byte) error {
532 if len(msghash32) != 32 {
533 return errors.New("message hash must be 32 bytes")
534 }
535
536 if sig.r.isZero() || sig.s.isZero() {
537 return errors.New("invalid signature")
538 }
539
540 if sig.recid < 0 || sig.recid > 3 {
541 return errors.New("invalid recovery ID")
542 }
543
544 // Parse message hash
545 var msg Scalar
546 msg.setB32(msghash32)
547
548 // Recover the X coordinate of R
549 var rBytes [32]byte
550 sig.r.getB32(rBytes[:])
551
552 // If recid bit 1 is set, we need to add n to r to get the X coordinate
553 // This is very rare for secp256k1 (probability ~2^-128)
554 var rx FieldElement
555 if err := rx.setB32(rBytes[:]); err != nil {
556 return errors.New("invalid r value")
557 }
558
559 if sig.recid&2 != 0 {
560 // Add the group order to rx (very rare case)
561 // For secp256k1, this means rx + n, but since n < p, we need to handle overflow
562 // In practice, this case almost never happens
563 return errors.New("recovery with overflow not implemented (extremely rare case)")
564 }
565
566 // Recover the Y coordinate from X
567 var rPoint GroupElementAffine
568 odd := (sig.recid & 1) != 0
569 if !rPoint.setXOVar(&rx, odd) {
570 return errors.New("failed to recover R point")
571 }
572
573 // Compute r^-1 mod n
574 var rInv Scalar
575 rInv.inverse(&sig.r)
576
577 // Compute u1 = -msg * r^-1 mod n
578 var u1 Scalar
579 u1.mul(&msg, &rInv)
580 u1.negate(&u1)
581
582 // Compute u2 = s * r^-1 mod n
583 var u2 Scalar
584 u2.mul(&sig.s, &rInv)
585
586 // Compute Q = u1*G + u2*R using combined Strauss algorithm
587 var rJac GroupElementJacobian
588 rJac.setGE(&rPoint)
589
590 var Q GroupElementJacobian
591 EcmultCombined(&Q, &rJac, &u2, &u1)
592
593 if Q.isInfinity() {
594 return errors.New("recovered point is infinity")
595 }
596
597 // Convert to affine and save to pubkey
598 var qAff GroupElementAffine
599 qAff.setGEJ(&Q)
600 qAff.x.normalize()
601 qAff.y.normalize()
602
603 pubkeySave(pubkey, &qAff)
604
605 return nil
606 }
607
608 // ECDSARecoverCompact is a convenience function to recover a public key from a compact signature
609 func ECDSARecoverCompact(pubkey *PublicKey, sig64 []byte, recid int, msghash32 []byte) error {
610 var sig ECDSARecoverableSignature
611 if err := sig.FromCompact(sig64, recid); err != nil {
612 return err
613 }
614 return ECDSARecover(pubkey, &sig, msghash32)
615 }
616
617