bip340.go raw
1 package secp256k1
2
3 import (
4 "crypto/rand"
5 "crypto/sha256"
6 "math/big"
7 )
8
9 // taggedHash implements the BIP-340 tagged hash:
10 // SHA256(SHA256(tag) || SHA256(tag) || parts...).
11 func taggedHash(tag string, parts ...[]byte) [32]byte {
12 th := sha256.Sum256([]byte(tag))
13 buf := make([]byte, 0, 64+96)
14 buf = append(buf, th[:]...)
15 buf = append(buf, th[:]...)
16 for _, p := range parts {
17 buf = append(buf, p...)
18 }
19 return sha256.Sum256(buf)
20 }
21
22 // challenge computes e = int(taggedHash("BIP0340/challenge", R.x || pubkey ||
23 // msg)) mod N.
24 func challenge(rx *big.Int, pub, msg []byte) *big.Int {
25 var rb [32]byte
26 rx.FillBytes(rb[:])
27 h := taggedHash("BIP0340/challenge", rb[:], pub, msg)
28 return new(big.Int).Mod(new(big.Int).SetBytes(h[:]), N)
29 }
30
31 // Verify reports whether sig is a valid BIP-340 signature of the 32-byte msg
32 // under the x-only public key pub. Nostr event IDs are always 32 bytes, so
33 // this is the fast path.
34 func Verify(pub [32]byte, msg [32]byte, sig [64]byte) bool {
35 return verifyFast(pub, msg, sig)
36 }
37
38 // VerifyMsg is Verify for an arbitrary-length message. BIP-340 hashes the
39 // message as-is. The 32-byte case, which is the only one Nostr needs, uses the
40 // fast implementation; other lengths use the math/big reference below.
41 func VerifyMsg(pub [32]byte, msg []byte, sig [64]byte) bool {
42 if len(msg) == 32 {
43 var m [32]byte
44 copy(m[:], msg)
45 return verifyFast(pub, m, sig)
46 }
47 return verifySlowMsg(pub, msg, sig)
48 }
49
50 // verifySlowMsg is the math/big BIP-340 verifier. It remains the reference for
51 // arbitrary-length messages and the independent cross-check for the fast path.
52 func verifySlowMsg(pub [32]byte, msg []byte, sig [64]byte) bool {
53 px := new(big.Int).SetBytes(pub[:])
54 pubPoint := liftX(px)
55 if pubPoint == nil {
56 return false
57 }
58 r := new(big.Int).SetBytes(sig[:32])
59 s := new(big.Int).SetBytes(sig[32:])
60 if r.Cmp(P) >= 0 || s.Cmp(N) >= 0 {
61 return false
62 }
63 e := challenge(r, pub[:], msg[:])
64
65 // R = s*G - e*P = s*G + (N-e)*P.
66 sG := scalarMult(s, fromAffine(G))
67 ne := new(big.Int).Sub(N, e)
68 eP := scalarMult(ne, fromAffine(*pubPoint))
69 R := add(sG, eP)
70 if R.isInfinity() {
71 return false
72 }
73 ra := toAffine(R)
74 if ra.y.Bit(0) == 1 {
75 return false
76 }
77 return ra.x.Cmp(r) == 0
78 }
79
80 // PubKey returns the x-only public key for a secret key.
81 func PubKey(sk [32]byte) ([32]byte, bool) {
82 var out [32]byte
83 d := new(big.Int).SetBytes(sk[:])
84 if d.Sign() == 0 || d.Cmp(N) >= 0 {
85 return out, false
86 }
87 P := scalarMult(d, fromAffine(G))
88 if P.isInfinity() {
89 return out, false
90 }
91 toAffine(P).x.FillBytes(out[:])
92 return out, true
93 }
94
95 // Sign produces a BIP-340 signature using fresh auxiliary randomness.
96 func Sign(sk [32]byte, msg [32]byte) ([64]byte, bool) {
97 return SignMsg(sk, msg[:])
98 }
99
100 // SignMsg is Sign for an arbitrary-length message.
101 func SignMsg(sk [32]byte, msg []byte) ([64]byte, bool) {
102 var aux [32]byte
103 if _, err := rand.Read(aux[:]); err != nil {
104 // A zero aux_rand is valid BIP-340; it makes the nonce deterministic.
105 aux = [32]byte{}
106 }
107 if len(msg) == 32 {
108 var m [32]byte
109 copy(m[:], msg)
110 return signFastWithAux(sk, m, aux)
111 }
112 return signSlowAuxMsg(sk, msg, aux)
113 }
114
115 // SignAux produces a BIP-340 signature with an explicit aux_rand value. It is
116 // what the official test vectors exercise.
117 func SignAux(sk [32]byte, msg [32]byte, aux [32]byte) ([64]byte, bool) {
118 return SignAuxMsg(sk, msg[:], aux)
119 }
120
121 // SignAuxMsg is SignAux for an arbitrary-length message.
122 func SignAuxMsg(sk [32]byte, msg []byte, aux [32]byte) ([64]byte, bool) {
123 if len(msg) == 32 {
124 var m [32]byte
125 copy(m[:], msg)
126 return signFastWithAux(sk, m, aux)
127 }
128 return signSlowAuxMsg(sk, msg, aux)
129 }
130
131 // signSlowAuxMsg is the math/big signer. It reproduces the official vectors for
132 // every message length and cross-checks the fast signer in tests.
133 func signSlowAuxMsg(sk [32]byte, msg []byte, aux [32]byte) ([64]byte, bool) {
134 var sig [64]byte
135 d0 := new(big.Int).SetBytes(sk[:])
136 if d0.Sign() == 0 || d0.Cmp(N) >= 0 {
137 return sig, false
138 }
139
140 Pp := scalarMult(d0, fromAffine(G))
141 if Pp.isInfinity() {
142 return sig, false
143 }
144 Pa := toAffine(Pp)
145
146 var pub [32]byte
147 Pa.x.FillBytes(pub[:])
148
149 // The secret key is negated when P has odd y, so that the effective
150 // public key is the even-y lift that BIP-340 specifies.
151 d := d0
152 if Pa.y.Bit(0) == 1 {
153 d = new(big.Int).Sub(N, d0)
154 }
155
156 ah := taggedHash("BIP0340/aux", aux[:])
157 var db [32]byte
158 d.FillBytes(db[:])
159 var t [32]byte
160 for i := range t {
161 t[i] = db[i] ^ ah[i]
162 }
163
164 nh := taggedHash("BIP0340/nonce", t[:], pub[:], msg)
165 k0 := new(big.Int).Mod(new(big.Int).SetBytes(nh[:]), N)
166 if k0.Sign() == 0 {
167 return sig, false
168 }
169 R := scalarMult(k0, fromAffine(G))
170 if R.isInfinity() {
171 return sig, false
172 }
173 Ra := toAffine(R)
174 k := k0
175 if Ra.y.Bit(0) == 1 {
176 k = new(big.Int).Sub(N, k0)
177 }
178 e := challenge(Ra.x, pub[:], msg[:])
179 s := new(big.Int).Mod(new(big.Int).Add(k, new(big.Int).Mul(e, d)), N)
180 Ra.x.FillBytes(sig[:32])
181 s.FillBytes(sig[32:])
182
183 // Self-check: never emit a signature that would be rejected.
184 if !verifySlowMsg(pub, msg, sig) {
185 return sig, false
186 }
187 return sig, true
188 }
189