How can I recover the missing end of my private key?

Question

I found this paper among my old stuff. What can you do with it? Is there any way to fill in the missing part?

Answer 1

TL;DR:

You don't need to bruteforce anything here (at least almost), and can recover the missing last 7 characters on an average PC at home within less than 1 second using a simple Python script!

In detail:

In your picture there are 7 characters missing at the end of the private key (figured out by comparing with a test-printout using the same HTML file).

Yes, it is correct that this key format is using Base58 alphabet and therefore there are 58 possibilities per character, so for 7 characters you would need to try 58^7 possibilities (which would be about 2 trillions) in theory, but all these considerations are missing an important fact:

When such a private key (the format is called WIF short for Wallet Import Format, see also the reference documentation here) is encoded, at the end (after the actual private key) 4 bytes are added as a checksum. So if these 4 bytes are missing (at the end) you can calculate it from the rest.

Second: in your picture it looks like your private key starts with an L. This indicates that the Bitcoin address is based on a compressed public key. Don't worry, this is a technical detail, but this helps you further: Private keys for compressed pubkeys have another special byte added after the key (and before the checksum), namely a fixed 0x01 (see also in the reference documenation for WIF).

This means that the last 5 bytes of a WIF encoded private key (starting with L or K) are either static or can be computed from the rest.

So you are very lucky that the last 7 characters are missing (and not the first 7, because then you really would need to bruteforce 2 trillion possibilities).

What to do with this information:

If we apply this knowledge now to base58 we see that only a single character is missing and then we can calculate the rest.

Reasoning: first: a single base58 character carries ~5.85799 = log2(58) bits of information and second: we don't need the last 40 bits (4 bytes checksum + 1 static byte for compressed key are 5 bytes = 40 bits).

So, if only 6 characters would be missing at the end (6 * 5.85799.. = 35.14794) we not need to bruteforce anything, because this would be still less than the 40 bits we don't need.

Conclusion:

As you are missing 7 characters we just need to bruteforce one single character (and this means just 58 attempts, not 2 trillions). So we just attempt to add one of the 58 characters from the bas58 alphabet. For each attempt we calculate the full base58 string by adding the static compressed key flag byte (0x01) and after that the checksum and simply compare it with the rest of the key you have. If it matches it is a valid candidate.

At the end of these 58 attempts you will end up with 2 or 3 (at most) valid private key candidates, and just need to check these 3 keys, to see which one belongs to your address.

The Reddit user /u/dooglus/ (not me) pointed out exactly this in the first place in his comment on your post and he also added a snippet of Python code which does exactly I've described above.

Don't trust anybody, don't hand out your key to any stranger!

Now take your time, learn what the Python script below does (don't trust me or any strangers) and when you feel safe, copy the Python snippet from /u/dooglus/'s comment, save it in a text-file named complete-wif.py on a safe computer. After that take the computer offline and run the Python script by typing this into a commandline:

python3 complete-wif.py L...-your-private-key-goes-here...yhub

and it will print 2 or 3 completed WIF private keys in less than 1 second.

Appendix:

For reference, I appended the Python script but it's not my work, all credits go to /u/dooglus/. I just can confirm that it does what I described above (but ask others to confirm this and try it with other private keys before you trust it with your real private key):

#!/usr/bin/env python3

import base58, sys

partial = sys.argv[1]

if len(partial) != 45:
    print("partial key should be 45 characters")
    sys.exit(1)

results = {}
for c in '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz':
    wif = base58.b58encode_check(base58.b58decode(partial + c*7)[:33] + b'\x01').decode('ascii')
    if wif[:45] == partial: results[wif] = True

for k in results.keys(): print(k)

Answer 2

It has to be brute forced. There are a couple of ways but basically it is replacing each character by base-58 chars and checking the key.
The amount of time that process takes depends on the number of characters missing and slightly on whether the key is compressed or uncompressed and a little on your luck.

However if your key is compressed and is missing up to 11 characters or is uncompressed and is missing up to 9 characters from its end (which seems to be the case from your screenshot) it can be recovered within seconds.

Check out FinderOuter on GitHub. The Missing Base58 option handles your case. You'll have to enter the characters you already have and replace the missing ones with a special char like * then enter your address in second box and click Find.
Full disclosure: I'm the developer of The FinderOuter.
P.S. The released version (0.4.1) is old and doesn't have the optimization mentioned above, you'll have to compile the code yourself or wait for 0.5.0.
Edit: Version 0.5.0 released on 2020-09-17 and can recovery this special case with up to 11 missing chars from end.