Difference between revisions of "Mini private key format"
(→Entropy considerations: fix math - I did 58^26 instead of 58^25)
|Line 8:||Line 8:|
Revision as of 06:32, 23 September 2011
The mini private key format is a method of encoding a Bitcoin private key in as few as 22 characters so that it can be embedded in a small space. This private key format was first used in Casascius physical bitcoins, and is also favorable for use in QR codes. The fewer characters encoded in a QR code, the lower dot density can be used, as well as more dots allocated to error correction in the same space, significantly improving readability and resistance to damage. The mini private key format offers its own built-in check code as a small margin of protection against typos.
An example key using this encoding is S4b3N3oGqDqR5jNuxEvDwf.
Usage on a physical bitcoin
The way it might appear within a physical bitcoin is on a round card printed as follows:
To import the minikey in a user-friendly way the browser-wallet strongcoin can be used.
The private key encoding consists of 22 or 26 alphanumeric characters from the base58 alphabet used in Bitcoin. The first of the characters is always the uppercase letter S.
To obtain the full 256-bit private key, simply take the SHA256 hash of the entire string. There is no encoding for breaks in the string even if printed that way - the SHA256 should be taken of exactly twenty-two bytes.
SHA256("S4b3N3oGqDqR5jNuxEvDwf") = 0C28FCA386C7A227600B2FE50B7CAE11EC86D3BF1FBE471BE89827E19D72AA1D
The check code is designed to be simple, but relatively computationally expensive so that it cannot be used to quickly reduce the key space in a brute force attack. It offers seven bits worth of error protection (or, in other words, in the event of a typo, the typo will be caught about 127 out of 128 times, or over 99%).
To determine whether a string passes the check code, follow these steps:
- Ensure it is well-formed (22 or 26 characters, base58 alphabet, starts with S).
- Add a question mark to the end of the string, and take the SHA256 of that. If the SHA256 starts with eight zero bits (hex 00), then the string passes the check code.
- If it does not, then with the same string (ending in a question mark), do 717 (seven hundred seventeen) rounds of SHA256 on the string. If the result after the 717th round starts with eight zero bits (hex 00), then the string passes the check code.
- If the results of SHA256 after both tests don't start with eight zero bits, then the check fails.
Creating mini private keys
Creating mini private keys is relatively simple. One program which can create such keys is Casascius Bitcoin Utility.
Mini private keys must be created "from scratch", as the conversion from mini private key to full-size private key is one-way. In other words, there is no way to convert an existing full-size private key into a mini private key.
To create mini private keys, simply create random strings that satisfy the well-formedness requirement, and then eliminate the ones that do not pass the typo check. (This means eliminating more than 99% of the candidates.) Then use SHA256 to compute the corresponding private key, and in turn, the matching Bitcoin address. The Bitcoin address can always be computed from just the private key.
In all cases, you should use a secure cryptographic random number generator to eliminate risks of predictability of the random strings. Also, for stronger security, accept only the strings that pass the typo check on the 717th round rather than the first.
The 22-character mini private key code appears to offer about 123 bits of entropy, determined as log2(58^21). (Because the first character is fixed, there are 21 symbols which can each have one of 58 values).
The 26-character version offers about 146 bits of entropy by the same calculation.
Each attempt to convert a mini private key to a Bitcoin address requires an elliptic curve multiply operation, which itself is computationally intensive. This will slow a brute force attack with the same effect as several further bits of "apparent entropy" when compared to a brute force operation of much less complexity, such as hash cracking.
The following code produces sample mini private keys in Python. For real-world use, random must be replaced with a better source of entropy, as the Python documentation for random states the function "is completely unsuitable for cryptographic purposes".
import random import hashlib BASE58 = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz' def Candidate(): """ Generate a random, well-formed mini private key. """ return('%s%s' % ('S', ''.join( [BASE58[ random.randrange(0,len(BASE58)) ] for i in range(21)]))) def GenerateKeys(numKeys = 10, additionalSecurity = False): """ Generate mini private keys and output the mini key as well as the full private key. numKeys is The number of keys to generate, and additionalSecurity controls whether to do 717 rounds of SHA256 """ keysGenerated = 0 totalCandidates = 0 while keysGenerated < numKeys: try: cand = Candidate() # Do typo check t = '%s?' % cand # Take one round of SHA256 candHash = hashlib.sha256(t).digest() if additionalSecurity: # Do the other 716 rounds for additional security for i in range(716): candHash = hashlib.sha256(candHash).digest() # Check if the first eight bits of the hash are 0 if candHash == '\x00': privateKey = GetPrivateKey(cand) print('\n%s\nSHA256( ): %s\nsha256(?): %s' % (cand, privateKey, candHash.encode('hex_codec'))) if CheckShortKey(cand): print('Validated.') else: print('Invalid!') keysGenerated += 1 totalCandidates += 1 except KeyboardInterrupt: break print('\n%s: %i\n%s: %i\n%s: %r\n%s: %.1f' % ('Keys Generated', keysGenerated, 'Total Candidates', totalCandidates, 'Additional Security', additionalSecurity, 'Reject Percentage', 100*(1.0-keysGenerated/float(totalCandidates)))) def GetPrivateKey(shortKey): """ Returns the hexadecimal representation of the private key corresponding to the given short key. """ if CheckShortKey(shortKey): return hashlib.sha256(shortKey).hexdigest() else: print('Typo detected in private key!') return None def CheckShortKey(shortKey): """ Checks for typos in the short key. """ if len(shortKey) != 22: return False t = '%s?' % shortKey tHash = hashlib.sha256(t).digest() # Check to see that first byte is \x00 if tHash == '\x00': return True else: # Do an additional 716 rounds for i in range(716): tHash = hashlib.sha256(tHash).digest() # Check again for \x00 if tHash == '\x00': return True return False