Bitcoin Forum

Bitcoin => Bitcoin Technical Support => Topic started by: Albatroz4402 on May 12, 2018, 01:32:42 PM



Title: Private Key missing 4 characters
Post by: Albatroz4402 on May 12, 2018, 01:32:42 PM
Hello people! I've been looking at the forum and seen that there are some ways to recover a private key that is missing some characters, it fed me hope and I'm trying to figure out a way for me to recover my private key.

Currently my private key has only 47 characters, but of the remaining characters, I'm not sure if the missing ones are the end, beginning or middle of the private key (I think it's the end), you know some algorithm you can try to generate a valid private key in my situation?


Title: Re: Private Key missing 4 characters
Post by: LoyceV on May 12, 2018, 02:05:28 PM
I have a Python script C program (see Private Key Restorer (https://bitcointalk.org/index.php?topic=1624496.0) for source and credits) that can restore up to 5 characters, if you know their exact location.

If the missing characters are at the end, there may be an easier solution (https://bitcointalk.org/index.php?topic=3104338.msg32072283#msg32072283). I've successfully used this to restore the 7 characters checksum. Note that this means exposing your private key to blockchain.info, and I certainly don't recommend this for larger values or cold storage.


Title: Re: Private Key missing 4 characters
Post by: Albatroz4402 on May 12, 2018, 02:37:20 PM
I have a Python script (from someone on the forum here) that can restore up to 5 characters, if you know their exact location.

If the missing characters are at the end, there may be an easier solution (https://bitcointalk.org/index.php?topic=3104338.msg32072283#msg32072283). I've successfully used this to restore the 7 characters checksum. Note that this means exposing your private key to blockchain.info, and I certainly don't recommend this for larger values or cold storage.

I took a look at the topic you sent me, so I understood I should create a new wallet at blockchain.info and import my private key? I tried to do this but at the time of entering my private key in the import settings of the address, it tells me that it is invalid!

As for this script in Python, could you pass me?


Title: Re: Private Key missing 4 characters
Post by: LoyceV on May 12, 2018, 02:50:01 PM
I took a look at the topic you sent me, so I understood I should create a new wallet at blockchain.info and import my private key? I tried to do this but at the time of entering my private key in the import settings of the address, it tells me that it is invalid!
Try it without the last 3 characters (so the full checksum is gone).

Quote
As for this script in Python, could you pass me?
Sorry, it's C, I was wrong. See Private Key Restorer (https://bitcointalk.org/index.php?topic=1624496.0).


Title: Re: Private Key missing 4 characters
Post by: Albatroz4402 on May 12, 2018, 04:01:25 PM
I took a look at the topic you sent me, so I understood I should create a new wallet at blockchain.info and import my private key? I tried to do this but at the time of entering my private key in the import settings of the address, it tells me that it is invalid!
Try it without the last 3 characters (so the full checksum is gone).

Quote
As for this script in Python, could you pass me?
Sorry, it's C, I was wrong. See Private Key Restorer (https://bitcointalk.org/index.php?topic=1624496.0).

Hello Friend!

I've been able to compile the code and am waiting for it to run, but I have a question:

The characters of my private key are not separated by a "-", I only have 47 alphanumeric characters, in the code should I put my address separated by "-"? If so, what pattern should I adopt to put this "-"?


Title: Re: Private Key missing 4 characters
Post by: LoyceV on May 12, 2018, 04:44:27 PM
I've been able to compile the code and am waiting for it to run, but I have a question:

The characters of my private key are not separated by a "-", I only have 47 alphanumeric characters, in the code should I put my address separated by "-"? If so, what pattern should I adopt to put this "-"?
You have to put a "-" at the place where your private key is missing a character. I'm not sure if the code works with just 4 missing, if it doesn't, you can easily omit one more character.

Example: let's say this is your private key:
5Ht1xbx9coyDSTfpGWn882wdZSwTNmMUzfwd1amRpYUZs8Sv7H9 (do not use this one!)
You miss 4 characters, assuming they are missing at the end, this is what you have:
5Ht1xbx9coyDSTfpGWn882wdZSwTNmMUzfwd1amRpYUZs8S
I suggest to use this for the recovery program:
5Ht1xbx9coyDSTfpGWn882wdZSwTNmMUzfwd1amRpYUZs8-----


Title: Re: Private Key missing 4 characters
Post by: Albatroz4402 on May 12, 2018, 07:29:51 PM
I've been able to compile the code and am waiting for it to run, but I have a question:

The characters of my private key are not separated by a "-", I only have 47 alphanumeric characters, in the code should I put my address separated by "-"? If so, what pattern should I adopt to put this "-"?
You have to put a "-" at the place where your private key is missing a character. I'm not sure if the code works with just 4 missing, if it doesn't, you can easily omit one more character.

Example: let's say this is your private key:
5Ht1xbx9coyDSTfpGWn882wdZSwTNmMUzfwd1amRpYUZs8Sv7H9 (do not use this one!)
You miss 4 characters, assuming they are missing at the end, this is what you have:
5Ht1xbx9coyDSTfpGWn882wdZSwTNmMUzfwd1amRpYUZs8S
I suggest to use this for the recovery program:
5Ht1xbx9coyDSTfpGWn882wdZSwTNmMUzfwd1amRpYUZs8-----

I expected the program to run all the cycles until it finishes, but in the end, it does not show me any results, I imagined that it would show me the possible private keys with the missing characters ....

How can I interpret the result at the end of the program?


Title: Re: Private Key missing 4 characters
Post by: David Way on May 12, 2018, 08:21:48 PM
You need to be in Ubuntu: I ran a virtual machine in oracle virtualbox

if you need help doing that follow tutorial(https://linus.nci.nih.gov/bdge/installUbuntu.html)

i used this version of ubuntu (ubuntu-16.04.3-desktop-amd64.iso)

Once you are successfully in Ubuntu (probably works with other linux distributions but this is what i tested) follow these steps

go to documents and create a folder named "bruteforce"

follow this link https://gist.github.com/tayvano/7755e3e8d8b64581d5ff2865087b93f8

click "raw"

right click and select "save page as"

save page in folder "bruteforce" that we just created

Open the .js file you saved in text editor "gedit"

Change the stuff between the ' ' characters to the characters you have of your private key. Check it 5 times to be sure you got the correct characters in there: var basePrivateKey = 'afdfd9c3d2095ef696594f6cedcae59e72dcd697e2a7521b15781404'

Change the stuff between the ' ' characters to your address: var targetPublicAddress = '0x06A85356DCb5b307096726FB86A78c59D38e08ee';

save and exit gedit

open terminal

navigate to brute force folder. This can be done by typing "cd" hitting the space bar, then dragging and dropping the "bruteforce" folder into the terminal, then hitting enter.

now type "sudo apt-get update"

now type "sudo apt-get install nodejs-legacy" and install

now type "sudo apt-get install npm" and install

now type "npm install ethereumjs-wallet" and hit enter

now type "npm install etheruemjs-util" and hit enter

now type "node brute_force_end_of_private_key.js" and hit enter

thats it!

You should see the following:

$ node /Users/tay/Desktop/brute_force_8_char.js

searching for address : 0x06A85356DCb5b307096726FB86A78c59D38e08ee base private key : afdfd9c3d2095ef696594f6cedcae59e72dcd697e2a7521b15781404 missing chars : 8 it will be quiet now. if you don't see anything below me, it's working on finding your key. If you see something below that doesn't say 'FOUND KEY!', you have an error When it's done it will show:

********************************** FOUND PRIVATE KEY: afdfd9c3d2095ef696594f6cedcae59e72dcd697e2a7521b1578140422a4f890 matching address 0x06A85356DCb5b307096726FB86A78c59D38e08ee


Title: Re: Private Key missing 4 characters
Post by: Albatroz4402 on May 12, 2018, 08:56:10 PM
You need to be in Ubuntu: I ran a virtual machine in oracle virtualbox

if you need help doing that follow tutorial(https://linus.nci.nih.gov/bdge/installUbuntu.html)

i used this version of ubuntu (ubuntu-16.04.3-desktop-amd64.iso)

Once you are successfully in Ubuntu (probably works with other linux distributions but this is what i tested) follow these steps

go to documents and create a folder named "bruteforce"

follow this link https://gist.github.com/tayvano/7755e3e8d8b64581d5ff2865087b93f8

click "raw"

right click and select "save page as"

save page in folder "bruteforce" that we just created

Open the .js file you saved in text editor "gedit"

Change the stuff between the ' ' characters to the characters you have of your private key. Check it 5 times to be sure you got the correct characters in there: var basePrivateKey = 'afdfd9c3d2095ef696594f6cedcae59e72dcd697e2a7521b15781404'

Change the stuff between the ' ' characters to your address: var targetPublicAddress = '0x06A85356DCb5b307096726FB86A78c59D38e08ee';

save and exit gedit

open terminal

navigate to brute force folder. This can be done by typing "cd" hitting the space bar, then dragging and dropping the "bruteforce" folder into the terminal, then hitting enter.

now type "sudo apt-get update"

now type "sudo apt-get install nodejs-legacy" and install

now type "sudo apt-get install npm" and install

now type "npm install ethereumjs-wallet" and hit enter

now type "npm install etheruemjs-util" and hit enter

now type "node brute_force_end_of_private_key.js" and hit enter

thats it!

You should see the following:

$ node /Users/tay/Desktop/brute_force_8_char.js

searching for address : 0x06A85356DCb5b307096726FB86A78c59D38e08ee base private key : afdfd9c3d2095ef696594f6cedcae59e72dcd697e2a7521b15781404 missing chars : 8 it will be quiet now. if you don't see anything below me, it's working on finding your key. If you see something below that doesn't say 'FOUND KEY!', you have an error When it's done it will show:

********************************** FOUND PRIVATE KEY: afdfd9c3d2095ef696594f6cedcae59e72dcd697e2a7521b1578140422a4f890 matching address 0x06A85356DCb5b307096726FB86A78c59D38e08ee

Thanks for the sugestion! But would not this process work there only for the private key of the Ethereum wallet? The private key I'm trying to fix is from Bitcoin wallet.


Title: Re: Private Key missing 4 characters
Post by: bob123 on May 13, 2018, 07:32:35 AM
I expected the program to run all the cycles until it finishes, but in the end, it does not show me any results, I imagined that it would show me the possible private keys with the missing characters ....

How can I interpret the result at the end of the program?


What kind of output do you get? No at all?

According to the source code (https://pastebin.com/S8WARrRn (https://pastebin.com/S8WARrRn)):
Code:
int c1 = 0, c2 = 0, c3 = 0, c4 = 0, c5 = 0, status;
    float startTime, endTime;
    for (c1 = 0; c1 < 58; c1++) {
        addr[C_1_INDEX] = chars[c1];
        for (c2 = 0; c2 < 58; c2++) {
            addr[C_2_INDEX] = chars[c2];
            printf("Test: %c%c...", chars[c1], chars[c2]);fflush(stdout);
            startTime = (float)clock()/CLOCKS_PER_SEC;
            for (c3 = 0; c3 < 58; c3++) {
                addr[C_3_INDEX] = chars[c3];
                for (c4 = 0; c4 < 58; c4++) {
                    addr[C_4_INDEX] = chars[c4];
                    for (c5 = 0; c5 < 58; c5++) {
                        addr[C_5_INDEX] = chars[c5];
                        status = valid(addr);
                        if (status) {
                            printf("\nFOUND: %s\n", addr);
                            return 1;
                        }
                    }
                }
            }
            endTime = (float)clock()/CLOCKS_PER_SEC;
            printf("%fs\n", (endTime-startTime));
        }
    }


You should get at least the output of the overall time it took to run the script.

If you do see how long it took overall (in source code: printf("%fs\n", (endTime-startTime));) the program went through all combinations and didn't found the correct private key.
If you do NOT see this output the script somehow (1) is not done yet or (2) aborted.

This script requires you to know the exact location of the missing chars. It will iterate through the positions marked with an '-' only.



Thanks for the sugestion! But would not this process work there only for the private key of the Ethereum wallet? The private key I'm trying to fix is from Bitcoin wallet.

Yes, this is only for ethereum.


Title: Re: Private Key missing 4 characters
Post by: LoyceV on May 13, 2018, 10:01:27 AM
I expected the program to run all the cycles until it finishes, but in the end, it does not show me any results, I imagined that it would show me the possible private keys with the missing characters ....

How can I interpret the result at the end of the program?
What kind of output do you get? No at all?
Did you do this:
run it ( ./recovery ), and stop with ctrl+c, you got 5 "index: XX" lines.

Modify the "define C_X_INDEX" lines in the code (line 49-53). Compile again.
Basically, you need to edit and compile the source twice if you follow these instructions. Only on the second run it searches for your own private key.

If you don't mind me asking: how did you lose the characters, and why is the location of the lost characters uncertain? What happened?


Title: Re: Private Key missing 4 characters
Post by: Albatroz4402 on May 13, 2018, 02:39:01 PM


What kind of output do you get? No at all?

According to the source code (https://pastebin.com/S8WARrRn (https://pastebin.com/S8WARrRn)):
Code:
int c1 = 0, c2 = 0, c3 = 0, c4 = 0, c5 = 0, status;
    float startTime, endTime;
    for (c1 = 0; c1 < 58; c1++) {
        addr[C_1_INDEX] = chars[c1];
        for (c2 = 0; c2 < 58; c2++) {
            addr[C_2_INDEX] = chars[c2];
            printf("Test: %c%c...", chars[c1], chars[c2]);fflush(stdout);
            startTime = (float)clock()/CLOCKS_PER_SEC;
            for (c3 = 0; c3 < 58; c3++) {
                addr[C_3_INDEX] = chars[c3];
                for (c4 = 0; c4 < 58; c4++) {
                    addr[C_4_INDEX] = chars[c4];
                    for (c5 = 0; c5 < 58; c5++) {
                        addr[C_5_INDEX] = chars[c5];
                        status = valid(addr);
                        if (status) {
                            printf("\nFOUND: %s\n", addr);
                            return 1;
                        }
                    }
                }
            }
            endTime = (float)clock()/CLOCKS_PER_SEC;
            printf("%fs\n", (endTime-startTime));
        }
    }


You should get at least the output of the overall time it took to run the script.

If you do see how long it took overall (in source code: printf("%fs\n", (endTime-startTime));) the program went through all combinations and didn't found the correct private key.
If you do NOT see this output the script somehow (1) is not done yet or (2) aborted.

This script requires you to know the exact location of the missing chars. It will iterate through the positions marked with an '-' only.



The algorithm goes through all the cycles and in the end it does not show me any results, not even the total time spent for execution.

I even generated a private key in WIF format (I do not know if this implies some different behavior) to test the algorithm, I hid 5 random characters in the middle and in the end, I compiled twice the code doing the index changes and even then, end of the process, the algorithm also showed no results.

If you don't mind me asking: how did you lose the characters, and why is the location of the lost characters uncertain? What happened?

At the time when I got the private key, I just jotted down the numbers and letters generated for me, I did not back up, and nowhere else, so I'm not sure what characters in which positions were missing ... (I was very noob) .


Title: Re: Private Key missing 4 characters
Post by: LoyceV on May 13, 2018, 03:07:04 PM
The algorithm goes through all the cycles and in the end it does not show me any results, not even the total time spent for execution.
Did you use the first program, or the one that also works on compressed keys (https://bitcointalk.org/index.php?topic=1624496.msg16359515#msg16359515)?

Quote
At the time when I got the private key, I just jotted down the numbers and letters generated for me, I did not back up, and nowhere else, so I'm not sure what characters in which positions were missing ... (I was very noob) .
I don't think it's very likely your missing characters are at the end of the private key. It's also possible you wrote down one (or more) characters incorrectly.

Aren't you missing 5 characters missing instead of 4, if you have 47 only? A quick test shows my uncompressed private keys are 52 51 characters long.

If you don't know the location, you have (approximately) 47^5 possible locations for the missing digits. Multiply that by the number of possibilities per combination, and it quickly becomes impossible to find.
Do you have any idea how much is stored on your address?


Title: Re: Private Key missing 4 characters
Post by: Albatroz4402 on May 13, 2018, 03:56:34 PM
Did you use the first program, or the one that also works on compressed keys (https://bitcointalk.org/index.php?topic=1624496.msg16359515#msg16359515)?

I used the first program. The strangest thing is that even though I was using a private key that I know, hiding 5 characters, I did not get any results = /. Have you used the first program yet and were able to get a result?

Quote
Aren't you missing 5 characters missing instead of 4, if you have 47 only? A quick test shows my private keys are 52 characters long.

Yes you are right, I found that the private keys had 51 characters, but when testing a few others, I noticed that they are 52 characters.


Quote
Do you have any idea how much is stored on your address?
More or less 5 BTC.


Title: Re: Private Key missing 4 characters
Post by: LoyceV on May 13, 2018, 06:14:48 PM
Have you used the first program yet and were able to get a result?
Yes I have used it, and yes it worked for me. But it has to be uncompressed, you can test it with the private key I posted here (https://bitcointalk.org/index.php?topic=3758182.msg37071704#msg37071704).

I've just tested it, and I've edited this part of the source code (line 49 and further):
Code:
#define C_1_INDEX 46
#define C_2_INDEX 47
#define C_3_INDEX 48
#define C_4_INDEX 49
#define C_5_INDEX 50

int main (void) {
    const char *chars = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
    char addr[100];
    strcpy(addr, "5Ht1xbx9coyDSTfpGWn882wdZSwTNmMUzfwd1amRpYUZs8-----");

This is the result after many lines:
Code:
Test: Sq...1.940186s
Test: Sr...1.935791s
Test: Ss...1.942627s
Test: St...1.931152s
Test: Su...1.919434s
Test: Sv...
FOUND: 5Ht1xbx9coyDSTfpGWn882wdZSwTNmMUzfwd1amRpYUZs8Sv7H9

If you can reproduce this and it still doesn't work, at least you know it's not the last 5 characters you're missing.

Quote
More or less 5 BTC.
Well, don't give up, ever! If you can't find it now, try again in a few years.


Title: Re: Private Key missing 4 characters
Post by: Thirdspace on May 14, 2018, 04:04:54 AM
Quote
Aren't you missing 5 characters missing instead of 4, if you have 47 only? A quick test shows my private keys are 52 characters long.
Yes you are right, I found that the private keys had 51 characters, but when testing a few others, I noticed that they are 52 characters.
uncompressed address has private key of 51 characters base58 and starts with a '5'
compressed address has private key of 52 characters base58 and starts with a 'K' or 'L'
what is the prefix of your private key, runs the program accordingly with 51/52 char space

Quote
More or less 5 BTC.
Well, don't give up, ever! If you can't find it now, try again in a few years.
you should never give up for that amount. if you do give up,... give it up to me  :D ;D


Title: Re: Private Key missing 4 characters
Post by: LoyceV on May 14, 2018, 07:53:33 AM
uncompressed address has private key of 51 characters base58 and starts with a '5'
compressed address has private key of 52 characters base58 and starts with a 'K' or 'L'
Thanks, I stand corrected. It turns out wc (https://linuxconfig.org/wc-1-manual-page) ("word count") adds one byte to it's count.

Quote
what is the prefix of your private key, runs the program accordingly with 51/52 char space
This is the basic question indeed now. If you miss 4 characters, it's much more likely to restore them at random places than with 5 characters.


Title: Re: Private Key missing 4 characters
Post by: Albatroz4402 on May 14, 2018, 02:31:40 PM
Thanks for the great help my friend!

I have not yet tested the algorithm with the code change you made, I'll test it today at the end of the day and post the result here.

The private key starts with 5, so the total would be 51 characters right?


Title: Re: Private Key missing 4 characters
Post by: LoyceV on May 14, 2018, 04:11:01 PM
The private key starts with 5, so the total would be 51 characters right?
Correct.


Title: Re: Private Key missing 4 characters
Post by: Albatroz4402 on May 15, 2018, 06:20:32 PM
I did another test of the algorithm with my private key and got no feedback ...

But I understood the algorithm and I managed to reproduce a certain result, I used a random private key of 51 characters, the algorithm only shows a result with a private key of 51 characters and if the missing positions are filled exactly in the place of origin, in any other position the algorithm does not give a response with a valid private key.

Unfortunately in my case I have no idea of the positions of the lost characters, but I keep trying, because it has been very useful for me to learn new skills and resources.


Title: Re: Private Key missing 4 characters
Post by: HCP on May 16, 2018, 05:36:13 AM
Unfortunately in my case I have no idea of the positions of the lost characters, but I keep trying, because it has been very useful for me to learn new skills and resources.
In which case, I think the search space is something like (58chars*47positions)*(58chars*47pos)*(58chars*47pos)*(58chars*47pos)... (58*47)4 = 5.5220891*1013 possible combinations :-\

It should be possible to modify the code (or write new code) to test all the possible combinations... but it is going to take a LONG time to search all of that. Testing 1,000,000 combinations/second will take nearly 2 years to search all of them. (for reference, my Core i5-3570K, running Ubuntu on the Windows 10 Linux Subsystem seems to average around 200,000 combinations/second.)

Not exactly "impossible" (and for 5 BTC, probably worth it :P)... but technically it will be difficult to run a task non-stop for that period of time.


Title: Re: Private Key missing 4 characters
Post by: Thirdspace on May 16, 2018, 01:12:51 PM
The private key starts with 5, so the total would be 51 characters right?
Correct.
Unfortunately in my case I have no idea of the positions of the lost characters, but I keep trying, because it has been very useful for me to learn new skills and resources.
In which case, I think the search space is something like (58chars*47positions)*(58chars*47pos)*(58chars*47pos)*(58chars*47pos)... (58*47)4 = 5.5220891*1013 possible combinations :-\
---snip---
I think your calculation is a bit off. Also we can save computation power by narrowing down search space,
the first 2 chars always start with '5H', '5J', '5K', 51-2 = 49 positions and 49-4 = 45 characters known
if exact position of 4 lost characters are known = 58^4 = 11,316,496 iterations
if exact position is unknown = 58^4 * 4-combination
= (58^4) * ( 49! / 4! (49-4)! ) = (58^4) * (46*47*2*49)
= (58^4) * 211876 = 2,397,693,906,496 iterations = 2.39 * 1012
do I get this right?

Testing 1,000,000 combinations/second will take nearly 2 years to search all of them. (for reference, my Core i5-3570K, running Ubuntu on the Windows 10 Linux Subsystem seems to average around 200,000 combinations/second.)
are you sure we can have that computation power for combinations/second?
if compute power 200,000 combinations/second ~ 137.5 days (4.5 months)
if compute power 1,000,000 combinations/second ~ 27.75 days (1 month)
if by any chance the search space can be narrowed down even more (for e.g. assume the first 15 chars are correct)
it can cut down the number combinations and the needed time drastically


Title: Re: Private Key missing 4 characters
Post by: LoyceV on May 16, 2018, 03:50:44 PM
if by any chance the search space can be narrowed down even more (for e.g. assume the first 15 chars are correct)
it can cut down the number combinations and the needed time drastically
If someone skips 4 characters while writing down a private key, chances are he also wrote down one or more characters incorrectly.
If you're sure the rest is correct, it could be worth spending some money on Cloud computing, start up enough nodes, and crunch it quickly.

Someone specialized in wallet recoveries may be able to help you with this. I'm thinking about Dave from https://walletrecoveryservices.com/ for instance.


Title: Re: Private Key missing 4 characters
Post by: bob123 on May 17, 2018, 08:51:40 AM
Unfortunately in my case I have no idea of the positions of the lost characters, but I keep trying, because it has been very useful for me to learn new skills and resources.
In which case, I think the search space is something like (58chars*47positions)*(58chars*47pos)*(58chars*47pos)*(58chars*47pos)... (58*47)4 = 5.5220891*1013 possible combinations :-\
---snip---
I think your calculation is a bit off. Also we can save computation power by narrowing down search space,
the first 2 chars always start with '5H', '5J', '5K', 51-2 = 49 positions and 49-4 = 45 characters known
if exact position of 4 lost characters are known = 58^4 = 11,316,496 iterations
if exact position is unknown = 58^4 * 4-combination
= (58^4) * ( 49! / 4! (49-4)! ) = (58^4) * (46*47*2*49)
= (58^4) * 211876 = 2,397,693,906,496 iterations = 2.39 * 1012
do I get this right?



I am pretty sure you made a small mistake there. You do ignore the order of the 4 missing words with your statement: ( 49! / 4! (49-4)! )
You do iterate through each position with your words, but you have to iterate within the words too.

This should be the correct calculation:



There are 58 choose 4 possible combinations to pick the 4 correct chars from the charspace (without considering the order).


Now consider the first two characters as already known. Only looking at the private key without the first two chars here:

To put the first unknown char into the correct place, you can choose between 1) before of each already existing char (45 possibilities) and 2) behind the last one (45+1).
For the second one you choose either before each char in your privkey (46 possibilities) or behind the last one (46+1)...

Overall there are 46 * 47 * 48 * 49 possible combinations to place the 4 chars into a private key with 45 known characters (ignoring the first two) into the right order. This assumes the already known characters are in a correct order already.


The total search space (for the private key without the first 2 chars) therefore is 46 * 47 * 48 * 49 * (58 choose 4) = 2.1574231*1012.
Multiplied with 4 (combinations the priv key can start with) = total amount of combinations = 8.6296925 * 1012


Considering the birthay paradox, there is a 50% chance to find the correct private key after 1/2 of this space.



Feel free to correct me if i have made a mistake!


Title: Re: Private Key missing 4 characters
Post by: HCP on May 17, 2018, 09:45:20 AM
Considering the birthay paradox, there is a 50% chance to find the correct private key after 1/2 of this space.
Surely it is just common sense that searching half the space obviously has a 50% chance of finding the right key :P

The maths of the birthday attack (https://en.wikipedia.org/wiki/Birthday_attack#Mathematics) suggests that by randomly generating keys (as opposed to sequentially searching the space), the smallest number of keys we'd need to test to have a 50% chance of finding the right one would be:
https://wikimedia.org/api/rest_v1/media/math/render/svg/a31a9674c3d9f5249ad6d124f5c51d5f1d04294f

Which for your calculated search space is only something like: ~3,458,770 guesses... which isn't a great deal to be honest.

I'm pretty sure that the Birthday Attack is the reason why VanityGen generates keys randomly rather than sequentially


Title: Re: Private Key missing 4 characters
Post by: korandek on May 17, 2018, 10:01:10 AM
Hello people! I've been looking at the forum and seen that there are some ways to recover a private key that is missing some characters, it fed me hope and I'm trying to figure out a way for me to recover my private key.

Currently my private key has only 47 characters, but of the remaining characters, I'm not sure if the missing ones are the end, beginning or middle of the private key (I think it's the end), you know some algorithm you can try to generate a valid private key in my situation?
Just say, that when i read this information, i starting to go in shock - it is your own security!
What is your opinion in it? Why you didn't put this information on a safe place???


Title: Re: Private Key missing 4 characters
Post by: LoyceV on May 17, 2018, 10:03:24 AM
the smallest number of keys we'd need to test to have a 50% chance of finding the right one would be:
This can't be right. The birthday paradox is about finding a collision, in other words testing the same private key twice.

Quote
Which for your calculated search space is only something like: ~3,458,770 guesses... which isn't a great deal to be honest.
I can believe it takes about 3 million guesses for a 50% chance (out of 8 trillion possibilities) to guess the same key twice. But that's not going to help you, as you'll still need to search 4 trillion keys for 50% chance of finding the right one.
Using a random search only means you test the same key several times, while you may never test some of the other keys.


Title: Re: Private Key missing 4 characters
Post by: bob123 on May 17, 2018, 11:17:01 AM
Considering the birthay paradox, there is a 50% chance to find the correct private key after 1/2 of this space.
Surely it is just common sense that searching half the space obviously has a 50% chance of finding the right key :P

Unfortunately not as common sense as it should be  ;D
But you are right. The expression itself is a bit odd.

I just wanted to say that you don't actually have to seach the whole space (because thats what most people believe when they hear they are that much combination).
On average, it is enough to seach 50% of the space.



The maths of the birthday attack (https://en.wikipedia.org/wiki/Birthday_attack#Mathematics) suggests that by randomly generating keys (as opposed to sequentially searching the space), the smallest number of keys we'd need to test to have a 50% chance of finding the right one would be:
https://wikimedia.org/api/rest_v1/media/math/render/svg/a31a9674c3d9f5249ad6d124f5c51d5f1d04294f

Which for your calculated search space is only something like: ~3,458,770 guesses... which isn't a great deal to be honest.

It is not about a 50% chance to find one correct key, but to find '2 same keys'.
~3,458,770 would be the amount of guesses it would take to have a 50% chance for having generated the same key twice.



I'm pretty sure that the Birthday Attack is the reason why VanityGen generates keys randomly rather than sequentially

Actually this should be a reason for vanitygen to not use randomly.
My guess would be that it is just way faster to randomly generate them than to create them sequentially + memory storage and I/O.
And since vanitygen is used to create addresses with a relatively small prefix (compared to the overall length), it probably doesn't make a huge difference. 


Title: Re: Private Key missing 4 characters
Post by: LoyceV on May 19, 2018, 07:35:36 AM
Am having some missin numbers right at the middle(after the first ten digits), would this algorithm work in such case?
Yes.


Title: Re: Private Key missing 4 characters
Post by: Thirdspace on May 19, 2018, 11:11:35 AM
The total search space (for the private key without the first 2 chars) therefore is 46 * 47 * 48 * 49 * (58 choose 4) = 2.1574231*1012.
Multiplied with 4 (combinations the priv key can start with) = total amount of combinations = 8.6296925 * 1012
I don't understand where you come up with 46 * 47 * 48 * 49 and (58 choose 4)
we're not choosing 4 out of 58, but we pick 1 of 58, do 4 times (positions) = 58*58*58*58 = 58^4
 
I am pretty sure you made a small mistake there. You do ignore the order of the 4 missing words with your statement: ( 49! / 4! (49-4)! )
You do iterate through each position with your words, but you have to iterate within the words too.

There are 58 choose 4 possible combinations to pick the 4 correct chars from the charspace (without considering the order).
why 58 choose 4? the 4 chars are not guaranteed distinct
what I do is C(n,k) = n choose k = 49 choose 4 , but not for chars
I'm doing this ( 49! / 4! (49-4)! ) for possible position combinations of the missing 4 chars
then for each possible position combination, there are 58^4 possible char combinations

49 positions, 45 known chars (order sequence assumed) and trying to fill 4 chars in any 4 positions
so total = (49 choose 4) * 58^4 = 211,876 * 58^4 = 2,397,693,906,496 = 2.39 * 1012



small example:
4 positions, 2 known chars (order sequence assumed) and trying to fill 2 chars in any 2 positions
4 choose 2 = ( 4! / 2! (4-2)! ) = ( 1*2*3*4 / 1*2*1*2 ) = 6 possible position combinations
so total = 6*58*58 = (4 choose 2) * 58^2
Code:
5 K x x x x
1. 5 K _ _ x x 58*58
2. 5 K _ x _ x 58*58
3. 5 K _ x x _ 58*58
4. 5 K x _ _ x 58*58
5. 5 K x _ x _ 58*58
6. 5 K x x _ _ 58*58


Title: Re: Private Key missing 4 characters
Post by: ikatamoonshots on June 01, 2018, 11:34:08 PM
here a very simple bash to guess last 5 chars allnum of a string and add the string as prefix, then import prefixed string to bitcoin-core wallet.

Code:
#!/bin/bash

BRUTELIST=/home/$USER/brutelist.tst
ADDEDPREFIXLIST=/home/$USER/addedprefixlist.tst

crunch 5 5 -f /usr/share/crunch/charset.lst mixalpha-numeric > $BRUTELIST

cat $BRUTELIST | while read LINE
do
sed -e 's/^/incompletekeyprefix/' $BRUTELIST > $ADDEDPREFIXLIST
done


cat $ADDEDPREFIXLIST | while read LOSTKEY
do
bitcoin-cli -rpcuser=rpcuser -rpcpassword=rpcpass importprivkey $LOSTKEY "mylostkey" false
done

echo "check console output for errors"
echo "if all went fine you can rescan the wallet now and then export the relevant key(s)"




Title: Re: Private Key missing 4 characters
Post by: LoyceV on June 02, 2018, 06:31:11 AM
here a very simple bash to guess last 5 chars allnum of a string and add the string as prefix, then import prefixed string to bitcoin-core wallet.
It's less efficient but easier to understand than the Private Key Restorer in the second post. I'd still be interested in a way to just restore the checksum, that should be quite easy and very fast, but I haven't been able to find anything for it.


Title: Re: Private Key missing 4 characters
Post by: ikatamoonshots on June 02, 2018, 07:12:33 AM
here a very simple bash to guess last 5 chars allnum of a string and add the string as prefix, then import prefixed string to bitcoin-core wallet.
It's less efficient but easier to understand than the Private Key Restorer in the second post. I'd still be interested in a way to just restore the checksum, that should be quite easy and very fast, but I haven't been able to find anything for it.

Checksum for what? Same as restoring the key, no?
Dont exactly get what you mean, bit tired :P


Title: Re: Private Key missing 4 characters
Post by: LoyceV on June 02, 2018, 07:25:02 AM
Checksum for what? Same as restoring the key, no?
Dont exactly get what you mean, bit tired :P
The last 7 characters of the WIF private key are a checksum. I have successfully used this method (https://bitcointalk.org/index.php?topic=3104338.msg32072283#msg32072283) to import a private key without the last 7 characters into blockchain.info, and when I export it again, it's complete.
If blockchain.info can do that, it would be very nice to have a local program that does the same.


Title: Re: Private Key missing 4 characters
Post by: ikatamoonshots on June 02, 2018, 07:38:30 AM
7 chars allnum 25terabyte of data, they probably have big IO throughput at hand and did the same as the script, import the entire batch to a wallet or scan it with a block explorer or match the list against one checksum - now idea what else would do, where else could that be derived?


Title: Re: Private Key missing 4 characters
Post by: LoyceV on June 02, 2018, 07:50:20 AM
7 chars allnum 25terabyte of data, they probably have big IO throughput at hand
Nothing like that, see https://en.bitcoin.it/wiki/Wallet_import_format for the theory.