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 secp256k1
7 8 import (
9 "bytes"
10 "crypto/sha256"
11 "hash"
12 )
13 14 // References:
15 // [GECC]: Guide to Elliptic Curve Cryptography (Hankerson, Menezes, Vanstone)
16 //
17 // [ISO/IEC 8825-1]: Information technology — ASN.1 encoding rules:
18 // Specification of Basic Encoding Rules (BER), Canonical Encoding Rules
19 // (CER) and Distinguished Encoding Rules (DER)
20 //
21 // [SEC1]: Elliptic Curve Cryptography (May 31, 2009, Version 2.0)
22 // https://www.secg.org/sec1-v2.pdf
23 24 var (
25 // singleZero is used during RFC6979 nonce generation. It is provided
26 // here to avoid the need to create it multiple times.
27 singleZero = []byte{0x00}
28 29 // zeroInitializer is used during RFC6979 nonce generation. It is provided
30 // here to avoid the need to create it multiple times.
31 zeroInitializer = bytes.Repeat([]byte{0x00}, sha256.BlockSize)
32 33 // singleOne is used during RFC6979 nonce generation. It is provided
34 // here to avoid the need to create it multiple times.
35 singleOne = []byte{0x01}
36 37 // oneInitializer is used during RFC6979 nonce generation. It is provided
38 // here to avoid the need to create it multiple times.
39 oneInitializer = bytes.Repeat([]byte{0x01}, sha256.Size)
40 )
41 42 // hmacsha256 implements a resettable version of HMAC-SHA256.
43 type hmacsha256 struct {
44 inner, outer hash.Hash
45 ipad, opad [sha256.BlockSize]byte
46 }
47 48 // Write adds data to the running hash.
49 func (h *hmacsha256) Write(p []byte) {
50 h.inner.Write(p)
51 }
52 53 // initKey initializes the HMAC-SHA256 instance to the provided key.
54 func (h *hmacsha256) initKey(key []byte) {
55 // Hash the key if it is too large.
56 if len(key) > sha256.BlockSize {
57 h.outer.Write(key)
58 key = h.outer.Sum(nil)
59 }
60 copy(h.ipad[:], key)
61 copy(h.opad[:], key)
62 for i := range h.ipad {
63 h.ipad[i] ^= 0x36
64 }
65 for i := range h.opad {
66 h.opad[i] ^= 0x5c
67 }
68 h.inner.Write(h.ipad[:])
69 }
70 71 // ResetKey resets the HMAC-SHA256 to its initial state and then initializes it
72 // with the provided key. It is equivalent to creating a new instance with the
73 // provided key without allocating more memory.
74 func (h *hmacsha256) ResetKey(key []byte) {
75 h.inner.Reset()
76 h.outer.Reset()
77 copy(h.ipad[:], zeroInitializer)
78 copy(h.opad[:], zeroInitializer)
79 h.initKey(key)
80 }
81 82 // Resets the HMAC-SHA256 to its initial state using the current key.
83 func (h *hmacsha256) Reset() {
84 h.inner.Reset()
85 h.inner.Write(h.ipad[:])
86 }
87 88 // Sum returns the hash of the written data.
89 func (h *hmacsha256) Sum() []byte {
90 h.outer.Reset()
91 h.outer.Write(h.opad[:])
92 h.outer.Write(h.inner.Sum(nil))
93 return h.outer.Sum(nil)
94 }
95 96 // newHMACSHA256 returns a new HMAC-SHA256 hasher using the provided key.
97 func newHMACSHA256(key []byte) *hmacsha256 {
98 h := new(hmacsha256)
99 h.inner = sha256.New()
100 h.outer = sha256.New()
101 h.initKey(key)
102 return h
103 }
104 105 // NonceRFC6979 generates a nonce deterministically according to RFC 6979 using
106 // HMAC-SHA256 for the hashing function. It takes a 32-byte hash as an input
107 // and returns a 32-byte nonce to be used for deterministic signing. The extra
108 // and version arguments are optional, but allow additional data to be added to
109 // the input of the HMAC. When provided, the extra data must be 32-bytes and
110 // version must be 16 bytes or they will be ignored.
111 //
112 // Finally, the extraIterations parameter provides a method to produce a stream
113 // of deterministic nonces to ensure the signing code is able to produce a nonce
114 // that results in a valid signature in the extremely unlikely event the
115 // original nonce produced results in an invalid signature (e.g. R == 0).
116 // Signing code should start with 0 and increment it if necessary.
117 func NonceRFC6979(privKey []byte, hash []byte, extra []byte, version []byte, extraIterations uint32) *ModNScalar {
118 // Input to HMAC is the 32-byte private key and the 32-byte hash. In
119 // addition, it may include the optional 32-byte extra data and 16-byte
120 // version. Create a fixed-size array to avoid extra allocs and slice it
121 // properly.
122 const (
123 privKeyLen = 32
124 hashLen = 32
125 extraLen = 32
126 versionLen = 16
127 )
128 var keyBuf [privKeyLen + hashLen + extraLen + versionLen]byte
129 130 // Truncate rightmost bytes of private key and hash if they are too long and
131 // leave left padding of zeros when they're too short.
132 if len(privKey) > privKeyLen {
133 privKey = privKey[:privKeyLen]
134 }
135 if len(hash) > hashLen {
136 hash = hash[:hashLen]
137 }
138 offset := privKeyLen - len(privKey) // Zero left padding if needed.
139 offset += copy(keyBuf[offset:], privKey)
140 offset += hashLen - len(hash) // Zero left padding if needed.
141 offset += copy(keyBuf[offset:], hash)
142 if len(extra) == extraLen {
143 offset += copy(keyBuf[offset:], extra)
144 if len(version) == versionLen {
145 offset += copy(keyBuf[offset:], version)
146 }
147 } else if len(version) == versionLen {
148 // When the version was specified, but not the extra data, leave the
149 // extra data portion all zero.
150 offset += privKeyLen
151 offset += copy(keyBuf[offset:], version)
152 }
153 key := keyBuf[:offset]
154 155 // Step B.
156 //
157 // V = 0x01 0x01 0x01 ... 0x01 such that the length of V, in bits, is
158 // equal to 8*ceil(hashLen/8).
159 //
160 // Note that since the hash length is a multiple of 8 for the chosen hash
161 // function in this optimized implementation, the result is just the hash
162 // length, so avoid the extra calculations. Also, since it isn't modified,
163 // start with a global value.
164 v := oneInitializer
165 166 // Step C (Go zeroes all allocated memory).
167 //
168 // K = 0x00 0x00 0x00 ... 0x00 such that the length of K, in bits, is
169 // equal to 8*ceil(hashLen/8).
170 //
171 // As above, since the hash length is a multiple of 8 for the chosen hash
172 // function in this optimized implementation, the result is just the hash
173 // length, so avoid the extra calculations.
174 k := zeroInitializer[:hashLen]
175 176 // Step D.
177 //
178 // K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1))
179 //
180 // Note that key is the "int2octets(x) || bits2octets(h1)" portion along
181 // with potential additional data as described by section 3.6 of the RFC.
182 hasher := newHMACSHA256(k)
183 hasher.Write(oneInitializer)
184 hasher.Write(singleZero)
185 hasher.Write(key)
186 k = hasher.Sum()
187 188 // Step E.
189 //
190 // V = HMAC_K(V)
191 hasher.ResetKey(k)
192 hasher.Write(v)
193 v = hasher.Sum()
194 195 // Step F.
196 //
197 // K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1))
198 //
199 // Note that key is the "int2octets(x) || bits2octets(h1)" portion along
200 // with potential additional data as described by section 3.6 of the RFC.
201 hasher.Reset()
202 hasher.Write(v)
203 hasher.Write(singleOne)
204 hasher.Write(key)
205 k = hasher.Sum()
206 207 // Step G.
208 //
209 // V = HMAC_K(V)
210 hasher.ResetKey(k)
211 hasher.Write(v)
212 v = hasher.Sum()
213 214 // Step H.
215 //
216 // Repeat until the value is nonzero and less than the curve order.
217 var generated uint32
218 for {
219 // Step H1 and H2.
220 //
221 // Set T to the empty sequence. The length of T (in bits) is denoted
222 // tlen; thus, at that point, tlen = 0.
223 //
224 // While tlen < qlen, do the following:
225 // V = HMAC_K(V)
226 // T = T || V
227 //
228 // Note that because the hash function output is the same length as the
229 // private key in this optimized implementation, there is no need to
230 // loop or create an intermediate T.
231 hasher.Reset()
232 hasher.Write(v)
233 v = hasher.Sum()
234 235 // Step H3.
236 //
237 // k = bits2int(T)
238 // If k is within the range [1,q-1], return it.
239 //
240 // Otherwise, compute:
241 // K = HMAC_K(V || 0x00)
242 // V = HMAC_K(V)
243 var secret ModNScalar
244 overflow := secret.SetByteSlice(v)
245 if !overflow && !secret.IsZero() {
246 generated++
247 if generated > extraIterations {
248 return &secret
249 }
250 }
251 252 // K = HMAC_K(V || 0x00)
253 hasher.Reset()
254 hasher.Write(v)
255 hasher.Write(singleZero)
256 k = hasher.Sum()
257 258 // V = HMAC_K(V)
259 hasher.ResetKey(k)
260 hasher.Write(v)
261 v = hasher.Sum()
262 }
263 }
264