From d641f4566f051656bae79e406155c4f7f65ec338 Mon Sep 17 00:00:00 2001 From: Clawd Date: Fri, 20 Feb 2026 18:52:08 -0800 Subject: embed secp256k1: replace btcec with internal pure-go implementation This removes all external dependencies by embedding the secp256k1-learn implementation into internal/secp256k1. Changes: - Add internal/secp256k1 with field arithmetic, curve ops, keys, schnorr - Update keys.go to use internal secp256k1 package - Remove btcec/btcutil dependencies (go.mod is now clean) - All tests pass Tradeoffs: - ~10x slower crypto ops vs btcec (acceptable for nostr use case) - Not constant-time (documented limitation) - Zero external dependencies Refs: code.northwest.io/secp256k1-learn --- internal/secp256k1/schnorr.go | 236 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 236 insertions(+) create mode 100644 internal/secp256k1/schnorr.go (limited to 'internal/secp256k1/schnorr.go') diff --git a/internal/secp256k1/schnorr.go b/internal/secp256k1/schnorr.go new file mode 100644 index 0000000..ae7fa75 --- /dev/null +++ b/internal/secp256k1/schnorr.go @@ -0,0 +1,236 @@ +package secp256k1 + +import ( + "crypto/sha256" + "fmt" + "math/big" +) + +// Signature represents a Schnorr signature (r, s) +// r is the x-coordinate of R (32 bytes) +// s is the scalar response (32 bytes) +type Signature struct { + R *big.Int // x-coordinate of the nonce point + S *big.Int // the response scalar +} + +// TaggedHash computes SHA256(SHA256(tag) || SHA256(tag) || msg) +// This is BIP-340's domain separation technique +func TaggedHash(tag string, data ...[]byte) []byte { + tagHash := sha256.Sum256([]byte(tag)) + h := sha256.New() + h.Write(tagHash[:]) + h.Write(tagHash[:]) + for _, d := range data { + h.Write(d) + } + return h.Sum(nil) +} + +// LiftX recovers a point from just its x-coordinate +// Returns the point with even y (BIP-340 convention) +func LiftX(x *big.Int) (*Point, error) { + // Check x is in valid range + if x.Sign() < 0 || x.Cmp(P) >= 0 { + return nil, fmt.Errorf("x out of range") + } + + // Compute y² = x³ + 7 + xFe := NewFieldElement(x) + ySquared := xFe.Square().Mul(xFe).Add(curveB) + + // Compute y = sqrt(y²) mod p + // For secp256k1, sqrt(a) = a^((p+1)/4) mod p + exp := new(big.Int).Add(P, big.NewInt(1)) + exp.Div(exp, big.NewInt(4)) + y := new(big.Int).Exp(ySquared.value, exp, P) + + // Verify it's actually a square root + ySquaredCheck := new(big.Int).Mul(y, y) + ySquaredCheck.Mod(ySquaredCheck, P) + if ySquaredCheck.Cmp(ySquared.value) != 0 { + return nil, fmt.Errorf("x is not on the curve") + } + + // BIP-340: use the even y + if y.Bit(0) == 1 { + y.Sub(P, y) + } + + return &Point{ + x: NewFieldElement(x), + y: NewFieldElement(y), + infinity: false, + }, nil +} + +// hasEvenY returns true if the point's y-coordinate is even +func hasEvenY(p *Point) bool { + if p.infinity { + return false + } + return p.y.value.Bit(0) == 0 +} + +// xOnlyBytes returns the 32-byte x-coordinate of a public key +func (pub *PublicKey) XOnlyBytes() []byte { + result := make([]byte, 32) + xBytes := pub.Point.x.value.Bytes() + copy(result[32-len(xBytes):], xBytes) + return result +} + +// Sign creates a Schnorr signature for a message +// Follows BIP-340 specification +// aux is optional auxiliary randomness (32 bytes); nil uses zeros +func Sign(priv *PrivateKey, message []byte, aux ...[]byte) (*Signature, error) { + // Get the public key point + P := G.ScalarMul(priv.D) + + // BIP-340: if P.y is odd, negate the private key + d := new(big.Int).Set(priv.D) + if !hasEvenY(P) { + d.Sub(N, d) + P = P.Negate() + } + + // Serialize public key x-coordinate (32 bytes) + pBytes := make([]byte, 32) + pxBytes := P.x.value.Bytes() + copy(pBytes[32-len(pxBytes):], pxBytes) + + // BIP-340 nonce generation: + // t = d XOR tagged_hash("BIP0340/aux", aux) + // k = tagged_hash("BIP0340/nonce", t || P || m) + // For deterministic signing, use aux = 32 zero bytes + dBytes := make([]byte, 32) + dBytesRaw := d.Bytes() + copy(dBytes[32-len(dBytesRaw):], dBytesRaw) + + // Use provided aux or default to 32 zero bytes + var auxBytes []byte + if len(aux) > 0 && len(aux[0]) == 32 { + auxBytes = aux[0] + } else { + auxBytes = make([]byte, 32) + } + auxHash := TaggedHash("BIP0340/aux", auxBytes) + + t := make([]byte, 32) + for i := 0; i < 32; i++ { + t[i] = dBytes[i] ^ auxHash[i] + } + + kHash := TaggedHash("BIP0340/nonce", t, pBytes, message) + k := new(big.Int).SetBytes(kHash) + k.Mod(k, N) + + // k cannot be zero (extremely unlikely) + if k.Sign() == 0 { + return nil, fmt.Errorf("nonce is zero") + } + + // R = k * G + R := G.ScalarMul(k) + + // BIP-340: if R.y is odd, negate k + if !hasEvenY(R) { + k.Sub(N, k) + R = R.Negate() + } + + // Serialize R.x (32 bytes) + rBytes := make([]byte, 32) + rxBytes := R.x.value.Bytes() + copy(rBytes[32-len(rxBytes):], rxBytes) + + // Compute challenge e = hash(R.x || P.x || m) + eHash := TaggedHash("BIP0340/challenge", rBytes, pBytes, message) + e := new(big.Int).SetBytes(eHash) + e.Mod(e, N) + + // Compute s = k + e * d (mod N) + s := new(big.Int).Mul(e, d) + s.Add(s, k) + s.Mod(s, N) + + return &Signature{ + R: R.x.value, + S: s, + }, nil +} + +// Verify checks if a Schnorr signature is valid +// Follows BIP-340 specification +func Verify(pub *PublicKey, message []byte, sig *Signature) bool { + // Check signature values are in range + if sig.R.Sign() < 0 || sig.R.Cmp(P) >= 0 { + return false + } + if sig.S.Sign() < 0 || sig.S.Cmp(N) >= 0 { + return false + } + + // Lift R from x-coordinate + R, err := LiftX(sig.R) + if err != nil { + return false + } + + // Get public key with even y + P := pub.Point + if !hasEvenY(P) { + P = P.Negate() + } + + // Serialize for hashing + rBytes := make([]byte, 32) + rxBytes := sig.R.Bytes() + copy(rBytes[32-len(rxBytes):], rxBytes) + + pBytes := make([]byte, 32) + pxBytes := P.x.value.Bytes() + copy(pBytes[32-len(pxBytes):], pxBytes) + + // Compute challenge e = hash(R.x || P.x || m) + eHash := TaggedHash("BIP0340/challenge", rBytes, pBytes, message) + e := new(big.Int).SetBytes(eHash) + e.Mod(e, N) + + // Verify: s*G == R + e*P + sG := G.ScalarMul(sig.S) + eP := P.ScalarMul(e) + expected := R.Add(eP) + + return sG.Equal(expected) +} + +// Bytes returns the signature as 64 bytes (r || s) +func (sig *Signature) Bytes() []byte { + result := make([]byte, 64) + + rBytes := sig.R.Bytes() + sBytes := sig.S.Bytes() + + copy(result[32-len(rBytes):32], rBytes) + copy(result[64-len(sBytes):64], sBytes) + + return result +} + +// SignatureFromBytes parses a 64-byte signature +func SignatureFromBytes(b []byte) (*Signature, error) { + if len(b) != 64 { + return nil, fmt.Errorf("signature must be 64 bytes") + } + + r := new(big.Int).SetBytes(b[:32]) + s := new(big.Int).SetBytes(b[32:]) + + return &Signature{R: r, S: s}, nil +} + +// Hex returns the signature as a 128-character hex string +func (sig *Signature) Hex() string { + return fmt.Sprintf("%x", sig.Bytes()) +} -- cgit v1.2.3