1// Package bip39 is the Golang implementation of the BIP39 spec. 2// 3// The official BIP39 spec can be found at 4// https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki 5package bip39 6 7import ( 8 "crypto/rand" 9 "crypto/sha256" 10 "crypto/sha512" 11 "encoding/binary" 12 "errors" 13 "fmt" 14 "math/big" 15 "strings" 16 17 "github.com/tyler-smith/go-bip39/wordlists" 18 "golang.org/x/crypto/pbkdf2" 19) 20 21var ( 22 // Some bitwise operands for working with big.Ints 23 last11BitsMask = big.NewInt(2047) 24 shift11BitsMask = big.NewInt(2048) 25 bigOne = big.NewInt(1) 26 bigTwo = big.NewInt(2) 27 28 // used to isolate the checksum bits from the entropy+checksum byte array 29 wordLengthChecksumMasksMapping = map[int]*big.Int{ 30 12: big.NewInt(15), 31 15: big.NewInt(31), 32 18: big.NewInt(63), 33 21: big.NewInt(127), 34 24: big.NewInt(255), 35 } 36 // used to use only the desired x of 8 available checksum bits. 37 // 256 bit (word length 24) requires all 8 bits of the checksum, 38 // and thus no shifting is needed for it (we would get a divByZero crash if we did) 39 wordLengthChecksumShiftMapping = map[int]*big.Int{ 40 12: big.NewInt(16), 41 15: big.NewInt(8), 42 18: big.NewInt(4), 43 21: big.NewInt(2), 44 } 45 46 // wordList is the set of words to use 47 wordList []string 48 49 // wordMap is a reverse lookup map for wordList 50 wordMap map[string]int 51) 52 53var ( 54 // ErrInvalidMnemonic is returned when trying to use a malformed mnemonic. 55 ErrInvalidMnemonic = errors.New("Invalid mnenomic") 56 57 // ErrEntropyLengthInvalid is returned when trying to use an entropy set with 58 // an invalid size. 59 ErrEntropyLengthInvalid = errors.New("Entropy length must be [128, 256] and a multiple of 32") 60 61 // ErrValidatedSeedLengthMismatch is returned when a validated seed is not the 62 // same size as the given seed. This should never happen is present only as a 63 // sanity assertion. 64 ErrValidatedSeedLengthMismatch = errors.New("Seed length does not match validated seed length") 65 66 // ErrChecksumIncorrect is returned when entropy has the incorrect checksum. 67 ErrChecksumIncorrect = errors.New("Checksum incorrect") 68) 69 70func init() { 71 SetWordList(wordlists.English) 72} 73 74// SetWordList sets the list of words to use for mnemonics. Currently the list 75// that is set is used package-wide. 76func SetWordList(list []string) { 77 wordList = list 78 wordMap = map[string]int{} 79 for i, v := range wordList { 80 wordMap[v] = i 81 } 82} 83 84// GetWordList gets the list of words to use for mnemonics. 85func GetWordList() []string { 86 return wordList 87} 88 89// GetWordIndex gets word index in wordMap. 90func GetWordIndex(word string) (int, bool) { 91 idx, ok := wordMap[word] 92 return idx, ok 93} 94 95// NewEntropy will create random entropy bytes 96// so long as the requested size bitSize is an appropriate size. 97// 98// bitSize has to be a multiple 32 and be within the inclusive range of {128, 256} 99func NewEntropy(bitSize int) ([]byte, error) { 100 err := validateEntropyBitSize(bitSize) 101 if err != nil { 102 return nil, err 103 } 104 105 entropy := make([]byte, bitSize/8) 106 _, err = rand.Read(entropy) 107 return entropy, err 108} 109 110// EntropyFromMnemonic takes a mnemonic generated by this library, 111// and returns the input entropy used to generate the given mnemonic. 112// An error is returned if the given mnemonic is invalid. 113func EntropyFromMnemonic(mnemonic string) ([]byte, error) { 114 mnemonicSlice, isValid := splitMnemonicWords(mnemonic) 115 if !isValid { 116 return nil, ErrInvalidMnemonic 117 } 118 119 // Decode the words into a big.Int. 120 b := big.NewInt(0) 121 for _, v := range mnemonicSlice { 122 index, found := wordMap[v] 123 if found == false { 124 return nil, fmt.Errorf("word `%v` not found in reverse map", v) 125 } 126 var wordBytes [2]byte 127 binary.BigEndian.PutUint16(wordBytes[:], uint16(index)) 128 b = b.Mul(b, shift11BitsMask) 129 b = b.Or(b, big.NewInt(0).SetBytes(wordBytes[:])) 130 } 131 132 // Build and add the checksum to the big.Int. 133 checksum := big.NewInt(0) 134 checksumMask := wordLengthChecksumMasksMapping[len(mnemonicSlice)] 135 checksum = checksum.And(b, checksumMask) 136 137 b.Div(b, big.NewInt(0).Add(checksumMask, bigOne)) 138 139 // The entropy is the underlying bytes of the big.Int. Any upper bytes of 140 // all 0's are not returned so we pad the beginning of the slice with empty 141 // bytes if necessary. 142 entropy := b.Bytes() 143 entropy = padByteSlice(entropy, len(mnemonicSlice)/3*4) 144 145 // Generate the checksum and compare with the one we got from the mneomnic. 146 entropyChecksumBytes := computeChecksum(entropy) 147 entropyChecksum := big.NewInt(int64(entropyChecksumBytes[0])) 148 if l := len(mnemonicSlice); l != 24 { 149 checksumShift := wordLengthChecksumShiftMapping[l] 150 entropyChecksum.Div(entropyChecksum, checksumShift) 151 } 152 153 if checksum.Cmp(entropyChecksum) != 0 { 154 return nil, ErrChecksumIncorrect 155 } 156 157 return entropy, nil 158} 159 160// NewMnemonic will return a string consisting of the mnemonic words for 161// the given entropy. 162// If the provide entropy is invalid, an error will be returned. 163func NewMnemonic(entropy []byte) (string, error) { 164 // Compute some lengths for convenience. 165 entropyBitLength := len(entropy) * 8 166 checksumBitLength := entropyBitLength / 32 167 sentenceLength := (entropyBitLength + checksumBitLength) / 11 168 169 // Validate that the requested size is supported. 170 err := validateEntropyBitSize(entropyBitLength) 171 if err != nil { 172 return "", err 173 } 174 175 // Add checksum to entropy. 176 entropy = addChecksum(entropy) 177 178 // Break entropy up into sentenceLength chunks of 11 bits. 179 // For each word AND mask the rightmost 11 bits and find the word at that index. 180 // Then bitshift entropy 11 bits right and repeat. 181 // Add to the last empty slot so we can work with LSBs instead of MSB. 182 183 // Entropy as an int so we can bitmask without worrying about bytes slices. 184 entropyInt := new(big.Int).SetBytes(entropy) 185 186 // Slice to hold words in. 187 words := make([]string, sentenceLength) 188 189 // Throw away big.Int for AND masking. 190 word := big.NewInt(0) 191 192 for i := sentenceLength - 1; i >= 0; i-- { 193 // Get 11 right most bits and bitshift 11 to the right for next time. 194 word.And(entropyInt, last11BitsMask) 195 entropyInt.Div(entropyInt, shift11BitsMask) 196 197 // Get the bytes representing the 11 bits as a 2 byte slice. 198 wordBytes := padByteSlice(word.Bytes(), 2) 199 200 // Convert bytes to an index and add that word to the list. 201 words[i] = wordList[binary.BigEndian.Uint16(wordBytes)] 202 } 203 204 return strings.Join(words, " "), nil 205} 206 207// MnemonicToByteArray takes a mnemonic string and turns it into a byte array 208// suitable for creating another mnemonic. 209// An error is returned if the mnemonic is invalid. 210func MnemonicToByteArray(mnemonic string, raw ...bool) ([]byte, error) { 211 var ( 212 mnemonicSlice = strings.Split(mnemonic, " ") 213 entropyBitSize = len(mnemonicSlice) * 11 214 checksumBitSize = entropyBitSize % 32 215 fullByteSize = (entropyBitSize-checksumBitSize)/8 + 1 216 checksumByteSize = fullByteSize - (fullByteSize % 4) 217 ) 218 219 // Pre validate that the mnemonic is well formed and only contains words that 220 // are present in the word list. 221 if !IsMnemonicValid(mnemonic) { 222 return nil, ErrInvalidMnemonic 223 } 224 225 // Convert word indices to a big.Int representing the entropy. 226 checksummedEntropy := big.NewInt(0) 227 modulo := big.NewInt(2048) 228 for _, v := range mnemonicSlice { 229 index := big.NewInt(int64(wordMap[v])) 230 checksummedEntropy.Mul(checksummedEntropy, modulo) 231 checksummedEntropy.Add(checksummedEntropy, index) 232 } 233 234 // Calculate the unchecksummed entropy so we can validate that the checksum is 235 // correct. 236 checksumModulo := big.NewInt(0).Exp(bigTwo, big.NewInt(int64(checksumBitSize)), nil) 237 rawEntropy := big.NewInt(0).Div(checksummedEntropy, checksumModulo) 238 239 // Convert big.Ints to byte padded byte slices. 240 rawEntropyBytes := padByteSlice(rawEntropy.Bytes(), checksumByteSize) 241 checksummedEntropyBytes := padByteSlice(checksummedEntropy.Bytes(), fullByteSize) 242 243 // Validate that the checksum is correct. 244 newChecksummedEntropyBytes := padByteSlice(addChecksum(rawEntropyBytes), fullByteSize) 245 if !compareByteSlices(checksummedEntropyBytes, newChecksummedEntropyBytes) { 246 return nil, ErrChecksumIncorrect 247 } 248 249 if len(raw) > 0 && raw[0] { 250 return rawEntropyBytes, nil 251 } 252 253 return checksummedEntropyBytes, nil 254} 255 256// NewSeedWithErrorChecking creates a hashed seed output given the mnemonic string and a password. 257// An error is returned if the mnemonic is not convertible to a byte array. 258func NewSeedWithErrorChecking(mnemonic string, password string) ([]byte, error) { 259 _, err := MnemonicToByteArray(mnemonic) 260 if err != nil { 261 return nil, err 262 } 263 return NewSeed(mnemonic, password), nil 264} 265 266// NewSeed creates a hashed seed output given a provided string and password. 267// No checking is performed to validate that the string provided is a valid mnemonic. 268func NewSeed(mnemonic string, password string) []byte { 269 return pbkdf2.Key([]byte(mnemonic), []byte("mnemonic"+password), 2048, 64, sha512.New) 270} 271 272// IsMnemonicValid attempts to verify that the provided mnemonic is valid. 273// Validity is determined by both the number of words being appropriate, 274// and that all the words in the mnemonic are present in the word list. 275func IsMnemonicValid(mnemonic string) bool { 276 // Create a list of all the words in the mnemonic sentence 277 words := strings.Fields(mnemonic) 278 279 // Get word count 280 wordCount := len(words) 281 282 // The number of words should be 12, 15, 18, 21 or 24 283 if wordCount%3 != 0 || wordCount < 12 || wordCount > 24 { 284 return false 285 } 286 287 // Check if all words belong in the wordlist 288 for _, word := range words { 289 if _, ok := wordMap[word]; !ok { 290 return false 291 } 292 } 293 294 return true 295} 296 297// Appends to data the first (len(data) / 32)bits of the result of sha256(data) 298// Currently only supports data up to 32 bytes 299func addChecksum(data []byte) []byte { 300 // Get first byte of sha256 301 hash := computeChecksum(data) 302 firstChecksumByte := hash[0] 303 304 // len() is in bytes so we divide by 4 305 checksumBitLength := uint(len(data) / 4) 306 307 // For each bit of check sum we want we shift the data one the left 308 // and then set the (new) right most bit equal to checksum bit at that index 309 // staring from the left 310 dataBigInt := new(big.Int).SetBytes(data) 311 for i := uint(0); i < checksumBitLength; i++ { 312 // Bitshift 1 left 313 dataBigInt.Mul(dataBigInt, bigTwo) 314 315 // Set rightmost bit if leftmost checksum bit is set 316 if uint8(firstChecksumByte&(1<<(7-i))) > 0 { 317 dataBigInt.Or(dataBigInt, bigOne) 318 } 319 } 320 321 return dataBigInt.Bytes() 322} 323 324func computeChecksum(data []byte) []byte { 325 hasher := sha256.New() 326 hasher.Write(data) 327 return hasher.Sum(nil) 328} 329 330// validateEntropyBitSize ensures that entropy is the correct size for being a 331// mnemonic. 332func validateEntropyBitSize(bitSize int) error { 333 if (bitSize%32) != 0 || bitSize < 128 || bitSize > 256 { 334 return ErrEntropyLengthInvalid 335 } 336 return nil 337} 338 339// padByteSlice returns a byte slice of the given size with contents of the 340// given slice left padded and any empty spaces filled with 0's. 341func padByteSlice(slice []byte, length int) []byte { 342 offset := length - len(slice) 343 if offset <= 0 { 344 return slice 345 } 346 newSlice := make([]byte, length) 347 copy(newSlice[offset:], slice) 348 return newSlice 349} 350 351// compareByteSlices returns true of the byte slices have equal contents and 352// returns false otherwise. 353func compareByteSlices(a, b []byte) bool { 354 if len(a) != len(b) { 355 return false 356 } 357 for i := range a { 358 if a[i] != b[i] { 359 return false 360 } 361 } 362 return true 363} 364 365func splitMnemonicWords(mnemonic string) ([]string, bool) { 366 // Create a list of all the words in the mnemonic sentence 367 words := strings.Fields(mnemonic) 368 369 // Get num of words 370 numOfWords := len(words) 371 372 // The number of words should be 12, 15, 18, 21 or 24 373 if numOfWords%3 != 0 || numOfWords < 12 || numOfWords > 24 { 374 return nil, false 375 } 376 return words, true 377} 378