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