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 "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